Cara kerja mesin

Dua bagian: pencarian dan evaluasi

Mesin catur adalah dua program yang bekerja sama. Pencarian melihat ke depan: “kalau aku main ini, lawan bisa membalas itu, lalu aku main ini…”. Evaluasi melihat satu posisi saja, tanpa menggerakkan apa pun, dan memberinya satu angka: siapa yang lebih unggul, dan seberapa besar.

Keduanya saling membutuhkan. Makin dalam pencariannya, makin kecil pengaruh evaluasi yang lemah; makin baik evaluasinya, makin sedikit kedalaman yang dibutuhkan. Karena evaluasi dijalankan di setiap ujung setiap jalur — ratusan ribu kali per detik — ia harus bagus sekaligus sangat cepat.

Pencarian

Mesin berpikir satu tingkat lebih dalam setiap kali (iterative deepening), sehingga ia selalu punya langkah siap saat waktunya habis. Melihat setiap langkah sampai setiap kedalaman akan memakan waktu tak berujung, jadi sebagian besar kerjanya justru untuk tidak melihat langkah yang tidak mungkin berpengaruh:

• Alpha-beta. Begitu satu balasan mematahkan sebuah langkah, mesin berhenti memeriksa langkah itu. Dengan urutan langkah yang baik, cara ini melewati sebagian besar pohon tanpa mengubah hasilnya.
• Langkah terbaik lebih dulu. Langkah yang terbaik saat posisi ini terakhir kali dilihat, makan buah yang berharga, dan langkah tenang yang berhasil di posisi serupa (killer moves dan tabel riwayat) dicoba lebih dulu.
• Ingatan. Tabel transposisi mengingat posisi yang sudah dicari, karena posisi yang sama sering dicapai lewat urutan langkah yang berbeda.
• Jalan pintas yang terukur. Langkah belakangan yang kurang menjanjikan dicari dengan kedalaman lebih dangkal (late move reductions); posisi yang begitu bagus sehingga melewatkan giliran pun tetap mempertahankan keunggulan dipotong lebih awal (null move pruning); skak dicari satu langkah lebih dalam.
• Hanya posisi yang tenang. Pencarian tidak pernah berhenti di tengah pertukaran: di ujung setiap jalur ia terus mengikuti makan-memakan sampai posisinya tenang (quiescence search), sehingga evaluasi tidak pernah melihat ratu yang sebentar lagi dimakan balik.
• Beberapa inti. Mesin bisa mencari dengan beberapa thread sekaligus, semuanya berbagi satu tabel transposisi (Lazy SMP).

Papan

Di dalam mesin, papan adalah sekumpulan bilangan 64-bit, satu bit per petak (bitboard): satu bilangan untuk kuda putih, satu untuk benteng hitam, dan seterusnya. Langkah dan serangan menjadi beberapa operasi bit saja, dan buah jarak jauh mencari serangannya di tabel yang sudah dihitung sebelumnya (magic bitboard). Buah gabungan varian ini — Maharaja, Uskup Agung, dan Kanselir — bergerak sebagai gabungan komponennya, sehingga memakai ulang tabel yang sama.

Menilai posisi secara manual

Evaluasi asli mesin ini adalah daftar patokan praktis catur, masing-masing dengan bobotnya: material, letak setiap buah, berapa petak yang dikuasainya, bidak bebas dan bidak terisolasi, pasangan gajah, benteng di lajur terbuka, perisai bidak di depan raja. Bobotnya bergeser perlahan dari pembukaan ke akhir permainan.

Evaluasi ini berfungsi, dan dialah yang bermain di aplikasi saat ini, tetapi ia hanya tahu apa yang terpikir oleh seseorang untuk dituliskan. Selain itu, semuanya tak terlihat olehnya.

Jaringan saraf

Jaringan saraf hanya menggantikan evaluasi. Pencarian tetap persis seperti sebelumnya — jaringan tidak memilih langkah, ia menjawab satu pertanyaan, berkali-kali per detik: seberapa bagus posisi ini?

• Inputnya adalah papan itu sendiri. Ada 18 jenis buah — bidak, kuda, gajah, benteng, ratu, raja, dan tiga buah gabungan, dalam dua warna — dan 64 petak: 18 × 64 = 1152 pertanyaan ya-atau-tidak seperti “apakah ada kuda putih di f3?”. Dalam posisi biasa, sekitar 32 di antaranya bernilai “ya”. Buah gabungan punya input sendiri, bukan campuran dari buah lain, sehingga jaringan mempelajari nilai Maharaja apa adanya.
• Dua sudut pandang. Papan dimasukkan dua kali: seperti yang dilihat pihak yang melangkah, dan dicerminkan, seperti yang dilihat lawan. Jaringan tidak perlu belajar catur dua kali, sekali untuk Putih dan sekali untuk Hitam.
• Neuronnya tidak diprogram. Tidak ada yang memberi tahu neuron apa yang harus dicari. Selama pelatihan, neuron-neuron itu menjadi pendeteksi dengan sendirinya — kira-kira seperti “raja tanpa perlindungan bidak” atau “benteng yang sudah mencapai baris ketujuh”.

Mengapa cepat

Nama jaringannya, NNUE, adalah singkatan dari Efficiently Updatable Neural Network, jaringan saraf yang bisa diperbarui secara efisien. Lapisan pertama adalah tabel dengan satu kolom angka per input, dan neuronnya cukup berupa jumlah kolom dari input yang bernilai “ya”. Satu langkah hanya mengubah dua sampai empat input, jadi jumlahnya tidak pernah dihitung ulang dari awal — cukup diperbarui:

Semuanya dihitung dengan bilangan bulat kecil, banyak sekaligus, memakai instruksi vektor prosesor. Dalam pengukuran kami, mesin dengan jaringan mencapai kedalaman pencarian yang sama kira-kira dua kali lebih cepat daripada dengan evaluasi tulisan tangan (0,95 berbanding 2,0 detik pada posisi uji kami, satu inti mesin uji kami).

Cara belajarnya

Setiap contoh pelatihan adalah sebuah posisi dengan dua label: skor yang diberikan oleh pencarian beberapa langkah ke depan, dan bagaimana partai itu akhirnya berakhir. Jaringan belajar menebak keduanya sekilas pandang. Itulah seluruh triknya: saat pencarian bertanya kepada jaringan tentang sebuah posisi, jawabannya sudah membawa apa yang akan ditemukan oleh tinjauan yang lebih dalam, seolah-olah pencarian melangkah lebih jauh secara gratis.

Mesin ini belajar hanya dari partai-partainya sendiri, termasuk buah gabungan dan pasukan kustom — tidak ada analisis dari mesin lain yang masuk ke dalamnya. Jaringan baru hanya dipertahankan jika mengalahkan jaringan sebelumnya dalam match berisi ratusan partai. Sejauh ini setiap putaran jelas lebih kuat daripada sebelumnya:

Angka-angka ini berasal dari partai dengan pembukaan klasik antarversi mesin kami sendiri, 600 partai per match. Bermain melawan diri sendiri cenderung membesar-besarkan peningkatan; pengukuran melawan mesin dari luar ada di halaman kekuatan mesin.

Sejauh mana sekarang

• Jaringan keempat sudah terpasang di dalam mesin. Melawan Fairy-Stockfish yang disetel pada kekuatan 2500, jaringan ini meraih skor 55%, sekitar 2535 pada skala itu; evaluasi tulisan tangan mencapai sekitar 2210 dalam uji yang sama.
• Jaringan ini kurang mengenal varian dibandingkan catur klasik. Setiap pasukan kustom yang dipakai melatihnya berasal dari generator kami, bukan dari pemain, sehingga posisi awal itu agak buatan. Pasukan seperti apa yang akan disusun pemain sungguhan, kami belum tahu. Selain itu, varian memang lebih sulit dimainkan: lebih banyak jenis buah, dan posisi awal yang baru hampir di setiap partai.
• Partai para pemain belum dikumpulkan. Rencananya, server menyimpan partai di mana pemain memilih level 5 dan mengalahkan mesin dengan pasukan kustom. Itu belum bisa dilakukan. Jaringan membutuhkan puluhan juta posisi latihan — jaringan keempat belajar dari 68 juta — dan para pemain masih jauh dari memainkan cukup banyak partai varian untuk menyediakannya.