Perl, 147 bytes (non competing, takes more than 10 seconds per move)
Includes +4 for -0p
The program plays X
. It will play a perfect game.
Input the board on STDIN, e.g.:
tictaclatin.pl
-X-O
-X--
X-X-
O--O
^D
The ouptut will be the same board with all X
replaced by O
and vice versa. The empty spots will be filled with a number indicating the result if X would play there, with 1
meaning the result will be a win, 2
a draw and 3
a loss. A finished game just returns the same position with the colors reversed.
In this example the output would be:
1O1X
1O33
O3O3
X33X
So the position is a win for X
if he plays in the 3 spots along the top and the left. All other moves lose.
This confusing output is actually convenient if you want to know how the game continues after a move. Since the program always plays X
you have to swap X
and O
to see the moves for O
. Here for example it's pretty clear that X
wins by playing in the top left, but what about if X
plays in the third position along the top ? Just copy the output, put an O
in place of the move you select and replace all other numbers by -
again, so here:
-OOX
-O--
O-O-
X--X
Resulting in:
3XXO
3X33
X3X3
O33O
Obviously every move by O
should lose, so how does he lose if he plays in the top left ? Again do this by putting O
in the top left and replacing the digits by -
:
OXXO
-X--
X-X-
O--O
Giving:
XOOX
1O33
O3O3
X33X
So X has only one way to go for his win:
XOOX
OO--
O-O-
X--X
Giving
OXXO
XX33
X3X3
O33O
The situation for O
remains hopeless. It's easy to see now that every move allows X
to immediately win. Let's at least try to go for 3 O's in a row:
OXXO
XX--
X-X-
O-OO
Giving:
XOOX
OO13
O3O3
X3XX
X
plays the only winning move (notice that this makes XXXO
along the third column:
XOOX
OOO-
O-O-
X-XX
Here the output is:
OXXO
XXX-
X-X-
O-OO
because the game was already finished. You can see the win on the third column.
The actual 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)
Applied to the empty board this evaluates 9506699 positions which takes 30Gb and 41 minutes on my computer. The result is:
2222
2222
2222
2222
So every starting move draws. So the game is a draw.
The extreme memory usage is mostly caused by the recursion using do$0
. Using this 154 byte version using a plain function needs 3Gb and 11 minutes:
#!/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
which is more bearable (but still too much, something must still be leaking memory).
Combining a number of speedups leads to this 160 byte version (5028168 positions, 4 minutes and 800M for the empty board):
#!/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
That last one uses 0
for a win (don't confuse with O
), 1
for a draw and 2
for a loss.
All versions of course get faster and use less memory as the board fills up.
In principle this 146 byte version should also work:
#!/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)
but on my machine it triggers a perl bug and dumps core.
All versions will in principle still work if the 6 byte position caching done by $$_||=
is removed but that uses so much time and memory that it only works for almost filled boards. But in theory at least I have a 140 byte solution.
If you put $\=
(cost: 3 bytes) just before the $@<=>0
then each output board will be followed by the status of the whole board: 1
for X
wins, 0
for draw and -1
for loss.