This program was developed because I couldn't find one with the features I needed when looking for a Revesi/Othell game.
Introduction
There are many Reversi programs already, and I chose to develop this program because I couldn't find one with the features I needed when looking for a Revesi/Othell game.
Features
- Supports Mode Human vs Human, Human vs Bot, Bot vs Bot
- Supports board editor
- Supports Bot creator. You can choose an image and customize an AI score that will be used to evaluate the board.
- Can show the bot's last move
Minimax
search tree - Can change the profile picture of
Human Player1
and Human Player2
- Can navigate the move
- Support Dark Mode
File Extensions Used by the Program
- .brd is used as board information.
- .bot is used as bot information.
- .rev is used as game save information, Game information retains the history of the move, which is what distinguishes it from a board game, so you can navigate it via the navigate control.
How to Play
The rule of the game is exactly the same as a normal Reversi game.
The Concept
File Structure of the Project
Graphic
In this section, I would like to talk about the classes responsible to render the graphic, but I will not mention anything related to the Board Editor or Bot Creator yet.
The Game Board
The board also can display numbers.
UI\PictureBoxBoard.cs
This is a class that inherits from PictureBox
control.
It is responsible to display the Reversi board. This class itself consists of the control called pictureBoxTable
.
The pictureBoxTable
control will be the one that renders the table can disk from the pictureBoxTable_Paint()
method.
The pictureBoxTable_Paint()
method reads the board information from this class to
draw the table and disk.
This is the logic for drawing the board.
-
There is an array of 64 Rectangles. We create these 64 Rectangles to store the position of the cells on the board.
-
This method will call:
DrawBoard()
to draw the board table DrawIntersection()
as its names suggest DrawDisk()
just draws the disk DrawRedDot()
to show which is the last put position DrawDiskBorder()
to show which cell can be put DrawNumber()
- This method is for when we need to display the score of the cell.
All of the drawings in this method just use basic GDI+ methods such as FillEllipse()
, DrawEllipse()
, DrawRectangles()
There are no images being used for board drawing. These are the logic for drawing the notation:
- Just loop from 0 to 7.
- using
DrawString()
method to draw the string
This control has PictureBoxBoard_Paint()
method to render the notation.
public enum CellImageEnum
{
WhiteCell,
BlackCell,
BlankCell,
BlankCellWithRed
}
public enum BoardModeEnum
{
PlayMode,
EditMode
}
public Boolean IsSmallBoard { get; set; } = false;
public Boolean IsHideLegent { get; set; } = false;
public Boolean IsDrawNotion { get; set; } = true;
public event PictureBoxCellClick CellClick;
private void PictureBox1_MouseDown(object sender, MouseEventArgs e)
{
if (e.Button != MouseButtons.Left)
{
return;
}
int X = e.X;
int Y = e.Y;
int RowClick = Y / CellSize;
int ColClick = X / CellSize;
if (RowClick >= NoofRow ||
ColClick >= NoofRow ||
RowClick < 0 ||
ColClick < 0)
{
return;
}
if (CellClick != null)
{
CellClick(this, new Position(RowClick, ColClick));
}
}
private void DrawNumber(Graphics g, int Number, Rectangle rec)
{
Rectangle r = rec;
r.Height -= 10;
r.Width -= 10;
r.X += 10;
r.Y += 15;
Font SegoeUIFont = new Font("Segoe UI", 14, FontStyle.Bold);
Color NumberColor = Color.FromArgb(150, 180, 180);
String NumberText = "+" + Number;
if(Number < 0)
{
NumberText = Number.ToString ();
NumberColor = Color.FromArgb(255, 199, 79);
}
PointF pointF = new PointF(r.X, r.Y);
SolidBrush solidBrush = new SolidBrush(NumberColor );
g.DrawString(NumberText ,
SegoeUIFont,
solidBrush, pointF );
solidBrush.Dispose();
}
private void DrawDisk(Graphics g, CellImageEnum CellImage, Rectangle rec)
{
if (CellImage == CellImageEnum.BlankCell)
{
return;
}
Rectangle r = rec;
r.Height -= 10;
r.Width -= 10;
r.X += 5;
r.Y += 5;
DrawDiskBorder(g, r);
Color colorDisk = Color.White;
if (CellImage != CellImageEnum.WhiteCell)
{
colorDisk = Color.Black;
}
using (Brush brushDisk = new SolidBrush(colorDisk))
{
g.FillEllipse(brushDisk, r);
}
Color diskBorderColor = Color.Black;
using (Pen penDisk = new Pen(new SolidBrush(diskBorderColor)))
{
g.DrawEllipse(penDisk, r);
}
}
private void DrawDiskBorder(Graphics g, Rectangle rec)
{
Rectangle r = rec;
r.Height -= 10;
r.Width -= 10;
r.X += 5;
r.Y += 5;
using (Pen penDisk = new Pen(DiskBorderColor))
{
g.DrawEllipse(penDisk, r);
}
}
private void DrawBoard(Graphics g, Rectangle[] arrRac)
{
g.Clear(BoardColor);
g.DrawRectangles(PenBorder, arrRac);
Rectangle rectangleBorder = new Rectangle(0, 0, CellSize * 8, CellSize * 8);
using(Pen penBigBorder=new Pen ( Color.Black, 4))
{
g.DrawRectangle(penBigBorder, rectangleBorder);
}
}
The Board Information
The Board information will display the picture of the Player and Name and the number of disks for each side. They are just a group of controls on FormGame
, that will be used in the ReverseUI
class.
The Navigator Control and the History of the Moves
These are just controls in FormGame
that will be used in ReverseUI
class.
The Navigator
control consists of four buttons, the move history is a tableLayoutPanel
that
contain a Link
label.
Theme.cs
This class just contains the control color information.
public class Theme
{
public Color ButtonBackColor { get; set; }
public Color ButtonForeColor { get; set; }
public Color LabelForeColor { get; set; }
public Color FormBackColor { get; set; }
public Color InputBoxBackColor { get; set; }
public Color LinkLabelForeColor { get; set; }
public Color LinkLabelActiveForeColor { get; set; }
public Boolean IsFormCaptionDarkMode { get; set; } = true;
public Color MenuBackColor { get; set; }
public Color MenuHoverBackColor { get; set; }
public Color MenuForeColor { get; set; }
}
This Program supports DarkMode
, we use Global
class to have LightTheme
, DarkTheme<br /> Then
, when each of the forms loads, it will access Global.CurrentTheme
, then uses themeUtil
to set the appearance of the controls.
This is an example of using themUtil
object.
themeUtil.SetLabelColor(theme, lblNumberofBlackDisk,
lblNumberofWhiteDisk,
lblPlayer1Name,
lblPlayer2Name)
.SetButtonColor(theme, btnFirst,
btnNext,
btnPrevious,
btnLast)
.SetMenu (this.menuStrip1)
.SetForm(this);
FormGame.cs
This class is the main form, it contains the PictureBoxBoard
and the Navigator
controls and history of moves.
UI.Dialog.cs
All of the code to show dialog belongs here.
The Important Classes
AI.Board.cs
This is the class that holds the board information.
Fields and Properties
int[,] boardMatrix
we use simple 2D array to contain the disk, Black =-1, Blank =0, White =1
BoardPhase
has three phases: Beginning
, Middle
, and EndGame
. This value will be used by AI, it will determine which set of score values it needs to evaluate the board score. NumberofLastFlipCell
every time we flip the cell, we keep the number of the cells that were flipped CurrentTurn
the current turn generateMoves()
generates available moves PutValue()
just put the cell value IsLegalMove()
check to see if the position is valid SwitchTurn()
just switch the turn IsTherePlaceToPut()
- This method will return false
if there is no place to put it; otherwise, it will return true
.
These are the Board
constructors.
public Board()
{
boardMatrix = new int[8, 8];
SetCell(3, 3, CellValue.White);
SetCell(3, 4, CellValue.Black);
SetCell(4, 3, CellValue.Black);
SetCell(4, 4, CellValue.White);
listPutPosition.Clear();
}
public Board(Board OriginalBoard)
{
boardMatrix = new int[8, 8];
Array.Copy(OriginalBoard.boardMatrix, this.boardMatrix,
this.boardMatrix.Length);
this.CurrentTurn = OriginalBoard.CurrentTurn;
if (OriginalBoard.LastPutPosition != null)
{
this.SetLastPutPosition(OriginalBoard.LastPutPosition.Clone());
}
}
AI.BoardValue.cs
This class contains the board information, when we would like to save the board or create a custom board. We store the value in this class and then Serialize it.
ReverseUI.cs
This class implements the IUI interface, so it must have these methods:
void RenderHistory();
void RenderNumberofDisk(int WhiteDisk, int BlackDisk);
void ShowBoardAtTurn(int NumberofTurn);
void MoveBoardToNextTurn();
void MoveBoardToPreviousTurn();
void RenderBoard();
void SetGame(KReversiGame game);
void RemoveGame();
void BlackPutCellAt(Position position);
void WhitePutCellAt(Position position);
void Initial();
void ReleaseUIResource();
void InformPlayer1NeedtoPass();
void InformPlayer2NeedtoPass();
void InformGameResult(KReversiGame.GameResultEnum result);
event EventHandler MoveBoardToNextTurnClick;
event EventHandler MoveBoardToPreviousTurnClick;
event EventHandler MoveBoardToFirstTurnClick;
event EventHandler MoveBoardToLastTurnClick;
event PictureBoxBoard.PictureBoxCellClick CellClick;
event EventInt MoveBoardToSpecificTurnClick;
event EventHandler ContinuePlayingClick;
KReversiGame.cs
This class contains UIU
object and board object. It works as a glue between these two objects.
This program uses Inversion of control
https://en.wikipedia.org/wiki/Inversion_of_control
It means the UI part will not know anything much about the game data when we click on a cell.
It will not check if this cell is empty or if it is a valid position or not, it will just notify the game that this specific cell was clicked, then the game object will determine what to do next.
For example, the game object will check if it is a valid position and then it will call a board object to update the value and then it will notify the UI to let them know that it needs to update or it will call the UI to update itself directly.
Both BotPlayer1MoveDecision()
and HumanPlayer1MoveDecision()
will call Player1Move()
. The difference is BotPlayer1MoveDecision
will call minimaxbot.MakeMove(board)
to get the bot position, while HumanPlayer1MoveDecision()
will get the position from user input.
Player1Move()
- verify if the position is valid
- Put the disk, then switch turn
- Handle in case of passes
- Store board to history
- Tell UI to render a board
- Check if the game result is finished
public enum PlayerMode
{
FirstHuman_SecondHuman = 0,
FirstHuman_SecondBot = 1,
FirstBot_SecondHuman = 2,
FirstBot_SecondBot = 3
}
public enum GameStatusEnum
{
Pause=-1,
Playing = 0,
Finished = 1
}
public enum GameResultEnum
{
NotDecideYet=-2,
BlackWon = -1,
Draw = 0,
WhiteWon = 1,
}
public void BotPlayer1MoveDecision(out bool CanMove)
{
CanMove = false;
if (this.Player1 == null)
{
throw new Exception("Please Assign Player1bot");
}
if (this.GameState == GameStatusEnum.Finished ||
this.GameState == GameStatusEnum.Pause)
{
return;
}
if (!IsPlayer1Bot)
{
return;
}
if (IsPlayer1NeedtoPass())
{
board.SwitchTurnDueToPlayerPass();
}
else
{
Player1BotBeginToThink?.Invoke(this, new EventArgs());
if (Player1 is MiniMaxBotProto)
{
MiniMaxBotProto minimaxBot = (MiniMaxBotProto)Player1;
minimaxBot.IsAllowRandomDecision = this.IsAllowRandomDecision;
minimaxBot.IsKeepLastDecisionTree = false;
minimaxBot.IsUsingAlphaBeta = this.IsUsingAlphaBeta;
}
Position botPosition = Player1.MakeMove(board);
Player1Move(botPosition, out CanMove);
if (!CanMove)
{
throw new Exception("There must be something wrong with Player 1 Move");
}
Player1BotFinishedToThink?.Invoke(this, new EventArgs());
}
OnPlayer1Moved();
}
public void HumanPlayer1MoveDecision(Position pos, out bool CanMove)
{
CanMove = false;
if (this.GameState == GameStatusEnum.Finished ||
this.GameState == GameStatusEnum.Pause)
{
return;
}
if (IsPlayer1Bot)
{
return;
}
Player1Move(pos, out CanMove);
OnPlayer1Moved();
}
private void Player1Move(Position pos, out Boolean CanMove)
{
CanMove = false;
if (this.board.CurrentTurn != Player1Color)
{
return;
}
if (!this.board.IsLegalMove(pos, Player1Color))
{
return;
}
board.PutAndAlsoSwithCurrentTurn(pos, this.Player1Color);
CanMove = true;
boardHistory.IndexMoveAdd();
Boolean CanPlayer2MakeMove = board.generateMoves(Player2Color).Count > 0;
Boolean CanPlayer1MakeMove = board.generateMoves(Player1Color).Count > 0;
Board.PlayerColor PlayerColorForNextTurn = this.Player2Color;
if (!CanPlayer2MakeMove)
{
if (CanPlayer1MakeMove)
{
PlayerColorForNextTurn = this.Player1Color;
}
}
Board boardForHistory = (Board)this.board.Clone();
boardForHistory.CurrentTurn = PlayerColorForNextTurn;
AddCurrentBoardToHistory(boardForHistory, pos, this.Player1Color);
UIBoard.RenderBoard();
if (!CanPlayer2MakeMove)
{
if (!CanPlayer1MakeMove)
{
this.GameState = GameStatusEnum.Finished;
CalculateResult();
UIBoard.InformGameResult(this.GameResult);
}
else
{
if (!IsPlayer2Bot || !IsPlayer1Bot)
{
this.UIBoard.InformPlayer2NeedtoPass();
}
board.SwitchTurnDueToPlayerPass();
}
}
}
protected virtual void OnPlayer1Moved()
{
UIBoard?.RenderHistory();
NextTurn();
}
private void NextTurn()
{
if (this.GameState != GameStatusEnum.Playing)
{
return;
}
if (this.IsPlayer1NeedtoPass() && this.IsPlayer2NeedtoPass())
{
this.GameState = GameStatusEnum.Finished;
CalculateResult();
this.UIBoard.InformGameResult(this.GameResult);
return;
}
bool CanMove = false;
if (this.board.CurrentTurn == Board.PlayerColor.Black)
{
if (this.IsPlayer1Bot)
{
BotPlayer1MoveDecision(out CanMove);
return;
}
else
{
if (this.IsPlayer1NeedtoPass())
{
this.UIBoard.InformPlayer1NeedtoPass();
this.board.SwitchTurnDueToPlayerPass();
this.UIBoard.RenderBoard();
}
}
return;
}
if (this.IsPlayer2Bot)
{
BotPlayer2MoveDecision(out CanMove);
return;
}
else
{
if (this.IsPlayer2NeedtoPass())
{
this.UIBoard.InformPlayer2NeedtoPass();
this.board.SwitchTurnDueToPlayerPass();
this.UIBoard.RenderBoard();
}
}
}
This diagram is a simplified version of a sequence diagram. It is just a simplified version because:
Click()
, CellClick() UIBoard_CellClick()
are events that cannot be displayed on the sequence diagram easily. - The
pictureBoxBoard
is not an actual object that listens to Click()
event, it is another picturebox
that pictureBoxBoard
contains.
BoardHistory.cs
This is a class that keeps track of the position each time the disk is put. It also has the methods to navigate through these histories.
GameBuilder.cs
Since this game is quite complicated, so we need the GameBuilder
object to create a game object instead of using a constructor.
This is an example of how to create a game.
game = GameBuilder.Builder.BeginBuild
.GameMode(KReversiGame.PlayerMode.FirstHuman_SecondBot)
.BotPlayer1Is(BotPlayer1)
.BotPlayer2Is(BotPlayer2)
.Player1NameIs(Global.Player1Name)
.Player2NameIs(Global.Player2Name)
.AllowRandomDecision (Global.CurrentSettings.IsAllowRandomDecision)
.UsingAlphaBeta (Global.CurrentSettings.IsUsingAlphaBeta)
.KeepLastDecisionTree
(Global.CurrentSettings.IsKeepLastDecisionTree)
.OpenWithBoardFile(CurrentBoardFileName)
.OpenWithGameFile(CurrentGameFileName)
.FinishBuild();
Utility.SerializeUtility.cs
This is the class we use to Serialize and Deserialize any kind of file/object.
Utility.UI.cs
It has methods related to making a Dark mode.
Explain the important code.
These are the important codes that do not relate to AI.
AI.Board.IsLegalMove()
- If the row and column are not in the value range, return
false
; - If Cell is not a blank cell, return
false
; - When we tried to loop for 8 directions to check the next cell, we don't need to have 8 duplicate sets of code.
We can just use the loop for row and col like this:
They get 9 unique results from this nested loop.
We only need 8 of them for the row and column change in each direction.
Loop Row from -1 to 1 Loop Col from -1 to 1
- Row -1, Col -1 means North West.
- Row -1, Col 0 means North.
- Row -1, Col 1 means North East.
- Row 0, Col -1 means West.
- Row 0, Col 0 mean there is no change, just skip
- Row 0, Col 1 means East.
- Row 1, Col 1 means South East.
- Row 1, Col 0 means South.
- Row 1, Col -1 means South West.
In this picture, the middle cell represents a cell we need to check. It is in row 0, column 0.
We know that North West cell: Row is -1, Col is -1, we get it from 0 -1, 0 -1
We know that North cell : Row is -1, Col is 1, we get it from 0 -1, 0 -0 and so on.
For the condition, the cell must have at least one opponent cell first.
Then it must have the same side cell.
In this picture, only D1 is a valid position for a black turn.
public Boolean IsLegalMove(Position Position, PlayerColor cValue)
{
if (Position.Row < 0 ||
Position.Col < 0 ||
Position.Row > this.boardMatrix.GetLength (0)-1 ||
Position.Col > this.boardMatrix.GetLength(1) - 1)
{
return false;
}
if (GetCell(Position) != CellValue.Blank)
{
return false;
}
CellValue OponentValue = GetCellValueFromPlayerColor(GetOponentValue(cValue));
int iRowChange;
int iColChange;
Position PositionCheck = Position;
for (iRowChange = -1; iRowChange <= 1; iRowChange++)
{
for (iColChange = -1; iColChange <= 1; iColChange++)
{
if (iRowChange == 0 && iColChange == 0)
{
continue;
}
Boolean HasAtLeasOneOpoonentColor = false;
PositionCheck = Position.Clone();
while (true)
{
PositionCheck.Row += iRowChange;
PositionCheck.Col += iColChange;
if (PositionCheck.Row < 0 ||
PositionCheck.Row > 7 ||
PositionCheck.Col < 0 ||
PositionCheck.Col > 7)
{
break;
}
if (CellsByPostion(PositionCheck) == CellValue.Blank)
{
break;
}
if (CellsByPostion(PositionCheck) ==
GetCellValueFromPlayerColor(cValue))
{
if (!HasAtLeasOneOpoonentColor)
{
break;
}
else
{
return true;
}
}
if (CellsByPostion(PositionCheck) == OponentValue)
{
HasAtLeasOneOpoonentColor = true;
}
}
}
}
return false;
}
PutAndAlsoSwithCurrentTurn()
The logic behind this method is similar to IsLegalMove()
method. After it called SetCell()
method to put the cell value, it needs to loop in all 8 directions, when it finds the position it can flip, it will keep in the PositionFlip
object.
After it has finished checking for 8 directions, it will call SetCell
methods to flip the cell.
Introduction to AI Part
How Does MiniMax Work
Before I talk about Minimax
, I would like to introduce you to a decision tree first. The image below depicts an example of a decision node tree for the Tic Tac Toe game.
- There is a blank state.
- There are nine possible positions O can put.
- There are eight positions that can be put for each of the positions that O puts in #2.
- There are seven positions that can be put for each of the positions that X puts in #3.
At #3, there are totally:
- 81 nodes from 9 + (8 * 9)
- 72 possibilities from 9 * 8
At #4, there are totally:
- 585 nodes from 9 + (8 * 9) + (72 * 7)
- 504 possibilities from 9 * 8 * 7
In total, there are 362,880 possibilities to fill the board with O and X in the 3x3 board size.
This value can be calculated as x = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2.
However, the number of possible moves in a game of tic-tac-toe will be less than this because some games will end before the board is full.
If there are not too many nodes, we just search every node in the tree till we achieve our end goal.
However, the Reversi game has a tree with roughly 10 ^ 28 nodes.
We utilize Minimax to search for a limit-specific level with the node that is likely to be relevant because it is not practicable to calculate all of them.
There are two parts to the Minimax
algorithm.
1. Evaluate Function
It is the function that accepts board value as a parameter and then returns the score. We use this function because we would like to know if our position is good or bad.
int score = Evaluate(board);
2. Search Tree
It is a recursive tree to find the optimized value.
This is an example of using Minimax minimax
algorithm on a tree.
Supposing you need to decide to choose the best weapon to attack your enemy, while your enemy will decide to choose the best shield to protect themselves. Which weapon will you choose?
You are supposed to choose the Maximum
value. Your enemy is supposed to choose the Minimum
value and this is a Minimax
.
The evaluation function will happen only in these six nodes: LShield1
, LShield2
, FShield1
, FShield2
, IShield1
, IShield2
.
These are the order of progress. The value after the :
is the value from processing.
LShield1:100
LShield2:200
Lighting = Find Min(LShield1, LShield2) :100
FShield1:110
FShield2:90
Fire= Find Min(FShield1, FShield2) :90
IShield1:120
IShield2:150
ICE= Find Min(IShield1, IShield2) : 120
Which Magic to Attack = Find Max(Lighting, Fire, ICE) :120
The reason why I explain the order of the node to be executed is when the first time I learn Minimax
.
I mistakenly think that this is the order being processed.
Lighting:100
Fire:90
ICE:120
LShield1:100
LSheidl2:200
...
I was mistaken because the tree image shows the value after every node was calculated. So I don't know what happened first.
The Lighting, Fire, ICE nodes were never be evaluated.
They just use the value from their children nodes, only the leaf node will be evaluated.
Alpha Beta Pruning
Please look at the tree.
(I adjusted the value of FShiled1
to 90
.)
According to this tree, you no need to evaluate for FSheild2
. The reason that you can eliminate it due to the fact that:
Lighting = MIn(100,200)
Fire = Min(90,?)
Result = Max(Lighting,Fire)
We know that the result will be 100 regardless of the value of FShield2
node.
How do we know?
Let's try to substitute ?
with 50
and check the result.
Result = Max(Min(100,200), Min(90,50))
Result = Max(100,50)
Result = 100
Try again, this time we use 300.
Result = Max(Min(100,200), Min(90,300))
Result = Max(100,90)
Result = 100
You can try to change the value in ?
and finally, you will get 100
as a result.
You see that when we know these two things:
- The Fire node value is
100
. - The Minimum value of the Lighting node is less than
90
.
We can eliminate the Lighting at all.
The Alpha-beta pruning is used to eliminate the number of nodes when we minimax algorithm. You just use it, but in this example, we only have Beta because our tree is not deep enough, so it only has Min level node.
Alpha stores the best value that Maximizer can guarantee. Its initial value is -Infinity. We can just use int.MinValue
instead of -Infinity
.
Beta stores the best value that Minimizer
can guarantee.
Its initial value is Infinity
.
We can just use int.MaxValue
instead of Infinity
.
With Alpha Beta pruning:
LShield1:100
LShield2:200
Lighting = Find Min(LShield1, LShield2) :100 Set Beta to 100
FShield1:90
Since the value is 90, it is less than Beta, we can ignore the rest of the children of the Fire node.
This is a concept of how we use alpha and beta values in Minimax
function. Alpha is for the Maximize
player to update. Beta is for the Minimize player to update. You can look into this it will help you more understand. https://bsmith156.github.io/Alpha-Beta-Visualizer/
void Minimax(Node node,
int depth,
boolean isMaximize,
int alpha,
int beta)
{
if (depth==0)
{
return Evaluation(node.board);
}
int bestValue = int.Maxvalue;
if(isMaximize){
bestValue = int.Minvalue;
}
foreach(Board childboard in node.board.GenerateMoves)
{
Node childnode =new Node(childboard);
if(isMaximize)
{
;
int Score = Minimax(childnode, depth-1,!isMaximize,alpha,beta);
bestValue = Math.Max(bestValue, Score);
alpha = Math.Max(alpha, bestValue);
if(alpha > beta)
{
break;
}
}
else
{
int Score = Minimax(childnode, depth-1,!isMaximize,alpha,beta);
bestValue = Math.Min(bestValue, value);
beta= Math.Min(beta, bestValue);
if(alpha > beta)
{
break;
}
}
}
return bestValue
}
The Important Classes that Relate to AI
BasicMiniMaxEvaluate Calculate
How does our evaluation function works?
First, I would like to introduce you to the concept of PositionScore
.
In the Reversi game, the corner is considered a good position because it cannot be flipped by an opponent.
Since the corner is good, the cell next to the corner is bad because it allows your opponent to occupy the corner.
In this picture, every cell black can put the disk is a bad position because after black, put the disk in these positions, the white will be able to get to the corner immediately.
We can set the position score like this. The corner is good so we give it 100, while the next to the corner is bad, we set them to -50
and -100
while for the other cell, we set it to 1
.
This evaluation function is strong enough to defeat a relatively inexperienced player, but it has no chance of competing against a Reversi expert.
The problem I found about this PositionScore
is it will not choose a cell next to the border despite it being a good position.
This picture, it shows that cell G2 is in a good position for black because it will allow him to have a corner at A8.
Not all of the next-to-border cell is bad, sometimes it is good but the program cannot understand.
So I tried to look at a better method to improve AI and I found this article, Reversi by Zdravko Krustev.
For these two functions, I follow the same logic from him.
GetNumberofStableDiscsFromCorner()
GetStableDiscsFromFullEdge()
After I implemented these two evaluation variables, the AI improved a lot.
Calculate()
IsEndGame
if the game is ended, this function will just determine the result: win, loss, or draw. IsUseStatbleDiskScore
if this value is true
, it will call GetNoStableDisk
method IsUseScoreFromPosition -
In the end, it will compare BotScore
with OpponentScore
and then return ResultScore
. - This method will do an evaluation function, it will calculate the score for both sides (
Botscore
and Opponentscore
). Then it returns BotScore
- OpponentScore
. GetNoofDiskCanBeFlipped()
loops through all of the possible moves.
Try to put the disk.
Check how many disks can be flipped, then keep, then add the value.
GetNoStableDisk()
This is a method to check all four corners of the board and all four Edges of the board.
GetNumberofStableDiscsFromCorner()
Then call check all of the full edges on the 4 sides of the board.
Stable disk from Corner is that we count the number of the stable from each corner.
In this picture, we count that there are 5 stables disks, we don't count the disk on C2 because it does not follow the pattern.
GetStableDiscsFromFullEdge()
The stable disk from Full edge is we count that in case of the edge is full, we count how many of our disks are between the opponent.
In this picture, it is 6.
public int getScore(Board board, bool IsMyTurn, Board.PlayerColor BotColor)
{
var boardphase = board.BoardPhase;
EvaluateScore BotScore = new EvaluateScore();
EvaluateScore OpponentScore = new EvaluateScore();
bool IsUseStatbleDiskScore = this.StableDiskScore != 0;
bool IsUseAvailableScore = this.ScoreNumberMove(boardphase) != 0;
LogDebugL2("IsUseStatbleDiskScore::" + IsUseStatbleDiskScore);
LogDebugL2("IsUseAvailableScore::" + IsUseAvailableScore);
LogDebugL2("IsUseScoreFromPosition::" + IsUseScoreFromPosition);
int[,] positionScore = PositionScore(boardphase);
return Calculate(board, IsMyTurn, BotColor,
BotScore,
OpponentScore,
positionScore,
this.StableDiskScore,
this.ScoreNumberMove(boardphase),
IsUseScoreFromPosition);
}
public int Calculate(Board board, bool IsMyTurn, Board.PlayerColor BotColor,
EvaluateScore BotScore,
EvaluateScore OpponentScore,
int[,] ppositionScore,
int StableDiskScore,
int MobilityPieceScore,
Boolean IsUseScoreFromPosition)
{
bool IsUseStatbleDiskScore = StableDiskScore != 0;
LogDebugL2("IsUseStatbleDiskScore::" + IsUseStatbleDiskScore);
LogDebugL2("IsUseScoreFromPosition::" + IsUseScoreFromPosition);
Board.PlayerColor OppoColor =
board.GetOponentValue(BotColor);
List<Position> listNoofPossibleMoveForBot = board.generateMoves(BotColor);
List<Position> listNoofPossibleMoveForOpponent = board.generateMoves(OppoColor);
BotScore.NoofPossibleMove = listNoofPossibleMoveForBot.Count;
OpponentScore.NoofPossibleMove = listNoofPossibleMoveForOpponent.Count;
Boolean IsEndGame = false;
Boolean IsIWon = false;
Boolean IsDraw = false;
if (BotScore.NoofPossibleMove == 0 &&
OpponentScore.NoofPossibleMove == 0)
{
IsEndGame = true;
}
if (IsUseScoreFromPosition)
{
GetScoreFromPosition((Board)board, ppositionScore, BotColor, BotScore,
OpponentScore);
}
if (IsEndGame)
{
LogDebugL2("IsEndGame is true");
BotScore.DiskCount = board.NumberofDisk(BotColor);
OpponentScore.DiskCount = board.NumberofDisk(OppoColor);
if (BotScore.DiskCount == OpponentScore.DiskCount)
{
IsDraw = true;
LogDebugL2("IsDraw is true");
}
else
{
IsIWon = BotScore.DiskCount > OpponentScore.DiskCount;
LogDebugL2("IsIWon is true");
}
if (IsDraw)
{
return 0;
}
if (IsIWon)
{
return WonScore;
}
return LostScore;
}
Boolean IsINeedtoPass = false;
Boolean IsEnemyNeedtoPass = false;
if (OpponentScore.NoofPossibleMove == 0 &&
BotScore.NoofPossibleMove > 0)
{
IsEnemyNeedtoPass = true;
}
if (BotScore.NoofPossibleMove == 0 &&
OpponentScore.NoofPossibleMove > 0)
{
IsINeedtoPass = true;
}
if (IsEnemyNeedtoPass)
{
BotScore.ScorePassWeight += this.ForcePassSocre;
}
if (IsINeedtoPass)
{
OpponentScore.ScorePassWeight += this.ForcePassSocre;
}
if (IsUseStatbleDiskScore)
{
BotScore.NoofStableDisk = GetNoStableDisk(board, BotColor);
OpponentScore.NoofStableDisk = GetNoStableDisk(board, OppoColor);
BotScore.ScoreStableDiskWeight = BotScore.NoofStableDisk * StableDiskScore;
OpponentScore.ScoreStableDiskWeight =
OpponentScore.NoofStableDisk * StableDiskScore;
}
BotScore.NoofDiskCanFlip = GetNoofDiskCanBeFlipped
(board, BotColor, listNoofPossibleMoveForBot);
OpponentScore.NoofDiskCanFlip = GetNoofDiskCanBeFlipped
(board, OppoColor, listNoofPossibleMoveForOpponent);
BotScore.ScoreDiskCanFlip = MobilityPieceScore * BotScore.NoofDiskCanFlip;
OpponentScore.ScoreDiskCanFlip =
MobilityPieceScore * OpponentScore.NoofDiskCanFlip;
LogDebugL2("===BotScore");
LogDebugL2("BotScore.NoofPossbleMove::" + BotScore.NoofPossibleMove);
LogDebugL2("BotScore.NoofStableDisk::" + BotScore.NoofStableDisk);
LogDebugL2("BotScore.ScoreStableDiskWeight::" + BotScore.ScoreStableDiskWeight);
LogDebugL2("BotScore.ScorePositionWeight::" + BotScore.ScorePositionWeight);
LogDebugL2("BotScore.ScorePassWeight::" + BotScore.ScorePassWeight);
LogDebugL2("BotScore.ScoreDiskCanFlip::" + BotScore.ScoreDiskCanFlip);
LogDebugL2("===OpponentScore");
LogDebugL2("OpponentScore.NoofPossbleMove::" + OpponentScore.NoofPossibleMove);
LogDebugL2("OpponentScore.NoofStableDisk::" + OpponentScore.NoofStableDisk);
LogDebugL2("OpponentScore.ScoreStableDiskWeight::" +
OpponentScore.ScoreStableDiskWeight);
LogDebugL2("OpponentScore.ScorePositionWeight::" +
OpponentScore.ScorePositionWeight);
LogDebugL2("OpponentScore.ScorePassWeight::" + OpponentScore.ScorePassWeight);
LogDebugL2("OpponentScore.ScoreDiskCanFlip::" + OpponentScore.ScoreDiskCanFlip);
EvaluateScore ResultScore = BotScore - OpponentScore;
int ScoreTotal = ResultScore.GetTotalScore();
return ScoreTotal;
}
public int GetNoStableDisk(Board board, Board.PlayerColor color)
{
int NofromCorner =
this.GetNumberofStableDiscsFromCorner(board, color, Corner.TopLeft) +
this.GetNumberofStableDiscsFromCorner(board, color, Corner.TopRight) +
this.GetNumberofStableDiscsFromCorner(board, color, Corner.BottomLeft) +
this.GetNumberofStableDiscsFromCorner(board, color, Corner.BottomRigth);
int NofromEdge =
this.GetStableDiscsFromFullEdge(board, color, NEWS.North) +
this.GetStableDiscsFromFullEdge(board, color, NEWS.East) +
this.GetStableDiscsFromFullEdge(board, color, NEWS.West) +
this.GetStableDiscsFromFullEdge(board, color, NEWS.South);
return NofromCorner + NofromCorner;
}
public int GetNumberofStableDiscsFromCorner
(Board board, Board.PlayerColor color, Position PositionCorner)
{
int noofDisk = 0;
int rowDelta = 1;
int columnDelta = 1;
if (PositionCorner.Row != 0)
{
rowDelta = -1;
}
if (PositionCorner.Col != 0)
{
columnDelta = -1;
}
int LastRow = 7;
int LastColumn = 7;
if (PositionCorner.Row != 0)
{
LastRow = 0;
}
if (PositionCorner.Col != 0)
{
LastColumn = 0;
}
for (int indexRow = PositionCorner.Row; indexRow != LastRow; indexRow += rowDelta)
{
int indexColumn = 0;
for (indexColumn = PositionCorner.Col; indexColumn != LastColumn;
indexColumn += columnDelta)
{
if (board.boardMatrix[indexRow, indexColumn] != (int)color)
{
break;
}
noofDisk++;
}
Boolean IsThereColumnNeedtoCheck = false;
IsThereColumnNeedtoCheck =
(columnDelta > 0 && indexColumn < 7) ||
(columnDelta < 0 && indexColumn > 0);
if (!IsThereColumnNeedtoCheck)
{
continue;
}
LastColumn = indexColumn - columnDelta;
if (columnDelta > 0 && LastColumn == 0)
{
LastColumn++;
}
else if (columnDelta < 0 && LastColumn == 7)
{
LastColumn--;
}
if ((columnDelta > 0 && LastColumn < 0)
|| (columnDelta < 0 && LastColumn > 7))
{
break;
}
}
return noofDisk;
}
public int GetStableDiscsFromFullEdge(Board board, Board.PlayerColor color, NEWS news)
{
Board.PlayerColor OppositeColor = Board.PlayerColor.Black;
if (color == Board.PlayerColor.Black)
{
OppositeColor = Board.PlayerColor.White;
}
if (!IsEdgeFull(board, news))
{
return 0;
}
int result = 0;
Position positionBegin = null;
Position positionEnd = null;
GetPostionBeginandEnd(news, ref positionBegin, ref positionEnd);
bool hasFoundOppositeColor = false;
int NoofRepeatedDisk = 0;
for (int iRow = positionBegin.Row; iRow <= positionEnd.Row; iRow++)
{
for (int iColumn = positionBegin.Col; iColumn <= positionEnd.Col; iColumn++)
{
Board.PlayerColor DiskColor =
(Board.PlayerColor)board.boardMatrix[iRow, iColumn];
if (!hasFoundOppositeColor &&
DiskColor == OppositeColor)
{
hasFoundOppositeColor = true;
NoofRepeatedDisk = 0;
continue;
}
if (hasFoundOppositeColor)
{
if (DiskColor == color)
{
NoofRepeatedDisk++;
}
else
{
result += NoofRepeatedDisk;
NoofRepeatedDisk = 0;
}
}
}
}
return result;
}
How to Configure a Bot
You can create or update the bot.
The non-tabs area.
-
Choose a photo: Just click to choose a photo
-
Bot Name: The name of the bot
-
Time limit per move(seconds): Supposing the value is 5, the bot is allowed to use a maximum of 5 seconds per turn.
-
Stable disk score: This value will be multiplied by the number of stable disks.
Supposing this value is 20.
The number of stable disks is 10.
The Total Stable disk score will be 200 = 20 * 10.
-
Force pass score: In a Reversi game, when your opponent does not have a valid move, the game will switch to your turn.
If the position of the board forces your opponent to pass, you can get this score.
-
Check Use Position Score: If it is not checked, the bot will not use Position Score.
The tabs area.
We have three tabs, and each tab represents the value the bot will use during the game.
We allow configuring the value for Opening, Middle, End Game phases.
N = Number of white disk + Number of black disk;
Beginning : N <= 20
Middle: N <=40
End game: N > 40
- Score Position: You see that there is an array of
textbox
, you can configure the score position. - Score Mobilize: The number of available moves multiplied by Score Mobilize.
if this value is high, the bot will try to get an available move as much as it can. - Depth Level: You can configure the depth level, I suggest that it should not be more than 7
so the bot will not take too long to calculate. If you configure this value more than 7, please
make sure that you have configured the Time limit per move. - Copy cell to Middle, Copy cell to End Game: In case you would like to copy the Score Position to another tab, just click the button.
UI\PanelPositionBotConfigure.cs
This class inherits from Panel
, it contains an array of 64 Textbox
es to let the user enter the score value for evaluating function.
It allows you use only need to configure the score on A1 to D4 only then the other three parts of the board will change the value to match your A1 to D4 value.
UI\PanelBotConfigure.cs
This class inherits from Panel
, it consists of a tab control that has three tab pages: Opening
, Middle
, and End
Game.
Each page contains PanelPositionBotConfigure
, Score Mobilize, and Depth Level.
AI\MiniMaxBotProto.cs
This class is a class that implements IPlayer
interface, so we just need to implement
MakeMove(AI.IBoard pBoard)
method.
The value you configured when you create a bot, will be stored on a file then it will be deserialized then fill into the object from this class.
The main purpose of this class is to just store the evaluation function parameter and then
call the Minimax
class to execute it, there is no calculation in this class.
[Serializable]
public class MiniMaxBotProto : IPlayer
{
private BasicMiniMaxEvaluate Evaluate = null;
public MiniMaxBotProto()
{
}
public int ForcePassSocre { get; set; } = 1000;
public int StableDiskScore { get; set; } = 10;
public int TimeLimitPermove { get; set; } = 3;
public int ScoreNumberMoveAtBegingGame { get; set; }
public int ScoreNumberMoveAtMiddleGame { get; set; }
public int ScoreNumberMoveAtEndGame { get; set; }
public int DepthLevelAtBeginGame { get; set; }
public int DepthLevelAtMiddleGame { get; set; }
public int DepthLevelAtEndGame { get; set; }
public string BotName { get; set; }
public string Base64Image { get; set; }
public int[,] OpenGamePostionScore = new int[,] {
{ 100, -50, 20, 5, 5, 20, -50, 100},
{-50 , -70, -5, -5, -5, -5, -70, -50},
{20 , -5 , 15, 3, 3, 15, -5, 20},
{5 , -5 , 3, 3, 3, 3, -5, 5},
{5 , -5 , 3, 3, 3, 3, -5, 5},
{20 , -5 , 15, 3, 3, 15, -5, 20},
{-50 , -70, -5, -5, -5, -5, -70, -50},
{100 , -50, 20, 5, 5, 20, -50, 100}
};
public int[,] MidGamePostionScore = new int[,] {
{ 140, -20, 20, 5, 5, 20, -20, 140},
{-20 , -40, -5, -5, -5, -5, -40, -20},
{20 , -5 , 15, 3, 3, 15, -5, 20},
{5 , -5 , 3, 3, 3, 3, -5, 5},
{5 , -5 , 3, 3, 3, 3, -5, 5},
{20 , -5 , 15, 3, 3, 15, -5, 20},
{-20 , -40, -5, -5, -5, -5, -40, -20},
{140 , -20, 20, 5, 5, 20, -20, 140}
};
public int[,] EndGamePostionScore = new int[,] {
{ 20, -5, 10, 5, 5, 10, -5, 20},
{-5 , -10, 5, 5, 5, 5, -10, -5},
{20 , 5 , 5, 5, 5, 5, 5, 10},
{5 , 5 , 5, 5, 5, 5, 5, 5},
{5 , 5 , 3, 5, 5, 5, 5, 5},
{10 , 5 , 5, 5, 5, 5, 5, 10},
{-5 , -10, 5, 5, 5, 5, -10, -5},
{20 , -5, 10, 5, 5, 10, -5, 20}
};
public int DepthLevel(Board.BoardPhaseEnum boardPhase)
{
int depthLevel = 0;
switch (boardPhase)
{
case Board.BoardPhaseEnum.Begining:
depthLevel = DepthLevelAtBeginGame;
break;
case Board.BoardPhaseEnum.Middle:
depthLevel = DepthLevelAtMiddleGame;
break;
case Board.BoardPhaseEnum.EndGame:
depthLevel = DepthLevelAtEndGame;
break;
default:
depthLevel = 1;
break;
}
if (depthLevel < 1 ||
depthLevel > 10)
{
throw new Exception("Depth level is invalid");
}
return depthLevel;
}
public void FillEvaluateObject()
{
this.Evaluate = new BasicMiniMaxEvaluate(this);
}
public bool IsUseScoreFromPosition = true;
[NonSerialized()]
public bool IsAllowRandomDecision = false;
[NonSerialized()]
public bool IsKeepLastDecisionTree = false;
[NonSerialized()]
public bool IsUsingAlphaBeta = false;
[NonSerialized()] MiniMax m = null;
public Position MakeMove(IBoard pBoard)
{
Board.PlayerColor BotColor = ((Board)pBoard).CurrentTurn;
int depthLevel = DepthLevel(((Board)pBoard).BoardPhase);
Utility.TimeMeasure time = new Utility.TimeMeasure();
time.Start();
Boolean IsSortedNode = true;
if (m == null)
{
m = new MiniMax();
}
Position result = m.calculateNextMove(pBoard,
depthLevel,
Evaluate,
BotColor,
this.TimeLimitPermove,
IsUsingAlphaBeta,
IsKeepLastDecisionTree,
IsAllowRandomDecision,
IsSortedNode
);
time.Finish();
String strTemp = time.TimeTakes.Seconds.ToString();
return result;
}
public static MiniMaxBotProto CreateBot(String fileName)
{
MiniMaxBotProto Newbot =
Utility.SerializeUtility.DeserializeMinimaxBot(fileName);
Newbot.FillEvaluateObject();
return Newbot;
}
public static MiniMaxBotProto CreateBot()
{
MiniMaxBotProto minimaxBorProto = new MiniMaxBotProto();
minimaxBorProto.DepthLevelAtBeginGame = 2;
minimaxBorProto.DepthLevelAtMiddleGame = 3;
minimaxBorProto.DepthLevelAtEndGame = 5;
minimaxBorProto.ScoreNumberMoveAtBegingGame = 10;
minimaxBorProto.ScoreNumberMoveAtMiddleGame = 40;
minimaxBorProto.ScoreNumberMoveAtEndGame = 20;
minimaxBorProto.DepthLevelAtBeginGame = 2;
minimaxBorProto.DepthLevelAtMiddleGame = 2;
minimaxBorProto.DepthLevelAtEndGame = 2;
minimaxBorProto.Evaluate = new BasicMiniMaxEvaluate(minimaxBorProto);
return minimaxBorProto;
}
}
Keep the Score in the Cache
This picture shows an example of a duplicate node.
Hash.cs
When we create a search tree for the Minimax
function, there is a chance that the tree node will have a duplicate value for another tree node. If that case happens, we don't want to do the evaluation again, so we decide to keep the score value in the hash object.
Every time we call the evaluation function to calculate the score from the board. We keep the score value in this Hash
object, the next time when there is a duplicate node appears, we just retrieve the value that we already stored.
We also need to keep the depth level because the same board position has different scores for different levels.
public class Hash
{
public static int ScoreForNonExist = int.MaxValue / 2;
public static int GetHashForBoard(Board board)
{
return board.GetHashCode() * (int)board.CurrentTurn ;
}
private Dictionary<int, Dictionary<int, int>> DicHash =
new Dictionary<int, Dictionary<int, int>>();
private Dictionary<int, int> DicEvoScore = new Dictionary<int, int>();
public int NumberofNodeCount()
{
int NumberofNodeCount = 0;
foreach (int HashBoard in DicHash.Keys)
{
foreach (int DepthExist in DicHash[HashBoard].Keys)
{
NumberofNodeCount++;
}
}
NumberofNodeCount += DicEvoScore.Count;
return NumberofNodeCount;
}
public void Add(int HashCodeForBoard, int Score, int Depth)
{
Dictionary<int, int> DicDepthScore = new Dictionary<int, int>();
if (DicHash.ContainsKey(HashCodeForBoard))
{
DicDepthScore = DicHash[HashCodeForBoard];
if(DicDepthScore.ContainsKey(Depth))
{
return;
}
foreach(int DepthExist in DicDepthScore.Keys)
{
if(DepthExist >=Depth)
{
return;
}
}
} else
{
DicHash.Add(HashCodeForBoard, DicDepthScore);
}
DicDepthScore.Add(Depth, Score);
}
public void AddEvalScore(int HashCodeForBoard, int Score)
{
if(DicEvoScore.ContainsKey(HashCodeForBoard))
{
return;
}
DicEvoScore.Add(HashCodeForBoard, Score);
}
public int GetEvalScore(int HashCodeForBoard)
{
if(DicEvoScore.ContainsKey(HashCodeForBoard))
{
return DicEvoScore[HashCodeForBoard];
}
return ScoreForNonExist;
}
public int GetScore(int HashCodeForBoard, int DepthLeast)
{
if (!DicHash.ContainsKey(HashCodeForBoard))
{
return ScoreForNonExist;
}
foreach (int DepthExist in DicHash[HashCodeForBoard].Keys)
{
if(DepthLeast <= DepthExist)
{
return DicHash[HashCodeForBoard][DepthExist];
}
}
return ScoreForNonExist;
}
public Boolean ContainScore(int HashCodeForBoard, int DepthLeast)
{
return GetScore(HashCodeForBoard, DepthLeast) != ScoreForNonExist;
}
public Boolean ContainEvalScore(int HashCodeForBoard)
{
return GetEvalScore(HashCodeForBoard) != ScoreForNonExist;
}
}
MinimaxParameterExtend.cs
We use this class to store the value of the minimax
parameter.
Actually, you don't need this class to use a minimax
function.
I created this class because I need to keep the List
of MinimaxParameterExtend
as a child because
I need to show it later to the people who would like to learn how minimax
works.
[Serializable]
public class MiniMaxParameterExtend : MiniMaxParameter
{
public List<MiniMaxParameterExtend> child =
new List<MiniMaxParameterExtend>();
public PositionScore PositionScore { get; set; } =
new PositionScore();
public MiniMaxParameterExtend CloneExtendWithoutBoard()
{
MiniMaxParameterExtend CloneObject = new MiniMaxParameterExtend();
CloneObject.Depth = this.Depth;
CloneObject.IsMax = this.IsMax;
CloneObject.Alpha = this.Alpha;
CloneObject.Beta = this.Beta;
CloneObject.BotColor = this.BotColor;
if (this.PositionScore != null)
{
CloneObject.PositionScore = this.PositionScore.ClonePositionScore();
}
return CloneObject;
}
public MiniMaxParameterExtend CloneExtend()
{
MiniMaxParameterExtend CloneObject = CloneExtendWithoutBoard();
CloneObject.board = (Board)this.board.Clone();
return CloneObject;
}
}
MiniMax.cs
calculateNextMove()
This method is just for preparing a parameter to call MinimaxAlphaBetaExtend()
MinimaxAlphaBetaExtend()
-
If it is not the final move, check need to pass.
If the Bot color doesn't have a valid move switch to the opponent's color, then check if it has a valid move or not.
If both colors have no valid move, set IsFinalMove=true
-
If it is the final move, check from the hash if this position is already calculated and store it in the hash or not.
If it is, get the Score
from the hash.
If it is not, call evaluate board function then store the score in a hash.
Return score
.
-
It relates to sorting available moves.
The program will try to evaluate the score from the board and then try to sort the available moves.
We don't do this on every depth level.
The result from #3 will be sent to #4.
-
This is a part where we do the minimax
.
Loop through all of the Position
s in the available move.
Check if it can get a score from hash or not.
If it cannot, just call MinimaxAlphaBetaExtend
to get the childScore
.
Store it in the hash
object.
The result of this method is just ordinary minimax
.
public Position calculateNextMove(IBoard board,
int depth,
IEvaluate pEvaluateObject,
Board.PlayerColor BotColor,
int SecondsLimitPerMove,
Boolean IsUsingAlphaBeta,
Boolean IsKeepingChildValue,
Boolean IsUsingRandomIfNodeValueIsTheSame,
Boolean IsSortedNode)
{
Log("CalculateNextMove begin");
EvaluateObject = pEvaluateObject;
Position move = new Position(-1, -1);
PositionScore bestMove = new PositionScore();
MiniMaxParameterExtend Para = new MiniMaxParameterExtend();
Para.Depth = depth - 1;
Para.board = (Board)board.Clone();
Para.IsMax = true;
Para.Alpha = int.MinValue;
Para.Beta = int.MaxValue;
Para.BotColor = BotColor;
NodeCount = 0;
EvaluateCount = 0;
EndTime = DateTime.Now.AddSeconds(SecondsLimitPerMove);
Log("CalculateNextMove :: SecondLimitPerMove ::" + SecondsLimitPerMove);
Log("CalculateNextMove :: Depth ::" + Para.Depth);
Utility.TimeMeasure timeM = new Utility.TimeMeasure();
iCountHashCanAccess = 0;
timeM.Start();
this.FirstLevelDepth = Para.Depth;
listFirstLevelDepthMoves = new List<PositionScore>();
PositionScore score = MinimaxAlphaBetaExtend(Para,
IsUsingAlphaBeta,
IsKeepingChildValue,
IsSortedNode);
move = new Position(score.Row,
score.Col);
timeM.Finish();
Log("CalculateNextMove :: [" + score.Row + "," + score.Col + "]");
Log("CalculateNextMove :: Score::" + score.Score);
Log("CalculateNextMove :: iCountHashCanAccess::" + iCountHashCanAccess);
Log("CalculateNextMove :: Before Get Random");
if (Para.board.NumberofBothDisk() <= 14)
{
if (IsUsingRandomIfNodeValueIsTheSame)
{
Log("CalculateNextMove :: IsUsingRandomIfNodeValueIsTheSame");
score = GetRandomFromMaxScoreNode(listFirstLevelDepthMoves);
move = new Position(score.Row,
score.Col);
}
}
Log("CalculateNextMove :: hashTranportable :: " +
hashTranportable.NumberofNodeCount());
Log("CalculateNextMove :: [" + score.Row + "," + score.Col + "]");
Log("CalculateNextMove :: Score::" + score.Score);
Log("CalculateNextMove :: NodeCount ::" + NodeCount);
Log("CalculateNextMove :: EvaluateCount ::" + EvaluateCount);
Log("CalculateNextMove :: Time takes (Seconds)::" +
timeM.TimeTakes.Milliseconds / 1000.00);
Log("CalculateNextMove End");
ClearMinimaxForDebug();
_MiniMaxForDebug = Para;
Utility.SerializeUtility.SerializeMiniMaxParameterExtend(_MiniMaxForDebug,
Utility.FileUtility.MiniMaxParameterForDebugFilePath
);
return move;
}
private PositionScore MinimaxAlphaBetaExtend(
MiniMaxParameterExtend Para,
Boolean IsUsingAlphaBeta,
Boolean IsKeepingChildValue,
Boolean IsSortedNode
)
{
String tab = Tab(Para.Depth);
String methodName = tab + "Minimax::";
NodeCount++;
Board.PlayerColor DiskColor = Para.BotColor;
Board.PlayerColor OpponentColor =
((Board)Para.board).GetOponentValue(Para.BotColor);
LogDebug(methodName + "IsMax::" + Para.IsMax);
if (!Para.IsMax)
{
DiskColor = OpponentColor;
}
Boolean IsMyTurn = false;
if (DiskColor == Para.BotColor)
{
IsMyTurn = true;
}
if (IsExceedTimeLimitPermove())
{
LogDebug(methodName + " Exceed Time");
}
bool IsNeedtoPass = false;
List<Position> avilableMovePositions = new List<Position>();
bool isFinalMove = false;
if (Para.Depth <= 0 || IsExceedTimeLimitPermove())
{
isFinalMove = true;
}
LogDebug(methodName + "IsFinalMove::" + isFinalMove);
if (!isFinalMove)
{
avilableMovePositions = Para.board.generateMoves();
if (avilableMovePositions.Count == 0)
{
LogDebug(methodName + "possbileMove.Count of " + DiskColor + "is 0 ");
IsNeedtoPass = true;
List<Position> avilableMovePositionsForOppositeColor = null;
if (DiskColor == Para.BotColor)
{
avilableMovePositionsForOppositeColor =
((Board)Para.board).generateMoves(OpponentColor);
DiskColor = OpponentColor;
LogDebug(methodName + "Gen possbileMove from OpponentColor it is "
+ avilableMovePositions.Count);
}
else
{
avilableMovePositionsForOppositeColor =
((Board)Para.board).generateMoves(Para.BotColor);
DiskColor = Para.BotColor;
LogDebug(methodName + "Gen possbileMove from BotColor it is "
+ avilableMovePositions.Count);
}
avilableMovePositions = avilableMovePositionsForOppositeColor;
}
if (avilableMovePositions.Count == 0)
{
isFinalMove = true;
}
}
PositionScore BestScore = new PositionScore(-1, -1);
if (isFinalMove)
{
int BoardHash = Hash.GetHashForBoard(Para.board);
int Score = 0;
if (hashTranportable.ContainEvalScore(BoardHash))
{
iCountHashCanAccess++;
Score = hashTranportable.GetEvalScore(BoardHash);
}
else
{
EvaluateCount++;
Score = this.EvaluateObject.evaluateBoard
(Para.board, IsMyTurn, Para.BotColor);
hashTranportable.AddEvalScore(BoardHash, Score);
LogDebug("hashPutEvalScore::" +
Para.board.LastPutPosition.PositionString());
}
LogDebug(methodName + "Score::" + Score);
BestScore = new PositionScore(Score, -1, -1);
return BestScore;
}
BestScore = new PositionScore(int.MaxValue, -1, -1);
if (Para.IsMax)
{
BestScore.Score = int.MinValue;
}
if (IsSortedNode && Para.Depth >= this.FirstLevelDepth - 1)
{
LogDebug(methodName + "IsSortedNode is true");
List<PositionScore> lstPostion = new List<PositionScore>();
Dictionary<int, Board> DicBoard = new Dictionary<int, Board>();
LogDebug(methodName + "Begin calculate score");
foreach (Position nextMove in avilableMovePositions)
{
Board tempBoard = (Board)Para.board.Clone();
tempBoard.PutAndAlsoSwithCurrentTurn(nextMove, DiskColor);
EvaluateCount++;
int Score = this.EvaluateObject.evaluateBoard
(tempBoard, IsMyTurn, Para.BotColor);
lstPostion.Add(new PositionScore(Score, nextMove.Row, nextMove.Col));
DicBoard.Add(nextMove.GetHashCode(), tempBoard);
LogDebug(methodName + " Score::" + Score);
LogDebug(methodName + " move::" + nextMove.PositionString());
}
LogDebug(methodName + "End calculate score");
List<PositionScore> SortedList = null;
if (Para.IsMax)
{
SortedList = lstPostion.OrderByDescending(o => o.Score).ToList();
}
else
{
SortedList = lstPostion.OrderBy(o => o.Score).ToList();
}
LogDebug("Max Begin ViewSortedList");
avilableMovePositions.Clear();
foreach (PositionScore move in SortedList)
{
LogDebug(methodName + " Score::" + move.Score);
LogDebug(methodName + " move::" + move.PositionString());
avilableMovePositions.Add(new Position(move.Row, move.Col));
}
}
LogDebug(methodName + "Before loop");
foreach (Position nextMove in avilableMovePositions)
{
LogDebug(methodName + " position[" + nextMove.Row + "," + nextMove.Col + "]");
MiniMaxParameterExtend childPara = Para.CloneExtend();
LogDebug(methodName + "DiskColor::" + DiskColor);
((Board)childPara.board).PutAndAlsoSwithCurrentTurn(nextMove, DiskColor);
LogDebug(methodName + " After put");
if (IsKeepingChildValue)
{
Para.child.Add(childPara);
}
childPara.IsMax = !Para.IsMax;
if (IsNeedtoPass)
{
childPara.IsMax = Para.IsMax;
((Board)childPara.board).SwitchTurnDueToPlayerPass();
}
childPara.Depth--;
int Score = 0;
int BoardHash = Hash.GetHashForBoard(childPara.board);
PositionScore childScore = null;
int ScoreFromHash = hashTranportable.GetScore(BoardHash, childPara.Depth);
if (ScoreFromHash != Hash.ScoreForNonExist)
{
iCountHashCanAccess++;
childScore = new PositionScore(hashTranportable.GetScore
(BoardHash, childPara.Depth));
}
else
{
childScore = this.MinimaxAlphaBetaExtend
(childPara, IsUsingAlphaBeta, IsKeepingChildValue, IsSortedNode);
hashTranportable.Add(BoardHash, childScore.Score, childPara.Depth);
LogDebug("hashPut::" + nextMove.PositionString() + " depth::" +
childPara.Depth + "::CUrrentTurn:: " +
childPara.board.CurrentTurn + " :: BoardHash::" + BoardHash);
}
childPara.PositionScore = new PositionScore(childScore.Score, nextMove);
if (Para.Depth == this.FirstLevelDepth)
{
LogDebug("First Level::" + nextMove.PositionString() + " ::" +
childScore.Score);
listFirstLevelDepthMoves.Add
(new PositionScore(childScore.Score, nextMove));
}
LogDebug(methodName + " childScore.Score::" + childScore.Score);
if (Para.IsMax)
{
LogDebug(methodName + " BestScore.Score::" + BestScore.Score);
if (childScore.Score > BestScore.Score)
{
LogDebug(methodName + " childScore.Score > BestScore.Score");
BestScore = new PositionScore(childScore.Score, nextMove);
if (IsUsingAlphaBeta)
{
Para.Alpha = Math.Max(BestScore.Score, Para.Alpha);
if (Para.Beta < BestScore.Score)
{
LogDebug(methodName + " BoardValue >= Beta");
break;
}
}
}
}
else
{
LogDebug(methodName + " BestScore.Score::" + BestScore.Score);
if (childScore.Score < BestScore.Score)
{
LogDebug(methodName + " childScore.Score < BestScore.Score");
BestScore = new PositionScore(childScore.Score, nextMove);
if (IsUsingAlphaBeta)
{
Para.Beta = Math.Min(Para.Beta, BestScore.Score);
if (BestScore.Score <= Para.Alpha)
{
LogDebug(methodName + " BoardValue <= Alpha");
break;
}
}
}
}
}
LogDebug(methodName + "After Loop");
return BestScore;
}
Show Minimax Latest Move
You can click on Game->Show MiniMax Latest Move menu.
Please make sure that Player 2 is a bot.
Explain some of the values in this picture.
9[F5]Min
mean
9
is the min value of these below nodes (9, 10, 10, 10, 10, 10)
12[] Max
mean
12
is the max value of the below nodes (9, 7, 12, 7)
-4[D1]
Leaf mean - This is a leaf node, the evaluation function was executed on this node the value -4
.
Testing
You can just run all of the unit and integration tests.
Please make sure it passes all of them, but you can skip BotFightTest
because it takes about 20 seconds to finish.
What Can We Do To Improve
If we need to improve the program, these are some things we can do to strengthen AI.
- Change the data structure of the board from a 2D array to a
bitboard
. - Include Openbook features; we calculate the evaluation in advance to save it in a file, then we simply get the value from it without having to calculate it again.
- XOr hash should be used instead of this hash function.
Point of Interest
There are many features that I did not intend to include in the first place, such as creating a board or a bot, but after developing them, I realized that they greatly aided me in finding bugs and fixing programs.
References
History
- 6th December, 2022: Initial version