15,671,149 members
Articles / Programming Languages / C#
Article
Posted 7 Nov 2009

274.9K views
25 bookmarked

# Solve Tic Tac Toe with the MiniMax algorithm

Rate me:
A C# Console program to solve Tic Tac Toe with the MiniMax algorithm and alpha-beta pruning.

## Introduction

After learning the MiniMax algorithm, I decided to practice it on Tic Tac Toe. The algorithm is simple to implement. However, it took me much more time than I expected. So, I would like to share what I have learned here.

## MiniMax algorithm with alpha beta pruning

The shortest description of MiniMax that I can find is from Wikipedia. I implemented it this way:

C#
```public int MiniMaxShortVersion(int depth, int alpha, int beta, out Board childWithMax)
{
childWithMax = null;
if (depth == 0 || IsTerminalNode())
{
//When it is turn for PlayO, we need to find the minimum score.
RecursiveScore = m_Score;
return m_TurnForPlayerX ? m_Score : -m_Score;
}
foreach (Board cur in GetChildren())
{
Board dummy;
int score = -cur.MiniMaxShortVersion(depth - 1, -beta, -alpha, out dummy);
if (alpha < score)
{
alpha = score;
childWithMax = cur;
if (alpha >= beta)
{
break;
}
}
}
RecursiveScore = alpha;
return alpha;
}
//To call the function:
MiniMaxShortVersion(depth, int.MinValue + 1, int.MaxValue - 1, out ret);```

The description on Wikipedia is very short and elegant, but there are some things to watch out:

First, we cannot use `int.MinValue` and `int.MaxValue` as -/+infinity. `-int.MaxValue` is not a valid integer. So, I used `int.MinValue+1` and `int.MaxValue-1` instead.

Second, the terminal nodes include nodes with no successors, and game-over nodes (winner already decided). In my initial implementation, I forgot the game-over nodes.

Finally, the description on Wikipeida seems to indicate that the node type (min/max) doesn't matter. However, the heuristic value needs to change the sign based on whether the node is a min or max node. In the longer version descriptions, the heuristic score doesn't have to change, which makes the coding much easier. In order to find where the mistake is, I had to implement the longer version:

C#
```public int MiniMax(int depth, bool needMax, int alpha, int beta, out Board childWithMax)
{
childWithMax = null;
System.Diagnostics.Debug.Assert(m_TurnForPlayerX == needMax);
if (depth == 0 || IsTerminalNode())
{
RecursiveScore = m_Score;
return m_Score;
}
foreach (Board cur in GetChildren())
{
Board dummy;
int score = cur.MiniMax(depth - 1, !needMax, alpha, beta, out dummy);
if (!needMax)
{
if (beta > score)
{
beta = score;
childWithMax = cur;
if (alpha >= beta)
{
break;
}
}
}
else
{
if (alpha < score)
{
alpha = score;
childWithMax = cur;
if (alpha >= beta)
{
break;
}
}
}
}
RecursiveScore = needMax ? alpha : beta;
return RecursiveScore;
}```

The second version takes a few more minutes to type. But it saves me a couple hours from debugging. It has another advantage: when its `RecurisveScore` is positive, Player X is winning. When the `RecurisveScore` is negative, Player O is winning. The shorter version on Wikipedia requires more logic.

## Heuristic score in Tic Tac Toe

The Minimax algorithm can be applied to many games. Its implementation doesn't change for a different game. However, the challenge part is to define the heuristic score. I found that it is not easy even for a game as simple as Tic Tac Toe. There are totally 8 rows in a Tic Tac Toe board. The rules to calculate the score are:

• For each row, if there are both X and O, then the score for the row is 0.
• If the whole row is empty, then the score is 1.
• If there is only one X, then the score is 10.
• If there are two Xs, then the score is 100.
• If there are 3 Xs, then the score is 1000, and the winner is Player X.
• For Player O, the score is negative.
• Player X tries to maximize the score.
• Player O tries to minimize the score.
• If the current turn is for Player X, then the score of Player X has more advantage. I gave the advantage rate as 3.

The source code for computing the heuristic score is:

C#
```int GetScoreForOneLine(GridEntry[] values)
{
int countX=0, countO=0;
foreach (GridEntry v in values)
{
if (v == GridEntry.PlayerX)
countX++;
else if (v == GridEntry.PlayerO)
countO++;
}
if (countO == 3 || countX == 3)
{
GameOver = true;
}
//The player who has turn should have more advantage.
if (countO == 0)
{
if (m_TurnForPlayerX)
}
else if (countX == 0)
{
if (!m_TurnForPlayerX)
}
return 0;
}
void ComputeScore()
{
int ret = 0;
int[,] lines = { { 0, 1, 2 }, { 3, 4, 5 },
{ 6, 7, 8 }, { 0, 3, 6 },
{ 1, 4, 7 }, { 2, 5, 8 },
{ 0, 4, 8 }, { 2, 4, 6 }
};
for (int i = lines.GetLowerBound(0); i <= lines.GetUpperBound(0); i++)
{
ret += GetScoreForOneLine(new GridEntry[]
{ m_Values[lines[i, 0]],
m_Values[lines[i, 1]],
m_Values[lines[i, 2]] });
}
m_Score = ret;
}```

## Interesting Tic Tac Toe move

Because Player X always makes the first move, it is more difficult for Player O to win. The program prints all the winning moves for Player O. I found these moves for Player O are interesting:

```[1]Winner is PlayerO:
OXX    OXX    OXX    OXX    OXX    OXX
--- => O-- => O-- => OO- => OO- => OOO
---    ---    X--    X--    X-X    X-X
[2]Winner is PlayerO:
OX-    OX-    OX-    OX-    OX-    OXO
--X => --X => X-X => XOX => XOX => XOX
---    O--    O--    O--    O-X    O-X
[3]Winner is PlayerO:
X--    X--    X-X    X-X
XOX => XOX => XOX => XOX
--O    O-O    O-O    OOO
[4]Winner is PlayerO:
OX-    OX-    OXX    OXX
X-O => X-O => X-O => XOO
X--    X-O    X-O    X-O
[5]Winner is PlayerO:
XXO    XXO    XXO    XXO
X-- => X-- => XX- => XX-
-O-    OO-    OO-    OOO```

The program can also print out all the winning moves for Player X. The rules for Player O to defend are:

• If Player X makes the first move at the corner, then Player O has to take the center.
• If Player X makes the first move at the center, then Player O has take the corners.
• If Player X makes the first move at the top edge, then Player O cannot take the side edges or unconnected corners.

Two of the interesting moves for Player X are:

```[1]Winner is PlayerX:
X--    X--    X--    X-X    XOX    XOX
--- => --- => O-- => O-- => O-- => OX-
--O    X-O    X-O    X-O    X-O    X-O
[2]Winner is PlayerX:
X-O    X-O    X-O    X-O    X-O    X-O
--- => X-- => X-- => XX- => XXO => XXO
---    ---    O--    O--    O--    O-X```

## Similar Tic Tac Toe boards

When I printed out the Tic Tac Toe moves, I found that many moves were redundant because they were very similar. I defined a class `Transform` to find out all the similar Tic Tac Toe boards.

C#
```class Transform
{
const int Size = 3;
delegate Point TransformFunc(Point p);
public static Point Rotate90Degree(Point p)
{
//012 -> x->y, y->size-x
return new Point(Size - p.y -1, p.x);
}
public static Point MirrorX(Point p)
{
//012 -> 210
return new Point(Size - p.x -1, p.y);
}
public static Point MirrorY(Point p)
{
return new Point(p.x, Size - p.y -1);
}
List<TransformFunc> actions = new List<TransformFunc>();
public Point ActOn(Point p)
{
foreach (TransformFunc f in actions)
{
if(f!=null)
p = f(p);
}
return p;
}
Transform(TransformFunc op, TransformFunc[] ops)
{
if(op!=null)
if (ops!=null && ops.Length > 0)
}
public static List<Transform> s_transforms = new List<Transform>();
static Transform()
{
for (int i = 0; i < 4; i++)
{
TransformFunc[] ops =
Enumerable.Repeat<TransformFunc>(Rotate90Degree, i).ToArray();
}
}
}```

When a board can be transformed into another board, they are considered similar.

## Conclusion

In this article, I implemented Tic Tac Toe in two versions of the MiniMax algorithm. One is shorter but more difficult to debug. The longer version takes more time to type in, but saves a lot of trouble when debugging.

Written By
Web Developer
United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

 First Prev Next
 minimax method in Tic Tac Toe Member 103617314-Jul-14 11:35 Member 10361731 4-Jul-14 11:35
 My vote of 1 cboozb30-Jun-10 8:27 cboozb 30-Jun-10 8:27
 Re: My vote of 1 tomtom19806-Dec-10 1:52 tomtom1980 6-Dec-10 1:52
 Re: My vote of 1 t.heub28-Nov-12 5:26 t.heub 28-Nov-12 5:26
 Re: My vote of 1 Martin Capodici31-Jul-14 17:31 Martin Capodici 31-Jul-14 17:31
 I did this one at uni too. If you like AI you may like one Sacha Barber8-Nov-09 6:57 Sacha Barber 8-Nov-09 6:57
 Last Visit: 31-Dec-99 18:00     Last Update: 8-Jun-23 13:08 Refresh 1