Mesin Catur MiniMax yang Diimplementasikan dengan Ekspresi Reguler

 (nicholas.carlini.com)
4 poin oleh GN⁺ 2025-01-08 | 1 komentar | Bagikan ke WhatsApp

Mesin Catur MiniMax 2-Lapis

  • Catur dan Ekspresi Reguler: Penulis membuat program catur yang hanya menggunakan ekspresi reguler. Program ini menerima papan catur sebagai input dan terdiri dari 84.688 ekspresi reguler yang menghasilkan langkah valid.

  • Desain CPU Berbasis Ekspresi Reguler: Ia merancang eksekusi tanpa kondisi dan set instruksi SIMD (Single Instruction Multiple Data) menggunakan ekspresi reguler. Dengan ini, ia dapat menulis program untuk bermain catur.

  • Struktur Data: Status komputer saat ini direpresentasikan sebagai satu string tunggal yang berisi "stack" program dan semua variabel. Setiap instruksi memanipulasi variabel-variabel stack atau melakukan operasi baca/tulis pada variabel tertentu.

  • Operasi Dasar Stack:

    • Instruksi Push: Menambahkan nilai ke bagian teratas stack.
    • Instruksi Pop: Menghapus elemen teratas dari stack.

  • Perintah Variabel <-> Stack:

    • Membaca Variabel: Memuat isi variabel ke bagian teratas stack.
    • Menetapkan Variabel: Menetapkan nilai ke variabel; memperbarui jika variabel sudah ada atau membuat baru jika belum ada.

  • Pernyataan Kondisional: Program mengontrol alur eksekusi melalui kondisional. Bergantung pada kondisi, bagian tertentu dari program diaktifkan atau dinonaktifkan.

  • Ketidakmungkinan Loop: Karena reguler hanya (ekspresi reguler) tidak dapat mengimplementasikan loop, semua perhitungan berulang harus di-unroll sebelumnya.

  • Eksekusi Multi-Thread: Penggunaan fitur penggantian global regex memungkinkan menjalankan banyak thread secara bersamaan.

  • Penulisan Mesin Catur: Mesin catur ditulis mirip dengan bahasa pemrograman lain, dan berjalan cepat berkat paralelisasi.

  • Urutan Giliran:

    • Membaca Langkah Pemain: Menerima langkah input dan memvalidasi keabsahannya.
    • Menghasilkan Respons Komputer: Menghasilkan semua respons yang mungkin dan memilih langkah terbaik.

  • Pencarian MiniMax: Pilihan langkah optimal dibuat melalui pencarian minimax kedalaman 2. Proses ini dilakukan secara efisien lewat pemrosesan paralel.

Proyek ini menunjukkan implementasi mesin catur melalui penggunaan ekspresi reguler yang unik, menonjolkan kekuatan regex dan desain komputer yang kreatif.

Bacaan terkait

1 komentar

 
GN⁺ 2025-01-08
Komentar Hacker News

  • Pengembang ini adalah orang yang membuktikan bahwa printf() bersifat Turing-complete dan menulis game penembak orang pertama dalam JavaScript seukuran 13kB

  • Proyek ini menunjukkan keunggulannya karena menghitung beberapa posisi yang mungkin secara paralel

    • Bisa menjalankan banyak thread sekaligus dengan regex

  • Tidak ada yang istimewa untuk saya tambahkan pada kesimpulan artikel blognya, tetapi saya berharap lebih banyak orang mencoba proyek "tak berguna" semacam ini

    • Menyenangkan, tanpa tekanan soal waktu penyelesaian atau keberhasilan, dan Anda bisa mempelajari banyak hal dari berbagai bidang ilmu komputer

  • Pada permainan catur, terjadi bug "gerakan ilegal, kekalahan"

    • Dalam contoh permainan, game berakhir meski gerakannya sebenarnya legal

  • Lebih menyeramkan adalah seseorang yang memainkan catur dengan satu regex dibandingkan dengan 84.688 regex

  • Saya ingin memberikan penghormatan saat melihat proyek-proyek seperti ini

  • Bug terkait gerakan a-file sudah diperbaiki

  • Proyek ini bukan cuma mesin catur, tapi juga sebuah komputer dan bahasa assembly yang dibangun sepenuhnya dari regex

  • Dulu pernah ada proyek catur yang ditulis dengan sed

    • Versi sed menggunakan instruksi kontrol alur dan menelusuri hanya 1 ply

  • Tidak secepat ini saat mulai dengan a2a4

  • Mencoba sesuatu tanpa tujuan yang jelas tentang "produktivitas" dapat menghasilkan hal baru dan mendorong inovasi

    • Mesin kehilangan bidak sejak awal
    • Saat mengetik huruf kapital, itu dianggap gerakan ilegal

  • Saya sedang berupaya untuk mengejar inovasi dan menjadi lebih produktif