Saya hanya bisa menemukan tantangan kode-golf untuk Mastermind, jadi inilah versi tantangan kode yang ingin saya ambil sendiri.
Strategi optimal untuk game Mastermind normal, MM (4,6), ditemukan oleh Koyama dan Lai pada tahun 1993, memiliki rata-rata # tebakan = 5625/1296 ~ 4.34. MM (5,8) masih belum terpecahkan, tetapi diperkirakan memiliki rata-rata tebakan ~ 5.5.
Tugas Anda adalah membuat strategi MM (5,8), yaitu untuk 5 lubang dan 8 warna, yang mencakup semua pow(8,5) = 32768
solusi berbeda yang mungkin. Jelas, itu tidak harus yang optimal. Anda memiliki dua pilihan:
- Poskan program deterministik yang menghasilkan strategi. Program harus dapat dikompilasi / dijalankan pada Windows 7, Mac OS X atau Linux tanpa perangkat lunak tidak bebas tambahan.
- Publikasikan strategi Anda (bersama dengan nama StackExchange Anda) di suatu tempat di Internet dan posting URL di sini.
Dalam kedua kasus, nyatakan skor (lihat di bawah) di tajuk jawaban.
Strategi harus dikodekan sesuai dengan tata bahasa berikut:
strategy : guessing-strategy | known-solution-strategy
guessing-strategy : '{' guess ':' branches '}'
known-solution-strategy : guess
guess : color color color color color
color : 'A'..'H'
branches : '{' branch (',' branch)* '}'
branch : reply ':' strategy
reply : number-of-blacks number-of-whites
number-of-blacks : number-of-key-pegs
number-of-whites : number-of-key-pegs
number-of-key-pegs : '0'..'5'
Algoritma yang digunakan untuk menentukan jumlah pasak kunci hitam / putih dijelaskan di http://en.wikipedia.org/wiki/Mastermind_(board_game)
Perhatikan bahwa balasan "50" (yaitu tebakan yang benar) tersirat dan bukan bagian dari tata bahasa.
Penilaian: N = jumlah jumlah tebakan untuk masing-masing 32768 jalur / solusi. Strategi dengan N terendah menang. Tie-break pertama: Jumlah tebakan maksimum terendah. Ikatan kedua: Jawaban pertama yang diposting. Kompetisi berakhir 1 Agustus 2014 0:00 GMT .
Contoh strategi untuk MM (2,3) dengan skor = 21:
{AB:{10:{AC:{10:AA,01:CB,00:BB}},02:BA,01:{BC:{01:CA}},00:CC}}
Dengan menggunakan strategi ini, 9 kemungkinan game akan berjalan seperti ini:
- AB 20
- AB 10, AC 20
- AB 10, AC 10, AA 20
- AB 10, AC 01, CB 20
- AB 10, AC 00, BB 20
- AB 02, BA 20
- AB 01, BC 20
- AB 01, BC 01, CA 20
- AB 00, CC 20
Saya akan segera memposting verifikasi strategi MM berbasis Java (5,8) untuk kenyamanan Anda.
sumber
{AB:{10|01:BB}}
? Saya memang punya jawaban, tapi itu cukup naif dan karena struktur pohon tata bahasa itu tidak skala sama sekali (4 lubang, 3 warna, menghasilkan strategi 147MB, yang saya dapat mengurangi secara signifikan dengan menggabungkan bagian-bagian dari pohon).Jawaban:
Jawa
Algoritma saya untuk skor MM (5,8) dengan
177902178006182798182697 dengan kedalaman maksimum89 dan hanya perlu beberapa detik (pada komputer saya yang lambat).Contoh output dari strategi untuk MM (2,3) dengan skor = 21 ditemukan oleh algoritma ini terlihat seperti ini:
Tidak ada yang menarik dengan algoritma saya. Tidak ada penemuan. Saya hanya mengikuti resep yang ditemukan di internet dan mengompresnya ke dalam kode Java ini. Satu-satunya optimasi yang saya lakukan adalah mencoba mengoptimalkan baris kode (dengan cara tertentu). Bunyinya seperti ini:
@ MrBackend: Menulis verifier itu sulit, kurasa. ;-)
Beberapa komentar:
Strategi untuk
MM(5,8)
dapat ditemukan di sini . GitHub memiliki beberapa masalah menampilkan garis yang panjang, jadi klik tombol Raw .sumber
Rubi
EDIT: Menambahkan beberapa logika untuk mengecualikan tebakan yang tidak mungkin. Oleh karena itu, strategi sekarang mematuhi format yang diberikan dan jauh lebih mudah dikelola.
Jadi, inilah salah satu upaya untuk mewujudkannya. Ini cukup naif (dan tidak terlalu terbaca - membantu untuk membaca cabang if / elsif / else dari bawah ke atas).
Pertama, saya mencoba 5 dari masing-masing warna:
AAAAA
,BBBBB
, dll Dari bahwa saya mencari tahu mana warna yang benar-benar digunakan dalam pola. Dan kemudian saya hanya mencoba semua permutasi dari warna yang diberikan, menghilangkan yang telah dikesampingkan oleh pasak hitam.Inilah
MM(2,3)
strateginya:Strategi untuk
MM(5,8)
mengambil 376KB dan dapat ditemukan di sini . GitHub memiliki beberapa masalah menampilkan garis yang panjang, jadi klik tombol Raw .Sekarang jika saya mendapatkan verifikasi, saya juga bisa memberi tahu Anda berapa skor saya yang sebenarnya. :)
sumber