Probabilistic Tic Tac Toe Tutorial - ZviRosenfeld/MinMaxSearch GitHub Wiki
In this tutorial, we'll implement a probabilistic version of Tic Tac Toe. Probabilistic Tic Tac Toe is the same as regular Tic Tac Toe but with one added rule. Before every player's turn they roll a dice, and can only place a token on a cell who's row is greater or equal to half of what they rolled (we assume the rows are numbered from top to bottom). For instance, if they rolled a 4, they'd be able to place a token in rows one and two, but not row three.
I'm using this example to show how MinMaxSearch can be used to implement a probabilistic game (a game with an element of luck in it).
Let's start by creating a class that will describes the tic tac toe board. Most of the elements of this class are taken from the TicTacToeState state class in the Tic Tac Toe Tutorial, so refer to that if something isn't clear to you.
class TicTacToeBoard
{
public Player[,] Board { get; }
public Player Turn { get; }
public TicTacToeBoard(Player[,] board, Player turn)
{
Board = board;
Turn = turn;
}
public double Evaluate(int depth, List<IState> passedThroughStates)
{
if (Board.IsWin(Player.Max)) // IsWin is an extension method defined in class BoardWinEvaluator
return 1;
if (Board.IsWin(Player.Min)) // IsWin is an extension method defined in class BoardWinEvaluator
return -1;
return 0;
}
public override bool Equals(object obj)
{
if (!(obj is TicTacToeBoard 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 the 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;
}
}Now, let's create a util class to get a board's list of neighbors. Note that this class is using the ProbabilisticTicTacToeState class that we'll create in the next section.
The GetNeighbors method returns a list of 3 list of possible moves, where each one has a probability of 1/3. The first list is if the player will roll a 1 or a 2; the second list for if they roll a 3 or 4, and the last is for a 5 or 6.
static class NeighborGenerator
{
// Note the extension methods
public static IEnumerable<Tuple<double, List<IState>>> GetNeighbors(this Player[,] board, Player turn)
{
if (board.IsWin(Player.Max) || board.IsWin(Player.Min))
return new List<Tuple<double, List<IState>>>();
return new List<Tuple<double, List<IState>>>()
{
new Tuple<double, List<IState>>(1.0 / 3, board.GetNeighbors(turn, 1)), // For rolling 1 or 2
new Tuple<double, List<IState>>(1.0 / 3, board.GetNeighbors(turn, 2)), // For rolling 3 or 4
new Tuple<double, List<IState>>(1.0 / 3, board.GetNeighbors(turn, 3)), // For rolling 5 or 6
};
}
public static List<IState> GetNeighbors(this Player[,] board, Player turn, int tillRow)
{
var neighbors = new List<IState>();
for (var i = 0; i < tillRow; 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 ProbabilisticTicTacToeState(newBoard, turn.GetReversePlayer()));
}
return neighbors;
}
private static Player GetReversePlayer(this Player player) =>
player == Player.Max ? Player.Min : Player.Max;
}With that, implement ProbabilisticTicTacToeState should be quite easy.
class ProbabilisticTicTacToeState : IProbabilisticState
{
public ProbabilisticTicTacToeState(Player[,] board, Player turn)
{
Board = new TicTacToeBoard(board, turn);
}
public TicTacToeBoard Board { get; }
public double Evaluate(int depth, List<IState> passedThroughStates) =>
Board.Evaluate(depth, passedThroughStates);
public Player Turn => Board.Turn;
public IEnumerable<Tuple<double, List<IState>>> GetNeighbors() =>
Board.Board.GetNeighbors(Turn);
public override bool Equals(object obj)
{
if (!(obj is ProbabilisticTicTacToeState probabilisticState))
return false;
return Board.Equals(probabilisticState.Board);
}
public override int GetHashCode() => Board.GetHashCode();
}You might notice that all of MinMaxSearch's search methods require a IDeterministicState as their start state. The reason for this is that MinMaxSearch answers the question "What move should I do next?" and this question only really makes sense when the player can choose his next move.
We expect the player to first roll the dice to see what moves are available to him, and then create a IDeterministicState from that dice roll.
Let's see how we can implement a IDeterministicState for our game.
class DeterministicTicTacToeState : IDeterministicState
{
public TicTacToeBoard Board { get; }
private int diceRoll;
public DeterministicTicTacToeState(Player[,] board, Player turn, int diceRoll)
{
this.diceRole = diceRole;
Board = new TicTacToeBoard(board, turn);
}
public double Evaluate(int depth, List<IState> passedThroughStates) =>
Board.Evaluate(depth, passedThroughStates);
public Player Turn => Board.Turn;
public IEnumerable<IState> GetNeighbors() =>
Board.Board.GetNeighbors(Turn, diceRoll);
public override bool Equals(object obj)
{
if (!(obj is DeterministicTicTacToeState deterministicState))
return false;
if (diceRole != deterministicState.diceRole)
return false;
return Board.Equals(deterministicState.Board);
}
public override int GetHashCode() => Board.GetHashCode();
}There. We now have all the states required to describe our probabilistic game.