5. game playing
Post on 02-Aug-2015
69 Views
Preview:
TRANSCRIPT
Kecerdasan Buatan
Lecture 5 Game Playing
Joan Santoso, S.Kom.© Sekolah Tinggi Teknik Surabaya
1
What is Game ?» Game adalah sebuah permainan yang
dilakukan oleh n individu atau group.» Game theory menunjukkan sebuah
permainan strategi» John von Neumann dikenal sebagai
bapak dari Game Theory.» Neuman mendefinisikan Game Theory
pada tahun 1928 dan 1937.
2
© Sekolah Tinggi Teknik Surabaya
What is Game ?» Game Theory mengijinkan player untuk
saling bermain dengan strateginya masing-masing.
» Dalam memainkan sebuah game biasanya juga diperlukan intelligence untuk bermain.
» Dalam memainkan game juga terkadang langkah dari lawan tidak dapat ditebak.
3
© Sekolah Tinggi Teknik Surabaya
Hubungan Game Playing dan Mathematics dan Ekonomi
4
© Sekolah Tinggi Teknik Surabaya
Game Playing» Game dapat deterministic atau non
deterministic» Game dapat memiliki perfect
information atau imperfect information.
5
© Sekolah Tinggi Teknik Surabaya
Game Playing » Karakteristik dan Batasan Game untuk
Game Playing˃ Dimainkan oleh dua orang˃ Perfect information game˃ No determined by chances˃ No physychological factors˃ No Oversight Error, Smart Opponent
6
© Sekolah Tinggi Teknik Surabaya
Game Playing» Contoh permainan yang digunakan
sebagai contoh kasus dari Game Playing:˃ Last one loses˃ N coins Grundy’s Game˃ Slide 5˃ Tic-Tac-Toe˃ Checkers˃ Go˃ Nim˃ Othelo˃ Chess
7
© Sekolah Tinggi Teknik Surabaya
Game Playing» Dengan memperhatikan karateristik dan
batasan dari game maka sejumlah permainan tradisional sehari-hari juga dapat diimplementasikan dengan game playing
» Contoh:˃ Dakon˃ Halma
8
© Sekolah Tinggi Teknik Surabaya
Game Playing» Jika sebuah pencarian dalam game
playing dapat dilambangkan dengan tree maka tree tersebut dinamakan search tree.
» State dimana game berakhir disebut terminal state.
» Setiap layer dari sebuah search disebut dengan ply
9
© Sekolah Tinggi Teknik Surabaya
Game Playing
10
© Sekolah Tinggi Teknik Surabaya
Game Playing» Metode pencarian yang digunakan
metode iterative.» Alasan : karena space pencarian solusi
terlalu besar, sehingga dalam hal ini pencarian akan dilakukan sebelum setiap langkah dilakukan untuk mendapatkan langkah berikutnya yang terbaik.
11
© Sekolah Tinggi Teknik Surabaya
Game Playing» Contoh search space yang sangat besar
adalah pada catur, misalnya. ˃ Branching factor : 35˃ Depth : 50 moves untuk setiap player˃ Search tree : 35^100 nodes
12
© Sekolah Tinggi Teknik Surabaya
State of the Art Game Playing» Chess : Deep Blue mengalahkan juara
dunia catur˃ fungsi evaluasi dibuat oleh expert˃Memiliki opening dan end-game database
» Checkers :˃ Program yang dibuat oleh Samuel’s
mengalahkan pembuatnya» Backgammon : Neural-net learning
program TDGammon merupakan salah satu pemain top 3 teratas dunia. 13
© Sekolah Tinggi Teknik Surabaya
Fungsi Evaluasi» Fungsi evaluasi digunakan untuk menilai
"seberapa baik" konfigurasi suatu game.» Tidak seperti heuristic search yang fungsi
evaluasinya adalah sebuah bilangan non-negatif, sebagai estimasi biaya dari start-state menuju goal-state.
» Pada game playing, fungsi evaluasi memberikan estimasi tentang kualitas papan permainan dalam mengarahkan seorang pemain untuk memenangkan permainan (static evaluation function).
14
© Sekolah Tinggi Teknik Surabaya
Fungsi Evaluasi» Fungsi evaluasi sering disebut dengan
Static Board Evaluator, f(n).» Pada setiap branch nodes:˃ Jika f(n) bilangan positif besar, artinya
konfigurasi papan dengan pemilihan node n "baik untuk saya dan buruk untukmu“
˃ Jika f(n) bilangan negatif besar, artinya konfigurasi papan dengan pemilihan node n "buruk untuk saya dan baik untukmu“
˃ Jika f(n) dekat dengan 0, artinya papan dalam keadaan netral
15
© Sekolah Tinggi Teknik Surabaya
Fungsi Evaluasi» Pada leaf nodes:˃ Jika f(n) = + "tak terhingga", artinya kondisi saya
memenangkan pertandingan.˃ Jika f(n) = - "tak terhingga", artinya kondisi kamu
memenangkan pertandingan» Static Board Evaluator tidak selalu mudah
untuk ditulis, misalnya untuk permainan catur.» Banyak fungsi evaluasi game playing yang
dispesifikasikan sebagai "jumlah berbobot dari featuresnya": (w1*feature1) + (w2*feature2) + (w3*feature3) + ... (wn*featuren).
16
© Sekolah Tinggi Teknik Surabaya
Fungsi Evaluasi» Sebagai contoh pada Deep Blue
(program catur yang "imbang" saat menghadapi Gary Kasparov) memiliki tidak kurang dari 6000 features dalam fungsi evaluasinya.
» Contoh static evaluation function untuk Tic-Tac-Toe: f(n) = [jumlah 3-length yang terbuka untuk saya] - [jumlah 3-length yang terbuka untukmu]
17
© Sekolah Tinggi Teknik Surabaya
Minimax» Minimax adalah sebuah prosedur
pencarian yang melihat ke depan -- memperhatikan apa yang akan terjadi kemudian -- yang digunakan untuk memilih langkah berikutnya.
» Asumsikan bahwa kita telah memiliki sebuah Static Board Evaluator yang akan mengembalikan sebuah bilangan yang menunjukkan "seberapa baiknya" sebuah konfigurasi papan. 18
© Sekolah Tinggi Teknik Surabaya
Minimax
» Anggaplah static board evaluator untuk konfigurasi papan D, E, F, G, masing-masing adalah 4, 7, 2, dan 8.
» Nilai konfigurasi B adalah 4 (karena jika saya memilih B, lawan akan memilih D – langkah terbaik untuk dia).
» Hal yang sama akan terjadi bila saya melangkah ke C yang nilai konfigurasinya 2.
» Dengan demikian nilai konfigurasi A adalah 4 (artinya melangkah ke konfigurasi B=4 lebih baik bagi saya dibanding C=2).
19
© Sekolah Tinggi Teknik Surabaya
Pseudocode Minimax
20
© Sekolah Tinggi Teknik Surabaya
Tugas Kelompok Proyek» Cari static board evaluator untuk
Othello.» Ubahlah permainan anda, pada langkah
salah satu player menggunakan minimax.
» Lihat apakah anda dapat mengalahkan computer anda ?
» Laporkan tugas anda.
21
© Sekolah Tinggi Teknik Surabaya
Konsultasi » Bagaimana progress kelompok anda ?
22
© Sekolah Tinggi Teknik Surabaya
Referensi» Bahan Kuliah Artificial Intelgence STTS yang dibuat oleh Ir.
Gunawan, M.Kom. » RC Chakraborty, Game Playing AI Couse,
www.myreaders.info.» Slide kuliah AI Game Playing oleh Raymond J. Mooney. The
University of Texas at Austin » Rajjan Shinghal. 1992.“Formal Concepts in Artificial
Intellegence”. Chapman & Hall
23
© Sekolah Tinggi Teknik Surabaya
Terima Kasih
24
© Sekolah Tinggi Teknik Surabaya
top related