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?

Solution 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)

Solution 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.

Solution 3

I know this is an extremely late answer but I thought I'd chime in to help anyone finding this. Here's some help to make a convincing and beatable ai. On the computer's turn it should roughly follow these steps:

• Look at each placement for a win. If found take it otherwise continue.
• Look at each placement for an opponent's win. If found, take it for a block otherwise continue.
• Look at the center square. If open take it otherwise continue.
• Look at the 4 corners of the board. Randomly choose from any open ones. None open, continue.
• Look at the 4 sides and randomly choose from any open ones. None open, Then the game is a tie.

Solution 4

Other answers tell you to use a lookup table. But note that if there are more than 3 pieces on the board, there is a very simple algorithm (since there will exist at least one line with two of a kind and an empty space): Win if possible, otherwise block the opponent.

Then you only need a much smaller lookup table, to handle opening moves.

Solution 5

With Tic-Tac-Toe, it should be possible for the AI to analyse every possible game outcome. You could do this by creating a tree structure which branches for every choice the player and AI can make. From there the AI can choose a path that leads towards its victory.

To make a beatable opponent though, you could limit the amount of analysis the AI does (ie. limit the depth of the tree structure) and make the AI decide a path without knowing the final outcome. A stronger AI will analyse more moves, a weaker AI less.

View more solutions

Comments

[Ben Voigt]

The only winning move is not to play?

[Michael Stum]

@Ben How about a nice game of chess instead?

[Javed Akram]

@Michael: I can't able to understand that table(image).

[st0le]

@Michael, This might be helpfull, it generates all possible outcomes, which can be used to construct a lookuptable/ codegolf.stackexchange.com/questions/1065/…

[Javed Akram]

@Michael: Thanks, for explanation. ;)

[zmbq]

Sorry for nitpicking a year later, I just found this post. Tic Tac Toe has way less than 3^9 states - the number of X's is at most 1 more than the number of O's.

[paxdiablo]

That's a good point and you're absolutely right. However, for simplicity, I'd probably still allow for all combinations, in the scoring, even if some were impossible. Then I needn't worry about a complex formula for assigning a bard to an array position. It doesn't affect the moves of course, since they're drawn from the up-to-nine possible next moves.

[Soumyajit]

OK this might be veryyyyy late for the post but I was just asking can I use your said algorithm for implementing AI in a Hex game? The thing is the number of possible states are huge even for a 11x11 board.