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