Game Theory - algoritma Minimax

Dear rekan-rekan..

Bagaimanakah komputer dapat bermain othello? Apakah dia juga dapat berpikir seperti kita manusia? Bagaimana caranya berpikir? Pada tulisan kali ini kita akan coba memahami bagaimana cara komputer 'berpikir' dalam bermain othello.

Manusia berpikir dengan intuisi dan perhitungan

Ketika bermain othello, demikian juga permainan-permainan lain seperti catur, shogi, igo dll., kita manusia berpikir dengan menggabungkan intuisi yang menggunakan perasaan dan perhitungan yang menggunakan otak.

Pada sebuah posisi papan othello tertentu, mula-mula intuisi kita akan segera mengenali pola susunan keping di saat itu, ini adalah kemampuan pattern recognition yang inheren dimiliki oleh setiap manusia. Beberapa langkah yang jelas-jelas buruk atau 'dianggap' buruk segera dapat dikenali dan dihilangkan dari daftar langkah yang mungkin dilakukan (disebut possible moves, legal moves atau valid moves). Setelah itu barulah kita menghitung langkah-langkah sisanya yang 'terlihat' baik, dengan melakukan simulasi permainan di dalam kepala kita untuk setiap langkah, kemudian membandingkan untung-ruginya untuk menentukan langkah terbaik.

Misalnya di dalam sebuah posisi papan, ada 10 valid moves. Mula-mula intuisi kita akan menghapus 3 langkah yang jelas-jelas buruk, lalu 2 langkah lagi yang 'kelihatannya' buruk, dari daftar valid moves. Dengan demikian, hanya tinggal tersisa 5 langkah yang perlu diperhitungkan. Di sini, barulah kita melakukan simulasi permainan, ketika langkah 1 dilakukan maka lawan akan menjawab dengan langkah 1-1, 1-2, 1-3, ... Kalau kita melangkah dengan langkah 2 maka lawan akan menjawab dengan langkah 2-1, 2-2, 2-3, ... dst, sampai beberapa langkah ke depan (kedalaman tertentu) tergantung daya ingat kita.

Di sinipun intuisi manusia selalu berperan besar dalam mengenali pola-pola yang muncul di setiap kedalaman simulasi permainan untuk menghilangkan langkah-langkah yang 'dianggap' buruk dari perhitungan. Sehingga kita manusia dapat memilih hanya satu atau dua langkah tertentu saja yang 'dianggap' baik untuk ditelusuri sampai kedalaman cukup jauh, sementara langkah-langkah lain yang 'dianggap' tidak menjanjikan hanya diperhitungkan seperlunya saja. Dari hasil simulasi ini, kita membandingkan untung-rugi setiap langkah yang disimulasikan, dan menentukan langkah mana yang terbaik.

Komputer berpikir hanya dengan perhitungan

Nah.. di sisi lain, berbeda dengan manusia, komputer tidak mempunyai intuisi yang menggunakan perasaan. Sebagai gantinya, komputer mempunyai daya perhitungan yang jauh lebih besar daripada manusia. Ketika diberikan sebuah posisi papan othello tertentu, sama seperti manusia komputer juga melakukan perhitungan simulasi permainan untuk valid moves yang tersedia. Tetapi berbeda dengan manusia, dia tidak mempunyai intuisi untuk mengenali langkah-langkah yang jelas-jelas buruk lalu menghilangkannya dari daftar perhitungan. Sehingga komputer harus memperhitungkan semua valid moves, di sinilah daya perhitungan yang besar sangat diperlukan.

Pada dasarnya ketika diberikan sebuah susunan posisi papan tertentu, komputer menghitung nilai posisi tersebut menggunakan fitur-fitur yang dijelaskan pada artikel Strategi bermain othello, seperti jumlah keping, penguasaan sudut/x-quare/c-square, jumlah keping stabil, mobility, jumlah keping tepi, parity, dan pola sisi/sudut. Di setiap posisi papan yang sedang dipertimbangkan, mula-mula komputer menghitung nilai dari setiap fitur. Misalnya ketika dilakukan simulasi langkah 1, maka jumlah keping (discs) ada 30, sudut yang dikuasai (corners) ada 2, jumlah keping stabil (stables) ada 5, mobility ada 15, jumlah keping tepi (frontiers) ada 10, parity yang dimenangkan ada 3, dan nilai pola sisi/sudut (pattern) adalah 20.

Selanjutnya nilai dari masing-masing fitur ini digabungkan secara linier dengan bobot-bobot tertentu yang dianggap tepat. Misalnya nilai total dari posisi papan ini adalah:

score = w_d * discs + w_c * corners + w_s * stables + w_m * mobility + w_f * frontiers + w_p * parity + w_t * pattern
= -3 * 30 + 5 * 2 + 9 * 5 + 7 * 15 - 5 * 10 + 8 * 3 + 6 * 20
= 164

Dengan asumsi bahwa bobot-bobot untuk setiap fitur yang dianggap tepat adalah:

w_d = -3 (bobot untuk discs)
w_c = 5 (bobot untuk corners)
w_s = 9 (bobot untuk stables)
w_m = 7 (bobot untuk mobility)
w_f = -5 (bobot untuk frontiers)
w_p = 8 (bobot untuk parity)
w_t = 6 (bobot untuk pattern)

Ini adalah nilai papan untuk simulasi langkah 1. Berikutnya dilakukan simulasi untuk langkah 2, dihitung lagi berapa nilainya, langkah 3 berapa nilainya.. dst. Dan ini baru berpikir sampai kedalaman satu, disebut juga 1-ply dalam istilah kecerdasan buatan untuk permainan komputer. Untuk berpikir sampai kedalaman 2, maka di setiap posisi papan (hasil simulasi kedalaman 1) belum dihitung dulu nilainya, tetapi harus dilakukan lagi simulasi kedalaman 2 untuk setiap langkah di posisi tersebut, baru kemudian dilakukan perhitungan di atas.

Jadi kalau di kedalaman 1 ada 3 valid moves, yang membawa ke 3 posisi papan berbeda, dan di setiap posisi papan rata-rata ada 3 valid moves yang dimiliki lawan kita, maka untuk berpikir sampai kedalaman 2 kita perlu memperhitungkan sebanyak 3 x 3 = 9 posisi papan. Tetapi rata-rata jumlah valid moves pada othello diperkirakan sekitar 8, sehingga 'berpikir' sampai kedalaman 2 perlu menghitung 8^2 = 64 posisi, kedalaman 3 perlu 8^3 = 512 posisi.. dan kedalaman 10 perlu menghitung lebih dari 1 milyar posisi!

Algoritma Minimax

Untuk melakukan perhitungan simulasi permainan inilah, digunakan algoritma standar di dalam bidang kecerdasan buatan (artificial intelligence, AI) yang sudah dikembangkan sejak lama, yaitu Game Theory, terutama algoritma yang disebut Minimax. Sesuai namanya, algoritma minimax adalah aturan untuk permainan zero-sum 2 pemain, yang berusaha meminimalkan kemungkinan kalah sambil memaksimalkan kemungkinan menang untuk pemain yang akan melangkah.

Di kedalaman 1 (dan kedalaman ganjil lainya), posisi papan akan menentukan nilai untuk pemain yang akan melangkah saat ini (current player), sehingga di kedalaman ganjil ini algoritma minimax memilih langkah bernilai maksimal sebagai langkah terbaik. Sebaliknya di kedalaman 2 (dan kedalaman genap lainnya), posisi papan akan menentukan nilai untuk pemain lawan yang akan melangkah berikutnya (opponent player), sehingga di kedalaman genap ini algoritma minimax memilih langkah bernilai minimal sebagai langkah terbaik.

Sebagai ilustrasi sampai kedalaman dua bisa digambarkan dengan tabel berikut:

	B memilih B1	B memilih B2	B memilih B3
A memilih A1	+3	−2	+2
A memilih A2	−1	0	+4
A memilih A3	−4	−3	+1

Ketika A memilih langkah A1 dilanjutkan dengan B memilih langkah B1, posisi papan yang terbentuk bernilai +3. Demikian pula untuk A1 → B2 nilainya -2, A1 → B3 nilainya +2 dst. Sekarang mari kita coba aplikasikan algoritma minimax untuk menghitung langkah terbaik bagi pemain A.

Terhadap langkah A1 (kedalaman 1) misalnya valid moves pemain B adalah B1, B2 dan B3 (kedalaman 2), dan langkah terbaik menurut algoritma minimax didapat dengan mencari langkah bernilai minimal (karena di kedalaman 2), yaitu B2 (bernilai -2). Demikian pula terhadap langkah A2 yang terbaik bagi B adalah B1 (bernilai -1), dan terhadap A3 adalah B1 juga (bernilai -4). Selanjutnya, nilai untuk langkah pemain A (kedalaman 1) adalah nilai yang 'dikembalikan' dari pemain B di kedalaman 2, yaitu A1 adalah -2, A2 adalah -1, dan A3 adalah -4. Kemudian untuk kedalaman 1 ini algoritma minimax mencari nilai maksimal sebagai langkah terbaik, yaitu A2 (bernilai -1).

Untuk kedalaman lebih dari dua, cara 'berpikir' algoritma minimax dapat digambarkan sebagai pohon permainan (game tree) seperti pada gambar di atas. Di lokasi paling dalam (disebut lokasi node daun atau leaf node), dalam hal ini kedalaman 4, dilakukanlah perhitungan nilai posisi papan yang selanjutnya 'dikembalikan' ke node pada kedalaman di atasnya terus hingga sampai lokasi paling atas (di sebut akar atau root). Panah merah menunjukkan nilai yang dikembalikan dari langkah terbaik pilihan algoritma minimax ke kedalaman di atasnya. Demikianlah, kita dapat melihat algoritma minimax bergantian memilih langkah dengan nilai minimal dan maksimal sebagai langkah terbaik sesuai dengan kedalamannya. Dengan algoritma ini komputer dapat 'berpikir' sampai kedalaman tertentu untuk menentukan langkah terbaik untuk memenangkan permainan.

Tetapi pada prakteknya, algoritma minimax kini tidak pernah digunakan lagi, karena algoritma ini harus memperhitungkan semua valid moves, sehingga memerlukan waktu yang sangat lama. Sebagai gantinya telah dikembangkan beberapa improvisasi dari minimax seperti algoritma AlphaBeta, NegaScout dll. yang dapat melakukan pemangkasan game tree supaya tidak perlu memperhitungkan semua valid moves, sehingga dapat 'berpikir' dalam waktu jauh lebih cepat.

Strategi bermain othello

Dear rekan-rekan..

Othello adalah permainan yang sangat mudah dipelajari, tetapi memerlukan waktu lama untuk menjadi pandai.. seperti judul buku yang ditulis oleh mantan juara dunia othello, Brian Rose.. "Othello: A minute to learn...A lifetime to master". Dan pada tulisan kali ini saya ingin mengupas sedikit tentang strategi bermain othello supaya menang.

1. Jumlah keping

Tujuan permainan othello adalah untuk memiliki jumlah keping sebanyak-banyaknya di akhir permainan. Karena inilah pemain pemula othello selalu berusaha melangkah di kotak-kotak di mana dia bisa membalik keping lawan sebanyak-banyaknya. Strategi ini disebut 'greedy strategy' (= strategi rakus).

Greedy strategy memang diperlukan di akhir permainan untuk memperbanyak jumlah keping, tetapi di awal dan tengah permainan strategi ini akan membawa malapetaka, dengan alasan 'mobility' seperti di bawah. Untuk itu disarankan supaya kita menjaga jumlah keping sedikit di awal dan tengah permainan, tetapi tentu saja harus memperbanyak keping di akhir permainan.

2. Kotak sudut (corners), x-squares, dan c-squares

Ketika kita berhasil meletakkan keping di kotak sudut (corner), maka keping itu tidak akan pernah bisa dibalik oleh lawan, karena tidak ada keping yang dapat mengapitnya. Bahkan bermula dari kotak sudut ini, kita dapat menggunakannya untuk membalik keping-keping lawan di sekitarnya. Itulah sebabnya kotak sudut adalah kotak yang paling penting di dalam permainan othello. Untuk itu disarankan supaya kita berusaha mendapatkan kotak sudut di awal dan tengah permainan.

Kotak x-square adalah kotak di sebelah diagonal kotak sudut. Kotak ini dipandang sebagai kotak yang paling berbahaya, karena ketika kita meletakkan keping kita di kotak ini, lawan dapat segera memanfaatkannya untuk mendapatkan kotak sudut di sebelahnya. Karena itulah disarankan untuk tidak melangkah di kotak x-squares pada awal dan tengah permainan.

Kotak c-square adalah kotak di sebelah kotak sudut secara horizontal atau vertikal. Kotak ini juga dipandang berbahaya setelah x-squares, karena pemain lawan dapat memanfaatkannya untuk mendapatkan sudut dengan trik-trik tertentu. Untuk itu disarankan supaya kita tidak melangkah ke kotak c-squares di awal dan tengah permainan.

3. Keping stabil

Keping yang tidak dapat diapit oleh keping lawan, sehingga tidak dapat dibalik, disebut keping stabil. Contoh paling ekstrim, keping di sudut adalah keping stabil. Selain itu keping di sisi papan yang bersambung dengan keping sudut juga keping stabil. Atau keping yang semua baris horizontal, vertikal dan diagonalnya bersambung dengan keping stabil lain, adalah juga keping stabil.

Keping stabil ini menjadi penentu kemenangan secara mutlak karena tidak bisa dibalik lagi menjadi keping lawan. Untuk itu disarankan supaya kita memperbanyak jumlah keping stabil di semua tahapan permainan.

4. Mobility

Di permulaan permainan hitam dapat melangkah di empat buah kotak. Selanjutnya putih dapat melangkah di tiga buah kotak. Demikian seterusnya jumlah kotak di mana pemain dapat melangkah, yaitu dapat mengapit keping lawan, berubah-ubah tergantung langkah lawan sebelumnya. Jumlah kotak di mana pemain dapat melangkah ini disebut mobility.

Semakin banyak mobility maka semakin banyak kemungkinan pilihan langkah yang bagus, sebaliknya semakin sedikit mobility maka semakin sedikit pilihan langkahnya sehingga semakin besar kemungkinan hanya tersisa langkah-langkah buruk. Karena itu disarankan untuk memperbanyak mobility kita di semua tahapan permainan.

Mobility berkaitan erat dengan jumlah keping. Apabila jumlah keping kita banyak, maka semakin susah kita mengapit keping lawan, sehingga mobility kita jadi sedikit. Sebaliknya ketika jumlah keping kita sedikit, akan semakin mudah kita mengapit keping lawan, sehingga mobility meningkat.

5. Keping tepi (frontier disc)

Ini adalah keping yang terletak di tepi kotak kosong. Ketika jumlah keping tepi yang kita miliki banyak, maka semakin besar kemungkinan lawan dapat melangkah di kotak kosong di sampingnya, sehingga mobility lawan meningkat. Untuk itu disarankan supaya kita mempersedikit keping tepi di semua tahapan permainan.

Strategi mempersedikit keping tepi ini juga berarti kita harus berusaha supaya keping kita selalu tersambung satu sama lain dan berada di dalam kepungan keping lawan.

6. Parity (ganjil-genap)

Di akhir permainan, kotak kosong di papan sering terbagi-bagi menjadi beberapa kelompok. Dan parity adalah kesempatan untuk melangkah terakhir di sebuah kelompok kotak kosong. Pemain yang dapat melangkah terakhir di sebuah kelompok kotak kosong akan diuntungkan karena dia mendapat kesempatan terakhir untuk membalik keping-keping lawan menjadi kepingnya. Karena itulah disarankan supaya kita menjadi pemain terakhir yang melangkah di semua kelompok kotak kosong di akhir permainan.

Caranya adalah dengan menghitung jumlah kotak kosong di sebuah kelompok. Ketika jumlahnya genap maka kita jangan melangkah ke sana, biarkan lawan kita yang melangkah ke sana. Sebaliknya ketika jumlahnya ganjil, maka kita usahakan untuk melangkah kesana, sebelum lawan kita melangkah ke sana. Dengan demikian kita akan menjadi yang terakhir untuk melangkah di semua kelompok kotak kosong.

7. Pola susunan keping

Di akhir permainan, susunan keping hitam dan putih di sisi dan sudut papan, sering membentuk pola-pola berulang yang dapat dikaitkan dengan kemenangan hitam atau putih. Contohnya adalah ketika keping hitam (h) dan putih (p) membentuk pola di sisi papan, h-p-p-p-...-p-p-h, adalah pola kemenangan untuk hitam, sebaliknya ini adalah juga pola kekalahan untuk putih. Karena pada akhirnya hitam dapat melangkah di kotak kosong di tengah-tengah untuk membalik semua keping putih menjadi hitam.

Pola-pola seperti ini ada banyak jumlahnya, dan akan kita ingat secara alami seiring dengan semakin seringnya kita bermain othello dan menemui berbagai pola-pola yang berujung pada kemenangan atau kekalahan.

Demikianlah beberapa strategi yang dapat kita gunakan untuk dapat bermain othello dengan kuat dan memenangkan permainan.

Apa itu Othello?

Dear rekan-rekan,

Othello atau disebut juga reversi adalah permainan yang menggunakan papan berisi kotak sebanyak 8x8, antara dua orang pemain dengan keping hitam dan putih seperti di bawah.

Tujuan dari permainan ini adalah kedua pemain saling berusaha memiliki jumlah keping terbanyak di akhir permainan untuk jadi pemenang.

Aturan permainannya adalah sebagai berikut:

1. Permainan dimulai dari posisi papan dengan susunan keping hitam dan putih seperti pada gambar di atas, yaitu dua keping hitam dan dua keping putih tepat di tengah-tengah papan dengan posisi saling memotong secara diagonal, dengan keping hitam miring ke kanan-atas dan putih miring ke kiri-atas.
2. Pemain hitam melangkah pertama kali dengan meletakkan keping hitam di kotak kosong di mana dia bisa mengapit keping putih di antara dua keping hitam, yaitu di antara keping hitam yang sudah ada di papan dan keping hitam yang baru diletakkan, boleh mengapit secara horizontal, vertikal maupun diagonal, misalnya di kotak "d3".
3. Keping putih yang terjepit pada no. 2 di atas, dibalik semua menjadi keping hitam.
   
4. Berikutnya giliran pemain putih melangkah dengan meletakkan keping putih di kotak kosong di mana dia bisa mengapit keping hitam di antara dua keping putih, yaitu di antara keping putih yang sudah ada di papan dan keping putih yang baru diletakkan, boleh mengapit secara horizontal, vertikal maupun diagonal, misalnya di kotak "c3".
5. Keping hitam yang terjepit pada no. 4 di atas, dibalik semua menjadi keping putih.
   
   
6. Demikian kedua pemain bergantian saling meletakkan kepingnya di kotak kosong di mana dia bisa mengapit keping lawannya, dan membalik keping lawannya menjadi kepingnya.
7. Kedua pemain tidak boleh meletakkan kepingnya di kotak yang sudah terisi, atau di kotak kosong di mana dia tidak mengapit keping lawannya.
   
   
   Gambar kiri menunjukkan kotak yang sudah terisi sehingga tidak bisa diletakkan keping baru. Gambar kanan, tanda lingkaran biru menunjukkan kotak kosong yang mengapit keping putih oleh hitam, sehingga hitam boleh melangkah ke sana. Tanda silang merah dan semua kotak kosong diluarnya, menunjukkan kotak kosong yang tidak mengapit keping putih oleh hitam, sehingga hitam tidak boleh melangkah ke sana. 
8. Apabila pemain tidak mempunyai kotak di mana dia bisa melangkah, maka dia harus 'pass' yaitu memberikan gilirannya melangkah kepada lawannya.
9. Apabila kedua pemain sama-sama tidak mempunyai kotak di mana dia bisa melangkah, biasanya ketika papan sudah penuh, maka permainan selesai.
10. Pemain dengan jumlah keping terbanyak adalah pemenang.

Demikianlah sekilas tentang permainan othello. Anda ingin mencobanya? Silakan coba lawan genethello di..

http://genethello.blogspot.com/2010/02/genethello-applet.html