1

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.

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:

  • Empty: [ | | ] - 1 point
  • One symbol: [X| | ] - 10 points // can be any symbol in any place
  • Two different symbols: [X|O| ] - 0 points // they can be arranged in any possible way
  • Two identical opponents symbols: [X|X| ] - 100 points // arranged in any of three ways
  • Two identical "my" symbols: [O|O| ] - 1000 points // arranged in any of three ways

This way for example beginning situation has values as below:

 3 | 2 | 3 
---+---+---
 2 | 4 | 2 
---+---+---
 3 | 2 | 3

However a later one can be like this (X is moving now):

 X | 10| O
---+---+---
 O | O |110
---+---+---
 X | 20| 20

So is there any reliable way to find out whether is this a perfect algorithm, or does it have any disadvantages?

PS. I was trying (from the perspective of player) to create a fork situation so I could beat this AI, but I have failed.

Sushi271
  • 544
  • 2
  • 8
  • 22
  • 1
    You could play all tic-tac-toe games and see if your algorithm forces a draw. –  Mar 14 '15 at 17:58
  • @Hurkyl +1 for beating me to it. I had to answer because at the time I didn't have the rep to comment. – tyapo Mar 14 '15 at 19:06

2 Answers2

2

Wikipedia: tic-tac-toe says that there are only 362,880 possible tic-tac-toe games. A brute force approach to proving your algorithm would be to exhaustively search the game tree, having your opponent try each possible move at each turn, and see if your algorithm ever loses (it's guaranteed a win or draw if perfect). The space is small enough that a program could do this very quickly. Of course, you would then be faced with proving that your test program is correct.

tyapo
  • 120
  • 2
  • 8
1

To know if your bot good enough you have to play a lot games bot vs top players and bot vs the best bots in the market (usually for much complicated game like chess or go).

Did you tried this (I play first)?

 13| 12| 13
---+---+---
 12| 14| 12 
---+---+---
 13| 12| O

Right?

   |   |   
---+---+---
   | X |   
---+---+---
   |   | O 

 O |20 |30 
---+---+---
 20| X |20 
---+---+---
 30|20 | O

If I understand it well the X next move will be on the corner

 O |20 | X 
---+---+---
 20| X |20 
---+---+---
 30|20 | O

And from here I win..

If this pass (if I missed something..) so your solution look perfect

Roy Shmuli
  • 4,979
  • 1
  • 24
  • 38
  • 1
    :o I missed this badly. Although you made mistakes in the first table (it should be: `12, 2, 12 | 2, 13, 11 | 12, 11, O`), it doesn't make a difference. I was suspecting I should somehow protect myself against forks, however I couldn't reproduce fork situation with this algorithm. Thanks :) – Sushi271 Mar 14 '15 at 18:55