Game 2-Pemain Terpendek dari Halma

19

Dalam Catur, permainan bisa berakhir setelah 4 gerakan (masing-masing 2) dengan Fool's Mate .

Tujuan Anda adalah menemukan Fool's Mate of Halma : permainan 2-pemain Halma yang meminimalkan jumlah putaran yang dimainkan.

Ada lebih dari 10 56 status papan, dan saya telah melihat faktor percabangan melampaui 1000, sehingga kemungkinan tidak ada yang akan menemukan solusi optimal. Sebaliknya, Anda mencoba mencari solusi terbaik yang Anda bisa.

Anda harus mengirimkan daftar gerakan, dan kode apa pun yang Anda gunakan untuk membuat gerakan itu.

Penjelasan Game

Halma mirip dengan Checkers Cina, tetapi dimainkan pada papan 16 * 16 persegi.

Awalnya, papan terlihat seperti ini:

Papan Awal

Tujuan permainan ini adalah untuk memindahkan semua bagian Anda ke posisi awal bagian lawan Anda.

Pada giliran pemain, dia dapat:

  • Lewati belokan

  • Pindahkan salah satu bagiannya ke ruang kosong yang berdekatan. Ruang yang berdekatan termasuk diagonal.

  • Ambil salah satu potongannya dan lakukan hal berikut beberapa kali: Lompat potongan di atas potongan yang berdekatan, mendaratkannya di ruang di seberang potongan melompati.

Berikut ini contoh untuk menggambarkan tipe gerakan ke-2.

Melompat

Aturan

Kirim daftar langkah hukum yang menghasilkan permainan berakhir.

Kirim kode apa pun yang Anda gunakan untuk menghasilkan daftar.

Jika Anda memperoleh hasil yang lebih baik dari kode orang lain, poskan hasilnya dalam komentar atau edit posting mereka dengan hasil baru.

Setiap gerakan harus Nonemelewati putaran, atau (x1,y1,x2,y2)untuk memindahkan potongan, di mana (x1,y1)koordinat potongan untuk bergerak dan (x2,y2)merupakan tujuan potongan itu (untuk gerakan melompat, abaikan koordinat menengah). Koordinat mulai dari (0,0)di sudut kiri atas. koordinat x bertambah ke kanan, koordinat y bertambah ke bawah. Pergerakan harus dipisahkan oleh baris baru.

Anda dapat menggunakan skrip python ini untuk memverifikasi gerakan Anda. Gunakan python halma_verify.py < fileuntuk memverifikasi perpindahan file.

Daftar terpendek menang.

optimization board-game puzzle-solver kotak kardus
sumber
6
beberapa diskusi teknis tentang gerakan, dan solusi dalam 47 gerakan: arxiv.org/pdf/0803.1245.pdf
SeanC

Jawaban: