Skip to main content
3 of 8
edited body
Ton Hospel
  • 14.9k
  • 1
  • 22
  • 45

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 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 be leaking memory). 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.

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.

Ton Hospel
  • 14.9k
  • 1
  • 22
  • 45