1/5/2012
1
Game PlayingGame PlayingBy:Uro Abdulrohim, S.Kom, MT
Mengapa mempelajari gamesMengapa mempelajari games
ó Menyenangkanó Kriteria menang dan kalah, jelasó Dapat mempelajari masalahó Alasan historió Biasanya mempunyai search space yang
besar (Game catur mempunyai 34100 node dalam search tree dan 1040 legal state)
1/5/2012
2
Seberapa Hebat Games KomputerSeberapa Hebat Games Komputer
ó Game Gatur◦ DeepBlue mengalahkan Gary Kasparov pada tahun 1997◦ DeepBlue Vs Gary Kasparov 2003 dengan hasil Seri
ó Checkers◦ Chinnok adalah juara dunia
ó Go◦ Komputer player yang sangat tangguh
ó Bridge◦ Komputer player yang mempunyai level “Expert level”
Ciri Umum pada GamesCiri Umum pada Gamesó 2 pemainó Kesempatan pemain bergantianó Zero-sum; kerugian seorang pemain adalah
keuntungan pemain lainó Perfect Information; pemain mengetahui semua
informasi state dari gameó Tidak mengandung probalistik (seperti dadu)
◦ Contoh Tik-Tak-Toe, Checkers, Chess, Go, Nim, Othelloó Games tidak termasuk Bridge, Solitaire,
BackGammen dan semisalnya
1/5/2012
3
Bagaimana bermain gameBagaimana bermain gameó Cara bermain game
◦ Pertimbangkan segala kemungkinan jalan◦ Berikan nilai pada semua kemungkinan jalan◦ Jalankan pada kemungkinan yang mempunyai nilai terbaik◦ Tunggu giliran pihak lawan◦ Ulangi cara diatas
ó Key problem◦ Representasikan “board” dan “state”◦ Buatlah nextboard yang legal◦ Lakukan evaluasi pada posisi
Evaluation FunctionEvaluation Functionó Evaluation Function atau static evaluator digunakan
untuk mengevaluasi nilai posisi yang baikó Zero-sum assumption membolehkan untuk
menggunakan single evaluation function untuk mendeskripsikan nilai posisi◦ f(n)>> 0: nilai posisi n baik untuk saya dan jelek untuk
lawan◦ f(n)<< 0: nilai posisi n jelek untuk saya dan baik untuk
lawan◦ f(n) =+Infinity: Saya menang◦ f(n) =-Infinity: Lawan menang
1/5/2012
4
Contoh Evaluation Function Contoh Evaluation Function ó Tic-Tac-Toe
◦ f(n)=[# of 3 lengths open for me ] – [# of 3 length open for you]
◦ Dimana 3-lengths adalah complete row, column atau diagonal yang terisi
ó Alan Turing’s function untuk catur◦ f(n)=w(n) / b(n) dimana w(n) = jumlah point value bidak
putih and b(n) = jumlah point value dari bidak hitam
ó DeepBlue mempunyai lebih dari 8000 features untuk evaluation fuction
Game TreeGame Tree
1/5/2012
5
MinimaxMinimax
ó John Von Neumann pada tahun 1944 menguraikan sebuah algoritma search pada game, dikenal dengan nama Minimax, yang memaksimalkan posisi pemain dan meminimalkan posisi lawan
1/5/2012
6
Contoh: Games NimContoh: Games Nim
ó Diawali serangkain batangó Setiap pemain harus memecah serangkaian batang
menjadi 2 kumpulan dimana jumlah batang ditiap kumpulan tidak boleh sama dan tidak boleh kosong
1/5/2012
7
AsumsiAsumsi
ó MIN bermain dahulu
ó Evaluation function ◦ 0 min memang◦ 1 max menang
1/5/2012
8
Alpha Beta Pruning Alpha Beta Pruning
ó Merupakan impovisasi dari minimaxó Basic idea
◦ If you have an idea that surely bad, don’t take the time to see how truly awful it is (Pat Winson)
1/5/2012
9
1/5/2012
10
