| specgram.com |
1.
Introductoin
Adversarial search
adalah sebuah alat yang sering digunakan di dalan Artificial Intelligence,
terutama di dalam teori game. Ini merupakan suatu metode yang digunakan agar
agents memutuskan tindakan yang terbaik pada suatu lingkungan, dan biasa
digunakan pada permainan catur atau permainan yang sifatnya memiliki
perencanaan. Mari kita gunakan permainan Tic-Tac-Toe sebagai suatu contoh
permainan yang menggunakan Adversarial Search. Di dalam adversarial search sebuah
game di rancang seperti tree (pohon) yang memiliki node-node. Permainan tic-tac-toe
terdiri atas konfigurasi papan sehingga root (akar) dari node di dalam
permainan akan mencari pohon sehingga menjadi suatu susunan pada papan
Tic-Tac-Toe yang kosong. Bagian children dari root adalah bentuk berwujud yang
mewakili gerakan yang sah pada papan konfigurasi (terminal), dan seterusnya
sampai tidak ada lagi gerakan yang dilakukan. Di dalam permainan tic-tac-toe tidak
ada lagi gerakan yang dilakukan ketika ruang pada papan konfigurasi (terminal)
penuh atau ketika seorang pemain menang pada saat dia memiliki karakter yang
sama pada baris yang sama, kolom yang sama atau berbentuk diagonal.
Setiap node di dalam
permainan memiliki skor atau nilai melalui sebuah fungsi evaluasi yang
menentukan tingkat optimal diantara solusi. Bagian daun dari node-node diberi
suatu nilai kegunaan berdasarkan pada papan konfigurasi (termial) pada bagian
yang diinginkan atau tidak. Tic-Tac-Toe disebut juga zero-sum game, artinya
bahwa jika kamu menang (bernilai +1), jika kamu kalah (bernilai -1), atau kamu
seri (bernilai 0). Sekarang kita dapat menentuka bahwa sebuah game terlihat
seperti tree (pohon), kita harus memutuskan
bagaimana membuat keputusan yang diberikan berdasarkan pohon. Algoritma
yang digunakan di dalam tulisan ini adalah minimax search.
1.
Minimax
Minimax search adalah
algoritma rekursif yang berbentuk pohon yang sifatnya downward, setiap node
melakukan expanding untuk masing-masing langkah yang menjelaskan informasi dan
membackup tree (pohon). Setiap tingkatan pohon (atau gerakan atau langkah di
dalam game) juga dikatakan level Max atau level Min. Level Max adalah level
yang melakukan perkiraan musuh. Sebenarnya goal (tujuan) adalah untuk menjangkau
node daun dimana ada suatu utiliti
positif, tetapi tujuan musuh melakukan sebaliknya. Untuk mempertimbangkan ini,
minimax mengasumsikan musuh akan selalu membuat langkah yang paling optimal
untuk itu, dan demikian setidaknya yang paling optimal untuk agent.
Algortitma minimax di
mulai dengan melintasi ke node daun dari pohon. Pada gambar 1, kita memutuskan
bahwa agent akan bermain dengan menggunakan “X” dan akan melangkah untuk yang
pertama. Selanjutnya parents dari daun mendapatkan nilai minimum atau maksimum
(tergantung jika parents berada di level min atau level max) dari nilai
children. Kemudian nilai-nilai ini disebarkan ke parents dan seterusnya sampai
mencapai node root. Minimax melacak node yang diberkan nilai, sehingga pada
saat algoritma selesai menyebarkan utiliti pada pohon, akan diketahui langkah
apa yang harus dilakukan dalam rangka untuk mendapatkan utiliti yang
diinginkan.
 |
| wiimedia.org |
Di dalam teori
melintasi pohon ke daun untuk menemukan utilitas adalah baik. Namun, kebanyakan
game pohon terlalu besar untuk melintas atau menyilang ke bawahdalam sejumlah
waktu. Minimax mempunyai kompleksitas waktu yaitu O(bm) dan kompleksitas ruang yaitu O(bm) dimana b adalah
faktor percabangan dan m adalah kedalaman
maksimum pohon. Tic-tac-toe memiliki faktor percabangan 9 (lvl-1), dimana lvl
adalah tingkat pohon, yang cukup besar untuk suatu permainan sederhana.
Permainan seperti catur mempunyai lebih tinggi lagi faktor percabangannya.
Untuk bekerja dengan
menggunakan kompleksitas waktu dan ruang yang tinggi, minimax dapat menggunakan
fungsi evaluasi pemberian nilai untuk setiap papan konfigurasi (terminal) untuk
menentukan bagaimana solusi yang diinginkan. Sebagai ganti menyebaran
nilai-nilai utilitas dari node dan ke atas pohon, minimax dapat menentukan
kedalaman maksimum untuk melintasi, dan lewat nilai-nilai evaluasi tersebut
node-node mendapatkan tingkat kedalaman dari pohon (tree). Pada gambar 2, kedalaman
tree ditetapkan pada tingkat 2. Minimax melihat bahwa nilai-nilai 3,2 dan 2
akan dipilih oleh musuh sebagai nilai yang optimal. Tentang ini, 3 adalah yang
paling tinggi, sehingga memutuskan untuk memilih untuk pindah ke node dengan
nilai minimax nilai 3.
 |
| www.massey.ac.nz |
Ada beberapa fitur yang
baik dari minimax search. Jika kita menganggap ruang pencarian kita tidak
berkahir, yaitu kedalaman pohon tidak terhingga, maka minimax akan selalu
kembali jika ada satu solusi yaitu komplit. Juga, jika kita berasumsi bahwa
musuh optimal, maka minimax optimal, artinya akan selalu menemukan solusi yang
paling diiginkan.
Meskipun dalam beberap
kasus hanya menentukan suatu kedalaman adalah cukup, dalam kebanyakan kasus
faktor percabangan pohon yang terlalu tinggi untuk fungsi evaluasi untuk mengembalikan
informasi yang berguna. Salah satu cara terbaik untuk mengurangi kompleksitas
waktu dan ruang adalah dengan menghilangkan node yang tidak perlu diperluas
melalui proses yang disebut pemangkasan. Dengan memangkas beberapa node, anda
dapat menghilangkan jalan untuk solusi bahwa agent tidak akan pernah mencapai.
hadifun
Comments
Post a Comment
terima kasih