Artificial Intelligence in Tic-Tac-Toe using C#

Question

I have made a Tic-Tac-Toe game for 2 players. Now, I want to give the game Artificial Intelligence.

So that game can be played between 1 player and computer.
Please, help How do I start?

Answer 1

With Tic Tac Toe it's not so much an AI but a lookup table: For each possible board layout, find the best spot.

XKCD has such a lookup table. Basically each Board Layout gets a unique ID and the address of the field where to set the next mark. Wikipedia has that table in another format.

The table works like this: X goes first, then O. X puts his X into one of the 9 cells. When O goes, there are now 9 possible Board Layouts, depending on which Cell has the X:

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

If you look at the map of O, there are 9 big grids in it, and the one in the top left has X in the top left spot, so that is the one to use. Place O in the Middle.

Now when X goes again, it needs to find this board layout:

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

You will find this in the middle. Red is where to put the X in the XKCD image, and that shows you put it in the lower right:

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

Now, O goes again and looks for the above board layout, which is in the bottom right small grid in the top left big grid. O needs to be placed into the middle bottom:

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

And so forth. The diagram is a bit hard to read at first (click on it to enlarge it) as it's nested, but as said: You create a Lookup table that has each unique board layout and information where to put the next mark.

This creates a perfect opponent though: The computer will never ever lose. How to make him more human is then fine-tuning (e.g., randomly discard the choice and place the mark in a random cell)

Answer 2

I actually wrote such a beast many moons ago, an actual automaton that learnt from its mistakes.

The nature of the game means that you could store outcomes for every possible position. While not practicable for a game like chess, TicTacToe only has 3⁹, or 19683, states.

Here's the intelligence bit I used.

An array of bytes was allocated giving the desirability of every single state and these were all initialised to 127 so that all states were equally desirable. In order for the AI to select a move to make, it added up the scores of all states that could result from a possible move and used that to generate a random number to select which move it would make.

In other words, if only two moves were possible and the outcomes had scores of 200 and 50, the AI would generate a random number from 0 to 249 and use that to select one, with the former would be four times (values 0-199) more likely than the latter (values 200-249).

As to how the scores change, the AI simply remembered every state that existed in the game that resulted from a move you made. If it won the game, the score of all those positions would be bumped up by one (but limiting it to 255 of course, since it had to fit in a byte). If it lost, it would drop the scores (keeping them at one or more).

That way, positions that lead to a win would become more likely, while those that led to a loss would become less likely.

The reason the desirability never dropped to zero was so that no state was ever impossible to get. Of course, one with a desirability score of one was very unlikely if all the others had higher scores.

It took quite a lot of games for the AI to become a decent player but you could accelerate it by pitting it against an automated enemy that alternated between the same AI and random moves.

And there were tricks you could use to bump up or drop more states than existed in the game since you could rotate or mirror each state to get an equivalent position.

You could also set a lower bound for the score to reach (other than one) - this would make it more likely that the AI would select a less optimal move, effectively dropping the intelligence level.