PENERAPAN KONSEP ALGORITMA MINIMAX & MTD(f)
PADA PERMAINAN TIC TAC TOE
Artificial Inteligence
Jurusan Teknik Informatika, Fakultas Teknologi Informasi
Institut Teknologi Adhitama Surabaya
E-mail: http://www.itats.ac.id
ABSTRACT
Minimax algorithm (also often called Minmax) is an algorithm that underlies step problem-solving mindset in some types of computer games, like tic-tac-toe, Othello, checkers, chess, dll.Pada essentially, very reliable Minimax algorithm to solve all problems in pencarianlangkah for computer games with a small number of possible settlement, as in a game of tic-tac-toe. However, if the Minimax algorithm used in the game with a large number of possibilities such as the tic tac toe games, Minimax algorithm requires a very long time to build a tree settlement.
This journal will try to explain a concept minimax algorithm and machine learning applied to the game of tic-tac-toe. After learning of the strategies for a game to get, minimax algorithm is expected to help the players to play tic-tac-toe with the good. The results of this process is expected to be compared with some other methods within the scope of artificial intelligence.
Keywords: Minimax Algorithm, Machine Learning, Game, Tic-Tac-Toe.
ABSTRAK
Algoritma Minimax (juga sering disebut Minmax) adalah sebuah algoritma yang mendasari pola pikir langkah penyelesaian masalah dalam beberapa jenis permainan komputer, seperti tic-tac-toe, othello, checkers, catur, dll.Pada dasarnya, algoritma Minimax sangat andal untuk menyelesaikan segala masalah dalam pencarianlangkah untuk permainan komputer dengan jumlah kemungkinan penyelesaian yang kecil, seperti pada permainan tic-tac-toe. Tetapi, jika algoritma Minimax digunakan pada permainan dengan jumlah kemungkinan penyelesaian yang besar seperti pada
permainan tic tac toe, algoritma Minimax ini memerlukan waktu yang sangat lama untuk membangun pohon penyelesaian.
Jurnal ini akan mencoba menjelaskan sebuah konsep algoritma minimax dan pembelajaran mesin yang diterapkan pada permainan tic-tac-toe. Setelah pembelajaran dari strategi-strategi untuk sebuah permainan didapat, algoritma minimax diharapkan mampu membantu pemain memainkan tic-tac-toe dengan baik. Hasil dari proses ini diharapkan dapat dibandingkan dengan beberapa metode-metode yang lain dalam lingkup kecerdasan buatan.
Kata kunci: Algoritma Minimax, Pembelajaran Mesin, Permainan, Tic-Tac-Toe.
1. PENDAHULUAN
Memainkan sebuah permainan merupakan sebuah konsep penelitian yang sangat populer dikalangan komunitas AI (kecerdasan buatan). Para peneliti di bidang itu telah mengembangkanbeberapa metode pencarian untuk permainan. Metode-metode pencarian yang dikembangkan bias berupa pencarian secara tradisional maupun secara heuristic yang lebih cerdas. Penelitian ini akan mencoba memfokuskan pada permainan sederhana yang dinamakan Tic-Tac-Toe. Algoritma genetika mempunyai ciri yaitu mampu membangun beberapa strategi pada berbagai situasi ,dan melalui aturan ’kemampuan bertahan hidup’, beberapa strategi yang tidak baik dapat dieliminasi sehingga hanya strategi baik yang dipakai.
Kekuatan komputer yang mengandalkan proses
komputasi yang sangat cepat harus didukung oleh
algoritma yang memiliki efisiensi dan efektifitas yang
tinggi. Untuk menyelesaikan permasalahan ini, permainan
tic tac toe pada komputer menggunakan optimasi dari
algoritma Minimax untuk memberikan hasil terbaik dalam
waktu yang singkat.
2. ALGORITMA MINIMAX
2.1 Dasar Teori
Secara teori, algoritma Minimax didefinisikan sebagai berikut:
“Untuk setiap permainan satu-lawan satu, ada
sebuah nilai yang bernilai V dan strategi yang dipilih oleh tiap pemain, sehingga: (a), Jika diberikan strategi dari pemain ke-2, maka langkah penyelesaian terbaik dari
pemain pertama adalah V. Dan (b), jika diberikan strategi dari pemain pertama, maka langkah penyelesaian terbaik
dari pemain kedua adalah -V” [6]
Singkatnya, pemain pertama memberikan langkah
penyelesaian yang bernilai V terhadap permainan pemain
kedua, dan sebaliknya, pemain kedua memberikan
langkah peyelesaian bernilai -V. Pemikiran inilah yang mendasari asal usul penamaan algoritma Minimax,
dimana pemain yang satu berjuang untuk mendapat nilai
maksimum,sedangkan lawannya berjuang untuk mendapat nilai minimum.
Gambar 1. Gambar pohon yang dibangun dengan algoritma Minimax. Disini MAX diwakili aras genap,
sedangkan MIN diwakili aras ganjil.
Langkah-langkah membuat algoritma Minimax adalah sebagai berikut:
1. Misalkan ada 2 pemain yang terlibat, kita namakan
MAX dan MIN.
2. Lalu sebuah pohon pencarian dibangkitkan secara
depth-first-search dari posisi awal permainan hingga
akhir permainan.
3. Dari sudut pandang MAX, akan dicari posisi terakhir
yang paling menguntungkan bagi MAX.
Algoritma Minimax adalah sebagai berikut:
MinMax (GamePosition game) {
return MaxMove (game);
}
MaxMove (GamePosition game) {
if (GameEnded(game)) {
return EvalGameState(game);
}
else {
best_move < - {};
moves <- GenerateMoves(game);
ForEach moves {
move <-
MinMove(ApplyMove(game));
if (Value(move) >
Value(best_move)) {
best_move < - move;
}
}
return best_move;
}
}
MinMove (GamePosition game) {
best_move <- {};
moves <- GenerateMoves(game);
ForEach moves {
move <-
MaxMove(ApplyMove(game));
if (Value(move) >
Value(best_move)) {
best_move < - move;
}
}
return best_move;
Yang terjadi pada algoritma diatas adalah, MAX akan mengambil nilai maksimum dari pohon pencarian yang dibangkitkan pada simpul terakhir. Sebaliknya, MIN akan menangkis serangan MAX dengan mengambil nilai
minimum pada posisi akhir permainan, yang akan
meminimalisasi serangan MAX.
2.2 Implementasi Algoritma Minimax
Untuk lebih jelasnya, kita misalkan ada sebuah
permainan sederhana yang dengan hanya ada satu langkah untuk tiap pemain dengan kemungkinan situasi seperti ini:
Pergerakan Pergerakan Nilai
MAX MIN Evaluasi
A C 12
A D -2
B C 5
B D 6
Tabel 1. Contoh nilai akhir pergerakan MAX dan MIN
pada pohon Minimax.
Fungsi evaluasi berlaku untuk posisi akhir papan, yang berupa kombinasi langkah dari MIN dan MAX.
MAX berasumsi jika MIN akan bermain dengan baik.
Maka dari itu, MAX tahu jika dia melakukan pergerakan
A, maka MIN akan membalasnya dengan melakukan
pergerakan D, yang mengakibatkan nilai evaluasi -2
(kemenangan bagi MIN). Bagaimanapun juga, jika MAX melakukan gerakan B, dia pasti akan menang karena
pergerakan MIN yang terbaik hanya akan menghasilkan nilai evaluasi terbaik sebesar 5 saja. Jadi, dengan
menggunakan algoritma Minimax, MAX akan selalu
memilih untuk melakukan langkah B, walaupun dia
sebenarnya akan mendapatkan kemenangan yang lebih baik jika melakukan A dan MIN melakukan kesalahan dengan memilih langkah C.
2.3 Kelemahan Algoritma Minimax
Dengan membangkitkan pohon pencarian ini, komputer akan selalu mendapatkan penyelesaian terbaik untuk `
setiap langkahnya. Tetapi, masalah muncul ketika jumlah
input yang dimasukkan menjadi banyak. Bayangkan saja, untuk posisi pertama dalam permainan tic tac toe dimana
hanya terdapat kemungkinan untuk bergerak bagi 8 pion
dan 2 kuda, akan terdapat sebanyak 8*2 + 2*2 = 20
kemungkinan. Hal ini berarti pada simpul awal akan
didapatkan 20 sub-simpul sebagai langkah penyelesaian
pada aras (level) ke 1. Jika komputer melakukan hal yang sama untuk menganalisis langkah selanjutnya (berarti komputer melakukan pembangkitan pohon untuk simpul pada aras ke 1) maka akan dilakukan 20 pembangkitan dimana pada tiap pembangkita akan dilakukan puluhan pembangkitan lain untuk aras ke 2. Demikian seterusnya hingga algoritma mencapai aras terakhir permainan, menang
Berarti, usaha yang dilakukan akan tumbuh secara
dramatis mengikuti:
Jumlah kemungkinan posisi penyelesaian untuk
setiap pemain, dinamakan branching factor.
Sering dinotasikan sebagai B.
Kedalaman aras pada pembangunan pohon
pencarian, sering dinotasikan sebagai d. Biasa
disebut juga 'ply', yang berarti sebuah langkah
yang dilakukan oleh pemain.
Jika komputer hanya mengandalkan algoritma Minimax ini, proses membangkitkan simpul akan menjadi sangat lama. Kompleksitas dari algoritma Minimax ini adalah
eksponensial sebesar O(Bd) [5]. Dengan nilai B untuk
catur rata-rata adalah 35, dan jika kita akan menentukan 9 langkah kedepan, diperlukan sekitar 50 juta kemungkinan
untuk dieksplorasi. Hal ini tentunya membutuhkan usaha yang sangat keras untuk mengecek seluruh kemungkinan. Tentu saja diperlukan waktu yang lama untuk menganalisis seluruh kemungkinan ini dalam sebuah permainan tic tac toe jika hanya mengandalkan algoritma Minimax.
3. The Game Tic Tac Toe
Permainan Tic-Tac-Toe sangatlah sederhana; diilhami oleh permainan anak-anak. Dimainkan pada papan berukuran 3 x 3. Pada awal permainan, papan dikosongkan. Kedua pemain, X dan O, akan
menempatkan biji-bijinya keatas papan, sekali
pasang satu biji. Pemain yang mampu menempatkan tiga bijinya dalam satu garis (vertikal, horizontal, diagonal) itulah yang menang. Dan dikatakan seri
0
X
Gambar 1. contoh konfigurasi
4. IMPLEMENTASI
4.1 Konfigurasi Pengkodean
Untuk membangun strategi dalam permainan
Tic-tac-toe, ada sebuah langkah jitu di tiap konfigurasi papan. Tic-tac-toe dimainkan pada papan dengan sembilan kotak. Tiap kotak dapat terisi oleh ‘X’ atau ‘O’ maupun kosong. Total jumlah kemungkinan konfigurasi adalah 3 pangkat 9 Jika diasumsikan bahwa akan dibentuk sebuah susunan angka bayangan, maka ‘0’ akan merepresentasikan kosong, 1 untuk ‘X’ dan 2 untuk ‘O’. Misalnya:
Algoritma MTD(f) adalah sebuah algoritma optimasi Minimax baru yang lebih sederhana dan lebih sangkil
daripada beberapa pendahulunya[4]. Nama dari algoritma ini adalah kependekan dari MTD(n,f), yang disingkat dari Memory-enhanced Test Driver with node n and value f. MTD adalah nama dari sekumpulan driver program yang mencari pohon Minimax menggunakan pemanggilan zerowindow AlphaBetaWithMemory.
Dalam beberapa percobaan permainan komputer seperti
tic tac toe, catur, othello, dan checkers, algoritma ini mempunyai performa rata-rata lebih baik daripada Negascout (variasi dari Alphabeta yang diimplementasikan dalam hampir
semua permainan catur, checkers, dan othello). Salah satu
program tic tac toe terkuat, Cilkchess (http://theory.lcs.mit.
edu/~cilk/chess.html) milik MIT yang menggunakan
metode komputasi pararel, juga menggunakan MTD(f)
sebagai algoritma pencariannya menggantikan Negascout
yang digunakan oleh program tic tac toe pendahulunya,
StarSocrates.
4.2 Implementasi Algoritma MTD(f)
MTD(f) 'hanya' terdiri dari 10 baris kode saja, yaitu
seperti berikut:
function MTDF(root, f, d)
g := f
upperBound := +•
lowerBound := -•
while lowerBound < upperBound
if g = lowerBound then
• := g+1
else
• := g
g :=
AlphaBetaWithMemory(root, •-1, •, d)
if g < • then
upperBound := g
else
lowerBound := g
return g
Algoritma MTD(f) diatas memanggil fungsi
AlphaBetaWithMemory berkali-kali dengan metode zerowindow pencarian Alpha-beta, tidak seperti Negascout yang menggunakan pencarian wide-window. Pemanggilan AlphaBetaWithMemory mengembalikan batas dari nilai evaluasi Minimax. Batas dari nilai itu kemudian disimpan dalam upperbound (batas atas) dan lowerbound (batas bawah), membentuk sebuah interval yang melingkupi nilai Minimax yang sebenarnya pada pencarian dengan
kedalaman tertentu. Positif dan negatif tak hingga adalah
kependekan dari nilai diluar interval pada daun pohon. Ketika batas atas dan batas bawahnya bernilai sama atau batas bawah telah melampaui nilai batas atas, maka nilai
Minimax telah ditemukan.
Efisiensi dari MTD(f) berasal dari pencarian Alpha-beta dengan zero-window, dan menggunakan sebuah nilai batas yang baik (variabel beta) untuk melakukan pencarian
zero-window tersebut. Dalam versi yang sebelumnya,
Alpha-beta dipanggil dengan pencarian wide-window
seperti ini AlphaBeta(root, -INFINITY, +INFINITY,
depth), yang memastikan nilai kembaliannya berada
dalam interval alpha dan beta. Sedangkan dalam
algoritma MTD(f), digunakan pencarian zero-window, jadi
untuk setiap pemanggilan Alpha-beta akan
mengembalikan batas bawah dan batas atas dari nilai
Minimax berturut-turut. Pencarian dengan zero-window memberikan lebih banyak jalan pintas, tetapi lebih sedikit
informasi -hanya batas dari nilai minimax saja. Untuk
menyiasati hal itu MTD(f) perlu memanggil Alpha-beta beberapa kali, untuk mendekati nilai itu. Imbas dari
pemanggilan Alpha-beta secara berulang-ulang dapat
dihilangkan dengan menggunakan versi dari Alpha-beta yang menyimpan nilai simpul dalam memori.
Agar algoritma MTD(f) dapat berjalan dengan baik,
maka diperlukan “tebakan pertama” sebagai pengarah untuk menemukan nilai Minimax yang baik. Semakin baik
tebakan pertama, maka algoritma tersebut akan semakin efisien, dan diperlukan lebih sedikit pengulangan. Jika kita memberikan tebakan nilai Minimax pada MTD(f), dia
hanya akan melakukan dua pengulangan, yang satu untuk menentukan batas atas dari nilai x, dan yang satunya lagi untuk menemukan batas bawah dari nilai tersebut.
4.3 Algoritma AlphaBetaWithMemory
Sebagai catatan, MTD(f) memanggil fungsi Alpha-Beta yang menyimpan nilai simpul-simpulnya dalam memori, dan mengembalikan nilainya untuk pencarian kembali.
Untuk membuat MTD(f) sangkil, maka fungsi Alpha-beta harus menyimpan nilai simpul yang telah dicari.
Berikut ini adalah kode dari AlphaBetaWithMemory:
function AlphaBetaWithMemory(n :
node_type; alpha , beta , d : integer) : integer;
if retrieve(n) == OK then /*
Melihat tabel transposisi */
if n.lowerbound >= beta
then return n.lowerbound;
if n.upperbound <= alpha
then return n.upperbound;
alpha := max(alpha,
n.lowerbound);
beta := min(beta,
n.upperbound);
if d == 0 then g :=
evaluate(n); /* simpul daun */
else if n == MAXNODE then
g := -INFINITY; a :=
alpha; /* menimpan nilai
alpha yang sebenarnya */
c := firstchild(n);
while (g < beta) and (c
!= NOCHILD) do
g := max(g,
AlphaBetaWithMemory
(c, a, beta, d -
1));
a := max(a, g);
c :=
nextbrother(c);
else /* n adalah sebuah
MINNODE */
g := +INFINITY; b :=
beta; /* save original
beta value */
c := firstchild(n);
while (g > alpha) and (c
!= NOCHILD) do
g := min(g,
AlphaBetaWithMemory
(c, alpha, b, d -
1));
b := min(b, g);
c :=
nextbrother(c);
/* Tabel transposisi menyimpan
nilai simpul */
if g <= alpha then n.upperbound
:= g; store n.upperbound;
if g > alpha and g < beta then
n.lowerbound := g;
n.upperbound := g; store
n.lowerbound,
n.upperbound;
if g >= beta then n.lowerbound := g;
store n.lowerbound;
return g;
Tabel transposisi yang digunakan berguna untuk
menyimpan dan mengambil panggilan. Retrieve
berfungsi untuk memastikan jika sebuah nilai terdapat
5. KESIMPULAN
Untuk setiap permainan satu-lawan-satu, hampir selalu digunakan algoritma Minimax dalam permainan komputer. Proses pembangunan pohon pencarian Minimax dilakukan dengan metode depth-first-search. Algoritma Minimax mampu menganalisis segala kemungkinan posisi permainan untuk menghasilkan keputusan yang terbaik. Tetapi, dengan kelebihan yang seperti ini, algoritma Minimax tidak sangkil untuk memroses data dengan ukuran masukan yang besar, karena proses untuk membangun pohon pencarian dangan algoritma ini memiliki kompleksitas algoritma eksponensial. Maka dari itu, diperlukan optimasi dalam algoritma ini agar tidak semua simpul dibangkitkan.
Jenis optimasi dalam permainan TIC TAC TOE dengan algoritma Minimax ada bermacam-macam, tetapi dalam makalah ini hanya dibahas mengenai optimasi MTD(f) karena algoritma MTD(f) diklaim sebagai algoritma terbaik dibandingkan dengan algoritma-algoritma pendahulunya. Dengan menggunakan algoritma MTD(f) ini, proses pencarian nilai Minimax berlangsung lebih cepat.
Kekuatan dalam permainan tic tac toe pada manusia terletak dari strategi dalam merencanakan langkah, pemikiran jauh kedepan, intuisi, dan kreatifitas. Sedangkan komputer hanya mengandalkan kemampuan komputasi yang sangat cepat.
Kekuatan komputer yang mengandalkan proses komputasi yang sangat cepat harus didukung oleh algoritma yang memiliki efisiensi dan efektifitas yang tinggi. Untuk menyelesaikan permasalahan ini, permainan tic tac toe pada komputer menggunakan optimasi dari algoritma Minimax untuk memberikan hasil terbaik dalam waktu yang singkat.
“Untuk setiap permainan satu-lawan satu, ada
sebuah nilai yang bernilai V dan strategi yang dipilih oleh tiap pemain, sehingga: (a), Jika diberikan strategi dari pemain ke-2, maka langkah penyelesaian terbaik dari
pemain pertama adalah V. Dan (b), jika diberikan strategi dari pemain pertama, maka langkah penyelesaian terbaik dari pemain kedua adalah -V” [6]
REFERENCES
ALI, A.M.A. 1998. Segmentation and Categorization of Phonemes in Continuous Speech. Technical Report TR-CST25JUL98, Center for Sensor Technology, University of Pennsylvania.
Abdul Gapur, “Aplikasi Struktur Data The Minimax Game
Tree pada Permainan Catur”, Teknik Informatika ITB, 2007
Khoirush Sholih Ridhwaana Akbar, “Algoritma Minimax
dalam Pengambilan Keputusan pada Permainan Tic-tac
toe”, Teknik Informatika ITB, 2007.
ALI, A.M.A., VANDER SPIEGEL, J., MUELLER, P., HAENTJENS, G., AND BERMAN, J. 1999. An Acoustic-Phonetic feature based system for Automatic Phoneme Recognition in Continuous Speech. In IEEE Proceedings of the International Symposium on Circuits and Systems (ISCAS), 3, 118-121.
Bagley, J.D. (1967). The behaviour of adaptive
systems which employ genetic and correlation
algorithms. Doctoral dissertation, Ann arbor:
The University of Michigan.
ANANDAN, P., SARAVANAN, K., PARTASARATHI, R., AND GEETHA, T.V. 2002. Morphological Analyzer for Tamil. In Proceedings of ICON2002, 3-10.
ARDEN, A.H. REV. AND CLAYTON, A. C. 1969. A Progressive Grammar of the Tamil Language, Christian Literature Society, Madras.
BROWN, P., PIETRA, S,.DELLA PIETRA, V., AND MERCER, R. 1993. The mathematics of statistical machine translation: Parameter estimation’, Computational Linguistics, 19(2), 263-311.
BYRNE, W., HACIC, J., IIRCING, P., JELINEK, F., KHUDANPUR, S., KRBEC,.P., AND PSUTKA, J. 2001. On large vocabulary continuous speech recognition of highly inflectional language – Czech. In Proceedings of Eurospeech 2001, Aalborg, Denmark, 487-489.
Minimax - Wikipedia, The Free Encyclopedia
en.wikipedia.org/wiki/Minimax
diakses pada tanggal 15 Mei 2008
