Generate a list of all unique Tic Tac Toe boards

Question

I would like to generate a text file containing all 19,683 Tic-Tac-Toe board layouts in the structure of 0 = Blank, 1 = X, and 2 = O. Unfortunately math is not my strong suit and I cannot seem to find any examples of this anywhere.

This isn't for homework I assure you. I intend to run this data through a Minimax calculator in order to generate an image that contains RGB values representing the optimal move based on the board setup. I am developing Tic-Tac-Toe for a platform that does not support functions (it's event-driven) so I will convert the board to a number in my game and then lookup the RGB of a pixel in an image which indicates what the best move is. It's a cheeky workaround, but one that requires no more RAM than an 145x145 pixel image (145x145 = 21,025 so each pixel represents the recommended move based on the board effectively). This also means I won't have to chew CPU time which is another plus.

Bantamweight

There are 362,880 possible move sequences. Are you looking for board layouts or move sequences? – Ladle

There are only 3^9 = 19683 different "layouts". Did you mean to say "different sequences"? – Aglimmer

That's quite a use case, how do you intend to encode the optimal moves into RGB? – Intrigant

I guess board layouts is actually what I want. So 362,880 is the number of sequences and 19,683 is the board possibilities. That will make the image much smaller. @Intrigant I plan to use RGB values representing the diff position 1-9 where the move is recommended. – Bantamweight

I'm just concerned that you're going about this all wrong: you're intending to use the image as a "database" for looking up board layouts. If that's the case then why not REALLY use a database and more precisely, use an embedded database like LevelDB or something of the sort. It will be MUCH more efficient, fast and compact than to use an image. – Brody

There are a handful of extra combinatorial considerations for possible layouts. For example, a game cannot reach a state wherein there is more than one win; there can be at most one win in a board. You also cannot have the number of X's different from the number of O's by more than one because a mark is placed on alternating turns. – Capricecapricious

@Capricecapricious I already have the two player logic embedded within my app so the board state can never reach an illegal state. If there is a win it is captured and no more moves can take place. The two player was easy :) To inject the CPU player I am going to hand off moves. For easy I will have 70% of the moves based on random picks and 30% on Minimax calcs. For hard I will have 30% of moves on random 70% on minimax. For the highest mode I will use Minimax results 90% of the time. I don't want the game to be impossible to win. – Bantamweight

@Lirik I am using a dev tool that targets Android, iOS, XNA, Flash, Java, Windows, and OS X. I need to make sure I do not use platform-specific functionality or I will never be able to convert my applications easily across platforms. This is not an ideal work-around, but it works and it is easy to do. If I was trying to do this for checkers it would never work and I know that. But for Tic-Tac-Toe it should suffice. – Bantamweight

Have a look at this: xkcd.com/832 – Furl

@Furl Saw that, but not trivial to implement as a series of conditions in a non-functional programming environment. I was able to nail it though using this approach. – Bantamweight

Answer 1

Since you want board layouts, there's only a small number of them (19683).

You can just brute-force generate all of these. Each box only has 3 possibilities. And there are 9 boxes, just run through all of them.

EDIT:

int c = 0;
while (c < 262144){
    bool valid = (c & 3) < 3;
    valid &= ((c >>  2) & 3) < 3;
    valid &= ((c >>  4) & 3) < 3;
    valid &= ((c >>  6) & 3) < 3;
    valid &= ((c >>  8) & 3) < 3;
    valid &= ((c >> 10) & 3) < 3;
    valid &= ((c >> 12) & 3) < 3;
    valid &= ((c >> 14) & 3) < 3;
    valid &= ((c >> 16) & 3) < 3;

    if (valid){
        int i = c;
        int j = 0;
        while (j < 9){
            cout << (i & 3) << " ";
            i >>= 2;
            j++;
        }
        cout << endl;
    }

    c++;
}

This will print out all 19,683 board layouts. I'm not sure what format you want, but it should be fairly easy to extract that from the output.

Aglimmer

That's what I'm trying to figure out how to do Mystical. Sorry, 30 years of programming but Math is not my strong suit. I'm assuming there is an easy way to get to these 19,683 board layouts. – Bantamweight

I'll post an answer in C++ in a few min. – Aglimmer

thanks ... was able to get it to C# by changing 2 lines. This works great and ran in about a 10th of a second. – Bantamweight

There are 5477 possible legal game states. A lot of the states generated with this can never happen in a real game because someone would have won in a preceding play. I know op doesn't care though – Spinoza

I obtained 5477, and that figure -is- terminating when tic-tac-toe (OOO, XXX) condition is met, but there may be a flaw in my logic. gitlab.com/n8chz/tic-tac-toe/-/blob/master/ttt.rb – Lithopone

@lori I calculate 5427 distinct boards. Is there any way you could send me a list of 5477 boards so I can compare? – Ridenour

@Ridenour pastebin.com/nJ4F61TS – Lithopone

Wow, someone even accounted for symmetry groups: cwoebker.com/posts/tic-tac-toe – Lithopone

Answer 2

My Minimax for Tic Tac Toe implementation generates a tree of 5477 nodes. Each node contains a Tic Tac Toe board state and satisfies the following conditions:

• the board state is valid as per Tic Tac Toe rule that players must take turns in placing Xs and Os. i.e. there's no board positions like:

  XXX
  XXX
  XXO

• all leafs of the tree contain board states that are consider end-game states as per Tic Tac Toe rules (player 1 wins, player 2 wins or draw). i.e. there's no branch of the tree like:

  XOX
  OXO
  X
  |
  |
  XOX
  OXO <-- no point in having this node, since its parent has an end-game position (X won)
  XO

• A given tree node may have multiple parents (multiple tree nodes may have the same child).

  i.e. since a given board state can be obtained through multiple different move sequences, when the tree nodes are being created, if there's already a node containing the board state that I'm about to (re)generate, I reuse (reattach) that existing node. This way, when I score the tree nodes bottom-to-top (as per Minimax theory), I don't have to calculate the same score multiple times for some subset of tree branches (which would be identical if I didn't reuse existing nodes).

I've also found a book which mentions the 5477 unique, distinct, valid Tic Tac Toe board states. :

Tic-Tac-Toe is has 5477 valid states excluding the empty position

Outcross

I ended up with 6,617 possible board state combinations. The board is turned into 0 = No player 1 = Player X 2 = Player Y. I broke the board into a 9 character string so X in the middle would show a string of 000010000 and then I would give the next best move as a number 0 to 8 where 0 is top left and 8 is bottom right. This final text file which represents perfect play was then used and a value lookup and is available for anyone to use from here: bit.ly/Xxf0Zw. To add less skill simply make random moves more or less. I made hard do perfect moves 90% of the time, medium 70% and easy 60%. – Bantamweight

@CatManDo thanks for the resource and the effort. However, I think that, since your states list doesn't take transitions into account (which sequence of moves generated a certain state), you have states which are unique among all others, valid in the sense where both players moved alternatively to generate them, but they are invalid in the sense where the game was already over before some of those states were obtained. – Outcross

You forgot to consider rotation and mirroring. – Florida

@GoswinvonBrederlow that's a great comment. I'm now curious myself by how many nodes the tree is reduced when taking this into consideration. Should be something like (5477 - [positions identical with their rotated/mirrored counterpart]) / 8 (?) – Outcross

Sorry for not answering earlier. I calculated (brute force) 626 unique and reachable positions. I'm not sure anymore if I included game ending positions there or not. – Florida

I also found 5477 states. Every time my program reached a state, it stored the state and 3 rotations, then the state flipped upside-down and its 3 rotations, for a maximum of 8 states. Duplicates were dropped. As soon as a player won, the program terminated. – Achromatism

I did a Q learned agent that picked random legal plays half of the time at training time, and after 1 million games of self play, it had found exactly 5477 different possible states. – Spinoza

@Shivan Dragon I calculate 5427 boards. Is there anyway you could send me a list of 5477 boards so I can compare? – Ridenour

I also calculated 5,477 reachable position through normal play with std::set of the board (no duplicate) through minimax in a 3x3 tic-tac-toe game. For a 4x4 it would be 9,772,010 possible reachable position through normal play. – Unlimited

@DanJarratt you found 5,477 states while addressing rotations and flips? that doesn't sound right, It should be way less than 5,477 if you treat the rotated and/or flipped variation of a board state as the same thing. – Unlimited

Answer 3

There are 9 positions and an alphabet with 3 letters (X, O, empty). Total number of possible combinations is 3^9 = 19683.

for(int i = 0; i < 19683; ++i)
{
    int c = i;
    for (int j = 0; j < 9; ++j)
    {
        cout << (c % 3) << " ";
        c /= 3;
    }

    cout << endl;
}

Redouble

There are 5477 possible legal game states. A lot of the states generated with this can never happen in a real game because someone would have won in a preceding play. Still, OP didn't really care, he wanted to make images. – Spinoza

@jules G.M. I calculate 5427 Is there anyway you can send me a list of all distinct boards? – Ridenour

(other boards that don't exist are those with impossible differences in numbers of Os vs Xs, like a board will all Xs) – Spinoza

Answer 4

Generating all possible game boards (depth first search works best) and excluding duplicates under rotation and mirroring results in 765 boards. 626 are mid game, 91 games X has won, 44 games O has won and 3 games are a draw.

If you are only intresetd in the optimal moves you can simply use https://xkcd.com/832/ as reference. Makes a nice poster.

But all the fun in tic-tac-toe is in implementing it. So I leaves that to the reader. Just a few tips:

1. Every tile on the board has 3 states so you can encode the board as number in base 3. For simpler math I use base 4 (2 bit per tile so I only need to shift). I then have a hash function that generates that number for a board under all possible rotations and mirroring (8 cases) and returns the minimum value. By that I can lookup if I played that board already.

2. Starting with an empty board place a mark on the board in every possible position, check if the board was already played, mark it played, check if the game is over and count the board, otherwise recurse alternating players.

3. The first X can only be set in 3 places (considering rotation and mirroring) and all later moves have at most 8 choices. Instead of encoding the absolute tile to be played you can only count empty tiles and encode that in 3 bit.

4. Using the above hash function gives us 626 boards where we have to make a move (you just have to reverse the rotation/mirroring to get the real move out of the data). There is probably a not much larger relative prime number so that each board fits in a hash table without collisions. Lets say that number is 696 (I know, not relative prime). At 3 bits per board that would only need 261 byte of data to store the best move for every possible game.

5. Since you are playing perfect the number of reachable boards goes way down again. Build a data set for playing X and one for playing O and you can cut that way down again.

6. Want to make it even smaller? Just program in a few basic rules like: The first O should be in the middle if free. With 2 "my color" in a row complete the row. With 2 "other color" in a row block the row and so on. Wikipedia has a list of 8 rules but I think I had less when I did it that way.

7. A perfect tic-tac-toe opponent is boring. You can never win. Why not make the game learn from failure? Keep track of all 626 boards and their possible moves. When a move results in a loss remove that move from the board. If the board has no more moves left remove from all boards leading to this one the move that causes it (recursively if that removes the last move there). Your game will never loose the same way twice. Similary for moves resulting in a win you remove the opponents move from the list of possible ones and if there are none left you mark the previous move as a sure win. That way if you can force a win you will always force it from now on. Playing X can you get it to loose 91 ways? Playing O can you get it to loose all 44 ways?

Florida

Answer 5

You can simply brute force your way through. Each of the squares is 0, 1 or 2 so...:

for (int i1 = 0; i1 <= 2; i++) {
    for (int i2 = 0; i2 <= 2; i++) {
        // ...
        // lot's of nested for loops
        // ...
    }
}

Or, if you can't be bothered with that ;) then you can write a recursive function for it:

int square[9];
void place(int square_num) {
    if (square_num == 9) {
        output the current configuration
    }

    for (int i = 0; i <= 2; i++) {
        square[square_num] = i;
        place(square_num+1);
    }
}

Then just do:

place(0);

and magic will occur.

This is in c++ by the way.

Ladle

@bdares And how is Mystical's answer correct? (I've also edited my answer) – Ladle

Mystical's answer isn't correct. Your revision looks good, but you forgot that there can be two 3-in-a-row configurations in a legal game, if the last move was the one that completed both lines for that player. – Verlinevermeer

Okay, so ending comment. I fail at life (ie I failed this question). But, as the OP said, he's already handled invalid configurations so, I'm going to remove that previous edit and leave the answer as it is so I don't stuff anything else up. – Ladle

Answer 6

The total possible moves is not 3^9 as it includes many non allowed move in Tic Tac Toe. (X's - O's) or (O's - X's) must be equal to 1 always. As https://mcmap.net/q/852844/-generate-a-list-of-all-unique-tic-tac-toe-boards mentions the total possible moves are 5477

Python code using numpy with states reduced to 5814:

import numpy as np
StatesMatrix = np.zeros((3**9,9))
for i in range(3**9):
     c = i
     for j in range(9):
       StatesMatrix[i][j] = c % 3
       c //= 3
StatesMatrix1 = np.zeros((5814,9))
k = 0
for i in range(0,StatesMatrix.shape[0]):
  if (np. count_nonzero(StatesMatrix[i] == 1) - np. count_nonzero(StatesMatrix[i] == 2)) == 1 or (np. count_nonzero(StatesMatrix[i] == 2) - np. count_nonzero(StatesMatrix[i] == 1))== 1:
    StatesMatrix1[k] = StatesMatrix[i]
    k = k + 1
    
print(StatesMatrix1)
print(k)

Microampere

Answer 7

Like an earlier solution, but easier to read and in Python.

for i in range(3**9):
     c = i
     for j in range(9):
         if j % 3 == 0:
             print("")
         print(str(c % 3) + " ", end='')
         c //= 3
     print("")

Position

Answer 8

On the implementation of the game itself:- Simply use sets as the abstract syntax representation of the game! Valid moves and winning moves are then just simple set expressions of the set of moves made by nought and/or the set of moves made by cross... The concrete syntax of the game, typically the board on which it is played, has little if anything to do with the abstract syntax of the game, except to capture it's usual user-representation. Simples, as it just means don't ever confuse concrete and abstract syntax... A really GOOD idea ):-)

Morra