Search code examples
theorytic-tac-toefinite-automatacomputation-theorydfa

DFA for a Tic Tac Toe Game

I'm suppose to make a c++ program that makes a DFA for Tic Tac Toe, accepting first player wins only. I have working code and it is generating a DFA. I also have a function that is counting the number of states. I'm getting 2,203,642 states, but I'm not sure if that is right or wrong. Can anyone tell me how many states I should have?

Solution

  • I'm not sure whether I fully understand the question, but I can answer based on my understanding.

    The first thing we need to do is model a game of Tic Tac Toe. There is no one right or wrong way to do this. I propose the following model: a game of Tic-Tac-Toe is a string of length 9 consisting of 0s, 1s and 2s. 0s correspond to unclaimed positions, 1s to those claimed by player 1, and 2s those claimed by player 2. Position inside the string corresponds to the positions by taking the positions from left to right, then top to bottom. Player 1 wins this game: 122010001; loses this game: 100222110; and this game is invalid 111222111.

    So we are looking for a DFA to recognize valid games where player 1 wins. A game is valid if (a) there is at least one player who hasn't won and (b) both players have the same number of moves or player 1 has one more move than player 2. Player 1 wins in any of these cases:

    • 111SSSSSS
    • SSS111SSS
    • SSSSSS111
    • 1SS1SS1SS
    • S1SS1SS1S
    • SS1SS1SS1
    • 1SSS1SSS1
    • SS1S1S1SS

    Here, S stands for any of the symbols 0, 1, 2. So, here's one way to approach making a DFA:

    1. Write a DFA that accepts the union of the languages described by the 8 regular expressions in the list above.

    2. Copy the DFA from 1, but for player 2 winning instead of player 1. Now, negate the DFA by toggling states from accepting to non-accepting and vice versa.

    3. Construct the Cartesian product machine by considering the intersection of the DFAs obtained from steps 1 and 2. This DFA now recognizes "player 1 wins and player 2 does not`.

    4. Now construct a new DFA to recognize whether the numbers of moves are valid. We will have 100 states: 10 move counts for player 1 and 10 for player 2. Mark as accepting those states corresponding to #1 = #2 or #1 = #2 + 1 (there should be 20 such states).

    5. Construct the Cartesian product machine of machines from steps 3 and 4 using intersection to determine accepting states. The resulting DFA recognizes exactly the valid games which player 1 wins and player 2 loses.

    Note: after each step, you can minimize the resulting DFA in order to make the Cartesian product machine constructions have fewer states. Also, you can minimize the machine from step 5 to get the smallest possible DFA accepting the language.

    Possibly not super helpful but if you write a program to generate the DFAs outlined above, and then have the program minimize the DFAs along the way, you should get the right answer.