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


.