title: Tic Tac Toe perfect AI algorithm: deeper in "create fork" step
body: <p>I've already read many Tic Tac Toe topics on StackOverflow. And I found the strategy on Wikipedia is suitable for my presentation project:</p>
  
  <blockquote>
    <p>A player can play perfect tic-tac-toe if they choose the move with the
    highest priority in the following table[3].</p>
    
    <p>1) Win: If you have two in a row, play the third to get three in a
    row.</p>
    
    <p>2) Block: If the opponent has two in a row, play the third to block
    them.</p>
    
    <p><strong>3) Fork: Create an opportunity where you can win in two ways.</strong></p>
    
    <p>4) Block Opponent's Fork:</p>
    
    <p>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.)</p>
    
    <p>Option 2: If there is a configuration where the opponent can fork,
    block that fork.</p>
    
    <p>5) Center: Play the center.</p>
    
    <p>6) Opposite Corner: If the opponent is in the corner, play the
    opposite corner.</p>
    
    <p>7) Empty Corner: Play an empty corner.</p>
    
    <p>8) Empty Side: Play an empty side.</p>
  </blockquote>
  
  <p>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.</p>
  
  <pre><code>private void step3() // Create Fork.
  {
      int[] dummyField = (int[])field.Clone();
      // Try Level 1 Dummy
      for (int i = 0; i &lt; 9; i++)
      {
          if (dummyField[i] != 0) continue;
          dummyField[i] = 2;
          if (countFork(dummyField, 2) &gt;= 2)
          {
              nextCell = i;
              return;
          }
          dummyField[i] = 0;
      }
  
  }
  </code></pre>
  
  <p>Please give me some advice about this step.</p>
  
  <p>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 <code>countFork</code> function).</p>
  
  <p>EDIT2: The reason why I say it is not perfect is this (CPU goes first, and its cells are blue, human cells are red).
  <img src="https://i.stack.imgur.com/8sbLN.png" alt="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.</p>
  
  <p><strong>EDIT3: Don't know why, but I commented out the step 3, and the computer plays... perfectly! I'm really surprised!</strong> 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):</p>
  
  <pre><code>private int countFork(int[] field, int token)
  {
      int result = 0;
  
      // Vertical
      int cpuTokenCount;
      int spareCell;
      for (int x = 0; x &lt; 3; x++)
      {
          cpuTokenCount = 0;
          spareCell = -1;
          for (int y = 0; y &lt; 3; y++)
          {
              if (field[getNumberFromXY(x, y)] == token)
                  cpuTokenCount++;
              else if (field[getNumberFromXY(x, y)] == 0)
                  spareCell = getNumberFromXY(x, y);
          }
          if (cpuTokenCount == 2 &amp;&amp; spareCell != -1) result++;
      }
  
      // Horizontal
      for (int y = 0; y &lt; 3; y++)
      {
          cpuTokenCount = 0;
          spareCell = -1;
          for (int x = 0; x &lt; 3; x++)
          {
              if (field[getNumberFromXY(x, y)] == token)
                  cpuTokenCount++;
              else if (field[getNumberFromXY(x, y)] == 0)
                  spareCell = getNumberFromXY(x, y);
          }
          if (cpuTokenCount == 2 &amp;&amp; spareCell != -1) result++;
      }
  
      // Top-Left To Lower-Right Diagonal
      cpuTokenCount = 0;
      spareCell = -1;
      for (int i = 0; i &lt; 3; i++)
      {
          if (field[getNumberFromXY(i, i)] == token)
              cpuTokenCount++;
          else if (field[getNumberFromXY(i, i)] == 0)
              spareCell = getNumberFromXY(i, i);
      }
      if (cpuTokenCount == 2 &amp;&amp; spareCell != -1) result++;
  
      // Top-Right To Lower-Left Diagonal
      cpuTokenCount = 0;
      spareCell = -1;
      for (int i = 0; i &lt; 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 &amp;&amp; spareCell != -1) result++;
  
      return result;
  }
  </code></pre>
  
  <p><strong>EDIT4: FIXED the bug according to soandos, and updated the code at EDIT 3, now it works perfectly!</strong></p>