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.

[oe_dmc] Generasi 1 vs 82 vs 435

Teman-teman,

Kali ini kita akan melihat perkembangan kromosom tipe oe_dmc, atau discs-mobility-corners tiga tahap. Untuk kromosom tipe oe_fmc (flips-mobility-corners tiga tahap) sebelumnya, kita sudah melihat bahwa generasi belakangan telah mengalahkan generasi awal dengan konsisten. Akankah hal ini juga kembali terjadi untuk kromosom tipe oe_dmc ini?

Informasi pemain

Generasi 1

Kromosom: 14:50:4:3:10:2:4:9:5:1:5:
Life: 1 ~ 6
Win: 35868
Lose: 40207
Draw: 1349
Elo: 395

Generasi 1 sempat menjadi best player pada generasi 1 dan 2.

Generasi 82

Kromosom: 8:47:5:0:2:2:4:8:1:4:2:
Life: 82 ~ 336
Win: 7655009
Lose: 6402677
Draw: 22412824
Elo: 985

Generasi 82 adalah juara bertahan untuk masa yang cukup lama, yaitu sejak generasi 187 ~ 238, tidak tanggung-tanggung selama 52 generasi.

Generasi 435

Kromosom: 14:42:0:0:4:0:4:10:2:7:9:
Life: 435 ~ 439
Win: 9091
Lose: 5977
Draw: 2806
Elo: 1652

Generasi 435 sempat menjadi best player pada generasi 435 ~ 437.


Generasi 1 vs 82

Pertama-tama kita akan melihat hasil pertandingan antara generasi 1 vs 82. Hasil akhirnya seperti terlihat pada gambar berikut, generasi 82 dengan keping putih memangkas habis generasi 1.



Ketika warna kedua pemain ditukar, generasi 82 kembali menang atas generasi 1 seperti ditunjukkan pada gambar di bawah.



Generasi 82 telah secara konsisten menang melawan generasi 1.


Generasi 82 vs 435

Berikutnya kita akan melihat pertarungan antara generasi 82 melawan generasi 435. Hasilnya, generasi 435 dengan keping putih menang mutlak atas generasi 82, seperti ditunjukkan pada gambar di bawah.



Selanjutnya kedua pemain bertukar warna, generasi 435 dengan keping hitam dan generasi 82 dengan keping putih. Hasilnya seperti dapat dilihat pada gambar di bawah, generasi 435 kembali menang dengan meyakinkan melawan generasi 82.



Generasi 435 telah secara konsisten menang melawan generasi 82.

Secara umum dapat kita lihat bahwa, sama seperti pada kromosom tipe oe_fmc, pada kromosom tipe oe_dmc juga terdapat proses perbaikan kemampuan bermain dari generasi ke generasi.

Saat ini proses evolusi masih terus berlangsung pada kromosom tipe oe_dmc. Bagaimanakah kelanjutan dari evolusi ini? .. mari ikuti terus kembara panjang ini.. :)

GeneThello: kembara panjang menuju batas intelijensia buatan

GeneThello (dibaca \jə-ˈne-ˈthe-lō\), kependekan dari genetic othello, adalah sebuah program bermain othello (reversi) [1] yang berbasis Algoritma Genetika (Genetic Algorithm, GA) [2].

Pada prinsipnya GeneThello terdiri dari sebuah program othello dengan fungsi evaluasi yang parameternya dapat diatur, dan sebuah sistem algoritma genetika untuk mencari parameter optimal dari fungsi evaluasi tersebut.

Program othello yang digunakan di sini saya buat menggunakan bahasa pemrograman Java dengan memanfaatkan Game Theory [3], yang sudah biasa digunakan orang untuk membuat program bermain game serupa, seperti tic-tac-toe, catur, shogi, igo dll. Sedangkan untuk sistem algoritma genetika, saya menggunakan sebuah framework java open source yang bernama JGAP [4].

Secara umum, fungsi evaluasi yang sering digunakan pada program othello, mempertimbangkan beberapa variabel utama, antara lain:

1. Flips: jumlah keping yang dibalik (flipped discs) pada sebuah langkah.

Permainan othello menghitung jumlah keping yang dimiliki oleh masing-masing pemain pada akhir permainan. Pemain dengan jumlah keping terbanyak akan menang. Sehingga pada umumnya semakin tinggi nilai Flips semakin baik langkah tersebut.

2. Discs: selisih jumlah keping yang dimiliki kawan dan yang dimiliki lawan setelah dilakukannya sebuah langkah.

Sama seperti Flips, pada umumnya semakin tinggi nilai Discs semakin baik langkah tersebut. Kemudian karena nilai Discs dapat dianggap sebagai akumulasi dari Flips sepanjang permainan, nilainya menjadi lebih stabil sehingga lebih sering digunakan.

3. Mobility: jumlah langkah yang dimiliki lawan, setelah dilakukannya sebuah langkah.

Ketika jumlah langkah yang dimiliki lawan adalah banyak, maka memungkinkan dia memilih langkah-langkah yang bagus. Sehingga perlu memperkecil nilai Mobility ini supaya lawan tidak mempunyai pilihan langkah yang bagus.

4. Corners: jumlah sudut yang ditempati kawan dikurangi jumlah sudut yang ditempati lawan, setelah dilakukannya sebuah langkah.

Posisi sudut pada permainan othello sangat penting, karena keping pada posisi ini bersifat permanen, yaitu tidak dapat dibalik lagi oleh lawan sampai permainan berakhir. Untuk itu perlu memperbesar nilai Corners ini, sehingga jumlah sudut yang kita tempati lebih banyak daripada yang ditempati lawan.

5. XSquares: selisih jumlah kotak berbahaya di samping diagonal sudut, yaitu kotak b2, b7, g2, g7, yang dimiliki oleh kawan dikurangi yang dimiliki oleh lawan.

Empat kotak xsquares ini dikenal sebagai kotak berbahaya, karena dapat menjadi jalan bagi lawan untuk mendapatkan kotak sudut. Sehingga di awal-awal permainan sedapat mungkin harus dihindari memasuki kotak xsquares ini.

6. Parity: kesempatan langkah terakhir di wilayah ruang kosong.

Pada satu wilayah ruang kosong yang bersambung, pihak yang melakukan langkah terakhir di wilayah tersebut akan mendapatkan kesempatan untuk membalik lebih banyak keping lawan. Dengan demikian parity sedapat mungkin harus direbut untuk setiap wilayah ruang kosong.

Advanced othello program seringkali menggunakan juga opening book sebagai pemandu di awal-awal permainan. Selain itu, pola tepi papan juga dapat menjadi salah satu faktor pertimbangan dalam fungsi evaluasi. Berbeda dengan faktor fungsi evaluasi lain yang berdasarkan heuristik, opening book dan pola tepi papan ini dibuat berdasarkan data statistika permainan othello yang penah dimainkan sebelumnya.

Dengan demikian perhitungan score sebuah langkah pada permainan othello, bentuknya yang umum akan mengikuti rumus berikut:

score = wf * Flips + wd * Discs - wm * Mobility + wc * Corners - wx * XSquares + wp * Parity

wf: bobot(weight) untuk Flips
wd: bobot untuk Discs
wm: bobot untuk Mobility
wc: bobot untuk Corners
wx: bobot untuk XSquares
wp: bobot untuk Parity

Permasalahan yang sering dijumpai adalah kesulitan untuk menentukan bobot-bobot ini secara tepat. Berdasarkan intuisi, Mobility sangat penting pada awal permainan, di mana pilihan langkah masih sangat banyak. Kemudian Corners dan XSquares menjadi semakin penting di permainan tengah, di mana posisi sudut mulai dapat dicapai. Dan akhirnya Flips, Discs dan Parity menjadi yang terpenting di permainan akhir, karena kemenangan ditentukan oleh banyaknya keping yang dimiliki.

Di sinilah algoritma genetika mengambil perannya dalam melakukan optimasi parameter, yaitu untuk menentukan bobot-bobot yang tepat. Sesuai namanya, algoritma ini memanfaatkan prinsip-prinsip genetika seperti yang berlaku pada teori seleksi alam. Di mana pada sebuah populasi makhluk hidup, hanya individu-individu terbaik saja yang dapat bertahan hidup dan menghasilkan keturunan untuk melanjutkan populasi tersebut. Proses ini juga dikenal sebagai evolusi.

Pertama-tama sistem GA akan membuat sebuah populasi dari program-program othello, misalnya berisi 300 program, yang kromosom awalnya dibangkitkan secara acak. Kromosom ini berisi kode-kode genetika yang mewakili parameter yang ingin dioptimasi, dalam hal ini bobot fungsi evaluasi.

Selanjutnya di antara program-program di dalam populasi ini diadakan turnamen untuk menentukan beberapa program terbaik. Setelah itu dilakukan kawin silang (crossover) di antara program-program terbaik untuk menghasilkan keturunan. Kemudian dengan kemungkinan tertentu, dilakukan juga mutasi terhadap kromosom dari program-program tersebut.

Beberapa program terbaik, keturunannya, dan program yang mengalami mutasi akan menjadi generasi berikutnya dari populasi tersebut menggantikan generasi sebelumnya. Di sini, jumlah program di dalam populasi dijaga tetap, yaitu dengan menghapus program-program terburuk dari generasi sebelumnya.

Setiap berganti generasi maka program-program di dalam populasi tersebut akan ber-evolusi menjadi semakin baik. Dan setelah beberapa generasi kita dapat berharap akan mendapatkan program terbaik yang benar-benar mampu bermain dengan kuat.

Skenario di atas adalah salah satu yang paling sederhana dari berbagai jenis optimasi yang dapat dilakukan oleh algoritma genetika terhadap permainan othello. Skenario lainnya ada banyak, misalnya fungsi evaluasi yang lebih rumit, fungsi evaluasi yang memanfaatkan logika fuzzy, fungsi evaluasi yang menggunakan neural network, dan yang paling canggih adalah fungsi evaluasi berupa "program yang ber-evolusi" menggunakan teknik Pemrograman Genetika (Genetic Programming, GP) [5].

Melalui blog ini saya akan mengajak anda semua, untuk berpetualang di dalam dunia algoritma genetika, dalam perjalanan mencari program othello terbaik yang mampu mengalahkan saya, mengalahkan anda, dan mengalahkan program othello lain yang pernah dibuat sebelumnya.. :)

Sampai kapankah perjalanan ini akan berlangsung? Mungkinkah kita akan bertemu dengan program othello terbaik itu? .. Satu yang jelas.. ini akan menjadi kembara panjang menuju batas intelijensia buatan..

References:

[1] http://en.wikipedia.org/wiki/Reversi
[2] John Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975, http://en.wikipedia.org/wiki/Genetic_algorithm
[3] Neumann, John Von., Theory Of Games And Economic Behavior, Princeton University Press., 1944, http://www.archive.org/details/theoryofgamesand030098mbp
[4] http://jgap.sourceforge.net/
[5] Koza, J.R., Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems, Stanford University Computer Science Department technical report STAN-CS-90-1314, 1990. http://en.wikipedia.org/wiki/Genetic_programming

.