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

Question

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!

Looks reasonable. What makes you think this doesn't work? What is the second parameter to countFork for? — Matthew Strawbridge
@MatthewStrawbridge Edited to answer your questions. Thank you for replying. — Luke Vo
bug: It does not check that if there are two cells in a row, that the thrid one is available. — soandos

soandos soandos · Accepted Answer · 2011-11-28T05:05:10

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.

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

1 Answers