Chess Bot, Bagaimana Komputer Bermain Catur

Siapa yang tidak kenal dengan Pak Dadang Subur, yang secara mengejutkan mengalahkan Levy Rozman dalam permainan catur online melalui Chess.com awal Maret lalu. Beritanya ramai diperbincangkan mengingat Levy memiliki gelar International Master sedangkan Pak Dadang bahkan tidak begitu aktif dalam percaturan Indonesia. Levy dan pihak Chess.com curiga Pak Dadang bermain curang semisal menggunakan chess bot (bot catur) dalam permainannya sehingga bisa mengalahkan Levy saat itu. Pak Dadang pun mengelak tuduhan tersebut. Kita tidak akan membahas siapa yang benar dan siapa yang salah, di artikel ini saya hanya akan sharing singkat tentang apa itu chess bot yang disebut-sebut Levy dan bagaimana sih cara kerjanya.

Kita mulai dengan istilah State

Sebuah state menyimpan informasi apa yang terjadi pada suatu permainan dalam satu waktu. Dalam permainan catur, sebuah state bisa berupa posisi bidak-bidak pada papan pada suatu waktu. Bayangkan ada orang bermain catur, lalu kita foto papan catur setiap pemain menggerakan bidaknya, maka foto-foto itu disebut dengan state. 

3 state terakhir sebelum akhirnya Pak Dadang (hitam) menyerah pada pertandingan pertama melawan Irene Sukandar (putih)

Dari foto-foto itu kita tahu bahwa state ada beragam. Setiap perubahan di papan merupakan state yang berbeda. Dalam permainan catur, ada banyak sekali state yang bisa dihasilkan. Di beberapa sumber, banyak kemungkinan state dalam catur tertulis hingga 10⁴⁶ state. Selain itu, kita juga bisa perhatikan bahwa ketika pemain melakukan suatu aksi, misalnya menggerakkan bentengnya, maka terjadi perpindahan dari satu state ke state yang lain. Contohnya pada ilustrasi di atas. Dengan memahami apa itu state, permainan catur kini bisa dilihat sebagai perpindahan-perpindahan state dari initial state (posisi awal) dan berakhir pada final state, ketika salah seorang pemain kalah. 

Bagaimana bot dalam game seperti catur bekerja?

Pada 1997, tim IBM membuat bot catur, Deep Blue, yang berhasil mengalahkan Grand Master (Juara Dunia) Gary Kasparov. Prinsip kerjanya hampir sama dengan bot saat ini.

Secara ringkas, yang dilakukan bot-bot pada setiap gilirannya:

1. Bot akan mencari kemungkinan-kemungkinan state yang akan terjadi
2. Menilai setiap state mana yang paling baik
3. memilih aksi yang membawanya ke state terbaik tersebut.

Menilai apakah sebuah state itu baik adalah suatu tantangan. Pemain catur saja bisa memiliki cara yang berbeda untuk melihat apakah suatu kondisi papan menguntungkan atau tidak. Seseorang pemula mungkin hanya melihat kondisi papan saat ini, menghitung jumlah pion yang telah dia makan. Namun, seorang profesional dapat melihat jauh ke depan. Bisa jadi terlihat kalah saat ini tapi sebenarnya dia bersiap menuju state yang jauh lebih baik. Bot biasanya menilai baik buruknya suatu state berdasarkan teori catur yang didesain oleh pembuatnya, atau bisa juga mengestimasi menggunakan machine learning.

Proses mencari semua kemungkinan sekaligus menilai state yang dapat terjadi dalam 1 langkah ke depan

Melihat kemungkinan state yang akan terjadi di masa depan juga bukan hal mudah. Setiap aksi bot dan aksi lawan, mempengaruhi apa yang terjadi nantinya. Ada banyak kemungkinan yang bisa muncul membuat proses pengecekan state akan memakan waktu komputasi yang sangat lama tergantung seberapa jauh dia ingin melihat (melihat berapa langkah ke depan). Sampai saat ini tidak mungkin suatu bot dengan kecanggihan komputasinya dapat melihat semua state yang dapat terjadi, dari state pertama hingga final state. Karenanya, bot akan membatasi seberapa jauh mengecek kemungkinan state. Semakin jauh bot mampu melihat kemungkinan state yang muncul di depan, bot akan semakin kuat.

Perbedaan yang mencolok antara algoritme-algoritme yang ada saat ini kebanyakan pada 2 hal tersebut:

• bagaimana cara mereka menilai suatu state, dan
• bagaimana mereka melakukan proses pencarian state yang akan terjadi setelahnya.

Kita ambil contoh algoritme chess bot Giraffe yang diusulkan tahun 2015. Giraffe menggunakan deep learning untuk mengestimasi suatu state bagus atau tidak, lalu mengombinasikannya dengan algoritme reinforcement learning, TD-Leaf, untuk menentukan aksi selanjutnya. Giraffe menggunakan TD-Leaf dengan pencarian state hingga 12 langkah ke depan.

Bot pada permainan lain

Keunggulan bot melawan manusia dalam game tidak hanya terjadi pada catur. Di tahun 2016, AlphaGo mengalahkan Lee Sedol dalam permainan go yang dianggap jauh lebih kompleks dibanding catur. Pada permainan poker, DeepStack secara fenomenal juga telah berhasil mengalahkan 11 pemain professional di tahun yang sama. Poker memiliki sifat yang berbeda dengan catur dan go, yakni hidden information. Bot tidak tahu kartu apa yang akan keluar dan tidak tahu kartu apa yang dimiliki lawannya. 

Riset kecerdasan buatan (AI) bot pada game berkembang sangat pesat. Bukan karena keseruan game-nya, tapi kemampuan AI untuk berinteraksi dan beradaptasi menghadapi lingkungannya merupakan hal yang sangat penting. Kemampuan tersebut merupakan salah satu kunci untuk lahirnya AGI yang dicita-citakan banyak researcher AI. Apa itu AGI? Artificial General Intelligence, sebuah AI dengan kecerdasan super, yah seperti yang diimajinasikan di film-film. Semoga bermanfaat!

Referensi:

• https://www.chessprogramming.org/Chess
• https://arxiv.org/abs/1509.01549
• https://en.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol
• https://www.deepstack.ai/

Penulis: Rian Adam Rajagede