Non-Recursive tic-tac-toe AI Algorithm

I intend to lay out the algorithm for a function that returns the next cell to be occupied by an AI in a game of Tic-tac-toe (iteratively). The AI’s difficulty can be divided into 3 levels: easy, medium and difficult.

Imagine that the board is comprised of cells numbered from 1 to 9 as shown below:

Tic_Tac_Toe_Board
Tic_Tac_Toe_Board

Data model

A *cell* represents each of the squares on the board.

A *state* is a list of two lists – the first corresponds to the cells occupied by player ‘x’ and the second corresponds to the cells occupied by player ‘o’. Therefore, S[0] is the list of cells occupied by player x and S[1] is the list of cells occupied by player ‘o’.

Note: Your representation of the state will probably be different, but the algorithm should probably be similar.

A *player* is either ‘x’ or ‘o’

A *collection* is a list of the possible cells which a player needs to occupy in order to win

Ex.1  collection = [[1,4,7],[2,5,8],[3,6,9],[1,2,3],[4,5,6],[7,8,9],[1,5,9],[3,5,7]]

Ex.2

Possible_game_state
Possible_game_state

The state above will be represented as S = [[1,9],[5,6]]

Assumption: I am assuming that the human player is always ‘x’ and that he/she always goes first.

# The easy AI is made to play like a silly child who is unaware of the consequences of it’s moves

#easy_AI: state x cell -> cell: easy_AI() is the next cell to be occupied by the AI if the difficulty level is easy

easy_AI(state):

check state and determine which cells are empty.

choose a random cell from the cells that are empty (let’s call it x)

return x

————————————————————————————————————————-

# medium AI is to win if it can. If it cannot, it should block the human player from winning if he/she can win and otherwise, return a random cell

#medium_AI: state x cell -> cell: medium_AI() is the next cell to be occupied by the AI if the difficulty level is medium

medium_AI(state):

if player o can win in state:

   check which of the combination in collection he has and return the third cell if it is empty

else if player x can win in state:

   check which of the combinations in collection he/she has and return the third cell if it is empty (this allows the AI to prevent the human from winning).

else:

   check which cells are empty and pick a random cell from those cells.

Ex.3

Possible_game_state
Possible_game_state

The state above will be represented as [[3,5],[2]]. It is clear that the AI, ‘o’, cannot win. The code under the first if statement is not executed. Player ‘x’ can win, so it is the duty of this more intelligent AI to block  and prevent him/her from winning. To do this, it has to play in cell ‘7’. In a case in which neither ‘x’ nor ‘o’ can win (e.g when it’s o’s first move), a random move should be made.

You can implement a can win function which receives a players cells and determines if he/she can win in state S.

canwin(p_cells,S,collection):

if the player has less than 2 cells, return false (you can’t win like in the case shown above)

else:

if the player has 2 cells in any of the winning combinations in collection, and the third is empty, return true

—————————————————————————————————————————

# hard_AI is the Tiger Woods of Tic-Tac-Toe. He knows all the moves and cannot lose. You either go down with him in a draw or he beats you (your choice).

Lets briefly describe some scenarios before we implement this.

1. This AI should win without any consideration if it can

2. This AI should block the opponent if there is imminent danger(i.e if there is the possibility that it will lose)

** A side as used below represents cells 2,4,6 and 8.

3. If 1 and 2 are not satisfied, it should make a move that is geared towards winning and will prevent the opponent from winning. To do this,

a. If the center is free, then, it’s probably best to occupy that (most organizations are controlled from a central point).

b. Besides the center, it’s always best to avoid the sides and take a corner. However, there are some tricks involved.

Scenarios 1 and 2

Tricky scenarios
Tricky scenarios
Result of a careless AI move
Result of a careless AI move

As shown above, if the game state is [[3,7],[5]] or [[1,9],[5]] and the AI plays in a corner, then, it will make the humans day because the human will have a 2 way win situation. To avoid this, It should play in one of the empty sides.

Scenarios 3,4,5 and 6

Requires wisdom.
Requires wisdom.
Requires wisdom
Requires wisdom

To avoid giving the human a 2 way win situation, in scenario 3, play in either 8 or 9; in scenario 4,  play in either 2 or 3; in scenario 5, play in either 7 or 8 and in scenario 6, play in either 1 or 2.

Scenarios 7,8,9,10

Needs Wisdom
Needs Wisdom
Needs Wisdom
Needs Wisdom

To avoid giving the human a 2 way win situation, in scenario 7, play in cell 7; in scenario 8, play in cell 9; in scenario 9,play in cell 1 and in scenario 10,play in cell 3.

c. If none of all the conditions above are satisfied, then pick a corner out of the free corners (because, corners are better than sides

d. else: pick a side out of the free sides.

#hard_AI: state x cell -> cell: hard_AI() is the next cell to be occupied by the AI if the difficulty level is hard

hard_AI(state):

if player o can win in state:

   check which of the combination in collection he has and return the third cell if it is empty

else if player x can win in state:

   check which of the combinations in collection he/she has and return the third cell if it is empty (this allows the AI to prevent the human from winning).

else if the center is empty: return the center

else if the state indicates scenarios 1 or 2: return a random side from the list of empty sides

else if the state indicates scenarios 3,4,5 or 6:

   if it is scenario 3, return either cell 8 or 9

   if it is scenario 4, return either cell 2 or 3

   if it is scenario 5, return either cell 7 or 8

   if it is scenario 6, return either cell 1 or 2

else if the state indicates scenarios 7,8,9 or 10:

   if it is scenario 7, return cell 7

   if it is scenario 8, return cell 9

   if it is scenario 9, return cell 1

   if it is scenario 10, return cell 3

else if none of all the above, return an empty corner

and if none of all that, return an empty side.

Now, using recursion may be a better way to implement these functions, but you could do it this way to fully grasp the game of Tic-Tac-Toe and master it. If you understand the hard_AI algorithm, then, you should never be beaten again in a game of Tic-Tac-Toe.

Note: Everything on this page is open to criticism. Besides the fact that I am human, I am still learning and so, my code may not be standard or even good code, but gets the job done (This is not really a good thing). Some steps can be solved in easier ways and I encourage you to do so if you see it fit.

If you have any questions or comments, please leave a comment.

Advertisements

4 thoughts on “Non-Recursive tic-tac-toe AI Algorithm

  1. I’m interested to see the finished coded algorithm. I just started playing around with the traditional minmax recursion solution to TTT. It should be possible to do iterative without too much pain since I believe the necessary recursion depth for an unbeatable AI is only a few calls deep.

    1. Yes, it’s possible without pain provided you follow the algorithm above. However, a lot of students are given this as a project or something, so I can’t just post the code up here as that will discourage learning. Thank you for understanding.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s