Tantangannya adalah menulis solver untuk pensil dan permainan kertas klasik Dots and Boxes . Kode Anda harus mengambil dua bilangan bulat m
dan n
sebagai input yang menentukan ukuran papan.
Dimulai dengan kisi-kisi titik yang kosong, pemain bergiliran, menambahkan garis horizontal atau vertikal tunggal antara dua titik yang berdekatan yang tidak terhubung. Seorang pemain yang menyelesaikan sisi keempat kotak 1 × 1 menghasilkan satu poin dan mengambil giliran lain. (Poin biasanya direkam dengan menempatkan di kotak tanda pengidentifikasi pemain, seperti inisial). Permainan berakhir ketika tidak ada lagi garis yang dapat ditempatkan. Pemenang permainan adalah pemain dengan poin terbanyak.
Anda dapat mengasumsikan bahwa baik n = m
atau n = m - 1
dan m
setidaknya 2.
Tantangannya adalah menuju solve
permainan Dots and Boxes sebesar mungkin dalam waktu kurang dari satu menit. Ukuran gim ini sederhana n*m
. Output dari kode Anda seharusnya win
, draw
atau lose
yang seharusnya menjadi hasil untuk pemain pertama dengan asumsi kedua pemain bermain secara optimal.
Kode Anda harus dapat dikompilasi / dijalankan di ubuntu menggunakan alat yang mudah diinstal dan gratis. Silakan laporkan skor Anda sebagai area terbesar yang dapat Anda selesaikan di komputer Anda dalam 1 menit bersama waktu. Saya kemudian akan menguji kode di komputer saya dan membuat daftar entri urutan peringkat.
Dalam kasus tie-break, pemenang akan menjadi kode tercepat di papan ukuran terbesar yang bisa diselesaikan dalam waktu kurang dari satu menit.
Akan lebih baik jika kode yang dihasilkan tidak hanya menang atau kalah tetapi juga skor aktual. Ini membuat pemeriksaan kewarasan kebenaran.
Jawaban:
Papan C99 - 3x3 dalam ukuran 0,084
Sunting: Saya refactored kode saya dan melakukan beberapa analisis yang lebih dalam pada hasilnya.
Pengeditan Lebih Lanjut: Menambahkan pemangkasan oleh simetri. Ini membuat 4 konfigurasi algoritma: dengan atau tanpa simetri X dengan atau tanpa pemangkasan alpha-beta
Edit Terjauh: Menambahkan memoisasi menggunakan tabel hash, akhirnya mencapai hal yang mustahil: menyelesaikan papan 3x3!
Fitur utama:
#define HASHTABLE_BITWIDTH
). Ketika ukuran ini lebih besar dari atau sama dengan jumlah dinding, itu tidak menjamin tabrakan dan pembaruan O (1). Hashtable yang lebih kecil akan memiliki lebih banyak tabrakan dan sedikit lebih lambat.-DDEBUG
untuk cetakanPeningkatan potensial:
memperbaiki kebocoran memori kecil yangdiperbaiki pada edit pertamapemangkasan alpha / betaditambahkan di edit ke-2simetri pruneditambahkan pada edit ke-3 (perhatikan bahwa simetri tidak ditangani oleh memoisasi, sehingga tetap merupakan optimasi yang terpisah.)memoisasiditambahkan di edit ke-4Kode
Karena kurangnya pengorganisasian, jumlah file telah bertambah. Semua kode telah dipindahkan ke Gudang Github ini . Dalam edit memoisasi, saya menambahkan skrip makefile dan pengujian.
Hasil
Catatan tentang Kompleksitas
Pendekatan brutal terhadap titik dan kotak meledak dengan sangat cepat .
Pertimbangkan papan dengan
R
baris danC
kolom. AdaR*C
kotak,R*(C+1)
dinding vertikal, danC*(R+1)
dinding horizontal. Itu totalW = 2*R*C + R + C
.Karena Lembik meminta kami untuk menyelesaikan permainan dengan minimax, kita perlu melintasi ke daun pohon permainan. Mari kita abaikan pemangkasan untuk saat ini, karena yang penting adalah urutan besarnya.
Ada
W
opsi untuk langkah pertama. Untuk masing-masing, pemain berikutnya dapat memainkan salah satu dariW-1
dinding yang tersisa, dll. Itu memberi kita ruang pencarianSS = W * (W-1) * (W-2) * ... * 1
, atauSS = W!
. Faktorial sangat besar, tetapi itu baru permulaan.SS
adalah jumlah node daun di ruang pencarian. Lebih relevan dengan analisis kami adalah jumlah total keputusan yang harus dibuat (yaitu jumlah cabangB
di pohon). Lapisan pertama cabang memilikiW
opsi. Untuk masing-masing, level selanjutnyaW-1
, dll.Mari kita lihat beberapa ukuran meja kecil:
Angka-angka ini semakin konyol. Setidaknya mereka menjelaskan mengapa kode brute-force tampaknya menggantung selamanya di papan 2x3. Ruang pencarian papan 2x3 adalah 742560 kali lebih besar dari 2x2 . Jika 2x2 membutuhkan 20 detik untuk menyelesaikan, ekstrapolasi konservatif memperkirakan lebih dari 100 hari waktu eksekusi untuk 2x3. Jelas kita perlu memangkas.
Analisis Pemangkasan
Saya mulai dengan menambahkan pemangkasan sangat sederhana menggunakan algoritma alpha-beta. Pada dasarnya, ia berhenti mencari jika lawan yang ideal tidak akan pernah memberikannya kesempatan saat ini. "Hei, lihat - saya menang banyak jika lawan saya membiarkan saya mendapatkan setiap kotak!", Pikir tidak AI, pernah.
sunting Saya juga menambahkan pemangkasan berdasarkan papan simetris.
Saya tidak menggunakan pendekatan memoisasi, kalau-kalau suatu hari saya menambahkan memoisasi dan ingin memisahkan analisis itu. Sebagai gantinya,ia bekerja seperti ini: sebagian besar garis memiliki "pasangan simetris" di tempat lain di grid. Ada hingga 7 simetri (horizontal, vertikal, 180 rotasi, 90 rotasi, 270 rotasi, diagonal, dan diagonal lainnya). Semua 7 berlaku untuk papan persegi, tetapi 4 terakhir tidak berlaku untuk papan non-persegi. Setiap dinding memiliki pointer ke "pasangan" untuk masing-masing simetri ini. Jika, setelah berbelok, papan itu simetris secara horizontal, maka hanya satu dari setiap pasangan horisontal yang perlu dimainkan.sunting sunting Memoisasi! Setiap dinding mendapatkan id unik, yang saya setel dengan mudah sebagai indikator; dinding ke-n memiliki id
1 << n
. Hash papan, maka, hanya OR dari semua dinding yang dimainkan. Ini diperbarui di setiap cabang dalam waktu O (1). Ukuran hashtable diatur dalam a#define
. Semua tes dijalankan dengan ukuran 2 ^ 12, karena mengapa tidak? Ketika ada lebih banyak dinding daripada pengindeksan bit hashtable (12 bit dalam kasus ini), 12 paling signifikan ditutup dan digunakan sebagai indeks. Tabrakan ditangani dengan daftar tertaut di setiap indeks hashtable. Bagan berikut ini adalah analisis cepat dan kotor saya tentang bagaimana ukuran hashtable mempengaruhi kinerja. Pada komputer dengan RAM tak terbatas, kami akan selalu mengatur ukuran tabel dengan jumlah dinding. Papan 3x4 akan memiliki hashtable 2 ^ 31 panjang. Sayangnya kami tidak memiliki kemewahan itu.Ok, kembali ke pemangkasan .. Dengan menghentikan pencarian tinggi di pohon, kita dapat menghemat banyak waktu dengan tidak turun untuk pergi. 'Faktor Pemangkasan' adalah fraksi dari semua cabang yang memungkinkan yang harus kami kunjungi. Brute-force memiliki faktor pemangkasan 1. Semakin kecil, semakin baik.
sumber
rows columns
menentukan ukuran papanPython - 2x2 dalam 29-an
Posting silang dari teka-teki . Tidak dioptimalkan secara khusus, tetapi dapat menjadi titik awal yang berguna untuk pendatang lain.
sumber
Javascript - papan 1x2 dalam 20 ms
Demo online tersedia di sini (peringatan - sangat lambat jika lebih besar dari 1x2 dengan kedalaman pencarian penuh ): https://dl.dropboxusercontent.com/u/141246873/minimax/index.html
Dikembangkan untuk kriteria kemenangan asli (kode golf) dan bukan untuk kecepatan.
Diuji di google chrome v35 pada windows 7.
sumber