ADVERSARIAL SEARCH / PENCARIAN BERLAWANAN

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