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

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

.