Semua orang menyadari bahwa Tic Tac Toe adalah permainan yang diselesaikan. Namun, versi Misère hanya-Xs memberikan alternatif yang menarik.

Dalam versi gim ini, kedua pemain memainkan Xs di papan tulis dan mencoba menghindari membuat tiga berturut-turut. Jika Anda ingin melihat lebih banyak tentang ini, Numberphile memiliki video yang bagus tentang konsep ini.

Diberi papan Misere Crosses, mainkan gerakan optimal.

Papan adalah tiga baris yang masing-masing terdiri dari tiga karakter, yaitu Xatau . Jadi:

X X
X  
 XX

adalah papan yang valid. Anda dapat mengambil ini dalam format yang mudah digunakan, selama input dan output Anda menggunakan format yang sama. Format termasuk (tetapi tidak terbatas pada): String multi-baris (dengan baris tambahan opsional); Array 2D karakter yang Xatau ; array 1D nilai boolean yang direpresentasikan mewakili jika setiap posisi telah dimainkan.

Langkah optimal adalah langkah yang menjamin Anda akan menang dengan terus bermain secara optimal atau memperpanjang kekalahan Anda selama mungkin dan ditentukan oleh aturan berikut:

• Hindari membuat tiga berturut-turut.
• Jika Anda duluan, mainkan di tengah.
• Jika satu-satunya ruang yang ditempati adalah tengah, mainkan di salah satu ruang yang tersisa.
• Jika alun-alun tengah tidak ditempati dan lapangan luar adalah, mainkan berlawanan dengan permainan terakhir lawan Anda.
• Jika alun-alun tengah ditempati dan sebuah alun-alun luar, mainkan "gerakan ksatria" (berlawanan, satu di atas) dari langkah sebelumnya yang tidak menyebabkan Anda kalah.
• Jika tidak ada kotak yang tersisa di mana Anda tidak akan kalah, mainkan di salah satu kotak yang tersisa.

[CATATAN: ini terbukti tidak optimal dalam satu kasus tetapi Anda tetap harus menggunakan algoritma ini.]

Anda dapat mengasumsikan bahwa semua gerakan Anda sebelumnya optimal. Jadi, papan contoh pertama bukanlah input yang valid. Gerakan lawan Anda mungkin atau mungkin tidak optimal.

Jika permainan telah berakhir (yaitu tiga berturut-turut telah dibuat), perilaku tidak ditentukan.

Karena ini adalah kode-golf , jawaban tersingkat dalam byte menang!

Satu jalur yang memungkinkan, hanya menggunakan gerakan optimal, adalah ini:

[   ]  [   ]  [X  ]  [X  ]  [X  ]  [X  ]  [XX ]
[   ]->[ X ]->[ X ]->[ XX]->[ XX]->[ XX]->[ XX]
[   ]  [   ]  [   ]  [   ]  [ X ]  [XX ]  [XX ]

Berikut adalah input yang mungkin berasal dari lawan menggunakan gerakan yang tidak optimal:
(Perhatikan bahwa hanya papan sisi kiri dalam daftar ini yang merupakan input yang valid.)

[X  ]  [X  ]
[   ]->[   ]
[   ]  [  X]

[XX ]  [XX ]
[   ]->[   ]
[  X]  [ XX]

[XX ]  [XX ]
[X  ]->[X X]
[ XX]  [ XX]

Ruby, Rev B 121 byte

Pengiriman adalah fungsi anonim, minus f=. Ditampilkan dalam program uji untuk menggambarkan penggunaan.

f=->n{["~mK)\7","}uYwQO"][l=n%2].bytes{|t|9.times{|i|(m=n|1<<i)==n||8.times{|j|m/2*257>>j&255==126-t&&t+j%2!=119&&l=m}}}
l}

puts g=f[gets.to_i]
puts
[7,6,5,
 8,0,4,
 1,2,3].each{|i|print g>>i&1; puts if i/3==1}

2 byte disimpan dengan menjadikan pusat kuadrat sebagai bit paling signifikan alih-alih bit paling signifikan (hapus dengan /2alih-alih %256.) Sisa tabungan dengan reorganisasi tabel gerakan yang dapat diterima. Pengorganisasian sebagai pusat kuadrat bebas / ditempati alih-alih dengan jumlah X memungkinkan uji sederhana. Juga, sekarang hanya ada 2 string dalam array sehingga %w{string1 string2}sintaksis ditinggalkan demi ["string1","string2"]sintaks. Ini memungkinkan karakter yang tidak \7dapat dicetak untuk dimasukkan, yang pada gilirannya memungkinkan pengkodean yang lebih sederhana untuk digunakan: 126-talih-alih (36-t)%120.

Ruby, Rev A 143 byte

->n{l=r=("%b"%n).sum%8
%w{$ %5 - I+Wy Q S#}[r].bytes{|t|9.times{|i|(m=n|1<<i)==n||8.times{|j|m%256*257>>j&255==(t-36)%120&&t+j%2!=43&&l=m}}}
l}

Ini adalah fungsi anonim. Format input / output dibiarkan terbuka, jadi saya menggunakan nomor biner 9-bit. bit 512 mewakili pusat, dengan bit yang tersisa berputar di sekelilingnya (bit 1 dianggap sebagai sudut.)

Ada jauh lebih banyak input yang mungkin daripada output yang dapat diterima, jadi algoritma ini adalah untuk mencoba semua gerakan, dan menemukan satu yang cocok dengan pola output yang dapat diterima. Pola keluaran yang dapat diterima untuk setiap angka X adalah hardcoded.

Informasi tentang pusat persegi dilucuti dan 8 bit yang tersisa dikalikan dengan 257 untuk menduplikatnya. Pola ini kemudian diputar melewati pola yang dapat diterima dengan pengalihan hak.

Loop tidak keluar ketika pola ditemukan, sehingga pola yang dikembalikan akan menjadi pola TERAKHIR yang ditemukan. Untuk alasan ini, pola yang lebih disukai (di mana ada preferensi) datang kemudian dalam daftar.

Mengingat strategi 'Ksatria bergerak', tidak penting apakah sebuah pola diputar 45 derajat atau tidak. Versi ungolfed mengikuti strategi ksatria bergerak dan karena itu tidak perlu membedakan antara kotak sudut dan kotak tepi: tiga berturut-turut harus dihindari.

Namun, saya menemukan bahwa ini tidak selalu merupakan strategi terbaik, karena ada trik berikut. Jika lawan Anda duluan dan mengambil pusat dia harus menang. Tetapi pada langkah keduanya, ia membuat kesalahan dengan mengizinkan Anda membuat kotak 2x2, Anda harus mengambilnya, karena ini memungkinkan Anda untuk memaksanya membuat tiga berturut-turut. Ini diimplementasikan dalam versi golf. Diperlukan sedikit kode tambahan dalam satu contoh ini untuk membedakan antara tiga X di sudut (memaksa lawan untuk kalah) dan 3 X di satu sisi (bunuh diri langsung.)

Tidak digabungkan dalam program uji

Versi ungolfed mengikuti logika yang diungkapkan dalam pertanyaan.

Dalam versi golf, tabel sedikit dimodifikasi [[0],[1,17],[9],[37,7,51,85],[45],[47,119]]untuk menerapkan perilaku yang sedikit berbeda untuk kasus ini r=3. Ini kemudian dikompres ke ASCII yang dapat dicetak (membutuhkan decoding (t-36)%120). Sedikit tambahan logika diperlukan untuk membedakan antara tiga X di sudut dan tiga X di sepanjang tepi dalam kasus entri tabel 7:&&t+j%2!=43

f=->n{l=r=("%b"%n).sum%8                                      #convert input to text, take character checksum to count 1's(ASCII 49.) 
                                                              #0 is ASCII 48, so %8 removes unwanted checksum bloat of 48 per char.
                                                              #l must be initialised here for scoping reasons.
  [[0],[1,17],[9],[11,13,37,51,85],[45],[47,119]][r].each{|t| #according to r, find the list of acceptable perimeter bitmaps, and search for a solution.
    9.times{|i|(m=n|1<<i)==n||                                #OR 1<<i with input. if result == n, existing X overwritten, no good.
                                                              #ELSE new X is in vacant square, good. So.. 
      8.times{|j|m%256*257>>j&255==t&&l=m}}                   #%256 to strip off middle square. *257 to duplicate bitmap.
                                                              #rightshift, see if pattern matches t. If so, write to l
  }
l}                                                            #return l (the last acceptable solution found) as the answer.

#call function and pretty print output (not part of submission)
puts g=f[gets.to_i]
puts
[6,7,0,
 5,8,1,
4,3,2].each{|i|print g>>i&1; puts if i<3}

Output dari program uji

Inilah yang terjadi ketika komputer bermain sendiri.

C: \ Users \ steve> ruby ​​tictac.rb
0
256

000
010
000

C: \ Users \ steve> ruby ​​tictac.rb
256
384

010
010
000

C: \ Users \ steve> ruby ​​tictac.rb
384
400

010
010
100

C: \ Users \ steve> ruby ​​tictac.rb
400
404

010
010
101

C: \ Users \ steve> ruby ​​tictac.rb
404
436

010
110
101

C: \ Users \ steve> ruby ​​tictac.rb
436
444

010
110
111

GAME ANALISIS PEMAIN PERTAMA

Ini sebenarnya sangat sederhana dan linier.

Saat bermain pertama, alun-alun tengah akan selalu menjadi alun-alun pertama yang ditempati.

r = 0

...  binary representation 0
.X.
...

r = 2

X..  binary representation 1001=9 
.XX
...

r = 4

X.. binary representation 101101=45
.XX
XX.

Hanya ada satu cara (hingga simetri) untuk memiliki lima X termasuk alun-alun tengah di papan tanpa permainan berakhir. Ada X di alun-alun tengah, satu di setiap diagonal (pada 90 derajat satu sama lain) dan satu pada setiap garis tengah horizontal / vertikal (pada 90 derajat satu sama lain.) Karena seluruh tepi tidak dapat ditempati di atas adalah satu-satunya pengaturan mungkin. Pemain lain harus kalah pada langkah selanjutnya.

ANALISIS GAME BERMAIN KEDUA

Bermain sangat berbeda tergantung jika pemain lain memilih alun-alun tengah.

r = 1

alun-alun tengah ditempati

.X. X..  binary representation 1 
.X. .X.
... ...

kotak tengah gratis

X.. .X. binary representation 10001=17
... ...
..X .X.

r = 3

Alun-alun tengah ditempati, jika pemain lain bermain berdekatan dengan X terakhir Anda, Memutar ksatria menjauh seperti di bawah ini didukung dalam versi yang tidak diserang

XX. .XX binary representation 1011=11 
.X. XX. or mirror image 1101=13
X.. ...

Namun di atas BUKAN langkah terbaik dan tidak didukung dalam versi golf. Langkah terbaik adalah sebagai berikut, memaksakan kemenangan pada giliran berikutnya:

XX. binary representation 111=7.           XXX
XX. Only to be used where j is odd.        .X.
... Even j would look like image to right. ...

Alun-alun tengah ditempati, jika pemain lain bermain di 90 atau 135 derajat ke X terakhir Anda (bermain ksatria menjauh.)

X.X .X. binary representation 100101=37 
.X. .XX
.X. X..

Kotak tengah gratis

X.X .X. XX. binary representations:
... X.X ...    1010101=85 (first two)
X.X .X. .XX and 110011=51 (last one)

r = 5

alun-alun tengah ditempati. Untuk alasan yang disebutkan di atas dalam r = 4, ada empat kemungkinan gerakan, yang semuanya kalah. hanya satu yang didukung: 101111 = 47.

kotak tengah gratis. Hanya ada satu kemungkinan papan hingga simetri, sebagai berikut. Pemain lain harus kalah pada langkah selanjutnya, jadi tidak perlu mendukung r> 5.

XX. binary representation 1110111=119
X.X
.XX