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