Wszyscy zdają sobie sprawę, że Tic Tac Toe to rozwiązana gra. Jednak wersja Misère only-Xs stanowi ciekawą alternatywę.

W tej wersji gry obaj gracze grają X na planszy i starają się unikać trzech z rzędu. Jeśli chcesz dowiedzieć się więcej na ten temat, Numberphile ma fajne wideo na temat tej koncepcji.

Biorąc pod uwagę planszę Misère Crosses, zagraj optymalnie.

Plansza składa się z trzech linii po trzy znaki każda, które są Xlub . A zatem:

X X
X  
 XX

jest prawidłową tablicą. Możesz wziąć to w dowolnym dogodnym formacie, o ile dane wejściowe i wyjściowe mają ten sam format. Formaty obejmują (ale nie wyłącznie): Wieloliniowy ciąg znaków (z opcjonalnym końcowym znakiem nowej linii); Tablica znaków 2D, które są Xlub ; spłaszczona tablica wartości logicznych 1D reprezentujących, czy każda pozycja została zagrana.

Optymalny ruch to taki, który gwarantuje wygraną przez kontynuowanie optymalnej gry lub przedłuża przegraną tak długo, jak to możliwe, i jest określony przez następujące zasady:

• Unikaj robienia trzech z rzędu.
• Jeśli pójdziesz pierwszy, zagraj w środku.
• Jeśli jedynym zajętym miejscem jest środek, zagraj na jednym z pozostałych pól.
• Jeśli środkowy kwadrat nie jest zajęty, a zewnętrzny jest, zagraj naprzeciwko ostatniej gry przeciwnika.
• Jeśli środkowy kwadrat jest zajęty, a zewnętrzny kwadrat jest, zagraj „ruch rycerzy” (przeciwnie, jeden ponad) od poprzedniego ruchu, który nie spowoduje przegranej.
• Jeśli nie pozostaną żadne kwadraty, w których nie przegrasz, zagraj na jednym z pozostałych kwadratów.

[UWAGA: okazało się, że nie jest to optymalne w jednym przypadku, ale i tak należy użyć tego algorytmu.]

Możesz założyć, że wszystkie poprzednie ruchy były optymalne. Zatem pierwsza przykładowa tablica nie jest prawidłowym wejściem. Ruchy twojego przeciwnika mogą być optymalne.

Jeśli gra się zakończyła (tj. Wykonano trzy z rzędu), zachowanie jest niezdefiniowane.

Ponieważ jest to kod-golf , wygrywa najkrótsza odpowiedź w bajtach!

Jedną z możliwych ścieżek, wykorzystującą tylko optymalne ruchy, jest:

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

Oto możliwe dane wejściowe pochodzące od przeciwnika przy użyciu nieoptymalnych ruchów:
(Uwaga: tylko lewe plansze na tej liście są prawidłowymi danymi wejściowymi).

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

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

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

Ruby, Rev B 121 bajtów

Składanie jest funkcją anonimową, pomniejszoną o f=. Pokazane w programie testowym, aby zilustrować użycie.

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 bajty zapisane przez uczynienie środkowego kwadratu najmniej znaczącym bitem zamiast najbardziej znaczącego bitu (usuń przez /2zamiast %256.) Pozostałe oszczędności poprzez reorganizację tabeli dopuszczalnych ruchów. Porządkowanie jako wolny kwadrat / zajęty zamiast całkowitej liczby X pozwala na prostszy test. Ponadto, teraz są tylko 2 ciągi w tablicy, więc %w{string1 string2}składnia jest porzucana na rzecz ["string1","string2"]składni. Umożliwia to włączenie znaku niedrukowalnego \7, co z kolei umożliwia zastosowanie prostszego kodowania: 126-tzamiast (36-t)%120.

Ruby, Rev A 143 bajty

->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}

To anonimowa funkcja. Format wejściowy / wyjściowy pozostawiono otwarty, więc wybrałem 9-bitową liczbę binarną. bit 512 reprezentuje środek, a pozostałe bity spiralnie go otaczają (bit 1 jest uważany za narożnik).

Istnieje znacznie więcej możliwych danych wejściowych niż akceptowalne dane wyjściowe, więc algorytm polega na wypróbowaniu wszystkich ruchów i znalezieniu takiego, który pasuje do akceptowalnego wzorca wyjściowego. Dopuszczalne wzorce wyjściowe dla każdej liczby X są zakodowane na stałe.

Informacje o środkowym kwadracie są usuwane, a pozostałe 8 bitów jest mnożone przez 257, aby je zduplikować. Ten wzór jest następnie obracany poza dopuszczalne wzorce poprzez przesunięcie w prawo.

Pętla nie jest opuszczana po znalezieniu wzorca, więc zwrócony wzorzec będzie OSTATNI dopuszczalny znaleziony wzorzec. Z tego powodu preferowane wzorce (tam, gdzie są preferencje) pojawiają się później na liście.

Biorąc pod uwagę strategię ruchu Rycerzy, nie ma znaczenia, czy wzór zostanie obrócony o 45 stopni, czy nie. Wersja bez golfa jest zgodna ze strategią ruchu rycerzy i dlatego nie musi rozróżniać kwadratów narożnych i kwadratowych krawędzi: i tak należy unikać trzech z rzędu.

Stwierdziłem jednak, że nie zawsze jest to najlepsza strategia, ponieważ istnieje następująca sztuczka. Jeśli twój przeciwnik pójdzie pierwszy i przejmie centrum, powinien wygrać. Ale w drugim ruchu popełnia błąd, pozwalając ci zrobić kwadrat 2x2, powinieneś go wziąć, ponieważ pozwala to zmusić go do zrobienia trzech z rzędu. Jest to realizowane w wersji golfowej. W tym jednym przypadku potrzebny jest dodatkowy kod, aby odróżnić trzy X w rogu (zmusić przeciwnika do przegrania) i 3 X wzdłuż jednej krawędzi (natychmiastowe samobójstwo).

Niegolfowany w programie testowym

Wersja bez golfa jest zgodna z logiką wyrażoną w pytaniu.

W wersji golfowej stół jest nieco zmodyfikowany, [[0],[1,17],[9],[37,7,51,85],[45],[47,119]]aby wprowadzić nieco inne zachowanie w przypadku r=3. Następnie jest kompresowany do formatu ASCII do wydruku (wymagającego dekodowania (t-36)%120). Dodatkowy kawałek logiki jest wymagany do rozróżnienia między trzema X w rogu i trzema X wzdłuż krawędzi w przypadku wpisu w tabeli 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}

Wyjście programu testowego

To się dzieje, gdy komputer się odtwarza.

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

PIERWSZA ANALIZA GRY

Jest to w rzeczywistości bardzo proste i liniowe.

Kiedy grasz pierwszy, środkowy kwadrat zawsze będzie pierwszym zajmowanym polem.

r = 0

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

r = 2

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

r = 4

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

Jest tylko jeden sposób (aż do symetrii), aby mieć pięć X, w tym środkowy kwadrat na planszy, bez zakończenia gry. W środkowym kwadracie znajduje się X, jeden na każdej przekątnej (90 stopni względem siebie) i jeden na każdej poziomej / pionowej linii środkowej (90 stopni względem siebie). Ponieważ nie można zająć całej krawędzi, powyższe jest jedynym możliwe ustawienie. Drugi gracz musi przegrać w następnym ruchu.

ANALIZA GRY ODTWARZANIE DRUGIEGO

Gra jest zupełnie inna, w zależności od tego, czy inny gracz wybierze środkowy kwadrat.

r = 1

zajmowany środkowy kwadrat

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

środkowy kwadrat wolny

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

r = 3

Zajęty środkowy kwadrat, jeśli inny gracz gra w sąsiedztwie twojego ostatniego X Rozgrywanie rycerza odejścia, jak poniżej, jest obsługiwane w wersji bez golfa

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

Jednak powyższe NIE jest najlepszym ruchem i nie jest obsługiwane w wersji golfowej. Najlepszy ruch jest następujący, co wymusza zwycięstwo w następnej turze:

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

Zajęty środkowy kwadrat, jeśli inny gracz gra pod kątem 90 lub 135 stopni do twojego ostatniego X (odsuń rycerza).

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

Środkowy kwadrat wolny

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

r = 5

zajmowany środkowy kwadrat. Z powodów podanych powyżej w = 4 istnieją cztery możliwe ruchy, z których wszystkie tracą. obsługiwany jest tylko jeden: 101111 = 47.

środkowy kwadrat wolny. Istnieje tylko jedna możliwa plansza do symetrii, jak pokazano poniżej. Inny gracz musi przegrać w następnym ruchu, więc nie ma potrzeby wspierania r> 5.

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