Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Pawned!

#PAWNED!

######CMPT317 - KIRK MCCULLOCH – 11146754 ######MARCH 4, 2015

##PROBLEM DESCRIPTION Pawned is a simple game based on chess, which is played on a 5 by 6 board. Each player has five pawns (black or white) placed along either the top or bottom rows. Similar to how a pawn moves in chess, in Pawned a pawn can only move forwards, or attack on the left and right diagonals. Additionally, pawns in Pawned cannot move two spaces on their first move, they are restricted to single space moves. The goal of the game is to get one of your pawns to the opponent's side of the board.

In any given turn, players are required to make a move if a valid move is available. If a player cannot move any of their pawns (e.g. all pawns are stuck with an opponent's pawn in the square directly in front), then the player must pass and the turn changes to the opponent. The game ends when one player reaches the opposite side or all pawns on the board are unable to move, in which case the player with the most pawns wins.

##SOLUTION DESCRIPTION The key to an AI solution for Pawned lies in adversarial search. We have two players, white and black, who are competing against each other to breach the other's defensive line. Like chess, Pawned is a zero-sum game with perfect information. That is, a game in which when one player wins, the other must lose. If we assign values to wins and losses, a zero-sum game always ends with a utility balance of zero. Either one player wins (+1) and one loses (-1) or they tie (+½, -½) and the utility of the game's outcome will always equal zero. Pawned also has perfect information in the sense that no information is hidden from either player. The entire board is visible and it is always possible to determine what moves can be made in any given board state. There is no randomness.

The solution to such a problem lies in a minimax search tree. A minimax search tree is one in which every other level seeks to maximize or minimize utility. Consider such a tree as a tree of max nodes and min nodes. Each max node can only have min nodes as children and each min node can only have max nodes as children. If a max node has two children with utilities of 2 and 5, the node will prefer the node with maximum utility, 5. If a min node has the same two child values, it will prefer the node with minimum utility, 2. The leaf nodes at the bottom are all terminal nodes, which each have inherent utility values and cannot be max or min.

We can think of Pawned as a minimax problem where the white player seeks to maximize utility and the black player seeks to minimize utility. The game can then be represented as a series of alternating moves from each player, with directly opposing goals. The white player's moves all take place on max nodes and the black player's moves all take place on min nodes, in the search tree.

One key drawback of the minimax search is that it has to search through the entire depth and width in the tree down to each leaf node before determining the best option. To make this style of search a viable option we can use Alpha-Beta pruning to eliminate portions of the search tree, which we know will not benefit us. We accomplish this by maintaining two values as we traverse the tree:

  • Alpha (α) – The value of the best (highest) choice for max
  • Beta (β) – The value of the best (lowest) choice for min

As we traverse the tree, two actions allow us to prune off sections of the tree. Max nodes will check whether the current node's value is greater than or equal (>=) to Beta, and if so we stop searching this branch because we know that the min nodes will ignore values larger than Beta. Similarly, min nodes will check whether the current node's value is less than or equal (<=) to Alpha, and if so we can stop searching this branch because max nodes will ignore values smaller than Alpha.

##IMPLEMENTATION DESCRIPTION For my implementation of Pawned written in C#, I created a base program script and two helper object classes, a Pawn class and BoardState class. The Pawn class is a simple representation of a pawn and allows for a way to associate x and y board coordinates with either the white or black player. The BoardState class is where most of the game takes place.

At the core, each BoardState stores a representation of the board as a 2D string array, as well as a list of white pawns, a list of black pawns, and which player has the next turn. This class performs most of the basic operations needed to make the game functional, such as initializing a fresh game board, printing the game board to the console, and making a deep copy of a BoardState (used to make board states immutable when necessary). The class can also use a given BoardState to calculate all legal moves that a given player can make, move a pawn on the board (this is where immutability is necessary) as defined by a transition string, report whether it is a terminal game state, and calculate a utility value for the state.

The base program script is where the AI search happens. Once I had my base game representation implemented, particularly the move calculation function, I began implementing a simple proprietary minimax algorithm. The minimax player move function takes in a BoardState and a search depth limit. In the case where it is the white player's turn, it will determine which of the available moves has maximum utility and return that transition string. In the case where it is the black player's turn, it will determine which of the available moves has the minimum utility and return that transition string. It will also never search beyond the set search depth. I found that at depths upwards of about 7 or 8 the unpruned minimax search became far too lengthy to expect a human player to wait on it. To improve the speed I added an alternative search with Alpha-Beta pruning. The pruned search produced immediately noticeable improvement and made a depth of 14 possible in less than 1 minute.

There are also a few additional ways I tried to improve the search. The first is in the StateUtility function, which calculates the approximate value for a state. Rather than giving terminal states defined values, I used this function to calculate a value for all states, so that when the search has to stop at the depth limit, it can still determine an intermediate value based on the pawns on the board. The general concept behind the function is that positive outcomes for white (more white pawns, white win) generate positive utility and positive outcomes for black (more black pawns, black win) generate negative utility. When a state really is a terminal state, the function reports a dramatically skewed utility value dependent upon the player who won and how they won. This way, the max (white) player will always prefer a terminal state with a utility of several thousand, and the min (black) player will always prefer a terminal state with negative several thousand utility.

An additional idea I explored for the utility function, but did not completely implement, was to employ a kind of passed-pawn logic to find states that may not be terminal states, but had a guaranteed terminal state within a few moves. The idea is that if a player has a pawn at the middle point and there exist no enemy pawns that can intercept it, then that pawn is guaranteed to win within three moves. If we consider a board, where white has a pawn in the center row and third column up, then the triangle with a height of 3 squares and base of 5 squares directly in front of the white pawn is the area where an enemy pawn could intercept the white pawn. If we check this area relative to all white pawns on the board in the third row or better, we can find cases where a player is certain to win in a minimum number of moves. We can then apply a boost to the utility (either positive or negative, depending on player) for all board states where this occurs.

I also tested out a method of logging board states to build an implicit tree as a way to try to improve performance and avoid recalculating the same board states with each turn. I did this by implementing a key/value list of successor states with each BoardState. During search, if a successor state does not already exist, it gets created and the move string and new state are added to the collection for future reference. However, what I found was that storing those precalculated states used an excessive amount of memory without giving significant speed gain. I will expand on this more in the results section.

Additionally, I had been doing something similar before implementing the key/value collection. For the sake of keeping my code concise, I had created an attribute in the BoardState class to store the calculated set of move strings and mapped it to a C# property, which would only calculate the move set if not already computed. The result is an effective way to log board states into an implicit tree, without storing numerous BoardState objects. By logging only the move transition strings, I was able to nearly double performance speed with very little additional memory usage.

##RESULTS To test my implementation I wanted to see how the AI would perform both against itself, playing both white and black, and against a person. To facilitate this I have two main testing functions: an automated game of Pawned that reports the total running time from beginning to end, and a single player game that reports only the time taken to compute AI moves.

To test the time performance I performed several comparison tests with the automated game, to ensure a consistent move pattern. To play these games myself would make the move pattern inconsistent, because I would not always play the same way. The AI will always stay consistent. First, a comparison of Minimax vs Alpha-Beta search at depth 8.

img Figure 1 - Alpha-Beta on the left, Minimax on the right

Here, the Alpha-Beta search as no trouble at all while the Minimax lags behind, but still completes within a reasonably fast period. Next, I want to try a depth that would cause Alpha-Beta to have noticeable slowdown, depth 10.

img Figure 2 - Alpha-Beta on the left, Minimax on the right

Here, Alpha-Beta took noticeably longer to complete, but still completed in less than 4 seconds. Minimax on the other hand took over 4 minutes to complete. Clearly, the Alpha-Beta pruning is cutting out a huge portion of the search tree, and they both arrived at the same terminal state. Next, I want to stress the limits of Alpha-Beta by running a game at depth 15.

img Figure 3 - Alpha-Beta running at depth 15

It took almost 9 minutes to complete this game. Depth 15 seems to be just beyond the feasibly acceptable limit for real time games. All further tests were ran at depth 14 or less.

Next, I want to talk about the logging of board states. When I tried running, the search with logging on at depth 14, it used so much memory so quickly that it crashed before making a single move. I ran it again at depth 10 and it completed in about 5 seconds.

img img Figure 4 - Top crash at depth 14, bottom complete at depth 10, both with state logging

For comparison, I ran without logging at depth 14 and depth 10. Both used negligible memory (< 10MB).

img Figure 5 - Left depth 14, right depth 10

Finally, I want to compare the logging of move transition strings against logging nothing at all. This test was run at depth 14. By logging the move strings the computation time is roughly cut in half.

img Figure 6 - Left logging move strings, right logging nothing

In terms of performance against a person, the AI performs poorly at low depths. At a low depth such as 5 or 8, the search simply does not go deep enough in the tree to find any substantial utility changes. Regardless of what moves the player chooses the AI seems to follow a consistent pattern, rarely adjusting to counteract the player's moves. Small depth searches are fast, but dumb and very easily beaten by a human. When playing a game against a depth 14 search the difficulty of the game becomes more noticeable. The AI will take steps to counteract the player's moves earlier and I found I actually had to actively think about my next move to avoid losing. I lost several times, but depth 14 can still be beaten easily with a little care and attention. Depth 14 is also still quite fast. Over the course of a game, the AI usually only spent about 18 – 20 seconds searching.

##CONCLUSIONS Ultimately, my chief goal is to increase the depth as much as possible. Greater depth directly translates into increased "intelligence", but it also leads to greater processing time and memory usage if state logging is used. State logging is something that could potentially speed up the search at extremely deeper depths, but it requires so much memory to accomplish that the search cannot run effectively beyond shallow depths. Any performance increase that may come from state logging cannot be reliably measured at shallow depths. When the depth gets too deep, the search reaches a hard limit and the program crashes. Considering that tree logging creates a hard depth limit from how much memory is available, I judge no logging to be the better method. It allows me to increase the depth well beyond my memory limitation and the only limiting factor is how long I am willing to wait on the AI.

Since the AI without logging can run at deep depths with low memory impact and comparable speed, it could also run at extremely deeper depths where the AI with logging would have crashed without completion. By not using state logging, an Alpha-Beta search could theoretically be used to solve the game. It would take an extremely long time, but the program would be able to complete with a modest amount of memory.

The deeper I am able to make the depth, the smarter the AI effectively gets. I was able to beat a depth 14 AI with some practice, but deeper depths could stump me. Games ran at depth 15 took roughly 9 minutes to complete when entirely ran by the AI. In practice, the first move took most of that time (~7 minutes) and the rest of the game ran much faster. It could be feasible to play a game against a depth 15 opponent, with enough patience. Beyond depth 15, it is probably not realistic to expect a person to wait on the AI.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CMPT317Assignment2
{
public class BoardState
{
public const int BOARD_ARRAY_ROWS = 6;
public const int BOARD_ARRAY_COLS = 5;
#region Attributes
//store some data about the board
private string[,] board = new string[BOARD_ARRAY_ROWS, BOARD_ARRAY_COLS];
private List<Pawn> whites = new List<Pawn>();
private List<Pawn> blacks = new List<Pawn>();
private List<string> _legalMoves = null; //to log the list of possible moves
private double _utility = double.NegativeInfinity;
private Dictionary<string, BoardState> _moveDictionary; //used when logging board states
#endregion
#region Properties
public List<Pawn> Whites { get { return whites; } set { whites = value; } }
public List<Pawn> Blacks { get { return blacks; } set { blacks = value; } }
public List<Pawn> AllPawns { get { List<Pawn> all = new List<Pawn>(); all.AddRange(whites); all.AddRange(blacks); return all; } }
public int Steps { get; set; } //a count of the steps/#turns taken to reach this state
public string Turn { get; set; } // the player whose turn it is
public double Utility //a property to force calculation of utility value only when not done yet.
{
get
{
//if utility is not calculated, then calculate it
if (_utility == double.NegativeInfinity || _utility == double.PositiveInfinity) { _utility = BoardState.StateUtility(this); }
return _utility;
}
set { _utility = value; }
}
public List<string> LegalMoves //a property to force calculation of move list only when not done yet.
{
get
{
if (_legalMoves == null) { _legalMoves = BoardState.ComputeLegalMoves(this, Turn, true); }
return _legalMoves;
//return BoardState.ComputeLegalMoves(this, Turn, true); //to test not logging move strings
}
}
public Dictionary<string, BoardState> MoveDictionary
{
get
{
if (_moveDictionary == null) { _moveDictionary = new Dictionary<string, BoardState>(); }
return _moveDictionary;
}
set { _moveDictionary = value; }
}
#endregion
#region Constructors
/// <summary>
/// Empty constructor initializes a fresh game board
/// </summary>
public BoardState()
{
InitFreshBoard();
this.Steps = 0;
this.Turn = "W";
}
/// <summary>
/// a constructor to build a new BoardState from a predetermined list of pawns
/// </summary>
/// <param name="whites">list of white pawns</param>
/// <param name="blacks">list of black pawns</param>
/// <param name="turn">whose turn it is</param>
public BoardState(List<Pawn> whites, List<Pawn> blacks, string turn = "W")
{
this.whites = whites;
this.blacks = blacks;
FillBoardFromLists();
this.Steps = 0;
this.Turn = turn;
}
#endregion
#region Methods
/// <summary>
/// set the board to the new game state
/// </summary>
public void InitFreshBoard()
{
//all default pawn locations
blacks = new List<Pawn>();
blacks.Add(new Pawn("B", 0, 0));
blacks.Add(new Pawn("B", 1, 0));
blacks.Add(new Pawn("B", 2, 0));
blacks.Add(new Pawn("B", 3, 0));
blacks.Add(new Pawn("B", 4, 0));
whites = new List<Pawn>();
whites.Add(new Pawn("W", 0, 5));
whites.Add(new Pawn("W", 1, 5));
whites.Add(new Pawn("W", 2, 5));
whites.Add(new Pawn("W", 3, 5));
whites.Add(new Pawn("W", 4, 5));
//fill the board array
FillBoardFromLists();
}
/// <summary>
/// Use the white and black pawn lists to populate the board array
/// </summary>
public void FillBoardFromLists()
{
//fresh board
board = new string[BOARD_ARRAY_ROWS, BOARD_ARRAY_COLS];
//fill board with dots
for (int i = 0; i <= board.GetUpperBound(0); i++)
{
for (int j = 0; j <= board.GetUpperBound(1); j++)
{
board[i, j] = ".";
}
}
//use the x and y coords in the pawns to place them on the board
Action<Pawn> placeOnBoard = delegate(Pawn p) { board[p.y, p.x] = p.team; };
blacks.ForEach(placeOnBoard);
whites.ForEach(placeOnBoard);
}
/// <summary>
/// Basic print out of the game board
/// </summary>
public void PrintBoard()
{
Console.WriteLine("\n 0 1 2 3 4");
for (int i = 0; i <= board.GetUpperBound(0); i++)
{
Console.Write(i + " ");
for (int j = 0; j <= board.GetUpperBound(1); j++)
{
//print each character
Console.Write(board[i, j] + " ");
}
Console.WriteLine();
}
Console.WriteLine(); //just to add some white space to the console
}
/// <summary>
/// Takes the current board state and returns a DEEP copy of it.
/// Useful for maintaining immutability when making moves.
/// </summary>
/// <returns>deep copy duplicate of the given state</returns>
public BoardState Clone()
{
BoardState clone = new BoardState();
//deep clone all pawns into the boardstate clone
List<Pawn> cloneWhite = new List<Pawn>();
Action<Pawn> clonePawnWhite = delegate(Pawn p) { cloneWhite.Add(p.ShallowCopy()); };
this.Whites.ForEach(clonePawnWhite);
clone.Whites = cloneWhite;
List<Pawn> cloneBlack = new List<Pawn>();
Action<Pawn> clonePawnBlack = delegate(Pawn p) { cloneBlack.Add(p.ShallowCopy()); };
this.Blacks.ForEach(clonePawnBlack);
clone.Blacks = cloneBlack;
clone.FillBoardFromLists();
clone.Steps = this.Steps;
clone.Turn = this.Turn;
clone.MoveDictionary = this.MoveDictionary;
return clone;
}
/// <summary>
/// quick way to calculate whose turn is next
/// </summary>
/// <returns></returns>
public string OppositePlayer()
{
//if white, return black, else not white, so return white
return (this.Turn == "W") ? "B" : "W";
}
#endregion
#region Static Methods
/// <summary>
/// Gets the list of all possible moves for a given board state and player turn
/// </summary>
/// <param name="state">the state of the board</param>
/// <param name="turn">who's turn is it: W or B</param>
/// <returns>List<string> of all valid moves</returns>
public static List<string> ComputeLegalMoves(BoardState state, string turn = "W", bool loopCheck = false)
{
//if the requested turn is the state's turn, use LegalMoves parameter to avoid double calculation
if (turn == state.Turn && !loopCheck)
{
return state.LegalMoves;
}
List<string> legalMoves = new List<string>();
string[] moveTemplate = new string[3];
//set player in template
moveTemplate[0] = turn;
//is it white's turn?
if (turn == "W")
{
//need set of options for each live pawn
foreach (Pawn p in state.whites)
{
//set current position in template
moveTemplate[1] = p.Pos;
//now determine what moves this pawn can make
if ( p.y - 1 >= state.board.GetLowerBound(0) && //still within bounds?
state.board[p.y - 1, p.x] == "." ) //and see an empty spot in the FORWARD direction?
{
//if we've gotten here, we have everything we need to confirm and generate a valid move
moveTemplate[2] = "FW"; // this is a forward move
//now put the move in the legal moves list: "W-YxX-FW"
legalMoves.Add(moveTemplate[0] + "-" + moveTemplate[1] + "-" + moveTemplate[2]);
}
if (p.y - 1 >= state.board.GetLowerBound(0) && p.x + 1 <= state.board.GetUpperBound(1) && //still within bounds?
state.board[p.y - 1, p.x + 1] == "B") //and see a BLACK PAWN on the forward right diagonal?
{
//if we've gotten here, we have everything we need to confirm and generate a valid move
moveTemplate[2] = "CR"; // this is a capture right move
//now put the move in the legal moves list: "W-YxX-CR"
legalMoves.Add(moveTemplate[0] + "-" + moveTemplate[1] + "-" + moveTemplate[2]);
}
if (p.y - 1 >= state.board.GetLowerBound(0) && p.x - 1 >= state.board.GetLowerBound(1) && //still within bounds?
state.board[p.y - 1, p.x - 1] == "B") //and see a BLACK PAWN on the forward left diagonal?
{
//if we've gotten here, we have everything we need to confirm and generate a valid move
moveTemplate[2] = "CL"; // this is a capture left move
//now put the move in the legal moves list: "W-YxX-CR"
legalMoves.Add(moveTemplate[0] + "-" + moveTemplate[1] + "-" + moveTemplate[2]);
}
}
}
else //turn == B
{
//need set of options for each live pawn
foreach (Pawn p in state.blacks)
{
//set current position in template
moveTemplate[1] = p.Pos;
//now determine what moves this pawn can make
if (p.y + 1 <= state.board.GetUpperBound(0) && //still within bounds?
state.board[p.y + 1, p.x] == ".") //and see an empty spot in the FORWARD direction?
{
//if we've gotten here, we have everything we need to confirm and generate a valid move
moveTemplate[2] = "FW"; // this is a forward move
//now put the move in the legal moves list: "W-YxX-FW"
legalMoves.Add(moveTemplate[0] + "-" + moveTemplate[1] + "-" + moveTemplate[2]);
}
if (p.y + 1 <= state.board.GetUpperBound(0) && p.x - 1 >= state.board.GetLowerBound(1) && //still within bounds?
state.board[p.y + 1, p.x - 1] == "W") //and see a WHITE PAWN on the forward right diagonal?
{
//if we've gotten here, we have everything we need to confirm and generate a valid move
moveTemplate[2] = "CR"; // this is a capture right move
//now put the move in the legal moves list: "W-YxX-CR"
legalMoves.Add(moveTemplate[0] + "-" + moveTemplate[1] + "-" + moveTemplate[2]);
}
if (p.y + 1 <= state.board.GetUpperBound(0) && p.x + 1 <= state.board.GetUpperBound(1) && //still within bounds?
state.board[p.y + 1, p.x + 1] == "W") //and see a WHITE PAWN on the forward left diagonal?
{
//if we've gotten here, we have everything we need to confirm and generate a valid move
moveTemplate[2] = "CL"; // this is a capture left move
//now put the move in the legal moves list: "W-YxX-CR"
legalMoves.Add(moveTemplate[0] + "-" + moveTemplate[1] + "-" + moveTemplate[2]);
}
}
}
return legalMoves;
}
/// <summary>
/// Takes a board state and a move identifier string, and produces a new board state with the move applied.
/// Does NOT perform any validity checking. Invalid moves will be processed as if valid => errors!
///
/// IMPORTANT: Be sure to use BoardState.Clone() to only opperate on COPIES of boardstates. This method
/// WILL modify the passed in boardstate.
/// **2015/03/02 - method updated to perform cloning automatically
/// </summary>
/// <param name="state">The entry state to apply the move too </param>
/// <param name="move">A string defining the pawn move parameters
/// Follow form: [Player]-[Pos]-[Move]
/// i.e. W-5x3-FW
/// B-0x4-FW
/// W-3x3-CR
/// B-3x1-CL
/// ROWxCOL
///
/// </param>
/// <returns>new board state, post move</returns>
public static BoardState MovePawn(BoardState stateIn, string move, bool print = false)
{
//do we already know this move? uncomment this section for logging
//if (stateIn.MoveDictionary.ContainsKey(move))
//{
// BoardState dic;
// stateIn.MoveDictionary.TryGetValue(move, out dic);
// //Console.WriteLine("DICTONARY!");
// return dic;
//}
//clone
BoardState state = stateIn.Clone();
//deal with NO-MOVE turns, if a no move identifier is passed in, move nothing
if (move != "NO-MOVE")
{
//parse parameters
string[] moveParams = move.Split('-');
string[] coordString = moveParams[1].Split('x');
int[] coords = { Int32.Parse(coordString[0]), Int32.Parse(coordString[1]) };
Pawn finder = new Pawn(moveParams[0], coords[1], coords[0]);
//if player to move is white
if (moveParams[0] == "W")
{
//find pawn in list
int index = state.whites.IndexOf(finder);
//change position of the pawn
if (moveParams[2] == "FW") //forward
{
state.whites.ElementAt(index).Pos = (coords[0] - 1) + "x" + coords[1];
}
else if (moveParams[2] == "CR") //capture right
{
state.whites.ElementAt(index).Pos = (coords[0] - 1) + "x" + (coords[1] + 1);
//remove black pawn
int bindex = state.blacks.IndexOf(new Pawn("B", /*y*/coords[1] + 1, /*x*/coords[0] - 1));
state.blacks.RemoveAt(bindex);
}
else //CL - capture left
{
state.whites.ElementAt(index).Pos = (coords[0] - 1) + "x" + (coords[1] - 1);
//remove black pawn
int bindex = state.blacks.IndexOf(new Pawn("B", /*y*/coords[1] - 1, /*x*/coords[0] - 1));
state.blacks.RemoveAt(bindex);
}
}
else // else player is black
{
//find pawn in list
int index = state.blacks.IndexOf(finder);
//change position of the pawn
if (moveParams[2] == "FW") //forward
{
state.blacks.ElementAt(index).Pos = (coords[0] + 1) + "x" + coords[1];
}
else if (moveParams[2] == "CR") //capture right
{
state.blacks.ElementAt(index).Pos = (coords[0] + 1) + "x" + (coords[1] - 1);
//remove white pawn
int windex = state.whites.IndexOf(new Pawn("W", /*y*/coords[1] - 1, /*x*/coords[0] + 1));
state.whites.RemoveAt(windex);
}
else //CL - capture left
{
state.blacks.ElementAt(index).Pos = (coords[0] + 1) + "x" + (coords[1] + 1);
//remove white pawn
int windex = state.whites.IndexOf(new Pawn("W", /*y*/coords[1] + 1, /*x*/coords[0] + 1));
state.whites.RemoveAt(windex);
}
}
//now that we have new pawn positions, refill the board array representation
state.FillBoardFromLists();
if (print) //print only if asked too
state.PrintBoard();
}
state.Steps++; //make sure we count the move
state.Turn = stateIn.OppositePlayer(); //give next turn to other player
//stateIn.MoveDictionary.Add(move, state); //uncomment for logging
return state;
}
/// <summary>
/// Determines whether the passed in state is a final game state of either stalemate or winning player
///
/// Causes of end game:
/// - Neither player can make a move - stalemate
/// - A white pawn has reached the top row - white wins
/// - A black pawn has reached the bottom row - black wins
/// </summary>
/// <param name="state">the state of the board</param>
/// <returns>is end game or not (true/false)</returns>
public static bool IsEndGame(BoardState state)
{
double graveyard = 0;
return IsEndGame(state, out graveyard);
}
/// <summary>
/// Determines whether the passed in state is a final game state of either stalemate or winning player
///
/// Causes of end game:
/// - Neither player can make a move - stalemate
/// - A white pawn has reached the top row - white wins
/// - A black pawn has reached the bottom row - black wins
/// </summary>
/// <param name="state">the state of the board</param>
/// <param name="terminalUtility">an output parameter that can be used to return a large positive or
/// negative number signifying terminal state utility</param>
/// <returns>is end game or not (true/false)</returns>
public static bool IsEndGame(BoardState state, out double terminalUtility)
{
bool endGame = false;
terminalUtility = 0;
//has white reached the top row? i.e. white pawn in row 0
Action<Pawn> whitePawnWin = delegate(Pawn p) { endGame = (p.y == 0) ? true : endGame ; };
state.whites.ForEach(whitePawnWin);
//if white won, show in utility. Add 10000 so that subtracting 5000 results in +5000 for white
terminalUtility = (endGame) ? terminalUtility + 10000 : terminalUtility;
//has black reached the bottom row? i.e. back pawn in row 5
Action<Pawn> blackPawnWin = delegate(Pawn p) { endGame = (p.y == 5) ? true : endGame; };
state.blacks.ForEach(blackPawnWin);
//black won, show in utility. Subtract 5000 for black
terminalUtility = (endGame) ? terminalUtility - 5000 : terminalUtility;
//have we reached stalemate?
List<string> whiteMoves = BoardState.ComputeLegalMoves(state, "W");
List<string> blackMoves = BoardState.ComputeLegalMoves(state, "B");
endGame = ((whiteMoves.Count + blackMoves.Count) < 1) ? true : endGame;
//stalemate, but who has most pawns
terminalUtility = (endGame) ? (state.Whites.Count > state.Blacks.Count) ? terminalUtility + 500 : terminalUtility - 500 : terminalUtility;
return endGame;
}
/// <summary>
/// Computes a utility value for a given state based on the # of pawns each player has, where
/// the pawns are on the board, whether we've found a terminal state, and what type of
/// terminal state we may have found
/// </summary>
/// <param name="state">the state of the board</param>
/// <returns>a utilit value as a double</returns>
public static double StateUtility(BoardState state)
{
/**
* Written from the perspective of the white player. So positive
* outcomes for white create utility, positive outcomes for black creates disutility.
*
* any case where a move is made, but nobody loses a pawn or wins the game, will NOT
* cause a significant change in utility, so it may appear that all moves are equal, in some iterations.
* This is not a problem if we consider deep enough states that players start to capture pawns.
* */
double utility = (state._utility == double.NegativeInfinity || state._utility == double.PositiveInfinity) ? 0 : state._utility;
utility += state.Whites.Count; //having more white pawns is good (for the white player)
utility -= state.Blacks.Count; //having more black pawns is bad (for the white player)
/**
* through this, moves which cause the white player to capture will be preferred, because
* they lead to the opponent (black) having fewer pawns left to work with. Likewise, moves
* which cause the black player to capture will be less valuable.
* */
// if we find a terminal state, use the type (win, lose, stalemate-tie, stalemate-win, stalemate-lose)
// to affect the utility of a state
double terminalUtility = 0;
BoardState.IsEndGame(state, out terminalUtility);
utility += terminalUtility;
//factor in passed-pawn logic - not fully implemented
//utility += BoardState.PassedPawn(state);
// work out closeness to finish line FOR THE CLOSEST PAWN ONLY
// i.e. foreach white pawn, 0+y=dist, subtract dist from utility
// foreach black pawn, 5-y=dist, add dist to utility
double closestDist = 6;
foreach (Pawn p in state.Whites)
{
closestDist = (0+p.y < closestDist) ? 0+p.y : closestDist;
}
utility -= closestDist; //lower the utility by how far away white pawn is
closestDist = 6;
foreach (Pawn p in state.Blacks)
{
closestDist = (5 - p.y < closestDist) ? 5 - p.y : closestDist;
}
utility += closestDist; //raise utility by how far away black is
return utility;
}
/// <summary>
/// Prototype method for passed-pawn logic. Never fully implemented. See discription below.
/// </summary>
/// <param name="state"></param>
/// <returns></returns>
public static double PassedPawn(BoardState state)
{
//TODO: Implement passed-pawn logic to find winning terminal states when a player's pawn
// has passed the point where an enemy pawn could intercept it
// CHECK if Turn is W AND this pawn is in row 3 or better (2 or better for black) AND for all rows above (below
// for black) there are no enemy pawns in the two adjacent columns on either side or in front
// i.e. check up to ColNo+2 and ColNo-2
// FOR middle column need to check both columns on both sides
// FOR far left or far right, need to check only to right or left
/* Example: Check in the shape of a pyramid in front of the given pawn passed the middle row
* If all spaces in the pyramid are free of enemy pawns, then this state is effectively terminal
* and can be assigned a value as such
*
* 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
* 0 B B B B B 0 . . . . . 0 . . . . .
* 1 . B B B . 1 . . . . . 1 . . . . .
* 2 . . B . . 2 . . B . . 2 . . . . .
* 3 . . W . . 3 . . W . . 3 . . B . .
* 4 . . . . . 4 . W W W . 4 . . W . .
* 5 . . . . . 5 W W W W W 5 . W W W .
* */
double ppUtility = 0;
bool foundOpponent = false; //false until we find an opponent pawn
if (state.Turn == "W")
{
foreach (Pawn p in state.Whites)
{
if (p.y <= 3) // if we are at least half way
{
//p.y - 1 >= state.board.GetLowerBound(0) && p.x + 1 <= state.board.GetUpperBound(1)
int row = p.y - 1; //start from one row up
//one row up
if (row >= state.board.GetLowerBound(0)) //still within bounds?
{
if (state.board[row, p.x] != "B") //is the space in front clear?
{
//so far so good
//two rows up
row--;
if (row >= state.board.GetLowerBound(0)) //still within bounds?
{
if (!(p.x - 1 >= state.board.GetLowerBound(1) && //still within bounds to left?
state.board[row, p.x - 1] != "B"))// now check the spaces are clear
{
//if we are here, then we DID find a space with a B
foundOpponent = true;
}
if (!(p.x + 1 <= state.board.GetUpperBound(1) && //still within bounds to right?
state.board[row, p.x + 1] != "B"))// now check the spaces are clear
{
//if we are here, then we DID find a space with a B
foundOpponent = true;
}
}
//three rows up
row--;
if (row >= state.board.GetLowerBound(0)) //still within bounds?
{
if (!(p.x - 1 >= state.board.GetLowerBound(1) && //still within bounds to left?
state.board[row, p.x - 1] != "B"))// now check the spaces are clear
{
//if we are here, then we DID find a space with a B
foundOpponent = true;
}
if (!(p.x + 1 <= state.board.GetUpperBound(1) && //still within bounds to right?
state.board[row, p.x + 1] != "B"))// now check the spaces are clear
{
//if we are here, then we DID find a space with a B
foundOpponent = true;
}
if (!(p.x - 2 >= state.board.GetLowerBound(1) && //still within bounds to left?
state.board[row, p.x - 2] != "B"))// now check the spaces are clear
{
//if we are here, then we DID find a space with a B
foundOpponent = true;
}
if (!(p.x + 2 <= state.board.GetUpperBound(1) && //still within bounds to right?
state.board[row, p.x + 2] != "B"))// now check the spaces are clear
{
//if we are here, then we DID find a space with a B
foundOpponent = true;
}
}
}
else //found B on first row
{
foundOpponent = true;
}
}
}
//now we need to know if we ran into an opponent
if (!foundOpponent) //if not
{
//we didn't find any black pawns, thus we have a passed-pawn state
ppUtility += 750; //nice big recognizable jump
}
}
}
else //Turn = B ////////////////////////////////////////////////////////////////////////////////////
{
foreach (Pawn p in state.Blacks)
{
if (p.y >= 2) //are we half way?
{
int row = p.y + 1; //start from one row down
//one row up
if (row <= state.board.GetUpperBound(0)) //still within bounds?
{
if (state.board[row, p.x] != "W") //is the space in front clear?
{
//so far so good
//two rows up
row++;
if (row <= state.board.GetUpperBound(0)) //still within bounds?
{
if (!(p.x - 1 >= state.board.GetLowerBound(1) && //still within bounds to left?
state.board[row, p.x - 1] != "W"))// now check the spaces are clear
{
//if we are here, then we DID find a space with a W
foundOpponent = true;
}
if (!(p.x + 1 <= state.board.GetUpperBound(1) && //still within bounds to right?
state.board[row, p.x + 1] != "W"))// now check the spaces are clear
{
//if we are here, then we DID find a space with a W
foundOpponent = true;
}
}
//three rows up
row++;
if (row <= state.board.GetUpperBound(0)) //still within bounds?
{
if (!(p.x - 1 >= state.board.GetLowerBound(1) && //still within bounds to left?
state.board[row, p.x - 1] != "W"))// now check the spaces are clear
{
//if we are here, then we DID find a space with a W
foundOpponent = true;
}
if (!(p.x + 1 <= state.board.GetUpperBound(1) && //still within bounds to right?
state.board[row, p.x + 1] != "W"))// now check the spaces are clear
{
//if we are here, then we DID find a space with a W
foundOpponent = true;
}
if (!(p.x - 2 >= state.board.GetLowerBound(1) && //still within bounds to left?
state.board[row, p.x - 2] != "W"))// now check the spaces are clear
{
//if we are here, then we DID find a space with a W
foundOpponent = true;
}
if (!(p.x + 2 <= state.board.GetUpperBound(1) && //still within bounds to right?
state.board[row, p.x + 2] != "W"))// now check the spaces are clear
{
//if we are here, then we DID find a space with a W
foundOpponent = true;
}
}
}
else //found W on first row
{
foundOpponent = true;
}
}
//now we need to know if we ran into an opponent
if (!foundOpponent) //if not
{
//we didn't find any black pawns, thus we have a passed-pawn state
ppUtility -= 750; //nice big recognizable jump
}
}
}
}
return ppUtility;
}
#endregion
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CMPT317Assignment2
{
public class Pawn
{
public int x, y;
public string team; //B or W
/// <summary>
/// Returns pawn position in the form of ROWxCOL i.e. YxX
/// </summary>
public string Pos
{
//retrns an easy comparison string of the form 1x1 or YxX or ROWxCOL
get { return y + "x" + x; }
set
{
this.y = Int32.Parse(value.Split('x')[0]);
this.x = Int32.Parse(value.Split('x')[1]);
}
}
/// <summary>
/// Pawn constructor
/// </summary>
/// <param name="team">The player this pawn belongs too (W or B)</param>
/// <param name="x">the x position of the pawn, i.e. the zero indexed COLUMN</param>
/// <param name="y">the y position of the pawn, i.e. the zero indexed ROW</param>
public Pawn(string team, int x, int y)
{
this.team = team;
this.x = x;
this.y = y;
}
public override bool Equals(Object other)
{
return this.team == ((Pawn)other).team && this.x == ((Pawn)other).x && this.y == ((Pawn)other).y;
}
public override int GetHashCode()
{
return base.GetHashCode();
}
public Pawn ShallowCopy()
{
return (Pawn) this.MemberwiseClone();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace CMPT317Assignment2
{
class Program
{
public static BoardState masterBoard;
public static double depthLimit = 14;
static void Main(string[] args)
{
//TestAutomatedGame();
InteractivePawned();
}
#region Test functions
public static void InteractivePawned()
{
//set up a fresh board
masterBoard = new BoardState();
Console.WriteLine("New game get!");
masterBoard.PrintBoard();
Stopwatch watch = new Stopwatch();
while (!BoardState.IsEndGame(masterBoard))
{
//let player be white and have first turn
Console.WriteLine("Turn: " + masterBoard.Turn);
List<string> playerMoves = masterBoard.LegalMoves;
if (masterBoard.Turn == "W")
{
Console.Write("Moves: \n");
foreach (string move in playerMoves)
{
Console.WriteLine(playerMoves.IndexOf(move) + " - [" + move + "]");
}
int playerMove = GetPlayerMoveChoice(playerMoves);
//use entered move
masterBoard = BoardState.MovePawn(masterBoard, playerMoves[playerMove], true);
}
else
{
Console.WriteLine("Calculating... Please stand by");
watch.Start();
string aiMove = AlphaBetaMove(masterBoard, depthLimit);
watch.Stop();
Console.WriteLine("AI Calc Time: " + watch.Elapsed);
masterBoard = BoardState.MovePawn(masterBoard, aiMove, true);
}
}
Console.WriteLine("AI Calc Time: " + watch.Elapsed);
Console.WriteLine("Game set!");
}
/// <summary>
/// Simple script to ask the player to enter a move
/// </summary>
/// <param name="playerMoves">list of move the player can choose from</param>
/// <returns>player's choice and an index number</returns>
public static int GetPlayerMoveChoice(List<string> playerMoves)
{
int playerMove = -1;
do
{
Console.Write("Please choose a move by entering the index number: ");
try
{
string input = Console.ReadKey().KeyChar + "";
playerMove = Int32.Parse(input);
}
catch (FormatException e) { Console.WriteLine("\nERROR! Please enter a number from 0 - " + (playerMoves.Count-1)); playerMove = -1; }
catch (ArgumentNullException e) { Console.WriteLine("\nERROR! Please enter a number from 0 - " + (playerMoves.Count-1)); playerMove = -1; }
Console.Write("\n");
} while (playerMove == -1 || playerMove >= playerMoves.Count);
return playerMove;
}
public static void TestAutomatedGame()
{
masterBoard = new BoardState();
masterBoard.PrintBoard();
//Console.WriteLine("Best Move: " + MinimaxMove(masterBoard, 5));
Stopwatch watch = Stopwatch.StartNew();
string move = "";
do
{
//get best move
//move = MinimaxMove(masterBoard, depthLimit);
move = AlphaBetaMove(masterBoard, depthLimit);
//Console.ReadLine(); //reads the next line of test from stdin i.e. read everything users types until <enter>
//make move
masterBoard = BoardState.MovePawn(masterBoard, move);
masterBoard.PrintBoard();
watch.Stop();
Console.WriteLine("Time So Far: " + watch.Elapsed);
//Console.WriteLine("Press any key to continue... ");
//Console.ReadKey(true); //wait for user to confirm proceed
watch.Start();
//loop until game ends
}while (!BoardState.IsEndGame(masterBoard));
watch.Stop();
Console.WriteLine("Elapsed: \nTime - " + watch.Elapsed +"\nMilliseconds - "+ watch.ElapsedMilliseconds +"\nTicks - "+ watch.ElapsedTicks);
Console.WriteLine("Press <enter> to quit... ");
Console.ReadLine(); //wait for user to confirm proceed
}
/// <summary>
/// And early function I used to make sure my Minimax was working correctly
/// </summary>
public static void TestMinimax()
{
//BoardState oneNone = new BoardState();
List<Pawn> www = new List<Pawn>();
List<Pawn> bbb = new List<Pawn>();
www.Add(new Pawn("W", 3, 3));
www.Add(new Pawn("W", 0, 5));
bbb.Add(new Pawn("B", 4, 2));
BoardState oneNone = new BoardState(www, bbb, "W"); //white turn
Action<string> PrintMove = delegate(string s) { Console.Write("[" + s + "]"); };
Console.Write("WHITEMOVES"); BoardState.ComputeLegalMoves(oneNone, "W").ForEach(PrintMove);
Console.Write("\nBLACKMOVES"); BoardState.ComputeLegalMoves(oneNone, "B").ForEach(PrintMove);
oneNone.PrintBoard();
Console.WriteLine("Best Move: " + MinimaxMove(oneNone));
int i = 0;
}
/// <summary>
/// An early tester to see that move strings were being handled correctly and several other BoardState operations
/// </summary>
public static void TestParameterPassing()
{
BoardState first = new BoardState();
Console.Write("First: \n"); first.PrintBoard();
BoardState second = BoardState.MovePawn(first.Clone(), "W-5x3-FW");
Console.Write("First: \n"); first.PrintBoard();
Console.Write("Second: \n"); second.PrintBoard();//currently passing by object reference value, thus changes permeate through to "first"
//test successor generator
Action<string> printMoveIdentifier = delegate(string s) { Console.Write("[" + s + "]"); };
BoardState locomotion = new BoardState();
locomotion = BoardState.MovePawn(locomotion, "W-5x3-FW");
locomotion = BoardState.MovePawn(locomotion, "B-0x4-FW");
locomotion = BoardState.MovePawn(locomotion, "W-4x3-FW");
locomotion = BoardState.MovePawn(locomotion, "B-1x4-FW");
//locomotion = BoardState.MovePawn(locomotion, "B-2x4-CR");
locomotion = BoardState.MovePawn(locomotion, "W-3x3-CR"); //TODO: not capturing properly, pawn still kept in list after capture
//locomotion.PrintBoard();
List<string> whiteMoves = BoardState.ComputeLegalMoves(locomotion);
whiteMoves.ForEach(printMoveIdentifier);
Console.WriteLine();
List<string> blackMoves = BoardState.ComputeLegalMoves(locomotion,"B");
blackMoves.ForEach(printMoveIdentifier);
Console.WriteLine();
//test endgame checkerizer
Console.WriteLine(BoardState.IsEndGame(locomotion));
BoardState endSim = new BoardState();
//endSim.Blacks.Add(new Pawn("B", 3, 5));
endSim.Whites.Add(new Pawn("W", 3, 0));
endSim.PrintBoard();
//Console.WriteLine("Black win: " + BoardState.IsEndGame(endSim));
Console.WriteLine("White win: " + BoardState.IsEndGame(endSim));
List<Pawn> www = new List<Pawn>();
List<Pawn> bbb = new List<Pawn>();
www.Add(new Pawn("W", 3, 3));
bbb.Add(new Pawn("B", 3, 2));
endSim = new BoardState(www, bbb);
endSim.PrintBoard();
Console.WriteLine("Stalemate: " + BoardState.IsEndGame(endSim));
}
#endregion
#region Minimax
/// <summary>
/// For all possible moves given th state, will determine which is the best move and return it.
/// </summary>
/// <param name="state"> current board state</param>
/// <returns>The move parameter string for the move with best utility</returns>
public static string MinimaxMove(BoardState state, double limit = double.PositiveInfinity)
{
string bestMove = "NO-MOVE"; //NO-MOVE will return when the player can't move, this will cause a turn skip
double bestUtility = 0;
if (state.Turn == "W")// if white's turn
{
// need to find the MAX of all MinMoves on each successor
bestUtility = double.NegativeInfinity;
double stepUtility = double.NaN;
foreach (string m in state.LegalMoves) //all of white's moves
{
BoardState step = BoardState.MovePawn(state, m);
stepUtility = Math.Max(bestUtility, MinMove(step,limit)); //determine if this move step has better utility
bestMove = (stepUtility == bestUtility) ? bestMove : m; //if it does, change the best move string [left to right logic]
bestUtility = stepUtility; // make sure best utility is which ever was better
}
}
else //Turn == B
{
// need to find the MIN of all MaxMoves on each successor
bestUtility = double.PositiveInfinity;
double stepUtility = double.NaN;
foreach (string m in state.LegalMoves) //all of black's moves
{
BoardState step = BoardState.MovePawn(state, m);
stepUtility = Math.Min(bestUtility, MaxMove(step,limit)); //determine if this move step has better utility
bestMove = (stepUtility == bestUtility) ? bestMove : m; //if it does, change the best move string [left to right logic]
bestUtility = stepUtility; // make sure best utility is which ever was better
}
}
Console.WriteLine("Best Utility " + state.Turn + ": " + bestUtility + " Best Move: " + bestMove);
return bestMove;
}
/// <summary>
/// Traverses the game tree in search of the greatest utility value that min will allow
/// Recurses into MinMove()
/// </summary>
/// <param name="state">state to begin max search from</param>
/// <returns>The highest utility value found below starting state</returns>
public static double MaxMove(BoardState state, double limit = double.PositiveInfinity)
{
//for tracking moves in the search while testing
//Action<string> PrintMove = delegate(string s) { Console.Write("["+s+"]"); };
//Console.WriteLine("MaxMove Depth: " + state.Steps + " Moves: ");
//BoardState.ComputeLegalMoves(state, "W").ForEach(PrintMove);
//are we at the limit?
if (state.Steps >= limit)
{
//if yes, break recursion
return state.Utility;
}
double utility = double.MinValue; //default to smallest possible value that is not infinity
//is this state a terminal state?
if (BoardState.IsEndGame(state))
{
//if yes, return the utility of self
utility = state.Utility;
}
else // NOT terminal
{
// for all possible moves, find the max utility of all min player's moves
foreach (string m in BoardState.ComputeLegalMoves(state, "W"))
{
utility = Math.Max(utility, MinMove(BoardState.MovePawn(state,m), limit));
}
}
//Console.WriteLine("MAX Utility " + state.Turn + ": " + utility ); //for easily seeing the maximum found utility for this state
return utility;
}
/// <summary>
/// Traverses the game tree in search of the lowest utility value the max will allow
/// Recurses into MaxMove()
/// </summary>
/// <param name="state">state to begin min search from</param>
/// <returns>the lowest utility value found below starting state</returns>
public static double MinMove(BoardState state, double limit = double.PositiveInfinity)
{
//for tracking moves in the search while testing
//Action<string> PrintMove = delegate(string s) { Console.Write("["+s+"]"); };
//Console.WriteLine("MinMove Depth: " + state.Steps + " Moves: ");
//BoardState.ComputeLegalMoves(state, "B").ForEach(PrintMove);
//are we at the limit?
if (state.Steps >= limit)
{
//if yes, break recursion
return state.Utility;
}
double utility = double.MaxValue; //default to largest possible value that is not infinite
//is this state a terminal state?
if (BoardState.IsEndGame(state))
{
//if yes, return the utility of self
utility = state.Utility;
}
else // NOT terminal
{
// for all possible moves, find the min utility of all max player's moves
foreach (string m in BoardState.ComputeLegalMoves(state, "B")) //all black moves
{
utility = Math.Min(utility, MaxMove(BoardState.MovePawn(state, m), limit));
}
}
//Console.WriteLine("MIN Utility " + state.Turn + ": " + utility);
return utility;
}
#endregion
#region AlphaBeta Pruning
/// <summary>
/// For all possible moves in given state, will determine which is the best move and return it.
/// </summary>
/// <param name="state"> current board state</param>
/// <returns>The move parameter string for the move with best utility</returns>
public static string AlphaBetaMove(BoardState state, double limit = double.PositiveInfinity)
{
string bestMove = "NO-MOVE"; //NO-MOVE will return when the player can't move, this will cause a turn skip
double bestUtility = 0;
if (state.Turn == "W")// if white's turn
{
// need to find the MAX of all MinMoves on each successor
bestUtility = double.NegativeInfinity;
double stepUtility = double.NaN;
foreach (string m in state.LegalMoves) // all white's moves
{
BoardState step = BoardState.MovePawn(state, m);
stepUtility = Math.Max(bestUtility, MinMove(step, double.NegativeInfinity, double.PositiveInfinity, limit)); //determine if this move step has better utility
bestMove = (stepUtility == bestUtility) ? bestMove : m; //if it does, change the best move string [left to right logic]
bestUtility = stepUtility; // make sure best utility is which ever was better
}
}
else //Turn == B
{
// need to find the MIN of all MaxMoves on each successor
bestUtility = double.PositiveInfinity;
double stepUtility = double.NaN;
foreach (string m in state.LegalMoves) //all black's moves
{
BoardState step = BoardState.MovePawn(state, m);
stepUtility = Math.Min(bestUtility, MaxMove(step, double.NegativeInfinity, double.PositiveInfinity, limit)); //determine if this move step has better utility
bestMove = (stepUtility == bestUtility) ? bestMove : m; //if it does, change the best move string [left to right logic]
bestUtility = stepUtility; // make sure best utility is which ever was better
}
}
Console.WriteLine("Best Utility " + state.Turn + ": " + bestUtility + " Best Move: " + bestMove);
return bestMove;
}
/// <summary>
/// Traverses the game tree in search of the greatest utility value that min will allow
/// Recurses into MinMove()
/// </summary>
/// <param name="state">state to begin max search from</param>
/// <returns>The highest utility value found below starting state</returns>
public static double MaxMove(BoardState state, double alpha, double beta, double limit = double.PositiveInfinity)
{
//are we at the limit?
if (state.Steps >= limit)
{
//if yes, break recursion
return state.Utility;
}
double utility = double.MinValue; //default to smallest possible value not infinite
//is this state a terminal state?
if (BoardState.IsEndGame(state))
{
//if yes, return the utility of self
utility = state.Utility;
}
else // NOT terminal
{
// for all possible moves, find the max utility of all min player's moves
foreach (string m in BoardState.ComputeLegalMoves(state, "W"))
{
utility = Math.Max(utility, MinMove(BoardState.MovePawn(state, m), alpha, beta, limit));
//do additional logic for Alpha-Beta pruning
if (utility >= beta)
{
return utility;
}
alpha = Math.Max(alpha, utility); //keep track of max utility SO FAR
}
}
//Console.WriteLine("MAX Utility " + state.Turn + ": " + utility);
return utility;
}
/// <summary>
/// Traverses the game tree in search of the lowest utility value the max will allow
/// Recurses into MaxMove()
/// </summary>
/// <param name="state">state to begin min search from</param>
/// <returns>the lowest utility value found below starting state</returns>
public static double MinMove(BoardState state, double alpha, double beta, double limit = double.PositiveInfinity)
{
//are we at the limit?
if (state.Steps >= limit)
{
//if yes, break recursion
return state.Utility;
}
double utility = double.MaxValue; //default to largest possible value that is not infinite
//is this state a terminal state?
if (BoardState.IsEndGame(state))
{
//if yes, return the utility of self
utility = state.Utility;
}
else // NOT terminal
{
// for all possible moves, find the min utility of all max player's moves
foreach (string m in BoardState.ComputeLegalMoves(state, "B")) //all black moves
{
utility = Math.Min(utility, MaxMove(BoardState.MovePawn(state, m), alpha, beta, limit));
//do additional logic for Alpha-Beta pruning
if (utility <= alpha)
{
return utility;
}
beta = Math.Min(beta, utility); //keep track of min utility SO FAR
}
}
//Console.WriteLine("MIN Utility " + state.Turn + ": " + utility);
return utility;
}
#endregion
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.