Pemrograman Komputer Catur – Anatomi

June 19, 2010

Apa sih anatomi dari sebuah program catur? Well, pada dasarnya sebuah program catur terdiri dari empat bagian utama :

  1. Struktur Data. Yang dimaksud struktur data disini adalah bagaimana cara merepresentasikan suatu posisi papan catur dan susunan buah-buahnya di dalam program. Cara yang paling jelas dan paling sederhana tentu dengan menggunakan array dua dimensi 8×8, tapi cara ini mempunyai banyak kekurangan antara lain perfomance/kecepatan yang lambat. Baca bagian sebelumnya, perfomance adalah hal yang vital karena perfomance yang lebih cepat memungkinkan pencarian yang lebih dalam. Teknik yang lebih advanced misalnya menggunakan bitboard yang saya gunakan di program catur saya Petir. Bitboard ini akan dibahas lebih mendalam di bagian berikutnya.
  2. Move Generator. Move Generator adalah suatu fungsi untuk mendapatkan semua langkah yang mungkin dilakukan dalam suatu posisi papan. Tentu dengan mengikuti semua aturan catur misalnya rokade, en-passant (bidak potong), dll
  3. Fungsi evaluasi. Fungsi evaluasi digunakan untuk meng-evaluasi suatu posisi papan seberapa bagus atau seberapa buruk dan memberi nilai yang kurang lebih sesuai. Hal yang harus ada di fungsi evaluasi ini tentu saja nilai materi, misalnya mentri bernilai 9, kuda bernilai 3, dst. Selain itu juga harus mempertimbangkan aspek-aspek lain seperti keselamatan raja, struktur pion, mobility, dll. Fungsi evaluasi ini akan dibahas lebih detail di bagian lain
  4. Algoritma game playing, yaitu bagaimana algoritma yang memungkinkan komputer untuk mencari langkah yang dianggap terbaik berdasarkan fungsi evaluasi. Pada dasarnya algoritma ini meniru cara berpikir manusia dalam bermain catur : Jika saya melangkah ke sini maka lawan akan membalas dengan langkah itu trus saya membalas dengan langkah lain, dst. Bagian ini juga akan dibahas lebih dalam

Bagian yang bersifat opsional adalah Graphical User Interface (GUI) yang memungkinkan user berinteraksi dengan program catur yang dibuat. Kenapa opsional? Karena anda tidak perlu membuat GUI sendiri, tapi bisa menggunakan GUI freeware yang bisa didownload gratis di internet seperti misalnya Winboard dan lain-lain.

Advertisements

Pemrograman Komputer Catur – pendahuluan

June 17, 2010

Cara paling ideal bagi komputer untuk bermain catur tentu saja dengan menggunakan algoritma search untuk menelusuri semua kemungkinan langkah sampai mencapai goal state (keadaan final), yang dalam konteks game playing, adalah kondisi dimana salah satu pihak menang atau seri. Untuk beberapa game dengan kemungkinan langkah yang terbatas seperti tic tac toe, hal ini sangat mungkin. Namun catur mempunyai kemungkinan rata-rata 30 langkah yang dapat dilakukan untuk tiap giliran, dan permainan dapat berlangsung sampai ratusan langkah. Bahkan dengan mesin yang paling canggih saat ini, sangatlah tidak mungkin bagi program catur untuk menelusuri semua kemungkinan langkah sampai mencapai goal state. Untuk mengatasi masalah itu, Shannon mengusulkan dua macam pendekatan, yaitu:

  • Dengan melakukan brute force, komputer melakukan search dengan menelusuri semua kemungkinan langkah sampai beberapa langkah ke depan (dikenal dengan sebutan ply) dan kemudian memanggil fungsi evaluasi pada leaf node untuk menentukan seberapa bagus posisi yang terjadi untuk dibandingkan dengan posisi lain agar bisa ditentukan mana yang terbaik. Fungsi evaluasi ini  disusun berdasarkan pengetahuan manusia mengenai catur, contoh paling gamblang adalah nilai material, dimana semakin banyak maka semakin bagus. Pendekatan semacam ini dikenal dengan Shannon Type A
  • Dengan meniru cara berpikir manusia yang hanya mempertimbangkan beberapa langkah yang dianggap terbaik pada setiap ply-nya. Dikenal dengan Shannon Type B.

Dewasa ini, pendekatan Type A lebih banyak dipakai, sedangkan pendekatan Type B praktis telah ditinggalkan, walaupun sekilas tampak lebih menjanjikan. Kesulitan yang dihadapi oleh Type B adalah tingkat kerumitan yang tinggi, sangatlah sulit bagi komputer untuk menentukan mana langkah yang bagus dan mana langkah yang kurang bagus.

Konsekuensi dari hanya melakukan search beberapa langkah ke depan adalah fungsi evaluasi yang digunakan tidak mungkin bisa 100% akurat, misal jika ada dua alternatif langkah A dan B, pada search dengan kedalaman 2 ply langkah A menghasilkan nilai 1000, sedangkan langkah B menghasilkan nilai 300. Jelas bahwa search akan memilih langkah A. Namun bisa jadi setelah search dengan kedalaman 6 ply, langkah A ternyata menghasilkan nilai –300 sedangkan langkah B menghasilkan nilai 5000, sehingga langkah B ternyata lebih baik dari langkah A. Karena ketidak-akuratan fungsi evaluasi ini, semakin dalam search dilakukan, cenderung memberikan hasil yang lebih baik. Pada umumnya, lama berpikir komputer dibatasi oleh waktu tertentu, yang berarti komputer harus mampu mencapai ply sebanyak mungkin dalam waktu terbatas yang diberikan.

Ken Thompson melakukan penelitian yang terkenal pada program yang dibuatnya yang bernama “Belle” untuk menentukan seberapa besar pengaruh penambahan satu ply akan meningkatkan kualitas permainan komputer. Hasil experimennya menyatakan bahwa Belle mendapatkan tambahan 200 poin elo (ukuran kekuatan seorang pecatur, semakin tinggi berarti semakin kuat) untuk setiap tambahan satu ply yang didapat. Hal itu berarti Belle yang bermain pada n ply mempunyai kemungkinan 75% mengalahkan Belle yang bermain pada n-1 ply. Peneliti lain kemudian melakukan penelitian yang sama dan selalu mendapatkan hasil yang mirip.

Hal ini kemudian menimbulkan masalah karena akan menimbukan konflik dengan jumlah knowledge yang digunakan pada evaluator. Semakin banyak knowledge maka akan mengurangi kecepatan yang pada akhirnya akan mengurangi ply yang berhasil dicapai, namun kualitas evaluator akan meningkat. Sedangkan sedikit knowledge akan mengurangi kualitas evaluator namun program akan mampu mencapai ply yang lebih dalam. Hans Berliner kemudian mengadakan penelitian pada program caturnya yang bernama Hitech. Berliner menyingkirkan sebagian besar knowledge dalam evaluator Hitech, menghasilkan program baru yang dinamakan Lotech yang lebih cepat sehingga mampu mencapai satu ply lebih dalam. Berliner kemudian mengadu Lotech dan Hitech dan mendapatkan hasil mengejutkan, Lotech secara konsisten mampu mengalahkan Hitech.


Pemrograman komputer catur

June 17, 2010

Mulai hari ini saya akan menulis artikel bersambung mengenai teknik-teknik dan algoritma pembuatan program catur dengan artificiall intelligence kelas dunia. So, stay tune!