Perl, 147 bytes
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 XXOX
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. Both version 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.