title: Tic Tac Toe heuristic AI
body: <p>I designed simple AI for 3x3 Tic Tac Toe game. However I didn't want to do neither complete search, nor MinMax. Instead i thought of a heuristic that would evaluate values for all of 9 fields, and then AI would choose the field with highest value. The problem is, I have absolutely no idea how to determine, whether it is a perfect (unbeatable) algorithm.</p>
  
  <p>And here are the details:
  Every Field has several WinPaths on the grid. Middle one has 4 (horizontal, vertical and two diagonals), corners have 3 each (horizontal, diagonal and one vertical), sides have only 2 each (horizontal and vertical). Value of each Field equals sum of its WinPaths values. And WinPath value depends on its contents:</p>
  
  <ul>
  <li>Empty: <code>[ | | ]</code> - 1 point</li>
  <li>One symbol: <code>[X| | ]</code> - 10 points <code>// can be any symbol in any place</code></li>
  <li>Two different symbols: <code>[X|O| ]</code> - 0 points <code>// they can be arranged in any possible way</code></li>
  <li>Two identical opponents symbols: <code>[X|X| ]</code> - 100 points <code>// arranged in any of three ways</code></li>
  <li>Two identical "my" symbols: <code>[O|O| ]</code> - 1000 points <code>// arranged in any of three ways</code></li>
  </ul>
  
  <p>This way for example beginning situation has values as below:</p>
  
  <pre><code> 3 | 2 | 3 
  ---+---+---
   2 | 4 | 2 
  ---+---+---
   3 | 2 | 3 
  </code></pre>
  
  <p>However a later one can be like this (X is moving now):</p>
  
  <pre><code> X | 10| O
  ---+---+---
   O | O |110
  ---+---+---
   X | 20| 20
  </code></pre>
  
  <p>So is there any reliable way to find out whether is this a perfect algorithm, or does it have any disadvantages?</p>
  
  <p>PS. I was trying (from the perspective of player) to create a fork situation so I could beat this AI, but I have failed.</p>