_board.jpg)
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.
_board.jpg)