eight puzzle kotak 8 - final

Anthon R Tampubolon (23510311)I Putu Agus Eka Pratama (23510310)

I Made Andhika (23510307)Eko Budi Setiawan (23511032)

M. Tirta Mulia (23511037)

Eight Puzzle – Kotak 8

Puzzle-8 adalah permainan menyusun kotak-kotak berlabel dari keadaan awal (initial state) yang acak menjadi tersusun dalam suatu format tertentu (goal

state). Permainan ini terdiri dari 3 baris dan 3 kolom (9 kotak), 8 kotak berlabel dan 1 kotak kosong.

Pernyusunan kotak dilakukan dengan mengeser kotak-kotak berlabel satu per satu ke arah kotak kosong

secara vertikal atau horizontal

Permainan Kotak 8

2 8 3 4 5 6 7 1 0

1 2 3 4 5 6 7 8 0Til

eState

Faktadeskripsi tentang objek yang menjadi

perhatian Kaidah

aturan yang bila diterapkan pada suatu keadaan (state) menghasilkan keadaan yang baru Inferensi

untaian dari kaidah untuk bergerak dari keadaan awal (initial states) menuju keadaan sasaran (goal states)

Komponen AI

Penerapan AI dalam Permasalahan Kotak 8

FAKTA Initial State, Current State, dan Goal State

Penerapan dalan Program

get_new_data merupakan prosedur untuk pengambilan data dari database

Penerapan AI dalam Permasalahan Kotak 8

Rules Kanan, Kiri, Atas, dan BawahMetode yang digunakan adalah metode switch

2 8 3 4 5 6 7 1 0 2 8 3 0 5 6 7 1 4

Penerapan AI dalam Permasalahan Kotak 8

Inferensi

Depth First Search dan Breadth First SearchSistematis Search

Heuristic SearchMisMatch dan Manhattan Distance

Sistematis Search dan Heuristic Search

Depth First Search

Prosedur

Simpul yang lebih dalam diperiksa terlebih dahulu

Penelusuran simpul-simpul pada suatu cabang sampai

kedalaman yang ditentukan.

1. Berikan simpul awal pada daftar open

2. Loop: if open = kosong then exit (fail)

Depth First SearchSimpul yang lebih dalam diperiksa terlebih dahulu

Penelusuran simpul-simpul pada suatu cabang sampai

kedalaman yang ditentukan.3. n : = first (open)

Depth First SearchSimpul yang lebih dalam diperiksa terlebih dahulu

Penelusuran simpul-simpul pada suatu cabang sampai

kedalaman yang ditentukan.

5. Remove (n, open)

Melabelkan “Closed” pada Current State

4. if goal (n) then exit (success)

6. Ekspansikan n, berikan semua simpul anak pada kepala open dan bubuhkan pointer dari simpul anak ke n

Depth First SearchSimpul yang lebih dalam diperiksa terlebih dahulu

Penelusuran simpul-simpul pada suatu cabang sampai

kedalaman yang ditentukan.

If Depth <= Val(Text7.Text) Then Menyatakan Batasan Kedalaman yang harus di telusuri

7. Kembali ke Loop

Depth First SearchSimpul yang lebih dalam diperiksa terlebih dahulu

Penelusuran simpul-simpul pada suatu cabang sampai

kedalaman yang ditentukan.Prosedur AddOpenList()

• Nilai = Nilai Prioritas yang digunakan untuk memeringkatkan Kanan, Kiri, Atas dan Bawah

• Secara Default, Nilai = 0

Testing Program DFS

B A Ka Ki

Ki Ka Jumlah Langkah Solusi

Jumlah Iterasi

Jumlah State yang dibangkitkan

Batas Kedalaman 6

4 Step

41 Step

45 State

Route : Atas, Kiri, Bawah, Kanan

Breadth First SearchEvaluasi dilakukan terhadap simpul-simpul pada suatu level

sebelum dilanjutkan pada level berikutnya

Prosedur

1. Berikan simpul awal pada daftar open

2. Loop: if open = kosong then exit (fail)

Breadth First SearchEvaluasi dilakukan terhadap simpul-simpul pada suatu level

sebelum dilanjutkan pada level berikutnya

3. n : = first (open)

get_new_data merupakan prosedur untuk pengambilan data dari database

Breadth First SearchEvaluasi dilakukan terhadap simpul-simpul pada suatu level

sebelum dilanjutkan pada level berikutnya

4. if goal (n) then exit (success)

5. Remove (n, open)

Melabelkan “Closed” pada Current State

Breadth First SearchEvaluasi dilakukan terhadap simpul-simpul pada suatu level

sebelum dilanjutkan pada level berikutnya

6. Ekspansikan n. Berikan pada ekor open semua simpul anak yang belum muncul pada open atau closed dan bubuhkan pointer ke n.

If Depth <= Val(Text7.Text) Then Menyatakan Batasan Kedalaman yang harus di telusuri

7. Kembali ke Loop

Prosedur AddOpenList()

• get_new_data3(state) adalah Prosedure untuk mengecek State sudah pernah dibangkitkan melalui Parent State yang lain

Breadth First SearchEvaluasi dilakukan terhadap simpul-simpul pada suatu level

sebelum dilanjutkan pada level berikutnya

Testing Program BFS

B A Ka Ki

Ki Ka Jumlah Langkah Solusi

Jumlah Iterasi

Jumlah State yang dibangkitkan

4 Step

32 Step

60 State

Route : Atas, Kiri, Bawah, Kanan

Best First SearchMisMatch

Pembangkitan simpul anak didasarkan pada hasil perbandingan

nilai heuristik tiap simpul yang dibuka. Simpul dengan nilai

heuristik terkecil akan dibuka terlebih dahulu. Nilai heuristik

diperoleh dari penjumlahan tile yang tidak tepat (mismatch tiles)Prosedur

1. Berikan simpul awal pada daftar open

2. Loop: if open = kosong then exit (fail)

3. n : = first (open)

Best First SearchMisMatch

Pembangkitan simpul anak didasarkan pada hasil perbandingan

nilai heuristik tiap simpul yang dibuka. Simpul dengan nilai

heuristik terkecil akan dibuka terlebih dahulu. Nilai heuristik

diperoleh dari penjumlahan tile yang tidak tepat (mismatch tiles)

4. if goal (n) then exit (success)

5. Remove (n, open)

Melabelkan “Closed” pada Current State

Best First SearchMisMatch

Pembangkitan simpul anak didasarkan pada hasil perbandingan

nilai heuristik tiap simpul yang dibuka. Simpul dengan nilai

heuristik terkecil akan dibuka terlebih dahulu. Nilai heuristik

diperoleh dari penjumlahan tile yang tidak tepat (mismatch tiles)

6. Ekspansikan n, berikan semua simpul anak pada kepala open dan bubuhkan pointer dari simpul anak ke n

7. Kembali ke Loop

Best First SearchMisMatch

Pembangkitan simpul anak didasarkan pada hasil perbandingan

nilai heuristik tiap simpul yang dibuka. Simpul dengan nilai

heuristik terkecil akan dibuka terlebih dahulu. Nilai heuristik

diperoleh dari penjumlahan tile yang tidak tepat (mismatch tiles)

Prosedur AddOpenList()

• get_new_data3(state) adalah Prosedure untuk mengecek State sudah pernah dibangkitkan melalui Parent State yang lain

Best First SearchMisMatch

Nilai Heuristik dijumlahkan setiap ada perbedaanPosisi pada current state dan goal state

Testing Program MisMatch

B5 A4 Ka5Ki4

Jumlah Langkah Solusi

Jumlah Iterasi

Jumlah State yang dibangkitkan

4 Step

4 Step

10 State

Route : Atas, Kiri, Bawah, Kanan

Ka5Ki3

B2

Ka0 B3

Best First SearchManhattan Distance

Manhattan Distance adalah jumlah gerakan minimum yang

diperlukan oleh sebuah kotak angka untuk berpindah ke goal

statenya.

Prosedur

1. Berikan simpul awal pada daftar open

2. Loop: if open = kosong then exit (fail)

3. n : = first (open)

Best First SearchManhattan Distance

Manhattan Distance adalah jumlah gerakan minimum yang

diperlukan oleh sebuah kotak angka untuk berpindah ke goal

statenya.

4. if goal (n) then exit (success)

5. Remove (n, open)

Melabelkan “Closed” pada Current State

Best First SearchManhattan Distance

Manhattan Distance adalah jumlah gerakan minimum yang

diperlukan oleh sebuah kotak angka untuk berpindah ke goal

statenya.

6. Ekspansikan n, berikan semua simpul anak pada kepala open dan bubuhkan pointer dari simpul anak ke n

7. Kembali ke Loop

Best First SearchManhattan Distance

Manhattan Distance adalah jumlah gerakan minimum yang

diperlukan oleh sebuah kotak angka untuk berpindah ke goal

statenya.

Prosedur AddOpenList()

• get_new_data3(state) adalah Prosedure untuk mengecek State sudah pernah dibangkitkan melalui Parent State yang lain

Best First SearchManhattan Distance

Testing Program Manhattan Distance

B6 A4 Ka6Ki4

Jumlah Langkah Solusi

Jumlah Iterasi

Jumlah State yang dibangkitkan

4 Step

4 Step

10 State

Route : Atas, Kiri, Bawah, Kanan

Ka6Ki4

B2

Ka0 B4

Kesimpulan

Keterangan DFS BFS MisMatchManhatta

n

Jumlah Langkah Solusi 4 4 4 4

Jumlah Iterasi 41 32 4 4

Jumlah State yang dibangkitkan

45 60 10 10

2 8 3 4 5 6 7 1 0

1 2 3 4 5 6 7 8 0