Mainkan Wythoff's Nim dengan sempurna

16

Tujuan Anda adalah menulis pemain yang sempurna untuk permainan Wythoff's Nim .

Aturan Wythoff's Nim

Wythoff's Nim adalah permainan dua pemain deterministik yang dimainkan dengan dua tumpukan counter identik. Pemain bergantian bergantian, di mana mereka melakukan salah satunya:

  1. Hapus satu atau lebih penghitung dari tumpukan pertama
  2. Hapus satu atau lebih penghitung dari tumpukan kedua
  3. Hapus jumlah penghitung yang sama (satu atau lebih), dari tumpukan pertama dan tumpukan kedua.

Tentu saja, tumpukan tidak bisa menjadi negatif, tetapi mereka bisa ke 0. Pemain mana saja yang menghapus counter terakhir secara keseluruhan memenangkan permainan.

Untuk yang lebih berpikiran geometris, berikut ini adalah rumusan setara game yang dapat Anda mainkan di applet ini . Seorang ratu tunggal mulai di atas papan catur berukuran seperempat tak terbatas yang sudutnya ada di kiri bawah. Pemain bergantian memindahkan sang ratu, yang bergerak seperti ratu catur tetapi terbatas pada tiga arah:

  1. Turun
  2. Kiri
  3. Diagonal ke bawah dan kiri

Siapa pun yang memindahkan ratu ke sudut akan menang.

Mengaitkan koordinat ratu (dengan sudut (0,0)) dengan ukuran tumpukan masing-masing, mudah untuk melihat kedua permainan itu sama.

Bermain sempurna

(Anda dapat melewati ini jika terbiasa dengan gagasan bermain sempurna dan gerakan menang.)

Karena Wythoff's Nim adalah permainan yang terbatas dan deterministik, ia memiliki gagasan permainan yang sempurna . Seorang pemain yang sempurna adalah strategi yang akan selalu menang dari posisi yang dimenangkan secara teoritis, artinya posisi di mana ada strategi yang menjamin kemenangan.

Untuk menjadi strategi kemenangan, cukuplah bergerak untuk selalu pindah ke posisi kemenangan teoretis untuk pemain yang baru saja pindah, dan dengan demikian pemain tidak akan maju berikutnya. Posisi pemenang pertama (juga disebut posisi dingin ) adalah (0,0), (1,2), (2,1), (3,5), (5,3). Lihat artikel Wikipedia untuk penjelasan tentang algoritma untuk menemukan strategi kemenangan untuk Wythoff's Nim, serta formula untuk menghasilkan posisi menang.

Persyaratan program

Menulis suatu program atau fungsi mengambil posisi sebagai input dan menghasilkan langkah kemenangan dalam bentuk posisi setelah langkah itu. Bytes paling sedikit menang.

Jika tidak ada langkah yang menang, yaitu, posisi itu adalah kerugian teoritis, program Anda harus menunjukkan begitu dan kehilangan.

Program Anda harus berjalan dalam jumlah waktu yang wajar. Jadi, pencarian pohon game rekursif eksponensial tidak akan cukup. Jika Anda ingin melakukan precompute dan melakukan hard-code sebuah strategi, itu tidak masalah.

Memasukkan

Sepasang (i,j)angka non-negatif yang mewakili ukuran tumpukan, masing-masing paling banyak 99. Ini dapat berupa dua angka, tupel, daftar, atau wadah apa pun yang Anda inginkan.

Keluaran

Cetak atau keluarkan posisi setelah Anda bergerak, sekali lagi sebagai dua angka atau wadahnya. Ini harus menjadi langkah hukum ke posisi yang menang. Jika ada beberapa gerakan seperti itu, ada yang baik-baik saja, tetapi hanya satu.

Jika tidak ada langkah kemenangan, Anda harus menunjukkan ini di output. Setiap output seperti False,, None0, atau (-1,-1)akan dilakukan, selama itu bukan posisi hukum, dan sama untuk setiap input yang hilang.

Contoh berjalan

f(5,0)   = (0,0)
f(2,2)   = (1,2)   # Or (2,1) or (0,0) 
f(1,2)   = False
f(13,9)  = (13,8)  # Or (10,6)
f(10,6)  = False
f(5,10)  = (5,3)
f(25,30) = (8,13)    
Tidak
sumber
2
+1, sebagian karena saya menyukai gagasan seperempat tak terhingga.
Level River St
mendefinisikan "jumlah waktu yang masuk akal". Apakah beberapa detik untuk (100,50) waktu yang wajar?
John Dvorak
Oh Tunggu. input dibatasi oleh ... 30 ??? Itu agak rendah, bukan?
John Dvorak
@JanDvorak Anda benar, ini mungkin memungkinkan pintasan murah. Berubah menjadi 99 - saya pikir itu sudah cukup? Permintaan maaf untuk mengedit spesifikasi setelah dikirim.
xnor
@PeterTaylor Terima kasih, sudah diperbaiki.
xnor

Jawaban:

6

Haskell, 167 165 karakter

c p=o p:c(o p:p)
o p=[(a,b)|a<-[0..],b<-[0..a],(a,b)?p==[]]!!0
(a,b)?p=[y|y@(c,d)<-p,c==a||c==b||d==b||a+d==b+c]
f x@(a,b)|a<b=f(b,a)|x?c[]!!0==x=(0,-1)|1>0=x?c[]!!0

Algoritma ini tidak efisien, tetapi masih berjalan dalam hitungan detik (meskipun tidak di konsol interaktif) untuk input <100.

Penjelasan:

c p=o p:c(o p:p)

Daftar posisi dingin yang diberikan satu set posisi dingin sebelumnya adalah satu posisi dingin diikuti oleh daftar posisi dingin yang diberikan posisi ini dan yang sebelumnya (Ketidakefisienan: posisi ini dihasilkan dua kali)

o p=[(a,b)|a<-[0..],b<-[0..a],(a,b)?p==[]]!!0

Satu posisi dingin adalah pasangan pertama sehingga tidak ada posisi dingin yang dapat dicapai dari pasangan itu (Ketidakefisienan: kita harus mencari dari pasangan sebelumnya sebagai gantinya)

(a,b)?p=[y|y@(c,d)<-p,c==a||c==b||d==b||a+d==b+c]

Posisi yang dapat dijangkau dari suatu pasangan adalah posisi sedemikian sehingga elemen pertama cocok, elemen kedua cocok, perbedaan selisih, atau tumpukan lebih kecil sebelum dilepas adalah tumpukan lebih besar setelah dilepas.

f x@(a,b)|a<b=f(b,a)
         |x?c[]!!0==x=(0,-1)
         |1>0=x?c[]!!0

(metode utama) Jika tumpukan berada di urutan yang salah, tukar mereka. Lain, jika posisi dingin pertama yang dapat dicapai dari suatu posisi adalah posisi itu sendiri, menunjukkan kegagalan (idealnya, seseorang akan kembali Maybe (Int,Int)sebagai gantinya). Jika tidak, kembalikan posisi dingin itu (Ketidakefisienan: pasangan ini dilihat dua kali. Lebih buruk lagi, daftar posisi dingin dihasilkan dua kali)

John Dvorak
sumber
Tampaknya " Jadi, pencarian pohon permainan rekursif eksponensial tidak akan cukup " optimis, karena apa yang Anda gambarkan terdengar persis seperti itu.
Peter Taylor
@PeterTaylor ini O (n ^ 4). Setiap pasangan dingin membutuhkan O (n ^ 3) waktu untuk menemukan dan ada O (n) dari mereka. Mengoptimalkan generasi akan membawanya ke O (n ^ 2) (jika saya membaca urutannya dengan benar). Algoritma eksponensial-waktu akan jauh lebih lambat. Haruskah saya menjalankan beberapa tes?
John Dvorak
Tidak apa-apa, saya percaya Anda.
Peter Taylor
Anda dapat menghapus x@x@(a,b)?p=...
haskeller
Tidak yakin bagaimana sampai di sana. Memperbaiki, terima kasih.
John Dvorak
5

GolfScript ( 63 57 byte)

{\]zip{~-}%0|$(!*,1=}+1,4*{..,,^[(.@,2/+.2$]+}38*2/?0]0=`

Mengharapkan input dari stdin dalam formulir [a b], dan meninggalkan output pada stdout dalam bentuk itu atau 0jika itu posisi yang hilang. Demo online

Gambaran

,4*{..,,^[(.@,2/+.2$]+}38*2/

menghitung daftar posisi dingin (termasuk versi membalik [b a]untuk setiap posisi dingin [a b]) menggunakan properti urutan Beatty .

Kemudian ?mencari posisi dingin pertama memuaskan blok yang dibuat oleh

{\]zip{~-}%0|$(!*,1=}+

yang pada dasarnya cek bahwa posisi dicapai dari posisi masukan dengan menghitung perbedaan vektor dan kemudian memverifikasi bahwa itu baik [0 x], [x 0]atau [x x]untuk beberapa x > 0. IMO tes yang adalah pintar bit: 0|$Pasukan setiap array dalam salah satu format ke dalam formulir [0 x]sementara pemetaan [0 0]untuk [0], [a b]di mana tidak ajuga badalah 0untuk array tiga elemen, dan [-x 0]atau [-x -x]untuk[-x 0] . Kemudian (!*,1=periksa yang kita miliki [0 x].

Akhirnya 0]0=`apakah kasus mundur dan format untuk output.

Peter Taylor
sumber
4

Pyth 57 58 61 62

K1.618Jm,s*dKs*d*KKU39M<smf|}TJ}_TJm,-Ghb-Hebt^,0hk2U99 1

Cobalah online.

Cukup mirip dengan jawaban lain, tetapi halaman wikipedia itu tidak memberikan banyak hal lain untuk dilanjutkan;) Angka ajaib 39adalah jumlah posisi dingin dengan nilai < 99.

Menentukan fungsi gyang dapat Anda panggil g 30 25. Pengembalian []untuk kegagalan, [(13,8)]pada kesuksesan.

Penjelasan

K1.618                            : K=phi (close enough for first 39 values)
      Jm,s*dKs*d*KKU39            : J=cold positions with the form (small,big)
M<s                              1: Define g(G,H) to return this slice: [:1] of the list below 
   mf|}TJ}_TJ                     : map(filter: T or reversed(T) in J, where T is each member of..
             m,-Ghb-Hebt^,0hk2    : [(G H) - (0 x+1),(x+1 0) and (x+1 x+1)]
                              U99 : for each x from 0 - 98
FryAmTheEggman
sumber
sdigunakan untuk menyimpan beberapa karakter /____1. rZ39dapat diganti dengan U39, menggunakan rentang unary. Demikian juga, Anda dapat menggantinya r99)dengan U99.
isaacg
@isaacg Terima kasih! Saya benar-benar lupa U. Saya benar-benar harus memperbarui penjelasan: P
FryAmTheEggman
@isaacg Hanya berpikir tentang Pyth, saya pikir Anda bisa @melakukan persimpangan set jika argumen kedua adalah daftar sekarang. Ini agak canggung ditinggalkan sejak adiubah: P
FryAmTheEggman
Itu ide yang bagus - saya sudah menerapkannya. Saya juga mengubah kode persimpangan untuk memungkinkan beberapa trik yang tidak mungkin dilakukan sebelumnya, termasuk mengambil persimpangan dua daftar daftar.
isaacg
2

Javascript ES6 - 280 byte

Diperkecil

r=x=>~~(x*1.618);g=(y,x)=>y(x)?g(y,x+1):x;s=A=>A?[A[1],A[0]]:A;f=(a,b)=>j([a,b])||j([a,b],1);j=(A,F)=>l(A,F)||s(l(s(A),F));l=(A,F)=>([a,b]=A,c=(F&&a+b>=r(b)&&(e=g(x=>a+b-2*x-r(b-x),0))?[a-e,b-e]:(e=g(x=>r(a+x)-2*a-x,0))+a<b?[a,a+e]:(e=r(b)-b)<a?[e,b]:0),c&&r(c[1]-c[0])==c[0]?c:0)

Diperluas

r = x => ~~(x*1.618);
g = (y,x) => y(x) ? g(y,x+1) : x;
s = A =>A ? [A[1],A[0]] : A;
f = (a,b) => j([a,b]) || j([a,b],1);
j = (A,F) => l(A,F) || s(l(s(A),F));
l = (A,F) => (
    [a,b] = A,
    c = (
        F && a+b >= r(b) && (e = g( x => a+b - 2*x - r(b - x), 0 )) ? [a-e,b-e] :
        (e = g( x => r(a+x) - 2*a - x, 0)) + a < b ? [a,a+e] :
        (e = r(b) - b) < a ? [e,b] : 0
    ),
    c && r(c[1] - c[0]) == c[0] ? c : 0
);

Algoritma bagus dan cepat. Berjalan di O (n), tetapi akan berjalan dalam waktu yang konstan jika tidak untuk loop byte-saving. Loop diimplementasikan sebagai incrementer rekursif, karenanya skrip pada akhirnya akan gagal dengan kesalahan rekursi untuk n dalam ratusan atau ribuan. Menggunakan properti urutan Beatty yang sama dengan yang disebutkan Mr. Taylor, tetapi alih-alih menghitung urutannya, ia hanya melangkah ke istilah yang benar.

Berjalan dengan baik pada semua input tes dan banyak lusinan selain itu saya diuji.

Fungsi untuk memanggil adalah f. Ini mengembalikan array pada kesuksesan dan 0menyerah.

COTO
sumber
Tunggu, mengeluarkan array ok?
John Dvorak
@ JanDvorak: xnor memiliki tuple yang tercantum dalam daftar output yang valid, maka saya pikir begitu. Mungkin dia bisa mengklarifikasi masalah ini. Bagaimanapun, ini adalah perbaikan sepele.
COTO
Array atau array tunggal dari pasangan baik-baik saja; beberapa langkah kemenangan tidak.
xnor
1

Perl 5 - 109 (dengan 2 bendera)

#!perl -pl
for$a(@v=0..99){for$b(@v){$c=$a;$d=$b;${$:="$a $b"}||
map{$$_||=$:for++$c.$".++$d,"$a $d","$c $b"}@v}}$_=$$_

Pemakaian:

$ perl wyt.pl <<<'3 5'

$ perl wyt.pl <<<'4 5'
1 2

Cukup hitung solusi untuk setiap input yang mungkin, lalu lakukan pencarian tunggal.

nutki
sumber