TDD for Tic Tac Toe using Java: Thinking about AI algorithm

Before we start implementing the AI, we need to consider how the guy is going to work. Tic Tac Toe is relatively simple game, and we can afford just building moves tree in order to identify which move to make.

The AI characteristics I would like to create can be outlined in several rules:
  1. if there's a move that will make us win by making it - choose this move
  2. else if there's a move that will make our opponent unless we make it - choose this move
  3. else if win is possible at all - analyze possible moves and choose the move that will make us victorious as soon as possible
I have been trying to devise a situation for a potential 4th rule (If all above conditions not met - do any possible move), but I couldn't, so for now we can ignore that. And we also shall assume that our opponent (the real player) is trying to follow similar logic to hours - that is to say, trying to win and doing it without major mistakes. Let's consider an example - assume our AI guy plays for X, and our board is following:

    1 2 3
1 [ . x . ]
2 [ . o . ]
3 [ o x . ]

It is X turn now. There's 5 possible moves for us, and we're going to check where those moves are going to lead us. It is easy to conceive, that any move except 3:3 is going to lead to our loose by rule 1. Then we must take rule 2 and make our move there. Let's assume our player wasn't really wise and made move to 2:3 and now we have following picture:

    1 2 3
1 [ . x x ]
2 [ . o o ]
3 [ o x . ]

In this case we should obey rule 1 and do move into 1:1. To illustrate rule 3 we need to consider some earlier game stage, for instance like this:

    1 2 3
1 [ . . . ]
2 [ . x o ]
3 [ . . . ]
 
Rules 1 and 2 are not applicable here, so we will have to analyze what to do next. there're all in all 7 possible options:

 1.        2.        3.        4.        5.        6.

[ . . x ] [ . . . ] [ . . . ] [ . x . ] [ x . . ] [ . . . ]
[ . x o ] [ . x o ] [ . x o ] [ . x o ] [ . x o ] [ . x o ]
[ . . . ] [ . . x ] [ . x . ] [ . . . ] [ . . . ] [ x . . ]

   7.
[ . . . ]
[ x x o ]
[ . . . ]

If we look into them, we will notice that moves 1 - 6 are kind of the same (not exactly, but yet). while 7 is obviously dumb - it is not making us closer to a win. We want our AI guy not to do it. Lets, however, play move 1 till the end and see what is happening there. If we assume our player following same rules as we do, it is going to make move 3:1 and we end up here:

    1 2 3
1 [ . . x ]
2 [ . x o ]
3 [ o . . ]

Which leaves us only 5 options:

 1.        2.        3.        4.         5.  
[ . . x ] [ x . x ] [ . x x ] [ . . x ] [ . . x ]
[ x x o ] [ . x o ] [ . x o ] [ . x o ] [ . x o ]
[ o . . ] [ o . . ] [ o . . ] [ o x . ] [ o x x ]
 
First is not moving us anywhere, 2 - 4 are kind of the same, while 5 will make us victorious at the next move. We definitely want to choose 5. 2 - 4 could lead us to victory, while 5 will do it faster.

After thinking a little bit longer, we can consider rule 1 as a special case of rule 3 (next move is pretty soon, right? :) ). Thus we're approaching a heart of our AI logic - Minimax algorithm. We will consider this particular challenge in details in a chapter concentrated on AI implementation.

Comments

Popular posts from this blog

Test automation framework architecture. Part 2 - Layered architecture

Test automation framework architecture. Preface.

Test automation framework architecture. Part 1 - No architecture