[AIMA] Russel, Stuart J., Peter Norvig, "Artificial Intelligence, A Modern Approach" 3rd Ed., Prentice Hall, New Jersey, 2010
KI091322 Kecerdasan Buatan Materi 6: Pencarian dgn. Lihat Status Lawan
(Adversarial Search) Teknik Informatika, Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya 2012 Pengembangan Bahan Ajar sebagai Pendukung Student Centered-Learning (SCL) melalui e-Learning : Share ITS
Pencarian dengan Lihat Status Lawan (Adversarial Search) • Teknik pencarian terdahulu… – uninformed, informed, local
…tidak memperhitungkan state dari pihak lawan • Adversarial Search peduli pada state lawan – contoh problem sering berupa permainan game • orang lawan komputer pada game catur • solusi dari Algoritma Adversarial Search menjadi langkah komputer • Misal: Algoritma Minimax, Algoritma Alpha Beta 2
Adversarial Search pada Problem Game • Initial State: posisi board dan pemain • Successor Function: mengembalikan daftar kemungkinan langka pemain • Terminal Test: penentuan syarat game berakhir • Utility function: nilai dari setiap state • Game Tree: kemungkinan langkah pemain (state) berdasarkan langkah sebelumnya 3
Contoh State pada Game Tic Tac Toe
X
X O
0
1
2
3
4
5
6
7
8
0
X
2
3
4
5
6
7
8
0
X
2
3
4
O
6
7
8
Nilai state disamping adalah [0, 1, 2, 3, 4, 5, 6, 7, 8]
Nilai state disamping adalah [0, X, 2, 3, 4, 5, 6, 7, 8]
Nilai state disamping adalah [0, X, 2, 3, 4, O, 6, 7, 8]
4
Contoh Utility Function • Istilah pada bahasan terdahulu, – Nilai fitness (fitness function pada Algoritma Genetika) – Cost Function pada uninformed & informed search
• Fungsi: memberikan suatu nilai pada state yang sedang diamati – Tidak ada aturan baku, heuristik, sesuai dengan definisi permasalahan 5
Contoh Utility Function Game Tic Tac Toe X
Nilai state untuk Pemain X disamping: 2 - 0 Ada 2 garis yang bisa dibuat Pemain X
X
Nilai state untuk Pemain X disamping: 2 – 1 = 1 Hanya ada 1 garis yang bisa dibuat Pemain X karena Pemain O menghalangi garis lainnya
O
Nilai Utility Function = banyaknya garis yang bisa dibuat seorang pemain tanpa gangguan dari pemain lain. 6
Contoh Game Tree pada Tic Tac Toe 2 pemain berusaha membuat garis pada papan n x n Posisi 0
initial state : [0,1,2,3,4,5,6,7,8]
Posisi 1
Daftar semua kemungkinan posisi X sebagai Pemain 1
SUCCESSORS( [0,1,2,3,4,5,6,7,8] ) returns [ Posisi 0 (0,[X,1,2,3,4,5,6,7,8]), Posisi 1 (1,[0,X,2,3,4,5,6,7,8]), ... ]
7
Algoritma Minimax
• Memberikan nilai paling maksimal atau nilai paling minimal dari pemain – Contoh berikut adalah game tree dari 2 pemain dengan kemungkinan langkah sampai 3 level • ruang kemungkinan terlalu banyak -> ada pembatasan kedalaman level (DEPTH-LIMITED SEARCH) • Nilai utility function untuk state langkah pemain di posisi level 3 telah dihitung • Tujuan Level 0 dan Level 2 -> mencari nilai state paling maksimal • Tujuan Level 1 -> mencari nilai state paling minimal
8
Algoritma Minimax • Buat 2 fungsi recursive : – max-value mencari nilai maksimal successors – min-value mencari nilai minimal successors def value(state): If terminal state: return the state’s utility If MAX agent: return max-value(state) If MIN agent: return min-value(state) def max-value(state): Initialize max = -∞ For each successor of state: V ← value(successor) max ← maximum(max, v) Return max 9
Minimax dengan Depth-Limited Search • Buat 2 fungsi recursive : – max-value mencari nilai maksimal successors – min-value mencari nilai minimal successors def value(state, limit): If terminal state: return the state’s utility If limit = 0: return evaluation_function(state) If MAX agent : return max-value(state, limit) If MIN agent : return min-value(state, limit) def max-value(state, limit): Initialize max = -∞ For each successor of state: V ← value(successor, limit-1) max ← maximum(max, v) Return max 10
Contoh Animasi Minimax
Min
Max
5
5 3
1 3
1
3
0 7
6
5
2
Langkah yang diambil komputer adalah state dengan nilai utility 6 function = 6
3 6
Max
6
2
0
7 11
-: Pruning di Depth-Limited Search • Pruning = pemotongan cabang pada game tree – Mengurangi waktu pembuatan dan penelusuran tree
• Algoritma Alpha Beta (-) – Minimax pada DepthLimited Search + pruning – Syarat pruning: nilai variabel alpha dan variabel beta • Alpha = nilai paling maksimal di semua level max • Beta = nilai paling minimal di semua level min 12
Algoritma Alpha Beta
13
State Awal Contoh Alpha-Beta Maximum-α Minimum-β Maximum-α Minimum-β Maximum-α Minimum-β
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 14
State Akhir Contoh Alpha-Beta Maximum-α
1
Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
1
0
0
-3
2
2
2
1
3
3
1
2
2
1
-5
2
1
-5
2
-3
-5
2
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 15
Alpha-Beta Example Maximum-α Minimum-β Maximum-α Minimum-β Maximum-α Minimum-β
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α Minimum-β Maximum-α Minimum-β Maximum-α Minimum-β
0
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α Minimum-β Maximum-α Minimum-β Maximum-α Minimum-β
0
0
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α Minimum-β Maximum-α Minimum-β Maximum-α Minimum-β
0
0
-3
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α Minimum-β Maximum-α Minimum-β Maximum-α Minimum-β
0
0
-3
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α Minimum-β Maximum-α Minimum-β
0
Maximum-α Minimum-β
0
0
-3
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α Minimum-β Maximum-α Minimum-β
0
Maximum-α Minimum-β
0
0
-3
3
3
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α Minimum-β Maximum-α Minimum-β
0
Maximum-α Minimum-β
0
0
-3
3
3
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
3
3
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
3
3
5
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
3
3
2
2
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
3
3
2
2
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
2
2
3
3
2
2
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
2
2
3
3
2
2
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α
0
Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
2
2
3
3
2
2
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α
0
Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
2
2
3
3
2
2
5
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α
0
Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
2
2
3
3
2
2
1
1
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α
0
Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
2
2
3
3
2
2
1
1
-3
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α
0
Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
2
2
3
3
2
2
1
1
-3
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α
0
Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
2
2
1
3
3
1
2
2
1
1
-3
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α
0
Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
2
2
1
3
3
1
2
2
1
1
-3
-5
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α
0
Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
2
2
1
3
3
1
2
2
1
1
-3
-5
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α
0
Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
2
2
1
3
3
1
2
2
1
-5
1
-5
-3
-5
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α
1
Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
0
0
-3
2
2
1
3
3
1
2
2
1
-5
1
-5
-3
-5
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α
1
Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
1
0
0
-3
2
2
1
3
3
1
2
2
1
-5
1
-5
-3
-5
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
Alpha-Beta Example Maximum-α
1
Minimum-β
0
Maximum-α
0
Minimum-β
0
Maximum-α Minimum-β
1
0
0
-3
2
2
2
1
3
3
1
2
2
1
-5
2
1
-5
2
-3
-5
2
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 17
