ki091322 kecerdasan buatan - share...
TRANSCRIPT
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
[AIMA] Russel, Stuart J., Peter Norvig, "Artificial Intelligence, A Modern Approach" 3rd Ed., Prentice Hall, New Jersey, 2010
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
4
Nilai state disamping adalah [0, 1, 2, 3, 4, 5, 6, 7, 8]
0 1 2
3 4 5
6 7 8
X 0 X 2
3 4 5
6 7 8
Nilai state disamping adalah [0, X, 2, 3, 4, 5, 6, 7, 8]
X
O
0 X 2
3 4 O
6 7 8
Nilai state disamping adalah [0, X, 2, 3, 4, O, 6, 7, 8]
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
6
X Nilai state untuk Pemain X disamping: 2 - 0 Ada 2 garis yang bisa dibuat Pemain X
X
O
Nilai state untuk Pemain X disamping: 2 – 1 = 1 Hanya ada 1 garis yang bisa dibuat Pemain X karena Pemain O menghalangi garis lainnya
Nilai Utility Function = banyaknya garis yang bisa dibuat seorang pemain tanpa gangguan dari pemain lain.
Contoh Game Tree pada Tic Tac Toe
7
Daftar semua kemungkinan posisi X sebagai Pemain 1
2 pemain berusaha membuat garis pada papan n x n initial state : [0,1,2,3,4,5,6,7,8]
SUCCESSORS( [0,1,2,3,4,5,6,7,8] ) returns [ (0,[X,1,2,3,4,5,6,7,8]), (1,[0,X,2,3,4,5,6,7,8]), ... ]
Posisi 0 Posisi 1
Posisi 0
Posisi 1
Algoritma Minimax
8
• 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
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
5 1 3 6 2 2 7 0
Max
Min
Max 5
5
6
7 0
6
6
3
3
3 1
Langkah yang diambil komputer adalah state
dengan nilai utility function = 6
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
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
State Awal Contoh Alpha-Beta
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
14
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
State Akhir Contoh Alpha-Beta
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
1
1
-3
1
1
-5
-5
-5
1
2
2
2
2
1
15
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0 -3
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0 -3
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0 -3
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0 -3 3
3
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0 -3 3
3
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
5
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
0
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
5
0
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
1
1
0
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
1
1
-3
0
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
1
1
-3
0
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
1
1
-3
1
1
0
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
1
1
-3
1
1
-5
0
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
1
1
-3
1
1
-5
0
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
1
1
-3
1
1
-5
-5
-5
0
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
1
1
-3
1
1
-5
-5
-5
1
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
1
1
-3
1
1
-5
-5
-5
1
1
17
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Minimum-β
Maximum-α
Alpha-Beta Example
0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5
0
0
0
0 -3 3
3
0
2
2
2
2
1
1
-3
1
1
-5
-5
-5
1
2
2
2
2
1
17