Tic Tac Toe perfect AI algorithm: deeper in "create fork" step

13,622

I am not sure that it is the most elegant way to do it, but here is a two step way of looking at forks.

If the computer cannot win next turn, and it is not the first or second turn, a fork might be possible (this does not deal with creating the setup for a fork, just finding a fork).

For each of the cells that are empty, fill it, then run your step 1 function (sees if there are two in a row). If it finds two places, congrats, you have a fork. If not, you don't.

Share:
13,622
Luke Vo
Author by

Luke Vo

Updated on June 09, 2022

Comments

  • Luke Vo
    Luke Vo almost 2 years

    I've already read many Tic Tac Toe topics on StackOverflow. And I found the strategy on Wikipedia is suitable for my presentation project:

    A player can play perfect tic-tac-toe if they choose the move with the highest priority in the following table[3].

    1) Win: If you have two in a row, play the third to get three in a row.

    2) Block: If the opponent has two in a row, play the third to block them.

    3) Fork: Create an opportunity where you can win in two ways.

    4) Block Opponent's Fork:

    Option 1: Create two in a row to force the opponent into defending, as long as it doesn't result in them creating a fork or winning. For example, if "X" has a corner, "O" has the center, and "X" has the opposite corner as well, "O" must not play a corner in order to win. (Playing a corner in this scenario creates a fork for "X" to win.)

    Option 2: If there is a configuration where the opponent can fork, block that fork.

    5) Center: Play the center.

    6) Opposite Corner: If the opponent is in the corner, play the opposite corner.

    7) Empty Corner: Play an empty corner.

    8) Empty Side: Play an empty side.

    I've followed these step, and the computer never loses. However, the way it attacks is not perfect. Because I have no clue how to do step 3. Here is what I do in step 3: scan every cell, check if put token on that cell creates a fork, then put it there.

    private void step3() // Create Fork.
    {
        int[] dummyField = (int[])field.Clone();
        // Try Level 1 Dummy
        for (int i = 0; i < 9; i++)
        {
            if (dummyField[i] != 0) continue;
            dummyField[i] = 2;
            if (countFork(dummyField, 2) >= 2)
            {
                nextCell = i;
                return;
            }
            dummyField[i] = 0;
        }
    
    }
    

    Please give me some advice about this step.

    EDIT1: The count fork will count how many forks that computer has (computer's tokens is 2, player tokens is 1, because I used that method for step 4 too, so there is a parameter for token in countFork function).

    EDIT2: The reason why I say it is not perfect is this (CPU goes first, and its cells are blue, human cells are red). enter image description here As you can see, if I put in the top-side cell, the computer wins. But if I put in the right-side cell, it's a tie, although the computer can still win.

    EDIT3: Don't know why, but I commented out the step 3, and the computer plays... perfectly! I'm really surprised! Here is my countFork function (I need to port this code to Alice, which doesn't support 2-dimension array, so I use getNumberFromXY to convert 2-dimension array into 1-dimension):

    private int countFork(int[] field, int token)
    {
        int result = 0;
    
        // Vertical
        int cpuTokenCount;
        int spareCell;
        for (int x = 0; x < 3; x++)
        {
            cpuTokenCount = 0;
            spareCell = -1;
            for (int y = 0; y < 3; y++)
            {
                if (field[getNumberFromXY(x, y)] == token)
                    cpuTokenCount++;
                else if (field[getNumberFromXY(x, y)] == 0)
                    spareCell = getNumberFromXY(x, y);
            }
            if (cpuTokenCount == 2 && spareCell != -1) result++;
        }
    
        // Horizontal
        for (int y = 0; y < 3; y++)
        {
            cpuTokenCount = 0;
            spareCell = -1;
            for (int x = 0; x < 3; x++)
            {
                if (field[getNumberFromXY(x, y)] == token)
                    cpuTokenCount++;
                else if (field[getNumberFromXY(x, y)] == 0)
                    spareCell = getNumberFromXY(x, y);
            }
            if (cpuTokenCount == 2 && spareCell != -1) result++;
        }
    
        // Top-Left To Lower-Right Diagonal
        cpuTokenCount = 0;
        spareCell = -1;
        for (int i = 0; i < 3; i++)
        {
            if (field[getNumberFromXY(i, i)] == token)
                cpuTokenCount++;
            else if (field[getNumberFromXY(i, i)] == 0)
                spareCell = getNumberFromXY(i, i);
        }
        if (cpuTokenCount == 2 && spareCell != -1) result++;
    
        // Top-Right To Lower-Left Diagonal
        cpuTokenCount = 0;
        spareCell = -1;
        for (int i = 0; i < 3; i++)
        {
            if (field[getNumberFromXY(2 - i, i)] == token)
                cpuTokenCount++;
            else if (field[getNumberFromXY(2 - i, i)] == 0)
                spareCell = getNumberFromXY(2 - i, i);
        }
        if (cpuTokenCount == 2 && spareCell != -1) result++;
    
        return result;
    }
    

    EDIT4: FIXED the bug according to soandos, and updated the code at EDIT 3, now it works perfectly!