11
\$\begingroup\$

Tic-Tac-Latin!

This is a true story, so names have been altered.

My latin teacher, Mr. Latin, created his own proprietary (no joke) tic tac toe variant. Let's call it tic-tac-latin. The game is simple, it is essentially tic tac toe played on a four by four grid.

Formal rule declaration

A line is either a row, column or a diagonal. There are two symbols, 'X' and 'O', but one or both may be substituted for a different symbol.
You score one point when you have three of your symbol and one of the other character.

These arrangements score:

---O
-O--
XXXO
XOOX

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

These do not score:

----
XXXX
----
OOOO

----
XXX-
----
OOO-

The game is won whenever one player has more points then another. The game is a draw only if the board gets filled up.

Challenge

Solve this game. Your job is to provide a way to guarantee a win or tie, whichever is the optimal result.

Your solution may choose to either start first or second (and may therefore choose it's symbol). It is not mandatory to implement an interactive game where the user inputs moves and the corresponding display changes. It may also be a function or program which takes input as a game state, and outputs a new board or a description of their move. Either option must run within approximately ten seconds per move made.


Playing your player against any sequence of moves must give the optimal result. This means that you may assume the input position is one that it reachable from play with your player. Submissions must be deterministic, and do not necessarily need to supply a proof of optimality, but if they get cracked (by being beaten) your submissions will be considered invalid (you may leave it up, but add (cracked) in the headline).
This is a non-trivial task, so any valid submission is impressive and is worthy of an accepted tick, but I will make code golf the primary winning criterion.

The winner is chosen by going down this list till one winner is chosen.

  • Shortest solved implemenation which always wins
  • Shortest implementation
\$\endgroup\$
  • 1
    \$\begingroup\$ "First the quality of play is looked at" Don't you think it's subjective? \$\endgroup\$ – user48538 Sep 23 '16 at 23:22
  • \$\begingroup\$ The task of providing an interface to play seems peripheral of writing a perfect player. I'd suggest simply passing the current game state as input and requiring the code to output a winning move, or even simply an evaluation under perfect play (win, draw, lose). \$\endgroup\$ – xnor Sep 23 '16 at 23:29
  • 1
    \$\begingroup\$ A solution can be golfy by doing an inefficient brute force search. Are you OK if the code runs very slowly? \$\endgroup\$ – xnor Sep 23 '16 at 23:31
  • 1
    \$\begingroup\$ "You win the game if you score and in the process do not score for your opponent." Does this mean that I can only win when I place a piece, not when my opponent does? What happens if a move creates winning lines for both players: game drawn or play on? \$\endgroup\$ – Peter Taylor Sep 24 '16 at 6:30
  • 1
    \$\begingroup\$ @RohanJhunjhunwala You should clarify allowed input of the game state, otherwise it's possible that people may take advantage of the currently undefined input format and choose a format that helps their solution a lot. \$\endgroup\$ – ASCII-only Sep 24 '16 at 7:19
6
\$\begingroup\$

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. The output of this one is also more confusing. It fills in the winning move for X in case of a win without color swap, but if the input game was already won is still does the color swap and does not fill in any move.

All versions of course get faster and use less memory as the board fills up. The faster versions should generate a move in under 10 seconds as soon as 2 or 3 moves have been made.

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.

Here is an interactive driver based on the fastest version mentioned above. The driver has no logic for when the game is finished so you have to stop yourself. The golfed code knows though. If the suggested move returns with no - replaced by anything the game is over.

#!/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;
}
\$\endgroup\$
  • \$\begingroup\$ NIce answer. Could you provide some easy way for me to test this? Ideally it would love to see an interactive version... (this is jut for my own curiosity). \$\endgroup\$ – Rohan Jhunjhunwala Sep 25 '16 at 11:42
  • \$\begingroup\$ @RohanJhunjhunwala Ok, added a simple interactive driver \$\endgroup\$ – Ton Hospel Sep 25 '16 at 15:23
  • \$\begingroup\$ Variable '$move' is not declared at prog.pl:2 \$\endgroup\$ – Rohan Jhunjhunwala Sep 25 '16 at 15:25
  • \$\begingroup\$ Is there a heuristic solution a human can implement? \$\endgroup\$ – Rohan Jhunjhunwala Sep 25 '16 at 15:25
  • \$\begingroup\$ @RohanJhunjhunwala Just rechecked the driver program. Runs fine, $move is declared on line 11. I have no idea if there is a human heuristic. This program just does minimax on the game tree, it doesn't have any strategic knowledge. \$\endgroup\$ – Ton Hospel Sep 25 '16 at 15:33
2
\$\begingroup\$

JavaScript (ES6) 392 bytes

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])

Usage

The "bot" will play second.

Draw a 4x4 grid which are numbered like this:

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

Let's run this in the browser console: Just put f= before the code

So, if I wanna start at 1, I would run f([1])([]) and it will give me 14.

Nice move... What if I play 2 afterwards? f([2,1])([14]). It will return 13.

Lemme try surrendering. Play 3. f([3,2,1])([14,13]). Oh 0! You got me!

Play 0? f([0,2,1])([14,13]). 15 Ok let's keep playing...

Note

  1. Play interactively. Start with f([your-step])([]).

  2. Prepend your next step. (See demo above)

  3. Help the "bot" input its steps. It will not give you good results if you give it a random setting. (Like f([1,2,4])([14,12]) will give 14 - Hey the bot wanted to play on 13 on its second move!

Brief Summary

As long as you are not surrendering, the bot will play a mirror move.

Thanks @EHTproductions for telling me that I misread the game rules and golfing tips :P

Now it will also detect if it got checkmate. If yes, block it!

Its priorities: Block > Mirror > (fallback) look for ways to reproducing a mirror

\$\endgroup\$
  • \$\begingroup\$ I really like the "mirror move" tactic :) I may be misunderstanding, but isn't 3,2,1 for you and 0 for the bot a win for you? \$\endgroup\$ – ETHproductions Sep 24 '16 at 18:47
  • \$\begingroup\$ Oops, I misunderstood as "who captures a pattern of 3 of a kind and 1 of another". Lemme tweak the solution a bit.. Thanks @ETHproductions. \$\endgroup\$ – Sunny Pun Sep 24 '16 at 18:50
  • \$\begingroup\$ A couple of golfing tips: [0,1,2,3].map(i=>{k(n=>n%4==i);k(n=>Math.floor(n/4)==i);}) can be golfed to [0,1,2,3].map(i=>k(n=>n%4==i)+k(n=>(n/4|0)==i)). \$\endgroup\$ – ETHproductions Sep 24 '16 at 18:57
  • \$\begingroup\$ I don't think this is provably winnable \$\endgroup\$ – Rohan Jhunjhunwala Sep 24 '16 at 18:59
  • \$\begingroup\$ 0 - 14 - 12 -13 cracks it \$\endgroup\$ – Rohan Jhunjhunwala Sep 24 '16 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.