Membangun AI yang sempurna untuk game 15

8

Dalam permainan 15, dua pemain bergiliran memilih angka dari 1 hingga 9 (tanpa memilih nomor yang telah dipilih salah satu pemain). Seorang pemain menang jika dia memiliki tiga angka yang berjumlah hingga 15. Jika semua angka telah dipilih dan tidak ada kombinasi dari masing-masing pemain yang menambah hingga 15, maka permainan itu seri.

Tugas Anda adalah membangun fungsi yang mengambil status permainan 15 (diwakili dalam bentuk apa pun yang Anda suka) dan mengembalikan nomor yang akan dipindahkan berikutnya, yang akan bertindak sebagai AI untuk memainkan permainan dengan pemain lain. Anda dapat mengasumsikan bahwa posisinya legal (tidak ada pemain yang memiliki lebih dari satu angka lebih dari pemain lain, dan tidak ada pemain yang memiliki tiga angka yang menambahkan hingga 15).

AI harus sempurna - yaitu, jika diberi posisi menang, ia harus memaksakan kemenangan, dan jika diberi posisi tidak kalah (posisi di mana lawannya tidak memiliki strategi kemenangan), ia tidak boleh membiarkannya lawan untuk memberikannya posisi yang kalah (yang mungkin, karena 15 adalah permainan yang diselesaikan).

Kode terpendek menang.

(catatan: Saya akan menerima jawaban terpendek yang sekarang dan mengubahnya jika jawaban yang lebih pendek muncul.)

Joe Z.
sumber
Apakah saya mengerti dengan benar bahwa kita dibiarkan kalah jika kita berada dalam posisi yang dapat dimenangkan yang tidak mungkin dicapai oleh AI kita?
John Dvorak
Ya itu benar. Jika AI disajikan dengan kondisi permainan yang tidak dapat dimenangkan atau diikat (mis. Perangkap ganda), maka dibiarkan kalah. Namun, AI seharusnya tidak pernah membiarkan game masuk ke kondisi yang hilang dari papan kosong.
Joe Z.
apakah saya berasumsi benar bahwa AI selalu yang pertama bermain?
John Dvorak
1
hmm ... sepertinya kita diizinkan menggambar meskipun kita bisa memaksakan kemenangan. Benarkah?
John Dvorak
2
Hah. Saya baru belajar tentang permainan ini, dan hal pertama ketika saya sampai di rumah adalah mempostingnya di sini. Sayangnya, saya sudah dipukuli karenanya.
stan

Jawaban:

6

GolfScript ( 129 86 81 85 75 karakter)

{:C[{.`{1$-\{+15\-}+%}:T+/}/10,1>C~+-:^{.{^T&}+C/,2<*T}/5^{1&}$][]*^&0=}:N;

Format input yang diharapkan: di [[int int ...][int int ...]]mana daftar pertama adalah nomor saya dan daftar kedua adalah nomor lawan saya. Untuk pengujian interaktif, tambahkan ~Nke akhir skrip dan berikan string dalam format itu: mis

$ golfscript.rb 15.gs <<<"[[5][2 8]]"
9
$ golfscript.rb 15.gs <<<"[[2][5 8]]"
6

Heuristik:

  1. Jika saya bisa memenangkan giliran ini, lakukanlah
  2. Jika lawan akan menang pada giliran berikutnya, blokir
  3. Jika saya bisa memaksa lawan ke kotak yang mencegah mereka membuat garpu, lakukanlah
  4. 5 adalah satu-satunya nomor yang dapat berkontribusi untuk menang dalam 4 cara, jadi raih jika tersedia.
  5. Favor bahkan lebih dari peluang

Kerangka uji:

{:Set;[1 5 9 1 6 8 2 4 9 2 5 8 2 6 7 3 4 8 3 5 7 4 5 6]3/{.Set&=},!!}:isWin;
{
    # Mine His
    .isWin{
        "Lost "@`@`++puts
    }{
        # If there are available moves, it's my move.
        # If I won before my move, I've still won after it.
        1$1$+,9<!!{
            # my move
            1$1$[\\]N 2$\+
            # Mine His Mine'
            .isWin!{
                # his move
                10,1>2$2$+-{
                    2$\+1$\
                    # Mine His Mine' Mine' His'
                    fullTest
                    # Mine His Mine'
                }/
            }*;
        }*;;
    }if
}:fullTest;
# I move first
'[][]fullTest'puts [][]fullTest
# He moves first
'[][1]fullTest'puts [][1]fullTest
'[][2]fullTest'puts [][2]fullTest
'[][5]fullTest'puts [][5]fullTest
Peter Taylor
sumber
Dapatkah Anda menjalankan input ini untuk saya: [5][3](harus mengembalikan 4 atau 8).
Joe Z.
9- tetapi kemudian Anda tampaknya telah mengubah peraturan.
Peter Taylor
Juga, mengapa hanya 4atau 8?
Peter Taylor
Oh, tunggu, sudahlah, aku salah. Apa pun kecuali 7harus bekerja, jadi 9dapat diterima.
Joe Z.
Juga, saya tidak bermaksud mengubah aturan; hanya saja aku salah mengartikannya saat pertama kali.
Joe Z.
4

Ruby, 330 315 341 karakter

def m i
$_=i.join
l='159258357456168249267348'.scan /(.)(.)(.)/
return 1 if /^5(28|46|64|82)$/
return 4 if /^[258]{3}$/
return 2 if /^[456]{3}$/
i.each{|i|l.map{|l|return l if(l-=i).size==1&&!/[#{l=l[0]}]/}}
.map{|i|l.map{|m|l.map{|l|return (l&m)[0] if(z=l-i|m-i).size==3&&l!=m&&!/[#{z.join}]/}}}
"524681379".chars{|z|return z if !/#{z}/}
end

Saya akan menahan detail untuk saat ini, tetapi katakanlah itu didasarkan pada algoritma optimal untuk masalah serupa yang telah diselesaikan juga dan algoritma optimalnya yang bekerja dengan baik di sini. Asumsi telah dibuat - ini akan memilih gerakan buruk dalam situasi yang tidak dapat dihasilkan oleh algoritma ini bermain melawan pemain lain, hanya oleh dua pemain yang saling berhadapan.

Input: array dua array string satu digit. Setiap array mewakili nilai yang diambil oleh satu pemain - yang pertama adalah AI, yang kedua adalah lawan.

Output: salah satu angka, atau string satu digit. Mereka setara secara semantik. Normalisasi ke string akan dikenakan biaya 8 karakter.

Tiga karakter lagi dapat disimpan jika kita mengasumsikan urutan angka yang diberikan oleh penelepon - ubah regex di L5 ke /^285$/atau /^258$/tergantung pada urutan yang dihasilkan dari game (opponent)5-(ai)2-(opponent)8.

John Dvorak
sumber
Sepertinya Anda memiliki simpanan yang mudah di tiga baris terakhir dengan hanya berpindah 5ke awal urutan preferensi Anda.
Peter Taylor
@ ya, terima kasih. Saya memiliki langkah lain di antara yang saya hapus (khusus-cased ke atas) dan saya lupa untuk menggabungkan langkah-langkah sekitarnya. Saya akan mengedit ketika saya sampai di rumah (kecuali jika Anda sukarela sebelumnya).
John Dvorak
1

GolfScript ( 90 85 84 karakter)

{.~.,3/*..2%.@^++3*3/{~++15=},,*10,1>2$~+-@`{([2$+]+v[0=~)\]}+%[1,]or$0=+}:v{1=}+:N;

Ini mengambil pendekatan yang sama sekali berbeda, tetapi berpotensi rentan terhadap optimisasi untuk mengalahkan yang heuristik. Di sini kita melakukan analisis pohon permainan penuh, sangat lambat. (Tidak, maksud saya. Diperlukan beberapa jam untuk menjalankan tes penuh, terutama karena `{...}+yang menambahkan status saat ini ke loop langkah berikutnya). Perhatikan bahwa bagian yang sulit adalah mengidentifikasi negara pemenang (sepertiga dari kode, saat ini).

Ada beberapa peretasan jelek di bagian non-rekursif. Secara khusus, ketika posisi diidentifikasi sebagai posisi yang kalah, kami mengambil posisi kami sebagai [value move]susunan, bergantung pada langkah yang tidak relevan dan nilainya tidak-nol.

Peter Taylor
sumber