Kamis, 16 Juni 2011

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 moveslegal 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 B1B memilih B2B memilih B3
A memilih A1+3−2+2
A memilih A2−10+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.

Sabtu, 11 Juni 2011

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.

Jumat, 10 Juni 2011

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..



Rabu, 01 Juni 2011

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

Rabu, 18 Mei 2011

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

Jumat, 29 April 2011

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

Senin, 28 Maret 2011

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

Kamis, 17 Maret 2011

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