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

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


.