Thread by @pacmannai

Kenapa bot bisa main catur
.
.
.
A thread

Hola semuanya! Pasti kalian udah denger dong tentang partai catur yang sangat fenomenal minggu lalu yang memecahkan rekor penonton catur tertinggi di dunia!

Sekarang mimin mau bahas tentang bot catur yang kemarin sempat jadi perbincangan nih, tapi disini mimin engga ngejudge yahh 🤣

Kalau kalian sendiri pernah ngebayangin ga gimana cara kerja bot catur? Kenapa mereka bisa membedakan mana langkah yang bagus atau jelek sampai bisa mengalahkan pemain profesional?

Yuk langsung deh kita bahas biar engga ada yang bingung lagi

Singkatnya itu pertama pasti kita harus mengajari mesin terlebih dulu tentang dasar-dasar main catur itu sendiri

Misalnya terdapat bidang berukuran 8x8, diisi oleh 16 buah catur pada kedua ujung sisinya dengan buah sebagai berikut,

♔ — 1 raja
♕ — 1 menteri
♖ — 2 benteng
♗— 2 gajah
♘ — 2 kuda
♙ — 8 pion

Bidang permainan berukuran 8x8 ini dapat diinterpretasikan sebagai matriks 8x8 supaya mesin dapat memahaminya

Juga kita harus memberitahu langkah-langkah dari setiap buah, misalnya kuda hanya bisa melangkah bentuk L, gajah hanya bisa diagonal dan seterusnya

Langkah-langkah khusus seperti en passant, promosi pion, dll bisa juga diajarkan pada mesin tetapi supaya lebih simpel memahaminya kita tidak gunakan terlebih dahulu yah

Lewat instruksi-instruksi sederhana ini sebenarnya kita sudah bisa membuat bot catur loh! Hanya saja langkah yang dimainkan bot adalah masih langkah acak saja. Ilustrasinya seperti ini (hitam adalah bot)

Gimana? Masih random banget kan ya langkah dari bot kita 😂

Kalau tadi langkah yang dijalankan bot adalah langkah acak, sekarang bagaimana supaya bot bisa mengetahui mana langkah yang efektif?

Caranya adalah dengan menetapkan nilai pada setiap buah catur saat dimakan dan termakan

Kalau memakan pion nilai akan ditambah 10, dan jika pion kita dimakan nilai kita akan dikurang 10 dan seterusnya

Raja disini memiliki poin terbesar agar kita bisa memberi tahu mesin secara implisit bahwa sebenarnya objektif permainan ini adalah untuk “membunuh” sang raja

Jadi nantinya langkah yang akan diambil oleh bot adalah langkah yang akan menghasilkan nilai terbesar. Tapi kalau semua langkah yang mungkin menghasilkan nilai yang sama, maka tetap akan dijalankan langkah random

Nah dengan begini bot catur kita sudah lumayan memahami permainan lho~ Ini hasilnya

Tapi terlihat jelas ya kalau bot yang kita buat ini masih belum baik, karena langkah yang diambil sangat terburu-buru. Disini bot akan selalu memilih memakan perwira lawan saat diancam daripada kabur karena memakan perwira memberikan nilai lebih tinggi daripada kabur

Padahal bisa saja setelah memakan perwira, pertahanan bisa menjadi sangat terbuka dan dapat diancam lebih parah lagi seperti pada contoh sebelumnya

Nah untuk mengatasi hal ini, kita dapat menggunakan algoritma minimax supaya dapat diketahui langkah-langkah apa saja yang memberikan nilai terbaik yaitu memaksimalkan poin kita dan meminimalkan poin lawan

Jadi dalam algoritma ini, akan dibentuk beberapa tree berisikan semua kemungkinan langkah. Maximizer (pemain) akan selalu memilih nilai terbesar dan minimizer (lawan) akan selalu memilih nilai terkecil supaya meminimalkan nilai si maximizer

Lewat skema ini, langkah akhir yang diambil nantinya adalah langkah yang menghasilkan nilai terbesar bagi si maximizer

Misalkan pada kasus ini, sebagai putih langkah yang dapat dimainkan adalah gajah memakan kuda atau gajah. Memakan kuda akan mendapatkan nilai 30 dan memakan gajah akan mendapatkan nilai 30 juga.

Jika gajah putih memakan kuda maka minimizer akan mengambil langkah yang meminimalkan poin putih, yaitu dengan memakan gajah putih dengan benteng

Tetapi jika gajah putih memakan gajah maka minimizer akan mengambil langkah minimal yaitu hanya menggerakkan perwiranya tanpa mengancam gajah putih. (jika hasil poin sama maka diambil langkah random)

Disini jika putih memakan kuda, hasil akhirnya adalah 0 karena akan dimakan kembali oleh benteng, tetapi jika memakan gajah hasil akhirnya adalah 30 karena tidak dapat dimakan kembali

Berarti disini langkah terbaik putih adalah dengan memakan gajah hitam karena akan memberikan nilai 30

Langkah ini akan diulangi pada setiap giliran supaya didapatkan langkah yang paling baik. Dan semakin banyak depth level (ply) yang terbentuk akan semakin baik langkah yang dipilih karena sudah mempertimbangkan beberapa langkah setelahnya

Dengan menggunakan minimax depth level 2 pun bot kita sudah mampu mempelajari teknik dasar permainan catur deh~ Ini hasilnya 👇🏼👇🏼👇🏼

Selain itu, kita juga akan melakukan optimisasi algoritma minimax menggunakan algoritma alpha-beta pruning

Jadi idenya adalah kita mengeliminasi semua cabang yang udah engga mungkin dipilih maximizer dan minimizer supaya tree yang kita buat bisa lebih dalam lagi dan tidak perlu mengevaluasi semua langkah yang mungkin

Alpha-beta pruning ini engga mengubah output dari minimax ya tapi hanya membuat proses penemuan langkah terbaiknya menjadi lebih cepat saja

Kalau untuk kasus tadi, alpha-beta pruning akan menyeleksi cabang-cabang yang udah ga mungkin dipilih oleh minimizer karena nilainya lebih besar, yaitu pilihan engga memakan gajah putih ketika gajah putih makan kuda

Terakhir untuk melengkapi sistem kerja bot kita, kita dapat menambahkan fungsi evaluasi lagi pada tiap petak bidang catur kita. Misalnya jika kuda berada pada petak tengah, maka nilai valuasinya akan meningkat

Jika aturan ini diterapkan, maka bot kita akan mempertimbangkan prinsip-prinsip dasar catur seperti penguasaan petak tengah terlebih dahulu yang dapat mengubah momentum permainan. Jadi lebih bagus lagi deh 😎

Tadaaa~ bot catur sederhana kita sudah jadi deh! Sekarang bot catur kita sudah cukup oke dalam bermain! Berikut ilustrasi saat bot dijalankan dengan alpha-beta pruning depth level 3

Tapi tetap mimin engga menyarankan kalian bermain catur pakai bot yah!! Kalau pake bot dan dibanned mimin engga tanggung jawab hehehe

FYI pasti setiap penyedia layanan permainan catur memiliki sistem keamanannya masing-masing ya. Kalau langkah kalian sama terus dengan langkah yang diambil bot, maka bisa saja kalian akan menjadi suspect curang

Seperti yang kita lihat tadi, langkah yang diambil bot merupakan hasil evaluasi semua langkah yang mungkin kan, jadi sangat jarang manusia bisa melakukannya apalagi pada setiap langkah secara konsisten.

Jadi bot ini sebagai teman latihan dan just for fun saja ya, tidak boleh digunakan saat bertanding 😂

Kalau kamu penasaran sama algoritma-algoritma seru lainnya, kamu bisa belajar AI di Pacmann.AI lho! Di non degree program Data Scientist, kamu bakal belajar A - Z tentang apa aja yang dibutuhkan buat jadi seorang Data Scientist.

Pendaftaran batch 3 udah resmi dibuka, jangan sampai kelewatan yaa! Cek kurikulumnya di bit.ly/brosurpacmannai atau langsung daftarin diri kamu di bit.ly/PendaftaranNon… See youu! 🤩👋🏼

Referensi:
freecodecamp.org/news/simple-ch…
medium.com/the-innovation….
jurnal.ugm.ac.id/teknosains/art…