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

Kromosom generasi 9 vs generasi 8

Dear rekan-rekan..

Selanjutnya masih permainan antara pemain yang sama yaitu kromosom generasi 8 vs generasi 9 dengan warna ditukar, yaitu generasi 9 dengan keping hitam melawan generasi 8 dengan keping putih. Kali ini, kromosom generasi 8 gantian mampu menang atas generasi 9, namun dengan selisih hanya 4 keping.

Kali ini permainan dibuka dengan perpendicular opening hingga langkah 5.. selanjutnya nilai posisi kedua pemain berkembang seperti dibawah, sebagaimana dianalisa oleh aplikasi WZebra..

Selepas opening perlahan-lahan putih menguasai permainan hingga sekitar langkah 25. Di sini hitam mampu memperbaiki posisi dan terus bertahan sampai kira-kira langkah 47.. di mana hitam melakukan blunder dengan langkah "a2" sehingga putih mendapatkan sudut "a1". Selanjutnya pelan-pelan hitam mencoba memperbaiki posisi, namun akhirnya harus kalah dengan selisih 4 keping.

Info pemain

Black: Computer
Time: 60 seconds
Chromosome: 9:46:-8:8:-6:6:-7:0:0:0:2:5:-9:0:-1:0:3:0:-8:-7:
Life: generation 9 ~ 11
Elo rating: 1407
Win: 4609 times
Lose: 3445 times
Draw: 237 times

White: Computer
Time: 60 seconds
Chromosome: 12:58:0:9:7:-5:5:2:3:2:4:5:-9:-6:-1:0:3:7:-1:0:
Life: generation 8 ~ 11
Elo rating: 1647
Win: 4521 times
Lose: 3500 times
Draw: 263 times

Result: white wins by 4 discs

Transkrip

1. d3 - c5
3. f6 - f5
5. c6 - e3
7. c3 - c4
9. b3 - b4
11. e2 - d6
13. a4 - f4
15. d7 - e7
17. f8 - e1
19. f2 - c2
21. d2 - c1
23. d1 - a5
25. a6 - b5
27. a3 - b6
29. g5 - g6
31. f3 - d8
33. f1 - g1
35. e6 - c7
37. h6 - e8
39. c8 - b1
41. f7 - g4
43. g2 - h5
45. a7 - b2
47. a2 - a1
49. h3 - h2
51. g3 - h4
53. h1 - b7
55. a8 - b8
57. pass - g7
59. g8 - h7
61. h8 - pass

Format SGF


(;FF[4]GM[2]SZ[8]
AP[GeneThello:0.7]

PB[9:46:-8:8:-6:6:-7:0:0:0:2:5:-9:0:-1:0:3:0:-8:-7:]
PW[12:58:0:9:7:-5:5:2:3:2:4:5:-9:-6:-1:0:3:7:-1:0:]
RE[W+4]
TM[60]

AB[e4][d5]
AW[d4][e5]
PL[B]
;B[d3];W[c5]
;B[f6];W[f5]
;B[c6];W[e3]
;B[c3];W[c4]
;B[b3];W[b4]
;B[e2];W[d6]
;B[a4];W[f4]
;B[d7];W[e7]
;B[f8];W[e1]
;B[f2];W[c2]
;B[d2];W[c1]
;B[d1];W[a5]
;B[a6];W[b5]
;B[a3];W[b6]
;B[g5];W[g6]
;B[f3];W[d8]
;B[f1];W[g1]
;B[e6];W[c7]
;B[h6];W[e8]
;B[c8];W[b1]
;B[f7];W[g4]
;B[g2];W[h5]
;B[a7];W[b2]
;B[a2];W[a1]
;B[h3];W[h2]
;B[g3];W[h4]
;B[h1];W[b7]
;B[a8];W[b8];W[g7]
;B[g8];W[h7]
;B[h8]
)

Kromosom generasi 8 vs generasi 9

Dear rekan-rekan..

Berikut adalah permainan antara kromosom generasi 8 dengan keping hitam, yang merupakan kromosom terbaik di zaman generasi 9, melawan kromosom generasi 9 dengan keping putih, yang merupakan kromosom terbaik di zaman generasi 10. Kromosom generasi 8 memilik Elo rating 1647 pada zamannya, sedangkan kromosom generasi 9 'hanya' memiliki Elo rating 1406 pada zamannya. Namun demikian, kromosom generasi 9 mampu menang atas generasi 8 dengan selisih 14 keping.

Permainan dibuka dengan diagonal opening, sampai hitam melangkah ke "b2" pada langkah ke-5 menjadikannya sebagai pembukaan x-square opening, yang merugikan hitam dan membuatnya rentan kalah. Selanjutnya permainan berkembang dengan nilai posisi kedua pemain bergerak seperti grafik di bawah, sebagaimana hasil analisa aplikasi WZebra..

Langkah 6-10 putih berhasil memanfaatkan x-square opening yang dimainkan hitam dan mempertahankan keunggulan posisinya. Lalu pada langkah 11 hitam berhasil membalikkan keadaan dan memperbaiki posisinya, dan berhasil dipertahankannya hingga sekitar langkah 35, puncaknya adalah pada langkah 19 di mana posisi hitam menjadi lebih unggul daripada putih.

Kemudian mulai langkah 36, putih kembali menguasai permainan hingga langkah 42.. lalu perlahan-lahan hitam kembali berhasil memperbaiki posisinya sedikit demi  sedikit.. hingga posisi kedua pemain kembali seimbang pada langkah 55-57, di mana hitam melakukan langkah blunder "b1".. yang kemudian dimanfaatkan oleh putih untuk memenangkan permainan.

Info pemain

Black: Computer
Time: 60 seconds
Chromosome: 12:58:0:9:7:-5:5:2:3:2:4:5:-9:-6:-1:0:3:7:-1:0:
Life: generation 8 ~ 11
Elo rating: 1647
Win: 4521 times
Lose: 3500 times
Draw: 263 times

White: Computer
Time: 60 seconds
Chromosome: 9:46:-8:8:-6:6:-7:0:0:0:2:5:-9:0:-1:0:3:0:-8:-7:
Life: generation 9 ~ 11
Elo rating: 1406
Win: 4600 times
Lose: 3442 times
Draw: 234 times

Result: white wins by 14 discs

Transkrip

1. d3 - c3
3. c4 - e3
5. b2 - c5
7. f4 - f3
9. e2 - c2
11. g4 - g3
13. f2 - g1
15. e6 - d6
17. h3 - f5
19. e1 - d2
21. b6 - a1
23. c6 - b5
25. g6 - f6
27. a4 - a5
29. g5 - a3
31. e7 - h5
33. b3 - b4
35. h4 - h2
37. d1 - c1
39. g2 - h6
41. a6 - f7
43. d7 - h1
45. g8 - f1
47. h7 - h8
49. g7 - a7
51. a2 - d8
53. a8 - f8
55. b7 - b8
57. b1 - c7
59. c8 - e8

Format SGF

(;FF[4]GM[2]SZ[8]
AP[GeneThello:0.7]

PB[12:58:0:9:7:-5:5:2:3:2:4:5:-9:-6:-1:0:3:7:-1:0:]
PW[9:46:-8:8:-6:6:-7:0:0:0:2:5:-9:0:-1:0:3:0:-8:-7:]
RE[W+14]
TM[60]

AB[e4][d5]
AW[d4][e5]
PL[B]
;B[d3];W[c3]
;B[c4];W[e3]
;B[b2];W[c5]
;B[f4];W[f3]
;B[e2];W[c2]
;B[g4];W[g3]
;B[f2];W[g1]
;B[e6];W[d6]
;B[h3];W[f5]
;B[e1];W[d2]
;B[b6];W[a1]
;B[c6];W[b5]
;B[g6];W[f6]
;B[a4];W[a5]
;B[g5];W[a3]
;B[e7];W[h5]
;B[b3];W[b4]
;B[h4];W[h2]
;B[d1];W[c1]
;B[g2];W[h6]
;B[a6];W[f7]
;B[d7];W[h1]
;B[g8];W[f1]
;B[h7];W[h8]
;B[g7];W[a7]
;B[a2];W[d8]
;B[a8];W[f8]
;B[b7];W[b8]
;B[b1];W[c7]
;B[c8];W[e8]
)

Telah keluar GeneThello v 0.7: animated GIF generator, parallel Evolver

Dear rekan-rekan GeneThello..

Hari ini GeneThello versi 0.7 telah rilis.. beberapa fitur baru adalah:

1. Animated GIF generator.
2. Parallel Evolver.
3. Penyesuaian nilai pattern.
4. Warna baru untuk papan game.. :)

Transkrip permainan othello adalah penting untuk merekam permainan othello sehingga dapat dimainkan dan dipelajari kembali di kemudian hari. Tetapi transkrip othello memerlukan aplikasi player untuk memainkannya kembali. Pada versi sebelumnya GeneThello telah dilengkapi fitur untuk meload dan memainkan kembali transkrip othello yang disimpan dalam format SGF.

Karena transkrip memerlukan aplikasi player untuk memainkannya kembali, maka tidak cocok untuk ditampilkan di halaman situs web, karena tidak mudah dipahami secara visual oleh manusia. Untuk tujuan ditampilkan di halaman situs web seperti ini, yang paling tepat adalah transkrip dalam bentuk animated GIF, yang otomatis memainkan transkrip tersebut dari awal sampai akhir. Pada versi 0.7 ini GeneThello dilengkapi dengan fitur baru untuk men-generate animated GIF dari permainan yang baru dimainkan, maupun dari transkrip berformat SGF.

Fitur baru yang juga ditambahkan untuk versi ini adalah parallel Evolver. Evolver adalah sebuah program GeneThello yang digunakan untuk melakukan evolusi algoritma genetika terhadap populasi kromosom di server. Pada versi ini, evolusi yang dilakukan oleh Evolver dilakukan secara parallel dengan dibagi ke dalam 8 thread, sehingga proses evolusi yang memakan waktu lama dapat dipercepat.

Selanjutnya fitur lain yang juga ditambahkan adalah penyesuaian nilai pattern. Seperti diketahui salah satu fitur yang digunakan GeneThello untuk menghitung nilai evaluasi langkahnya adalah nilai pattern, yaitu nilai statistika pola susunan keping (disc) di tepi dan sudut papan, yang menunjukkan seberapa baik/buruk susunan keping tersebut. Nilai pola ini selalu bertambah/berkurang setiap kali pemain mendapatkan kemenangan/kekalahan. 

Akibatnya untuk pola yang hampir selalu menang, misalnya susunan 8 keping hitam di tepi papan untuk pemain hitam, nilainya akan selalu bertambah tanpa batas. Demikian pula untuk pola yang hampir selalu kalah, misalnya susunan 8 keping hitam di tepi papan untuk pemain putih, nilainya akan selalu berkurang tanpa batas. Untuk mengatasi masalah ini, pada versi sekarang telah ditambahkan fitur penyesuaian nilai pattern yang menjaga deviasi standar dari nilai pattern selalu kurang dari 10000, dengan cara membagi dua nilai seluruh pattern ketika deviasi standar melebihi 10000.

Terakhir adalah pemberian warna baru untuk papan permainan dan penambahan hiasan pada penggambaran keping.. sehingga tampilan GeneThello kini menjadi lebih othello.. :)

User manual dan javadoc untuk GeneThello dapat dilihat di:

http://genethello.sourceforge.net/manual/
http://genethello.sourceforge.net/javadoc/

Dan silakan download versi terbaru di..

http://sourceforge.net/projects/genethello/files

Lalu silakan lawan kromosom 'Best so far' yang telah ditemukan.. dengan limit waktu 1 menit (60 detik).. dapatkah anda menang?.. :)

Rilis GeneThello versi 0.6

Dear rekan-rekan GeneThello..

Aplikasi GeneThello versi 0.6 telah dirilis.. beberapa fitur baru yang ditambahkan antara lain:

• Support transkrip dalam bentuk file format SGF.
• Dapat membaca dan mereplay file format SGF.
• Menggabungkan tipe-tipe kromosom menjadi satu.

Format SGF (Smart Game Format) adalah format file komputer yang digunakan untuk menyimpan transkrip permainan papan. Permainan yang disupport oleh forma SGF antara lain: Igo, Shogi, Catur, Reversi (Othello), Amazons, Backgammon, Gomoku+Renju dll. Igo adalah yang paling banyak menggunakan format ini dan menjadi default. SGF menggunakan representasi berbasis tree dari permainan untuk menyimpan informasi; struktur tree membuat penambahan variasi menjadi mudah. SGF juga berbasis teks bukan binari untuk tujuan portabilitas.

Fungsi replay dapat digunakan untuk memainkan kembali secara otomatis, permainan yang baru saja berakhir, atau untuk memutar ulang permainan lama yang disimpan dalam format SGF.

Pada versi sebelumnya tipe kromosom dibagi berdasarkan 6 fitur yang digunakan pada perhitungan fungsi evaluasi, yaitu: flips, discs, mobility, xsquares, corners, dan pattern. Flips adalah jumlah disc yang dibalik, di awal permainan sedikit flips lebih baik, tetapi di akhir permainan banyak flips lebih baik. Discs adalah jumlah disc yang dimiliki, mirip seperti flips, di awal permainan sedikit discs lebih baik, tetapi di akhir permainan banyak discs lebih baik. Kemudian mobility adalah jumlah valid move yang dimiliki, sepanjang permainan banyak mobility adalah lebih baik. XSquares adalah jumlah kotak x-square (kotak yang adjacent dengan sudut) yang dimiliki, sepanjang sudut belum terisi maka sedikit xsquares lebih baik. Dan corners adalah jumlah kotak sudut yang dimiliki, semakin banyak semakin baik. Dan terakhir patterns adalah pola menang dan kalah dari disc di sisi dan sudut papan, nilainya ditentukan secara statistik menggunakan ribuan permainan aktual.

Berdasarkan 6 fitur tersebut, maka dulu kita mengenal kromosom tipe 'fmc' yang menggunakan fitur flips, mobility dan corners, atau kromosom tipe 'dmc' yang menggunakan fitur discs, mobility dan corners, atau kromosom tipe 'dmp' yang menggunakan fitur discs, mobility dan pattern, dll. Tetapi kini semua tipe-tipe tersebut disatukan menjadi satu tipe besar yang mencakup semua fitur-fitur ini, yaitu tipe 'fdmxcp' yang menggunakan flips, discs, mobility, xsquares, corners dan pattern.

Tujuan penyatuan tipe-tipe ini adalah supaya proses evolusi dapat dilakukan secara global mencakup semua fitur fungsi evaluasi. Sehingga kita akan mendapatkan fungsi evaluasi optimal yang bersifat global bukan lokal pada fitur-fitur yang dipilih saja. Tetapi dengan waktu evolusi yang semakin lama.

User manual dan javadoc untuk GeneThello dapat dilihat di:

http://genethello.sourceforge.net/manual/
http://genethello.sourceforge.net/javadoc/

Dan silakan download versi terbaru di..

http://sourceforge.net/projects/genethello/files

Kemudian coba lawan kromosom yang ditemukan 'Best so far'.. dengan limit waktu 1 menit (60 detik).. apakah cukup kuat?.. :)

GeneThello 0.5 telah dirilis..

Dear rekan-rekan..

GeneThello versi 0.5 telah dirilis di SourceForge.. beberapa perubahan yang dilakukan adalah:

• injeksi top kromosom ekstra dari database ke populasi setiap selesai evolusi
• perbaikan implementasi game theory
  pembuatan versi fail-hard dan fail-soft untuk alphabeta dan negascout
• penambahan fitur manajemen waktu
  berpikirnya komputer kini dibatasi oleh waktu, bukan lagi 'depth'
• penambahan fitur blocking glass pane
  pengguna tidak lagi bisa mengklik sebelum waktunya
• pembaruan class PlayerHouse berisi data kromosom terbaru
• pembaruan class PatternHouse berisi data pola terbaru

http://genethello.sourceforge.net/manual/ http://genethello.sourceforge.net/javadoc/

Silakan download versi terbaru di..

http://sourceforge.net/projects/genethello/files

Kemudian coba lawan chromosome type 'oe_dmp' (Disc-Mobility-Pattern) generasi terakhir.. dengan limit waktu 1 menit (60 detik).. lumayan kuat kan?.. :)

GeneThello 0.4 is out..

Dear rekan-rekan..

GeneThello versi 0.4 telah upload di SourceForge.. kini ditambah fitur option '--nonetwork' sehingga dapat dimainkan tanpa koneksi ke server.. juga dilengkapi dengan user manual dan javadoc.. :)

http://genethello.sourceforge.net/manual/
http://genethello.sourceforge.net/javadoc/

Silakan download versi terbaru di..

http://sourceforge.net/projects/genethello/files

Kemudian coba lawan chromosome type 'oe_dmcp' (Disc-Mobility-Corner-Pattern) generasi terakhir.. lumayan kuat.. :)

GeneThello went SourceForge

Rekan-rekan semua..

Kini GeneThello telah diupload di situs open source SourceForge.net. Silakan teman-teman yang tertarik bergabung dengan GeneThello untuk posisi-posisi berikut.. :)

1. Developer

Untuk berperan serta dalam pengembangan GeneThello, silakan download source code-nya dari repositori subversion di SourceForge berikut:

https://genethello.svn.sourceforge.net/svnroot/genethello

Silakan gunakan IDE Netbeans untuk pengembangan, karena saya menggunakan itu. Untuk petunjuk download kode GeneThello dengan subversion, silakan lihat situs di bawah..

http://sourceforge.net/projects/genethello/develop

2. Evolver

Evolver adalah program untuk melakukan evolusi terhadap populasi othello di server. Anda dapat berkontribusi untuk membantu mempercepat proses evolusi dengan menjalankan program evolver di komputer anda. Program ini akan otomatis menyimpan hasil evolusi di server dan digabung dengan hasil evolusi dari evolver lain. Dengan cara distributed genetic algorithm seperti ini, di mana evolver dapat dilakukan secara terpisah-pisah di banyak komputer klien kemudian digabungkan di server, maka proses evolusi diharapkan dapat berjalan lebih cepat.

Silakan download binary code-nya dari situs sourceforge berikut:

https://sourceforge.net/projects/genethello/

Selanjutnya anda tinggal menginstallnya, kemudian jalankan perintah berikut dari installation directory..

java -cp Genethello.jar net.sf.genethello.ga.Main (ver 0.2 below)
java -cp Genethello.jar net.sf.genethello.ga.Evolver (ver 0.3 above)

Program evolver ini memerlukan waktu cukup lama untuk menyelesaikan satu kali turnamen, sekitar 6 jam di laptop intel core 2 duo saya. Tetapi program ini saya desain untuk tidak banyak memakan resource CPU, sehingga anda dapat menjalankan program ini di background dengan nyaman tanpa mengganggu pekerjaan lain.. :)

Kalau anda ingin menggunakan full CPU power untuk evolver, gunakan perintah berikut..

java -cp Genethello.jar net.sf.genethello.ga.Main --nosleep (ver 0.2 below)
java -cp Genethello.jar net.sf.genethello.ga.Evolver --nosleep (ver 0.3 above)

3. Tester

Untuk menguji seberapa kuat GeneThello dapat bermain, silakan download binary code yang sama seperti di Evolver, kemudian jalankan perintah berikut dari installation directory..

java. -jar Genethello.jar

Ini adalah program GUI yang dapat digunakan untuk bermain othello melawan pemain-pemain terkuat hasil evolusi sejauh ini. Program ini memerlukan koneksi network untuk mendownload informasi pemain dari server.

4. Just for fun

Untuk rekan-rekan yang ingin mencoba-coba dulu kekuatan GeneThello, dapat coba melawan applet berikut.. :)

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

[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.. :)

Kembara 1 (oe_fmc): generasi 436 vs generasi 1

Rekan-rekan semua..

Selanjutnya kita akan mempertandingkan generasi 436 yang memegang keping hitam, melawan generasi 1 yang memegang keping putih. Karena secara inheren keping putih diuntungkan dalam permainan othello, kita ingin melihat apakah generasi 436 dapat kembali menang melawan generasi 1.

Anda dapat mengulangi permainan ini menggunakan GeneThello Applet, dan melakukan setting seperti berikut:

Edit -> Black -> Machine
Edit -> Black -> Player -> oe_fmc_436_18:45:5:2:8:8:4:9:1:2:4
Edit -> White -> Machine
Edit -> White -> Player -> oe_fmc_1_14:49:3:2:2:3:3:9:1:10:3
File -> New

Informasi masing-masing pemain adalah sebagai berikut:

Hitam
Kromosom: 18:45:5:2:8:8:4:9:1:2:4
Life: 436 ~ 437
Win: 2136
Lose: 2822
Draw: 46
Elo: 1531

Putih
Kromosom: 14:49:3:2:2:3:3:9:1:10:3
Life: 1 ~ 12
Win: 17563
Lose: 14786
Draw: 329
Elo: 1781

Permainan awal ditunjukkan seperti pada gambar di bawah. Terlihat kedua pemain mengikuti pembukan Diagonal Opening -> Raccoon Dog.



Memasuki permainan tengah, putih unggul dan menguasai tepi atas, sementara hitam mulai terdesak dan kehabisan jalan. Sehingga terlihat hitam menyerah di sudut kiri atas dan terpaksa mengambil posisi berbahaya x-square di b2, dan c-square di a2.



Menjelang permainan akhir, keadaan terlihat membaik untuk hitam. Walaupun putih menguasai sudut kiri atas dan tepi kiri, tetapi ia akan kehilangan sudut kanan atas, serta tepi atas dan kanan kedua-duanya. Pengorbanan hitam dengan b2 di permainan tengah, tampak membuahkan hasil gemilang di sini.



Akhirnya hitam memenangkan pertandingan dengan 44-20. Hitam menguasai tiga sudut kanan atas, kanan bawah dan kiri bawah, serta tiga tepi atas, kanan dan bawah. Sementara putih hanya diberi satu sudut kiri atas dan satu tepi kiri.



Dengan hasil ini, terlihat bahwa generasi 436 dapat mengalahkan generasi 1 secara konsisten baik bermain putih maupun hitam. Dan hal ini sesuai dengan harapan kita.

Dan proses evolusi kromosom tipe oe_fmc ini suatu saat akan dilanjutkan kembali untuk mencari kromosom terbaik, yaitu hingga tercapai kondisi konvergen, di mana kromosom terbaik di setiap generasi tidak pernah lagi berubah dari generasi ke generasi.

Pengembaraan pun kembali berlanjut..


Transkrip permainan

1. d3 - c3
2. c4 - e3
3. e2 - c2
4. d2 - c1
5. d1 - e1
6. f2 - f3
7. f1 - g1
8. f4 - g3
9. h3 - g4
10. h4 - b5
11. f5 - c5
12. b2 - b3
13. a2 - a4
14. a6 - a5
15. b6 - h5
16. h6 - b4
17. g5 - a1
18. a3 - g2
19. c6 - h2
20. b1 - d6
21. f6 - e6
22. h1 - a7
23. d7 - c7
24. e7 - d8
25. e8 - f8
26. f7 - g8
27. b8 - g6
28. h7 - b7
29. a8 - c8
30. h8 - pass
31. g7 - pass

Kembara 1 (oe_fmc): generasi 1 vs generasi 436

Dear rekan-rekan,

Evolusi program dengan kromosom tipe oe_fmc telah berlangsung sampai generasi 437. Setiap generasi rata-rata memerlukan waktu 20 menit, sehingga total waktu yang dibutuhkan sampai generasi 437 adalah sekitar 6 hari.

Sekarang kita akan mencoba mengadu antara program terbaik di generasi awal dengan program terbaik di generasi akhir. Secara teoritis, generasi-generasi akhir seharusnya lebih baik dari generasi-generasi awal, sehingga kita berharap generasi 436 akan menang melawan generasi 1.

Hitam: generasi 1, Putih: generasi 436

Dalam permainan othello, pemain putih cenderung diuntungkan karena ia mempunyai kesempatan untuk melangkah terakhir, yang berarti ia mempunyai kesempatan untuk terakhir kali membalik keping-keping lawan. Dengan demikian, kedua pemain yang sama kuat cenderung akan dimenangkan oleh putih, atau minimal draw.

Anda dapat mengulangi permainan ini menggunakan GeneThello Applet, dan melakukan setting seperti berikut:

Edit -> Black -> Machine
Edit -> Black -> Player -> oe_fmc_1_14:49:3:2:2:3:3:9:1:10:3
Edit -> White -> Machine
Edit -> White -> Player -> oe_fmc_436_18:45:5:2:8:8:4:9:1:2:4
File -> New

Informasi masing-masing pemain adalah sebagai berikut:

Hitam
Kromosom: 14:49:3:2:2:3:3:9:1:10:3
Life: 1 ~ 12
Win: 17563
Lose: 14786
Draw: 329
Elo: 1781

Putih
Kromosom: 18:45:5:2:8:8:4:9:1:2:4
Life: 436 ~ 437
Win: 2136
Lose: 2822
Draw: 46
Elo: 1531

Data di atas adalah data yang dikumpulkan dari masa peng-evolusian program sejak generasi 1 sampai generasi 437. Dari data tersebut dapat kita ketahui antara lain, pemain hitam lahir pada generasi 1 dan mati pada generasi 12, dan Elo rating terakhirnya adalah 1781. Sedangkan pemain putih lahir pada generasi 436 dan masih bertahan hingga generasi 437, dan Elo rating terakhirnya adalah 1531.

Kedalaman berpikir untuk masing-masing pemain diset sama yaitu 9 langkah ke depan. Dengan ini diharapkan kedua pemain dapat memikirkan dengan baik langkahnya masing-masing tetapi dalam waktu yang tidak terlalu lama.

Permainan awal dapat dilihat seperti pada gambar berikut. Walaupun kedua pemain tidak menggunakan opening book, tetapi pembukaan kedua pemain tampak mengikuti Diagonal Opening -> Heath / Tobidashi.



Selanjutnya memasuki permainan tengah.. kedua pemain tampak bermain tepi, di mana empat kotak tengah di tepi ditempati terlebih dulu. Posisi ini dikenal sebagai posisi yang cukup kuat untuk pemain level pemula. Hitam tampak mulai terdesak, sehingga terpaksa mengambil posisi x-square g2 yang berbahaya, dan menyerahkan sudut kanan atas kepada putih.



Menjelang permainan akhir.. kemenangan putih terlihat semakin nyata. Sudut kanan atas sudah dikuasai demikian juga tepi atas dan kanan.. bahkan hitam juga sudah menyerah di sudut kiri atas dengan menempati kotak x-square b2. Selanjutnya putih tinggal mempertahankan kemenangan ini sampai permainan berakhir.



Akhirnya putih memenangkan pertandingan dengan 40 - 24, dan menguasai tiga sudut dan tiga tepi, sementara hitam hanya mendapatkan satu sudut dan satu tepi.



Dengan demikian, memainkan keping putih generasi 436 berhasil menang melawan generasi 1. Tetapi boleh jadi hal ini karena generasi 436 memainkan keping putih, yang secara inheren memang memiliki keuntungan dibanding keping hitam.

Bagaimanakah bila warna kedua pemain dibalik? Masihkah generasi 436 unggul dibanding generasi 1?

Mari kita ikuti terus pengembaraan ini..


Transkrip permainan

1. d3 - c3
2. c4 - e3
3. d2 - c2
4. c1 - b4
5. b3 - e1
6. e2 - a3
7. a4 - d1
8. f1 - a5
9. b5 - f2
10. g2 - a6
11. f4 - f3
12. g3 - c5
13. d6 - g4
14. f5 - h3
15. h2 - h1
16. g1 - b1
17. h4 - h5
18. b6 - a7
19. b2 - c6
20. g5 - h6
21. g6 - d7
22. d8 - e7
23. f6 - f8
24. c7 - e6
25. f7 - c8
26. b8 - g8
27. g7 - e8
28. h8 - h7
29. a2 - a1
30. b7 - a8

GeneThello Applet

Anda dapat mencoba GeneThello, dan juga kromosom-kromosom yang telah dicapai oleh algoritma genetika, dengan applet ini.

Untuk menjalankan applet ini anda perlu mengaktifkan Java applet di browser anda, dan menginstall Java plugin terbaru yang dapat didownload melalui:

http://www.java.com/en/download/manual.jsp

File size dari applet ini adalah sekitar 142.7 kB, dan memerlukan waktu sekitar 20 detik untuk loadingnya, menggunakan modem berkecepatan 56 kbps.


Cara penggunaan

Memilih pemain:

Edit -> Black/White -> Man/Machine

Pilih Man untuk pemain manusia atau Machine untuk pemain komputer.

Memilih (kromosom) pemain untuk Machine:

Edit -> Black/White -> Player -> ...

(Kromosom) pemain dituliskan dalam format TYPE_BIRTH_CHROMOSOME, yang menunjukkan tipe kromosom, pada generasi ke berapa kromosom itu lahir, dan nilai kromosom itu sendiri. Misalnya kromosom oe_fmc_1_14:49:3:2:2:3:3:9:1:10:3 berarti, pertama-tama tipenya adalah oe_fmc, yaitu mempunyai dua batas langkah, o yang membatasi opening-game dan mid-game, dan e yang membatasi mid-game dan end-game, serta mempertimbangkan tiga fitur yaitu: flips (jumlah keping yang dibalik), mobility (jumlah langkah lawan), dan corners (selisih jumlah sudut); kedua dia dilahirkan pada generasi pertama; terakhir nilai kromosomnya adalah 14:49:3:2:2:3:3:9:1:10:3.

Memilih kedalaman berpikir untuk Machine:

Edit -> Black/White -> Depth -> 1 ~ 15

Semakin dalam GeneThello diijinkan untuk berpikir, langkahnya akan semakin bagus tetapi waktunya juga semakin lama. Kedalaman 1 adalah yang paling cepat tetapi langkahnya tidak dipikirkan dengan baik. Kedalaman 15 menjadikan GeneThello berpikir sangat lama dalam melangkah dan tidak menyenangkan untuk lawan bermain. Kedalaman 9 adalah yang paling pas, langkahnya dipikirkan dengan cukup baik dan waktunya pun tidak terlalu lama.

Memulai permainan:

File -> New

Melihat transkrip permainan:

File -> Transcript


Applet

Kembara satu: Flips, Mobility dan Corners

Dalam pengembaraan yang pertama ini, kita menggunakan tiga buah fitur di dalam fungsi evaluasi, yaitu: Flips (jumlah keping yang dibalik), Mobility (jumlah langkah lawan) dan Corners (selisih jumlah sudut), dengan bobot masing-masing wf, wm dan wc.

Selain itu, rentang permainan othello dibagi ke dalam tiga babak, yaitu opening-game (permainan awal), mid-game (permainan tengah), dan end-game (permainan akhir). Opening-game dan mid-game dibatasi pada langkah ke-o, sementara mid-game dan end-game dibatasi pada langkah ke-e, di mana nilai optimal kedua batas inipun belum diketahui.

Pada masing-masing babak ini, bobot optimal untuk setiap fitur mungkin saja berbeda, sehingga fungsi evaluasi akan memiliki sembilan bobot, masing-masing tiga untuk setiap babak, yaitu wf₁, wm₁, wc₁, wf₂, wm₂, wc₂, wf₃, wm₃, wc₃.

Dan fungsi evaluasi lengkap untuk tipe kromosom ini dapat ditulis sebagai berikut:

int eval() {
   if (step <= o) 
      return wf1 * Flips + wm1 * Mobility + wc1 * Corners
   else if (o < step <= e) 
      return wf2 * Flips + wm2 * Mobility + wc2 * Corners
   else  
      return wf3 * Flips + wm3 * Mobility + wc3 * Corners
}

Dengan demikian, jumlah variabel yang perlu di-optimasi ada 11 buah, yaitu 2 batas o dan e, serta 9 bobot wf₁, wm₁, wc₁, wf₂, wm₂, wc₂, wf₃, wm₃, wc₃. Sehingga kromosom untuk individu pada program ini, disebut mempunyai tipe oe_fmc dan akan berbentuk:

o:e:wf₁:wm₁:wc₁:wf₂:wm₂:wc₂:wf₃:wm₃:wc₃

Setiap variabel (batas dan bobot) ini mempunyai tipe data integer yang mengambil tempat di memori sebesar 32 bit. Karena jumlahnya ada 11, maka total kromosom ini akan berukuran sebesar 11x32 = 352 bit. Menurut paper [1], jumlah populasi optimal untuk setiap generasi adalah sama dengan panjang kromosom di dalam bit. Maka kita pilih jumlah populasi untuk setiap generasi di dalam sistem algoritma genetika ini sebanyak 352 individu.

Untuk masing-masing variabel ini kita juga memberikan batas rentang nilai yang mungkin diambil, yaitu:

o: 1 ~ 20
e: 41 ~ 60
w: 0 ~ 10 (bobot untuk semua fitur)

Selanjutnya yang kita lakukan adalah:

1. Membangkitkan 352 individu (progam) dengan kromosom acak untuk membuat populasi generasi pertama.
2. Mempertandingkan setiap program dengan setiap program yang lain di dalam sebuah turnamen, masing-masing dua kali bergiliran hitam dan putih.
3. Memberi nilai ELO rating untuk setiap program dan mengupdatenya setiap selesai pertandingan.
4. Di akhir setiap turnamen, melakukan perkawinan silang (crossover) di antara 35% populasi (dipilih program-program ber-ELO rating tinggi), dan mutasi pada seluruh populasi dengan kemungkinan 8.3%.
5. Memilih 352 program yang merupakan keturunan hasil kawin silang, hasil mutasi dan program induk ber-ELO rating tinggi untuk dijadikan sebagai populasi baru pada generasi berikutnya.
6. Kembali ke nomor 2.

Demikian program-program othello ini akan di-evolusikan dari generasi ke generasi hingga tercapainya kriteria penghentian, yaitu dalam hal ini adalah, tidak ada lagi perubahan kromosom pada program terbaik dari setiap generasi, dalam bahasa komputer disebut telah konvergen.

Dan kita dapat berharap, bahwa program terbaik dari generasi terakhir ini adalah program othello paling kuat yang kita dapatkan untuk jenis kromosom tersebut.

Referensi:

[1] J.T. Alander, On optimal population size of genetic algorithms, CompEuro '92, 'Computer Systems and SoftwareEngineering', Proc. 04/06/1992


.

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

.