Tic-Tac-Latin!

To prawdziwa historia, więc imiona zostały zmienione.

Mój nauczyciel łaciny, pan Latin, stworzył swój własny wariant (bez żartów) kółko i krzyżyk. Nazwijmy to Tic-Tac-Latin. Gra jest prosta, to w zasadzie kółko i krzyżyk rozgrywane na siatce cztery na cztery.

Formalna deklaracja reguły

Linia to albo rząd, kolumna lub przekątna. Istnieją dwa symbole, „X” i „O”, ale jeden lub oba mogą być zastąpione innym symbolem.
Zdobywasz jeden punkt, gdy masz trzy symbole i jedną z pozostałych postaci.

Wynik tych ustaleń:

--- O
-O--
XXXO
XOOX

O -XX
- O -
- X -
--- O

Te nie oceniają:

----
XXXX
----
OOOO

----
XXX
----
OOO-

Gra jest wygrywana, gdy jeden gracz ma więcej punktów niż inny. Gra polega na losowaniu tylko wtedy, gdy plansza się zapełni.

Wyzwanie

Rozwiąż tę grę. Twoim zadaniem jest zapewnienie sposobu na wygraną lub remis, w zależności od tego, który wynik jest optymalny.

Twoje rozwiązanie może rozpocząć od pierwszego lub drugiego (i dlatego może wybrać jego symbol). Nie jest obowiązkowe wdrożenie interaktywnej gry, w której użytkownik wprowadza ruchy i zmienia się odpowiedni ekran. Może to być również funkcja lub program, który przyjmuje dane wejściowe jako stan gry i generuje nową planszę lub opis ich ruchu . Każda opcja musi działać w ciągu około dziesięciu sekund na każdy wykonany ruch.

---

Rozegranie gracza z dowolną sekwencją ruchów musi dać optymalny wynik. Oznacza to, że możesz założyć, że pozycja wejściowa jest możliwa do osiągnięcia w grze z twoim odtwarzaczem. Zgłoszenia muszą być deterministyczne i niekoniecznie muszą dostarczać dowód optymalności, ale jeśli zostaną złamane (przez bicie), zostaną uznane za nieważne (możesz je pominąć, ale dodać (pęknięty) w nagłówku).

---

Jest to nietrywialne zadanie, więc każde prawidłowe zgłoszenie jest imponujące i godne zaakceptowanego tiksa, ale ustawię golfa jako główne kryterium wygranej.

Zwycięzca jest wybierany przez przewijanie tej listy do momentu wybrania jednego zwycięzcy.

• Najkrótsza rozwiązana implementacja, która zawsze wygrywa
  
• Najkrótsza realizacja
  

Perl, 147 bajtów (niekonkurencyjny, zajmuje więcej niż 10 sekund na ruch)

Obejmuje +4 za -0p

Program jest odtwarzany X. Będzie grać w idealną grę.

Wprowadź tablicę na STDIN, np .:

tictaclatin.pl
-X-O
-X--
X-X-
O--O
^D

Ouptut będzie tą samą deską, a wszystkie zostaną Xzastąpione Oi odwrotnie. Puste miejsca zostaną wypełnione liczbą wskazującą wynik, jeśli X tam zagra, 1co oznacza, że ​​wynikiem będzie zwycięstwo, 2remis i 3przegrana. Ukończona gra po prostu zwraca tę samą pozycję z odwróconymi kolorami.

W tym przykładzie dane wyjściowe to:

1O1X
1O33
O3O3
X33X

Tak więc pozycja jest wygrana, Xjeśli gra w 3 miejscach u góry i po lewej stronie. Wszystkie pozostałe ruchy tracą.

Ten mylący wynik jest w rzeczywistości wygodny, jeśli chcesz wiedzieć, jak gra się rozwija po ruchu. Ponieważ program zawsze gra X, musisz zamienić Xi Ozobaczyć ruchy O. Na przykład tutaj jest całkiem jasne, że Xwygrywa, grając w lewym górnym rogu, ale co jeśli Xgra w trzeciej pozycji u góry? Po prostu skopiuj dane wyjściowe, umieść Omiejsce w miejscu wybranego ruchu i zamień ponownie wszystkie inne liczby -, więc tutaj:

-OOX
-O--
O-O-
X--X

Wynikające z:

3XXO
3X33
X3X3
O33O

Oczywiście każdy ruch Opowinien przegrać, więc jak on przegrywa, jeśli gra w lewym górnym rogu? Ponownie zrób to, umieszczając Ow lewym górnym rogu i zastępując cyfry -:

OXXO
-X--
X-X-
O--O

Dający:

XOOX
1O33
O3O3
X33X

Więc X ma tylko jedną drogę do zwycięstwa:

XOOX
OO--
O-O-
X--X

Dający

OXXO
XX33
X3X3
O33O

Sytuacja Opozostaje beznadziejna. Teraz widać, że każdy ruch pozwala Xod razu wygrać. Spróbujmy przynajmniej wybrać 3 O z rzędu:

OXXO
XX--
X-X-
O-OO

Dający:

XOOX
OO13
O3O3
X3XX

Xgra jedyny zwycięski ruch (zauważ, że robi to XXXOwzdłuż trzeciej kolumny:

XOOX
OOO-
O-O-
X-XX

Oto wynik:

OXXO
XXX-
X-X-
O-OO

ponieważ gra była już ukończona. Wygraną możesz zobaczyć w trzeciej kolumnie.

Rzeczywisty program tictaclatin.pl:

#!/usr/bin/perl -0p
y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/sx;$@<=>0||s%-%$_="$`O$'";$$_||=2+do$0%eg&&(/1/||/2/-1)

Zastosowane do pustej planszy, ocenia 9506699 pozycji, co zajmuje 30 Gb i 41 minut na moim komputerze. Wynik to:

2222
2222
2222
2222

Tak więc każdy ruch początkowy dobiera. Ta gra to remis.

Ekstremalne użycie pamięci jest spowodowane głównie przez użycie rekurencji do$0. Korzystanie z tej 154-bajtowej wersji przy użyciu zwykłej funkcji wymaga 3Gb i 11 minut:

#!/usr/bin/perl -0p
sub f{y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/sx;$@<=>0||s%-%$_="$`O$'";$$_||=2+&f%eeg&&(/1/||/2/-1)}f

co jest bardziej znośne (ale wciąż za dużo, coś wciąż musi przeciekać pamięć).

Połączenie kilku przyspieszeń prowadzi do tej 160-bajtowej wersji (5028168 pozycji, 4 minuty i 800 M dla pustej planszy):

#!/usr/bin/perl -0p
sub f{y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/osx;$@<=>0||s%-%$_="$`O$'";$a{$_}//=&f+1or return 1%eeg&&/1/-1}f

Ten ostatni wykorzystuje 0do wygranej (nie mylić z O), 1do remisu i 2do przegranej. Wydajność tego jest również bardziej myląca. Wypełnia wygrywający ruch dla X w przypadku wygranej bez zamiany kolorów, ale jeśli gra wejściowa została już wygrana, nadal zamienia kolor i nie wypełnia żadnego ruchu.

Wszystkie wersje oczywiście przyspieszają i zużywają mniej pamięci w miarę zapełniania się płyty. Szybsze wersje powinny wygenerować ruch w niecałe 10 sekund, jak tylko zostaną wykonane 2 lub 3 ruchy.

Zasadniczo ta 146-bajtowa wersja powinna również działać:

#!/usr/bin/perl -0p
y/XO/OX/,$@=-$@while/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^/sx,--$|;$@<=>0||s%-%$_="$`O$'";$$_||=2+do$0%eg&&(/1/||/2/-1)

ale na mojej maszynie uruchamia błąd perla i zrzuca rdzeń.

Wszystkie wersje będą w zasadzie nadal działać, jeśli $$_||=usunięte zostanie buforowanie 6-bajtowej pozycji, ale zajmuje to tyle czasu i pamięci, że działa tylko w przypadku prawie wypełnionych kart. Ale teoretycznie mam przynajmniej 140 bajtowe rozwiązanie.

Jeśli umieścisz $\=(koszt: 3 bajty) tuż przed $@<=>0czym każda płyta wyjście nastąpi statusu całego Zarządu: 1do Xzwycięstw, 0za remis i -1za utratę.

Oto interaktywny sterownik oparty na najszybszej wersji wspomnianej powyżej. Kierowca nie ma logiki po zakończeniu gry, więc musisz się zatrzymać. Kod w golfa jednak wie. Jeśli sugerowany ruch powróci bez -zastąpienia go przez cokolwiek, gra się kończy.

#!/usr/bin/perl
sub f{
    if ($p++ % 100000 == 0) {
        local $| = 1;
        print ".";
    }
y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/osx;$@<=>0||s%-%$_="$`O$'";$a{$_}//=&f+1or return 1%eeg&&/1/-1}

# Driver
my $tomove = "X";
my $move = 0;
@board = ("----\n") x 4;
while (1) {
    print "Current board after move $move ($tomove to move):\n  ABCD\n";
    for my $i (1..4) {
        print "$i $board[$i-1]";
    }
    print "Enter a move like B4, PASS (not a valid move, just for setup) or just press enter to let the program make suggestions\n";
    my $input = <> // exit;
    if ($input eq "\n") {
        $_ = join "", @board;
        tr/OX/XO/ if $tomove eq "O";
        $p = 0;
        $@="";
        %a = ();
        my $start = time();
        my $result = f;
        if ($result == 1) {
            tr/OX/XO/ if $tomove eq "O";
            tr/012/-/;
        } else {
            tr/OX/XO/ if $tomove eq "X";
            tr/012/123/;
        }
        $result = -$result if $tomove eq "O";
        my $period = time() - $start;
        print "\nSuggested moves (evaluated $p positions in $period seconds, predicted result for X: $result):\n$_";
        redo;
    } elsif ($input =~ /^pass$/i) {
        # Do nothing
    } elsif (my ($x, $y) = $input =~ /^([A-D])([1-4])$/) {
        $x = ord($x) - ord("A");
        --$y;
        my $ch = substr($board[$y],$x, 1);
        if ($ch ne "-") {
            print "Position already has $ch. Try again\n";
            redo;
        }
        substr($board[$y],$x, 1) = $tomove;
    } else {
        print "Cannot parse move. Try again\n";
        redo;
    }
    $tomove =~ tr/OX/XO/;
    ++$move;
}

JavaScript (ES6) 392 bajty

a=>b=>(c="0ed3b56879a4c21f",r=[],k=f=>r.push([a.filter(f),b.filter(f)]),[0,1,2,3].map(i=>k(n=>n%4==i)+k(n=>(n/4|0)==i)),k(n=>n%5==0),k(n=>n&&n-15&&!(n%3)),g=r.find(o=>(o[0].length==1&&o[1].length==2)||(o[0].length==2&&o[1].length==1)),g?parseInt(c[30-[...g[0],...g[1]].map(i=>parseInt(c[i],16)).reduce((p,c)=>p+c)],16):[...a,...b].indexOf(15-a[0])+1?15-a.find(i=>b.indexOf(15-i)==-1):15-a[0])

Stosowanie

„Bot” zagra na drugim miejscu.

Narysuj siatkę 4x4, które są ponumerowane w następujący sposób:

+----+----+----+----+
|  0 |  1 |  2 |  3 |
+----+----+----+----+
|  4 |  5 |  6 |  7 |
+----+----+----+----+
|  8 |  9 | 10 | 11 |
+----+----+----+----+
| 12 | 13 | 14 | 15 |
+----+----+----+----+

Uruchommy to w konsoli przeglądarki: po prostu umieść f=przed kodem

Tak więc, jeśli chcę zacząć od 1, ucieknę f([1])([])i da mi to 14.

Niezły ruch ... Co jeśli zagram 2później? f([2,1])([14]). Wróci 13.

Pozwól mi się poddać. Grać 3. f([3,2,1])([14,13]). Och 0! Masz mnie!

Grać 0? f([0,2,1])([14,13]). 15Ok, grajmy dalej ...

Uwaga

1. Graj interaktywnie. Zacznij od f([your-step])([]).

2. Przygotuj następny krok. (Zobacz demo powyżej)

3. Pomóż „botowi” wprowadzić swoje kroki. Nie da ci dobrych wyników, jeśli nadasz mu losowe ustawienie. (Jak f([1,2,4])([14,12])da 14- Hej bot chciał zagrać 13w swoim drugim ruchu!

Krótkie podsumowanie

Tak długo, jak się nie poddajesz, bot będzie wykonywać ruch lustra.

Dzięki @EHTproductions za poinformowanie mnie, że źle przeczytałem zasady gry i wskazówki dotyczące gry w golfa: P

Teraz wykryje również, czy dostał mat. Jeśli tak, zablokuj to!

Jego priorytety: Blok> Lustro> (awaryjne) szukają sposobów na odtworzenie lustra