Pemrograman Komputer Catur – pendahuluan

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: