Tic Tac Toe Tutorial - ZviRosenfeld/MinMaxSearch GitHub Wiki
Let's see how we can use MinMaxSearch to create an AI for tic-tac-toe.
Since tic-tac-toe is a deterministic game (has no element of luck in it), we'll be using an IDeterministicState to describe the game states.
Let's start be creating an empty implementation of the interface
class TicTacToeState : IDeterministicState
{
}We'll use a 3X3 array of type Player to describe the game board. Player is an enum defined in the NuGut, with 3 types: Player.Max, Player.Min and Player.Empty. We'll use Player.Max to describe cells with an X in them, Player.Min for cells with an O in them, and Player.Empty for empty cells.
We'll also add the Turn property to indicate who's turn it is. Let's initialize the Board and Turn from the constructor.
class TicTacToeState : IDeterministicState
{
public Player[,] Board { get; }
public TicTacToeState(Player[,] board, Player turn)
{
Board = board;
Turn = turn;
}
public Player Turn { get; }
}I'm going to use a simple evaluation schema: If X won, the evaluation will be 1, if O won the evaluation will be -1, and if no one won the evaluation will be 0. For most real games you'll probably want a more complex evaluation schema that take the board's state into account, but for this example our simple evaluation method should do.
We'll create a new class BoardWinEvaluator. (I'm using extension methods here. If you're not familiar with extension methods you might want to look them up.)
static class BoardWinEvaluator
{
public static bool IsWin(this Player[,] board, Player player) =>
board.IsStraightWin(player) || board.IsDiagonalWin(player);
private static bool IsDiagonalWin(this Player[,] board, Player player)
{
if (board[0, 0] == player && board[1, 1] == player && board[2, 2] == player)
return true;
if (board[0, 2] == player && board[1, 1] == player && board[2, 0] == player)
return true;
return false;
}
private static bool IsStraightWin(this Player[,] board, Player player)
{
for (var i = 0; i < 3; i++)
{
if (board[0, i] == player && board[1, i] == player && board[2, i] == player)
return true;
if (board[i, 0] == player && board[i, 1] == player && board[i, 2] == player)
return true;
}
return false;
}
}Now we can use BoardWinEvaluator to implement the evaluate method.
public double Evaluate(int depth, List<IState> passedThroughStates)
{
if (Board.IsWin(Player.Max))
return 1;
if (Board.IsWin(Player.Min))
return -1;
return 0;
}When implementing GetNeighbors, it's impotent to make sure that win states don't return any neighbors. That's why the first two lines in our method will check for a win - and return an empty list in case of one.
public IEnumerable<IState> GetNeighbors()
{
var isWin = Board.IsWin(Player.Max) || Board.IsWin(Player.Min);
if (isWin) return new List<IState>();
var neighbors = new List<TicTacToeState>();
for (var i = 0; i < 3; i++)
for (var j = 0; j < 3; j++)
if (Board[i, j] == Player.Empty)
{
var newBoard = (Player[,])Board.Clone();
newBoard[i, j] = Turn;
neighbors.Add(new TicTacToeState(newBoard, GetReversePlayer(Turn)));
}
return neighbors;
}
private Player GetReversePlayer(Player player) =>
player == Player.Max ? Player.Min : Player.Max;For every state, you should implement object's Equals and GetHashCode methods in a meaningful way. This is impotent since some of the Search Engine's optimizations rely on these methods.
Let's implement these methods:
public override bool Equals(object obj)
{
if (!(obj is TicTacToeState ticTacToeState))
return false;
if (Turn != ticTacToeState.Turn)
return false;
for (var i = 0; i < 3; i++)
for (var j = 0; j < 3; j++)
if (Board[i, j] != ticTacToeState.Board[i, j])
return false;
return true;
}
public override int GetHashCode()
{
int sum = 0;
for (var i = 0; i < 3; i++)
for (var j = 0; j < 3; j++)
sum += GetValue(Board[i, j]) * (int) Math.Pow(3, i + j * 3);
return sum + (int)Turn * (int) Math.Pow(3, 9);
}
private int GetValue(Player player)
{
switch (player)
{
case Player.Min:
return 1;
case Player.Max:
return 2;
default:
return 0;
}
}Finally, let's run a simple search to make sure our code works fine.
We'll create a state in which Player.Max can win next move and make sure that the Player.Min blocks Max's win.
var startState = new TicTacToeState(new[,]
{
{ Player.Empty, Player.Empty, Player.Empty},
{ Player.Empty, Player.Empty, Player.Empty},
{ Player.Max, Player.Empty, Player.Max},
}, Player.Min);
var searchEngine = new SearchEngine();
var searchResult = searchEngine.Search(startState, 2);
Console.WriteLine(((TicTacToeState)searchResult.NextMove).Board[2,1]); // Should print Player.Min class TicTacToeState : IDeterministicState
{
public Player[,] Board { get; }
public TicTacToeState(Player[,] board, Player turn)
{
this.Board = board;
Turn = turn;
}
public double Evaluate(int depth, List<IState> passedThroughStates)
{
if (Board.IsWin(Player.Max))
return 1;
if (Board.IsWin(Player.Min))
return -1;
return 0;
}
public Player Turn { get; }
public IEnumerable<IState> GetNeighbors()
{
var isWin = Board.IsWin(Player.Max) || Board.IsWin(Player.Min);
if (isWin) return new List<IState>();
var neighbors = new List<TicTacToeState>();
for (var i = 0; i < 3; i++)
for (var j = 0; j < 3; j++)
if (Board[i, j] == Player.Empty)
{
var newBoard = (Player[,])Board.Clone();
newBoard[i, j] = Turn;
neighbors.Add(new TicTacToeState(newBoard, Utils.GetReversePlayer(Turn)));
}
return neighbors;
}
private Player GetReversePlayer(Player player) =>
player == Player.Max ? Player.Min : Player.Max;
public override bool Equals(object obj)
{
if (!(obj is TicTacToeState ticTacToeState))
return false;
if (Turn != ticTacToeState.Turn)
return false;
for (var i = 0; i < 3; i++)
for (var j = 0; j < 3; j++)
if (Board[i, j] != ticTacToeState.Board[i, j])
return false;
return true;
}
public override int GetHashCode()
{
int sum = 0;
for (var i = 0; i < 3; i++)
for (var j = 0; j < 3; j++)
sum += GetValue(Board[i, j]) * (int)Math.Pow(3, i + j * 3);
return sum + (int)Turn * (int)Math.Pow(3, 9);
}
private int GetValue(Player player)
{
switch (player)
{
case Player.Min:
return 1;
case Player.Max:
return 2;
default:
return 0;
}
}
}And BoardWinEvaluator class
static class BoardWinEvaluator
{
public static bool IsWin(this Player[,] board, Player player) =>
board.IsStraightWin(player) || board.IsDiagonalWin(player);
private static bool IsDiagonalWin(this Player[,] board, Player player)
{
if (board[0, 0] == player && board[1, 1] == player && board[2, 2] == player)
return true;
if (board[0, 2] == player && board[1, 1] == player && board[2, 0] == player)
return true;
return false;
}
private static bool IsStraightWin(this Player[,] board, Player player)
{
for (var i = 0; i < 3; i++)
{
if (board[0, i] == player && board[1, i] == player && board[2, i] == player)
return true;
if (board[i, 0] == player && board[i, 1] == player && board[i, 2] == player)
return true;
}
return false;
}
}