Optimal Games of Tic Tac Torus

Question

This challenge is about the game Tic Tac Toe, but it's played on a torus.

How to play

To create the necessary game board, you start out with a regular Tic Tac Toe game board. First fold it into a cylinder by joining the left and the right edge. Then fold it into torus by joining the top and the bottom edge. Here's a simple visualization of such a game board with a few moves played (Sick Paint skills!).

The rules of Tic Tac Toe on a torus are the same as regular Tic Tac Toe. Each Player place alternating Xs and Os. The first one with 3 same symbols in a row, a column or a in a diagonal wins.

Since a torus is quite hard to visualize, we simply project the board back onto a paper. Now we can play the game as regular Tic Tac Toe. The only difference is, that you can also win with 3 same symbols in a broken diagonal. For instance Player 1 (X) wins the following board. You can see this easily by changing the view on the torus a little bit.

If your interested, you can play Tic Tac Toe on a Torus at Torus Games. There's a Windows, Mac and Android version.

Optimal Games

In this challenge were interested in optimal games. An optimal game is a game, where both players play an optimal strategy. On a regular Tic Tac Toe board optimal games always end in a draw. Fascinatingly on a torus board always the first player wins. In fact a game on a torus board can never end in a draw (also if the players play not optimal).

The optimal strategy is really easy:

• If you can win by placing your symbol, do it.
• Otherwise if your opponent has two symbols in one row/column/điagonal, try to block him. Otherwise, do what you want.
• Otherwise do what you want.

Every optimal game consists of exactly 7 moves and these moves can be described in the following way:

1. Player 1 places a X anywhere on the board (9 choices)
2. Player 2 places an O anywhere on the board (8 choices)
3. Player 1 places a X anywhere on the board (7 choices)
4. Player 2's move may be forced (1 choice), if not, he places the O anywhere (6 choices)
5. Player 1's move is forced (1 choice)
6. Player 2 is caught in a fork (Player 1 can win in two different ways), so Player 2 has to block Player 1 in one way (2 choices)
7. Player 1 places the his last move and wins (1 choice)

There are 9*8*1*6*1*2*1 + 9*8*6*1*1*2*1 = 1728 different optimal games on our projected board. Here you can see one typical optimal game:

If we label each cell of the board with the digits 0-8, we can describe this game by the digits 3518207. First a X is places in the cell 3 (middle row, left column), than an O in cell 5 (middle row, right column), than a X in cell 1 (upper row, middle column), ...

Using this digit notation we automatically generated an order. Now we can sort all of the 1728 optimal games and we get the list:

Game 0000: 0123845
Game 0001: 0123854
Game 0002: 0124735
Game 0003: 0124753
Game 0004: 0125634
   ...
Game 0674: 3518207
   ...
Game 1000: 5167423
Game 1001: 5167432
Game 1002: 5168304
   ...
Game 1726: 8765034
Game 1727: 8765043

Challenge

This list is part of your job. You will receive one number k between 0 and 1727 and you have to return the kth game in digit notation of that sorted list.

Write a function or a program, that receives the number k (integer) computes the correspondent game. You can read the input via STDIN, command-line argument, prompt or function argument and print the result (7 digits) in a readable format (e.g. 0123845 or [0, 1, 2, 3, 8, 4, 5]) or return it using an string (human readable format) or an integer (containing all digits in base 10), or in any array/list format.

The challenge type is code-golf. Therefore the shortest code wins.

Answer 1

JavaScript (ES6), 266 308 317 334 341

A function returning a string. Edit Found an arithmetic solution for function M (at last!)

F=(n,x=[],M=(a,b,t=-a-b)=>(a-b)%3?a<3&b<3?3+t:a>5&b>5?21+t:12+t:9+t+a%3*3)=>
[for(a of z='012345678')for(b of z)for(c of z)for(d of z) 
a-b&&c-a&&c-b&&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c)&&(
f=M(c,e=M(b,d)),g=M(a,e),g<f?[f,g]=[g,f]:0,r=a+b+c+d+e,x.push(r+f+g,r+g+f))]
&&x[n]

Very naive , it can be shortened in many ways. It simply enumerates all the possible legal values and returns what find at place n. The M function returns the position in between two cells, that is the mandatory move to block an opposite player.

More readable

F=(n,x=[],
  M=(a,b,t=-a-b)=>(a-b)%3? 
     a<3&b<3?
       3+t // first row
       :a>5&b>5?
          21+t // last row
          :12+t // middle row and diags
     :9+t+a%3*3 // columns
  )=>
  [for(a of z='012345678') // enumerate the first 4 moves
     for(b of z)
       for(c of z)
         for(d of z) 
           a-b&&c-a&&c-b // avoid duplicates
           &&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c) // and check if d must block a-c or it's free
           &&(
             e=M(b,d), // forced to block b-d
             f=M(c,e),g=M(a,e),g<f?[f,g]=[g,f]:0, // f and g could be in the wrong order
             r=a+b+c+d+e, // start building a return string
             x.push(r+f+g,r+g+f) // store all values in x
  )]&&x[n] // return value at requested position

Answer 2

APL (Dyalog Unicode), 73 bytes

⎕⊃z/⍨(∧/{⍵[4⍪3 2⍴5 6 1 3]∊⍨∘{3⊥3|-+/3 3⊤⍵}¨⍥↓⍵[1 3⍪3 2⍴0 4 2]},≠)¨z←,⍳7⍴9

Try it online!

A full program, and takes way too much time and memory to complete for any input. Also, the code includes some 18.0 features that aren't yet available on TIO. The TIO link includes a faster version using only features up to 17.1, so that the output can be checked.

Winning or blocking position

Given two positions, extract their row and column numbers. For each dimension (row/column), if the numbers are the same, so is the result; otherwise, the result is the third number. In both cases, the result coordinates can be found with the following property:

n1  n2  res  -(n1+n2)%3
0   0   0    0
0   1   2    2
0   2   1    1
1   0   2    2
1   1   1    1
1   2   0    0
2   0   1    1
2   1   0    0
2   2   2    2

The resulting code is as simple as the following.

{3⊥3|-+/3 3⊤⍵}  ⍝ ⍵←two positions
        3 3⊤⍵   ⍝ Convert the numbers to base 3, each number → column
      +/        ⍝ Sum of each row
   3|-          ⍝ Negate and modulo 3
 3⊥             ⍝ Convert from base 3 to integer

How the code works

z←,⍳7⍴9      ⍝ Create an array of 7-tuples of 0..8
z/⍨(...)¨z   ⍝ Filter the tuples by the following condition:
  ∧/{...},≠  ⍝ Check that Unique Mask (≠) is all ones AND it is an optimal TTT game:
    ⍵[...] ... ⍵[...]  ⍝ Extract certain indexes of the given tuple as matrices
    ⍥↓                 ⍝ Downrank both sides into four 2-tuples
    ∘{...}¨            ⍝ For each tuple of the right side,
      3⊥3|-+/3 3⊤⍵     ⍝ Compute the cell that completes a line in TTT
    ∊⍨                 ⍝ And check that the right side appears in
                       ⍝ the matching tuple on the left side
⎕⊃  ⍝ Take input n from stdin and pick the nth 7-tuple

-------------------
Left side idxs  ≡ ↓4⍪3 2⍴5 6 1 3 ≡ (4 4)(5 6)(1 3)(5 6)
Right side idxs ≡ ↓1 3⍪3 2⍴0 4 2 ≡ (1 3)(0 4)(2 0)(4 2)

Left  Right  Meaning
1 3   2 0    Turns 1 and 3 (by P1) are blocked by either Turn 2 or 4
4 4   1 3    Turns 2 and 4 (by P2) are blocked by Turn 5
5 6   0 4    Turn 6 blocks one of Turns 1,5 or Turns 3,5, and
             Turn 7 completes the other
5 6   4 2    ↑

Answer 3

APL (Dyalog Extended), 72 bytes

g←{⍵,⍨1⌽@(∊∘⍺)¨⍵}
7↑⎕⊃∧⍋¨5 6g,¨(⊂⍳3)(∪⊢,⌽¨,⊖¨,⊢∘⌽¨)⍣≡1 3g⊂3 3⍴⊃4 6 8g⊂⍳9

Try it online!

Decided to post as a separate answer, because the approach is drastically different.

Inspired from orion's comment, this one generates all optimal games by transforming a single game board in various ways.

The 3x3 toroidal board is very very permissive on its transformations; the three-in-a-rows are preserved through reflection, rotation (e.g. cycling the top row to the bottom), and shear (e.g. cycling elements of each row 0, 1, 2 units to the right respectively). With this information, I could identify four seed boards that have distinct topology (using 0 to 6 to denote the seven moves made in sequence):

P2#4 not forced
0 1 2    0 1 2
3 6 5    3 5 6
x x 4    x x 4

P2#4 forced
0 3 2    0 3 2
1 6 5    1 5 6
x x 4    x x 4

Then I tried various combinations of the transformations to find a short one that generates all 1728 boards. And I noticed that even the seed boards can be generated from one board, by swapping the positions of 1-3 (decides whether the 4th move is forced) and 5-6 (swap a block and a win).

How it works

⍝ Helper function
g←{⍵,⍨1⌽@(∊∘⍺)¨⍵}
1⌽@(∊∘⍺)¨⍵  ⍝ Cycle the positions of ⍺s in each of ⍵
⍵,⍨  ⍝ Prepend the above to ⍵

⍝ Main program
7↑⎕⊃∧⍋¨5 6g,¨(⊂⍳3)(∪⊢,⌽¨,⊖¨,⊢∘⌽¨)⍣≡1 3g⊂3 3⍴⊃4 6 8g⊂⍳9
3 3⍴⊃4 6 8g⊂⍳9  ⍝ Generate the seed board:
0 1 2
3 6 5
8 7 4
5 6g 1 3g  ⍝ Generate four seed boards from the above,
           ⍝ by swapping the numbers 1-3 and 5-6
(⊂⍳3)(...)⍣≡  ⍝ Repeat certain transformations until all are found:
  ⊢∘⌽¨  ⍝ Reverse the order of columns:
a b c   c b a
d e f → f e d
g h i   i h g
  ⊖¨,   ⍝ Join with vertical shear:
a b c   a e i
d e f → d h c
g h i   g b f
  ⌽¨,   ⍝ Join with horizontal shear:
a b c   a b c
d e f → e f d
g h i   i g h
  ∪⊢,   ⍝ Join with original and take unique results

⍋¨,¨  ⍝ Flatten each 3x3 matrix and extract where each number is
∧     ⍝ Ascending sort
⎕⊃    ⍝ Take input n and pick nth result
7↑    ⍝ Take first 7, since the last two are garbage

Answer 4

Octave, 467 369 363 309 297 characters

297:

global t=0*(1:9)m=dec2bin([15;113;897;1170;1316;1608;2370;2216;2580])-48 a;
function g(s,p)global a t m;
if nnz(s)<8&&any((t==1)*m>2)a=[a;s];return;end;q=t==3-p;
(r=sort(~q.*(1:9)*m(:,find([3 1]*([q;t==p]*m)==6)')))||(r=find(~t));
for i=r t(i)=p;g([s i+47],3-p);t(i)=0;end;end;g('',1);f=@(n)a(n+1,:);

The only relevant change is that we never check if the current player can win, only check the opponent's possibility to win the next turn. As the only turn the player 1 can win is turn 7, this is the only place when the algorithm would produce game that is not optimal, but it's very easy to filter such a situation out. We simply verify each game generated if it's won by player 1 - if it was not, the move in turn 7 was incorrect, so we don't add this game to optimal games table.

(Exactly half the games generated by this rule are false ie. in the 7th turn the player 1 always has two possibilities to block player two, but only one will make him win instantly).

Use:

$ octave
octave:1>> source script.m
octave:2>> f(634)
ans = 3270148

The ungolfed code looks like:

 global t=0*(1:9);
 global m=dec2bin([15;113;897;1170;1316;1608;2370;2216;2580])-48;
 global allgames;
 allgames=[];

 function r=canbewon(by)
  global t m
  q=[t==by;t==(3-by)]*m;
  g=(find([3 1]*q==6))';
  r=sort((~(t==by).*(1:9)) * m(:,g));
 end

 function games_starting_with(s)
 global allgames t;
 if 7==numel(s) && any((t==1)*m==3) # it's 7th move and first player won
  allgames=[allgames;s];
  return;
 end;
 poss=(find(~t));                  # for now all free slots are possible
 player=1+mod(numel(s),2);
 moves = canbewon(3-player);
 if numel(moves) poss=moves; end;  # ... no, we must block the other player
 for i=poss
  t(i)=player;
  games_starting_with([s char(i+47)]);
  t(i)=0;
 end
end

games_starting_with('');
f=@(n)(allgames(n+1,:));