Mesin catur minimax 2-ply yang dibuat dengan 84.688 ekspresi reguler

• Regex Chess adalah mesin 2-ply minimax yang memilih langkah legal dan “tidak sepenuhnya buruk” di papan catur hanya dengan menjalankan 84.688 substitusi ekspresi reguler secara berurutan
• Status disimpan sebagai satu string yang memuat stack dan variabel sekaligus, dan perintah seperti push, pop, pencarian variabel, serta assignment diproses melalui substitusi ekspresi reguler
• Percabangan kondisi ditiru dengan mengubah penanda %% yang berarti status aktif, dan berkat substitusi global, eksekusi paralel bergaya SIMD untuk banyak status sekaligus menjadi mungkin
• Mesin membuat semua langkah legal sebagai status paralel dan mengevaluasi sampai respons lawan, tetapi tidak melakukan pencarian depth-3 untuk memverifikasi sepenuhnya legalitas respons lawan
• Awalnya, satu respons langkah memakan waktu sekitar 30 menit, tetapi lewat penghapusan variabel perantara, optimasi matching, perintah tujuan khusus, dan paralelisasi, implementasi akhirnya turun menjadi sekitar 1–10 detik tergantung posisi

---

Struktur dasar Regex Chess

• Regex Chess menyusun seluruh mesin catur sebagai daftar 84.688 ekspresi reguler
• Struktur eksekusinya sederhana
  • Menelusuri daftar ekspresi reguler secara berurutan
  • Menerapkan setiap pola dan string pengganti ke string status papan catur saat ini
  • Menampilkan status akhir ke layar
• Input bukan PGN, melainkan format koordinat yang menuliskan petak asal dan petak tujuan berurutan seperti e2e4
• Kode proyek tersedia di GitHub

CPU berbasis ekspresi reguler

• Alih-alih langsung menulis aturan catur dalam ekspresi reguler, pembuatnya lebih dulu membuat komputer kecil yang bekerja dengan ekspresi reguler
• Komputer ini memakai himpunan instruksi yang memiliki eksekusi kondisional tanpa branch, single-instruction multiple-data, serta manipulasi stack dan variabel
• Status saat ini direpresentasikan sebagai satu string
  • %% menandai awal status eksekusi aktif
  • Di bawah #stack: item stack ditumpuk
  • Variabel disimpan dalam bentuk #nama_variabel: value

• Manipulasi stack dan variabel

  • push mencari header %%\n#stack:\n lalu menyisipkan nilai di bawahnya untuk menaruhnya di puncak stack
  • pop menghapus satu baris tepat di bawah #stack: untuk menghilangkan nilai teratas stack
  • Pencarian variabel mencari #nama_variabel: di dalam string status, menyalin nilainya, lalu menambahkannya ke puncak stack
  • Assignment variabel menangani dua kasus: variabel sudah ada atau belum ada
    • Jika sudah ada, nilai variabel lama diganti dengan nilai dari stack
    • Jika belum ada, baris variabel baru ditambahkan
  • Marker sementara seperti backtick dipakai agar instruksi yang sama tidak diterapkan lagi dalam urutan yang salah

Eksekusi kondisional tanpa branch dan batasan loop

• Eksekusi kondisional diimplementasikan dengan cond(tag) dan reactivate(tag)
• Jika nilai puncak stack adalah False, marker aktif %% diubah menjadi bentuk %tag sehingga instruksi berikutnya tidak diterapkan pada status tersebut
• Nantinya reactivate(tag) mengubah %tag kembali menjadi %% untuk mengaktifkan lagi status itu
• Dengan cara ini, eksekusi kondisional ditiru tanpa branch eksplisit
• Karena program berupa daftar berurutan ekspresi reguler, loop tidak bisa dijalankan secara langsung
  • Komputasi yang Turing-complete tidak bisa dilakukan
  • Namun komputasi yang berbatas, seperti menghitung langkah catur berikutnya, bisa ditangani dengan melakukan unrolling loop

Eksekusi paralel dengan substitusi global

• Karena substitusi ekspresi reguler diterapkan secara global ke seluruh string, jika ada beberapa status eksekusi %% di dalam satu string status, instruksi yang sama bisa diterapkan ke banyak status sekaligus
• Misalnya, jika ada dua stack yang masing-masing berisi dua bilangan bulat, menjalankan binary_add() akan melakukan dua penjumlahan itu secara bersamaan
• fork_inactive(tag) menggandakan status aktif saat ini dan menempatkan salinannya sebagai status bertag nonaktif
• fork_bool(variable) membagi satu status menjadi dua status, masing-masing dengan nilai True dan False
• Struktur ini dipakai untuk mengevaluasi banyak status papan secara serentak dalam catur, alih-alih memprosesnya satu per satu

Macro assembler dan symbolic execution

• Mesin ini tidak ditulis sepenuhnya dengan ekspresi reguler mentah secara manual, tetapi memakai macro assembler yang mengubah program bergaya Python menjadi urutan instruksi kecil
• Kode bergaya Python seperti fib() diubah menjadi daftar instruksi seperti push, lookup, binary_add, dan assign_pop
• Alih-alih parser dan code generation tradisional, digunakan symbolic execution
  • Objek variabel bukan dictionary nyata, melainkan objek khusus yang mencatat operasi yang dilakukan
  • a = b + 1 dicatat sebagai lookup('b'), push(1), binary_add(), assign_pop('a')
• Pernyataan if mencatat baik jalur kondisi benar maupun salah, lalu menggabungkannya kembali
  • Saat menemukan percabangan kondisi, dibuat dua jalur dalam call tree
  • Dengan penelusuran berulang, cabang yang lebih jarang dikunjungi dipilih untuk melengkapi kedua jalur
  • Titik penggabungan diubah menjadi instruksi reactivate

Cara menghasilkan langkah catur

• Penulisan mesin catur itu sendiri mirip dengan mesin catur dalam bahasa umum, tetapi inti utamanya adalah memproses banyak status secara paralel
• Pembuatan langkah pion mengikuti alur berikut
  • Mencari semua posisi pion putih
  • Membuat status paralel untuk setiap pion
  • Menghentikan status utama asli dan mengaktifkan status per pion
  • Memeriksa kandidat maju satu petak, maju dua petak, dan tangkapan diagonal pada semua status pion secara bersamaan
  • Menggabungkan kembali daftar langkah kandidat dari tiap status
• Contoh penjelasan langsung memanipulasi string FEN, tetapi implementasi sebenarnya memperluas papan catur menjadi variabel untuk 64 petak agar bisa dibaca dan ditulis
• Bidak geser seperti bishop, rook, queen, serta castling dan en passant juga diimplementasikan terpisah
• Detail implementasi ada di chess_engine.py

Pemrosesan satu giliran dan verifikasi langkah

• Satu giliran berjalan dengan urutan membaca langkah input manusia, memverifikasi apakah langkah itu legal, lalu menghasilkan langkah balasan komputer
• from_pretty_utf8_to_fen() mengubah tampilan papan catur Unicode menjadi notasi FEN dan mengekstrak petak asal serta tujuan dari input
• Legalitas langkah manusia tidak diperiksa dengan kode aturan terpisah, tetapi dengan menghasilkan semua papan legal berikutnya lalu membandingkannya
  • make_move membuat papan dengan langkah input diterapkan
  • compute_legal_boards menghasilkan semua papan legal yang mungkin dari posisi saat ini
  • fork_on_list memisahkan tiap papan menjadi status paralel
  • Status yang berbeda dari hasil penerapan langkah input dihapus dengan destroy_active_thread()
• Jika tidak ada langkah legal, seluruh output diubah menjadi teks hardcoded "Illegal Move"
• Respons komputer dibuat dengan menghasilkan papan respons hitam yang mungkin beserta skornya, lalu keep_best_scoring_board(score) menyisakan hanya papan dengan skor terbaik

Minimax 2-ply dan penyederhanaan yang disengaja

• compute_and_score_legal_boards berperan sebagai inti pencarian minimax depth-2
• Pertama, mesin menghasilkan kandidat langkah yang bisa dimainkan komputer, lalu membuat langkah respons yang bisa dimainkan lawan untuk memeriksa apakah raja bisa ditangkap
• Karena validasi status check memerlukan pembuatan respons lawan, struktur pencarian depth-2 pada dasarnya sudah terbentuk
• Setiap posisi kandidat dinilai berdasarkan skor saat lawan memainkan respons terbaiknya
• Namun ini bukan minimax depth-2 yang sepenuhnya lengkap
  • Langkah respons lawan tidak diverifikasi sampai tuntas apakah itu langkah ilegal yang menempatkan rajanya sendiri dalam check
  • Untuk menanganinya secara penuh dibutuhkan pencarian depth-3 dan biayanya meningkat besar
• Respons yang dihasilkan komputer sendiri bukan langkah ilegal, tetapi dalam beberapa kasus ia bisa memilih respons yang lebih lemah dari seharusnya karena mempertimbangkan langkah yang sebenarnya tidak bisa dimainkan lawan

Optimasi performa

• Implementasi awal membutuhkan sekitar 30 menit untuk menghasilkan respons terhadap satu langkah manusia
• Implementasi akhir membutuhkan sekitar 1–10 detik tergantung posisi pada mesin milik penulis
• Peningkatan kecepatan sekitar 100 kali adalah hasil dari beberapa optimasi

• Penghapusan variabel perantara

  • Pencarian variabel harus mencari nilai di seluruh string status sehingga biayanya O(n)
  • Saat status eksekusi di-fork, variabel juga ikut disalin sehingga penggunaan memori membesar
  • Variabel yang tidak lagi dibutuhkan dihapus secara agresif dan nama variabel dipakai ulang untuk menghemat waktu dan memori
  • Status internal saat evaluasi satu langkah berkurang dari 10GB sebelum optimasi menjadi sekitar 300MB

• Optimasi matching ekspresi reguler

  • Pada ekspresi reguler pembersihan untuk instruksi kondisi, hanya dengan menyertakan karakter newline di bagian depan, efisiensi instruksi itu hampir 2 kali lebih baik
  • Karena string True dan False sering muncul di dalam status, pola harus dibatasi agar cepat menemukan hanya nilai di puncak stack
  • Perbedaan kecil pada pola yang mengurangi matching kandidat yang tidak perlu memengaruhi waktu eksekusi keseluruhan

• Instruksi tujuan khusus dan paralelisasi

  • Bagian lambat seperti loop pencarian posisi bidak digabung menjadi satu instruksi ekspresi reguler khusus alih-alih merangkai instruksi yang sudah ada
  • Dalam pembuatan langkah rook, tiap arah tidak diperiksa secara berurutan, tetapi diproses sekaligus dengan membuat banyak status paralel
  • Evaluasi posisi juga dilakukan serentak dengan membuat status paralel untuk tiap papan kandidat
  • Eksekusi paralel sangat efektif untuk pekerjaan seperti menghitung nilai bidak, ketika operasi yang sama diulang di banyak status

Implementasi tambahan yang ada di sumber

• Sumber juga memuat elemen implementasi yang tidak dibahas mendalam dalam tulisan utama
  • Pembuatan langkah paralel untuk bidak geser seperti bishop, rook, dan queen
  • Prosedur “apakah petak ini diserang” untuk castling
  • Konversi antara papan catur FEN dan representasi variabel per petak
  • Deteksi hak castling dengan melacak posisi king dan rook
  • Deteksi dan pelacakan en passant
  • Sekitar 2000 baris pengujian untuk memverifikasi akurasi mesin di ribuan game
• Tulisan ditutup dengan komentar bahwa proyek tanpa tujuan praktis seperti ini justru membuatnya mempelajari banyak topik ilmu komputer di luar bidang utamanya
• Proyek terkait yang juga disebut adalah printf-tac-toe, yang memainkan tic-tac-toe dengan printf di C, dan klon Doom JavaScript 13kB

[GN⁺]

Komentar Hacker News

• Ini adalah karya orang yang menunjukkan bahwa printf() Turing-complete, dan yang membuat game first-person shooter dalam JavaScript 13kB
  https://github.com/HexHive/printbf
  https://github.com/carlini/js13k2019-yet-another-doom-clone

  • Saat membaca kalimat “menunjukkan bahwa printf() Turing-complete, dan membuat game first-person shooter …”, jujur saja aku kira akhirnya akan berlanjut seperti dia juga mengimplementasikan game shooter itu dengan printf
  • Catatan pengembangan Doom itu menarik karena detailnya banyak: https://nicholas.carlini.com/writing/2019/javascript-doom-cl...
    Meski masa penyelesaian untuk kompetisinya cuma sebulan, sepertinya dia bisa memakai ulang kode yang sudah ada
    Pengerjaannya sendiri kelihatannya cukup menyenangkan, dan agak sedih rasanya karena sekarang, dengan keluarga dan pekerjaan, sepertinya aku tak mungkin lagi punya waktu luang sebulan penuh untuk hal seperti ini
  • Waktu membaca “game first-person shooter dalam JavaScript 13kB” aku sempat berharap banyak, tapi agak kecewa setelah tahu rendering grafisnya memakai WebGL

• Di titik ini aku merasa karya ini sudah melampaui sekadar kegilaan yang menyenangkan dan menjadi sesuatu yang benar-benar luar biasa. Semua perhitungan berbagai posisi yang mungkin terjadi dilakukan secara paralel, dengan menjalankan regex di atas kumpulan state dan variabel yang terus bertambah, semacam thread
  “Sekarang inilah bagian favoritku dari bahasa yang kita buat. Berkat sihir regex, dan fakta bahwa kita melakukan substitusi global pada seluruh string, kita bisa menjalankan banyak thread sekaligus!”
  Penutupnya juga bagus. “Memangnya kalian mengharapkan apa sebagai kesimpulan tulisan blog seperti ini? Tidak ada kesimpulan khusus. Aku hanya berharap lebih banyak orang melakukan hal-hal yang benar-benar tidak berguna seperti ini. Ini sangat menyenangkan, tak ada yang peduli berapa lama waktu yang dibutuhkan untuk menyelesaikannya, tak ada yang peduli apakah hasilnya benar-benar bekerja atau tidak, dan sebagai bonus kalian akan belajar lebih banyak tentang berbagai bidang ilmu komputer di luar bidang kalian sendiri daripada yang kalian kira.”
  Benar-benar sikap yang keren

  • Kalau semua kekhawatiran lain disingkirkan, aku jadi penasaran apakah aku juga bisa melakukan hal seperti ini
    Yang didapat di sini adalah rasa bahwa saat duduk dan benar-benar memusatkan pikiran pada satu hal, kita tidak tahu sejauh apa yang mungkin bisa dicapai; sekaligus juga jelas bahwa penulisnya adalah orang yang sangat berbakat, terampil, dan kreatif

• Sepertinya ada bug di suatu tempat. Permainan di bawah ini bukan rangkaian langkah ilegal, tapi tetap berakhir dengan “Illegal move, you lose”

  1. e2e4, e7e5
  2. d2d4, e5d4
  3. d1d4, a7a5
  4. g1f3, b7b5
  5. b1c3, a5a4
  6. c3b5, a4a3
  7. b5a3, a8a3
  8. b2a3 -->
     Illegal Move
     You Lose.
     Game over.
     FEN untuk permainan di atas:
     1nbqkbnr/2pp1ppp/8/8/3QP3/P4N2/P1P2PPP/R1B1KB1R b KQk - 0 8
  • Kalau langkah pertama adalah a2a3, atau a2a3 dimainkan sebagai langkah kedua setelah e2e4, hasilnya juga dibilang ilegal
    Padahal keduanya legal, jadi ini memang bug
  • Bahkan kalau cuma memulai dengan a2a4 pun kejadian yang sama muncul

• Aku tidak takut pada orang yang bermain catur dengan 84.688 regex, tapi aku takut pada orang yang bermain catur dengan satu regex

  • Kalau ada heuristik umum untuk melinearkan regex-regex yang diterapkan secara berurutan, yaitu cara menggabungkan dua regex sembarang menjadi satu, sepertinya itu bisa diterapkan di sini
    Tolong, aku sedang kena nerd snipe
    Masalah potensial yang langsung terpikir adalah backreference
    Regex-nya pasti akan sangat panjang, tapi pada dasarnya itu berarti sedang mengenkode chess engine...

• Melihat hal seperti ini membuatku ingin angkat topi dan menyampaikan terima kasih yang khidmat kepada para pahlawan sejati umat manusia

• Bug langkah file a sudah diperbaiki: https://github.com/carlini/regex-chess/issues/1

• Contoh sebelumnya: catur yang ditulis dengan sed https://news.ycombinator.com/item?id=6261314
  Tentu saja versi sed memakai perintah control flow milik sed, dan mungkin hanya menelusuri satu langkah ke depan, jadi dalam hal itu cukup berbeda dari versi ini

• Ini bukan cuma chess engine, tapi juga komputer dan bahasa assembly yang dibuat hanya dengan regex

• Biasanya membuka dengan a2a4 tidak membuatmu kalah secepat ini!

  • Aku juga menemui bug serupa di file a. Jalurnya adalah e2e4-d2d4-d1d4-g1f3-f1b5-d4e5-e5c5-e1g1-b2a3

• Ini juga layak dibandingkan: https://codegolf.stackexchange.com/q/3503/32575

  • Semua aturan pengujian keterbagian pada akhirnya adalah bahasa reguler, jadi tidak terlalu mengejutkan. Kalau lebih rumit dari itu, maka itu bukan lagi “aturan” yang bisa dijalankan manusia