KReversi，通过创建黑白棋机器人学习实现Minimax算法

• 下载 KReversi-main - 990.9 KB
• 下载 KReversi - 291.4 KB

引言

已经有很多黑白棋程序了，我选择开发这个程序是因为我在寻找Revesi/Othello游戏时，找不到具有我所需功能的程序。

特点

1. 支持人机对战、人机对战、机器人对战模式
2. 支持棋盘编辑器
3. 支持机器人创建器。您可以选择一张图片并自定义一个AI分数，该分数将用于评估棋盘。
4. 可以显示机器人上次移动的Minimax搜索树
5. 可以更改人类玩家1和人类玩家2的头像
6. 可以导航移动
7. 支持深色模式

程序使用的文件扩展名

1. .brd 用作棋盘信息。
2. .bot 用作机器人信息。
3. .rev 用作游戏保存信息，游戏信息保留了移动历史，这是它与棋盘游戏的不同之处，因此您可以通过导航控件进行导航。

如何玩

游戏规则与普通的黑白棋游戏完全相同。

概念

项目文件结构

图形

在这一节中，我想谈谈负责渲染图形的类，但我暂时不会提及任何与棋盘编辑器或机器人创建器相关的内容。

游戏棋盘

棋盘也可以显示数字。

UI\PictureBoxBoard.cs

这是一个继承自PictureBox控件的类。
它负责显示黑白棋盘。这个类本身包含一个名为pictureBoxTable的控件。
pictureBoxTable控件将通过pictureBoxTable_Paint()方法渲染棋盘和棋子。
pictureBoxTable_Paint()方法从这个类读取棋盘信息以
绘制棋盘和棋子。

这是绘制棋盘的逻辑。

1. 有一个包含64个矩形的数组。我们创建这64个矩形来存储棋盘上单元格的位置。

2. 此方法将调用

• DrawBoard() 绘制棋盘
• DrawIntersection() 顾名思义
• DrawDisk() 仅绘制棋子
• DrawRedDot() 显示上次放置的位置
• DrawDiskBorder() 显示哪些单元格可以放置
• DrawNumber() - 当我们需要显示单元格分数时，使用此方法。
  此方法中的所有绘图都只使用基本的GDI+方法，例如FillEllipse()、DrawEllipse()、DrawRectangles()

棋盘绘图没有使用任何图像。这些是绘制符号的逻辑

1. 只需从0循环到7。
2. 使用DrawString()方法绘制string
   此控件具有PictureBoxBoard_Paint()方法来渲染符号。

 public enum CellImageEnum
 {
    WhiteCell,
    BlackCell,
    BlankCell,
    BlankCellWithRed  //To show which is the last cell that the disk was put
 }
 public enum BoardModeEnum
 {
    PlayMode,
    EditMode
 }
 public Boolean IsSmallBoard { get; set; } = false; // Support display the board 
                                                    // as small size
 public Boolean IsHideLegent { get; set; } = false; 
 public Boolean IsDrawNotion { get; set; } = true;  // Can hide the notation (A1-H8)

 public event PictureBoxCellClick CellClick;
 private void PictureBox1_MouseDown(object sender, MouseEventArgs e)
 {
    //Must be a left button
    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)
    {
        //Row and Column click must be in range.
        return;
    }

    if (CellClick != null)
    {
        //Raise event.
        CellClick(this, new Position(RowClick, ColClick));
    }
 }
 private void DrawNumber(Graphics g, int Number, Rectangle rec)
 {
     /*This method is for drawing a number in case of 
       showing a score value from evaluate function.
     */
     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)
     {
       //Negative number does not need "+" prefix.
       NumberText =  Number.ToString ();
       NumberColor = Color.FromArgb(255, 199, 79);
     }
     //Create Brush and other objects
     PointF pointF = new PointF(r.X, r.Y);
     SolidBrush solidBrush = new SolidBrush(NumberColor );
     //Draw text using DrawString
     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;
     //Reduce the size of Rectangle
     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;

     //Uncomment this line in case you would like white disk to have white color border
     //diskBorderColor = colorDisk
     using (Pen penDisk = new Pen(new SolidBrush(diskBorderColor)))
     {
      g.DrawEllipse(penDisk, r);
     }
 }
 private void DrawDiskBorder(Graphics g, Rectangle rec)
 {
     //Reduce the size of Rectangle
     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)
 {
     //This method just draw 64 array of Rectangle objects.

     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);
     }
 }

棋盘信息

棋盘信息将显示玩家图片、名称以及每边的棋子数量。它们只是FormGame上的一组控件，将在ReverseUI类中使用。

导航器控件和移动历史

这些只是FormGame中将在ReverseUI类中使用的控件。
导航器控件由四个按钮组成，移动历史是一个tableLayoutPanel，它
包含一个Link标签。

Theme.cs

这个类只包含控件颜色信息。

    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; }
    }

此程序支持DarkMode，我们使用Global类来设置LightTheme、DarkTheme<br />然后，当每个窗体加载时，它将访问Global.CurrentTheme，然后使用themeUtil
来设置控件的外观。

这是使用themUtil对象的示例。

themeUtil.SetLabelColor(theme, lblNumberofBlackDisk,
                        lblNumberofWhiteDisk,
                        lblPlayer1Name,
                        lblPlayer2Name)
         .SetButtonColor(theme, btnFirst,
                        btnNext,
                        btnPrevious,
                        btnLast)
         .SetMenu (this.menuStrip1)
         .SetForm(this);

FormGame.cs

这个类是主窗体，它包含PictureBoxBoard和Navigator控件以及移动历史。

UI.Dialog.cs

所有显示对话框的代码都属于这里。

重要的类

AI.Board.cs

这是保存棋盘信息的类。

字段和属性

• int[,] boardMatrix 我们使用简单的二维数组来包含棋子，Black = -1, Blank = 0, White = 1
• BoardPhase 有三个阶段：Beginning（开始）、Middle（中期）和EndGame（残局）。这个值将被AI使用，它将决定需要哪一组分数来评估棋盘得分。
• NumberofLastFlipCell 每次翻转单元格时，我们都会保留被翻转的单元格数量
• CurrentTurn 当前回合
• generateMoves() 生成可用的移动
• PutValue() 只放置单元格值
• IsLegalMove() 检查位置是否有效
• SwitchTurn() 只是切换回合
• IsTherePlaceToPut() - 如果没有地方放置，此方法将返回false；否则，它将返回true。

这些是Board构造函数。

        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

这个类包含棋盘信息，当我们想保存棋盘或创建自定义棋盘时。我们将值存储在这个类中，然后将其序列化。

ReverseUI.cs

这个类实现了IUI接口，所以它必须有这些方法

	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(); //To make sure there is no event leak
        void InformPlayer1NeedtoPass(); 
        void InformPlayer2NeedtoPass();
        void InformGameResult(KReversiGame.GameResultEnum result);        
	
	// Any event the begin with MoveBoard relate to navigation.
        event EventHandler MoveBoardToNextTurnClick;
        event EventHandler MoveBoardToPreviousTurnClick;
        event EventHandler MoveBoardToFirstTurnClick;
        event EventHandler MoveBoardToLastTurnClick;
        event PictureBoxBoard.PictureBoxCellClick CellClick;
        event EventInt MoveBoardToSpecificTurnClick;
        event EventHandler ContinuePlayingClick;

KReversiGame.cs

这个类包含UIU对象和棋盘对象。它充当这两个对象之间的粘合剂。
此程序使用控制反转
https://en.wikipedia.org/wiki/Inversion_of_control
这意味着当我们点击一个单元格时，UI部分不会对游戏数据了解太多。
它不会检查此单元格是否为空，或者它是否是有效位置，它只会通知游戏此特定单元格已被点击，然后游戏对象将决定下一步做什么。

例如，游戏对象将检查它是否是有效位置，然后它将调用棋盘对象来更新值，然后它将通知UI让他们知道它需要更新，或者它将直接调用UI来更新自身。

BotPlayer1MoveDecision() 和 HumanPlayer1MoveDecision() 都将调用 Player1Move()。区别在于 BotPlayer1MoveDecision 将调用 minimaxbot.MakeMove(board) 来获取机器人位置，而 HumanPlayer1MoveDecision() 将从用户输入获取位置。

Player1Move() - 验证位置是否有效

• 放置棋子，然后切换回合
• 处理通过的情况
• 将棋盘存储到历史记录
• 通知UI渲染棋盘
• 检查游戏结果是否已结束

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())
	{
		//This player1 is bot no need to inform
		//UIBoard.InformPlayer1NeedtoPass();
		board.SwitchTurnDueToPlayerPass();
	}
	else
	{
		Player1BotBeginToThink?.Invoke(this, new EventArgs()); // To make UI change 
                                             // mouse cursor to sandy clock
		if (Player1 is MiniMaxBotProto)
		{
			MiniMaxBotProto minimaxBot = (MiniMaxBotProto)Player1;
			// minimaxBot.
			//For Player1 IsKeepLastDecisionTree is always false;
			minimaxBot.IsAllowRandomDecision = this.IsAllowRandomDecision;
			minimaxBot.IsKeepLastDecisionTree = false;// this.IsKeepLastDecisionTree;
			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()); // To make UI 
                                                // change mouse cursor back
	}
	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)
		{
		        //Passes
			PlayerColorForNextTurn = this.Player1Color;
		}
	}

	Board boardForHistory = (Board)this.board.Clone();
	boardForHistory.CurrentTurn = PlayerColorForNextTurn;
	AddCurrentBoardToHistory(boardForHistory, pos, this.Player1Color);
	UIBoard.RenderBoard();

	if (!CanPlayer2MakeMove)
	{
		if (!CanPlayer1MakeMove)
		{
		    //Both Player cannot make move
			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();
		}
	}
}

此图是序列图的简化版本。它只是一个简化版本，因为

1. Click()、CellClick()、UIBoard_CellClick() 是事件，无法轻易在序列图上显示。
2. pictureBoxBoard 不是一个实际监听Click()事件的对象，它是pictureBoxBoard包含的另一个picturebox。

BoardHistory.cs

这是一个类，用于跟踪每次放置棋子时的位置。它还具有浏览这些历史记录的方法。

GameBuilder.cs

由于这个游戏相当复杂，因此我们需要GameBuilder对象来创建游戏对象，而不是使用构造函数。

这是一个创建游戏的示例。

game = GameBuilder.Builder.BeginBuild
                  .GameMode(KReversiGame.PlayerMode.FirstHuman_SecondBot)
                  .BotPlayer1Is(BotPlayer1) // BotPlayer1 can be null.
                  .BotPlayer2Is(BotPlayer2) // BOtPlayer2 can be null.
                  .Player1NameIs(Global.Player1Name)
                  .Player2NameIs(Global.Player2Name)
                  .AllowRandomDecision (Global.CurrentSettings.IsAllowRandomDecision) 
                  .UsingAlphaBeta (Global.CurrentSettings.IsUsingAlphaBeta) 
                  .KeepLastDecisionTree 
                   (Global.CurrentSettings.IsKeepLastDecisionTree) // In case we need 
                                                            //to view the minimax tree
                  .OpenWithBoardFile(CurrentBoardFileName)  //Path of .brd file, 
                                                            //it can be blank in case 
                                                            //of a new game.
                  .OpenWithGameFile(CurrentGameFileName)    //Path of .rvi file, 
                                                            //it can be blank 
                                                            //in case of a new game.
                  .FinishBuild();

Utility.SerializeUtility.cs

这个类用于序列化和反序列化任何类型的文件/对象。

Utility.UI.cs

它包含与深色模式相关的方法。
解释重要的代码。
这些是与人工智能无关的重要代码。

AI.Board.IsLegalMove()

1. 如果行和列不在值范围内，返回false；
2. 如果单元格不是空白单元格，则返回false；
3. 当我们尝试循环8个方向来检查下一个单元格时，我们不需要有8组重复的代码。
   我们可以像这样使用行和列的循环
   他们从这个嵌套循环中得到9个独特的结果。
   我们只需要其中8个用于每个方向的行和列更改。

行从 -1 到 1 循环，列从 -1 到 1 循环

• 行 -1，列 -1 表示西北。
• 行 -1，列 0 表示北。
• 行 -1，列 1 表示东北。
• 行 0，列 -1 表示西。
• 行 0，列 0 表示没有变化，跳过
• 行 0，列 1 表示东。
• 行 1，列 1 表示东南。
• 行 1，列 0 表示南。
• 行 1，列 -1 表示西南。

 

在这张图片中，中间的单元格代表我们需要检查的单元格。它在第0行，第0列。
我们知道西北单元格：行是-1，列是-1，我们从0-1，0-1得到它
我们知道北单元格：行是-1，列是1，我们从0-1，0-0得到它，以此类推。

对于这个条件，单元格必须首先至少有一个对手的单元格。
然后它必须有相同侧的单元格。

在这张图片中，只有D1是黑色回合的有效位置。

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)
        {
	     //Row and Col must be in range.
             return false;
        }
        //Not empty cell
        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)
                {
		        // just skip its self cell.
                        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)
                        {
			    //Encounter the same color without meeting the Opponent
			    //Case D5
                            break;
                        }
                        else
                        {
			    //If it can reach this point, it means it already hasAtLeastOne Opponent
			    //Then it meets the same color
			    //Case D1
                            return true;
                        }
                    }
                    if (CellsByPostion(PositionCheck) == OponentValue)
                    {
                        HasAtLeasOneOpoonentColor = true;
                    }
                }
            }
        }
    return false;
}

PutAndAlsoSwithCurrentTurn()

此方法的逻辑与IsLegalMove()方法类似。在调用SetCell()方法设置单元格值后，它需要循环8个方向，当找到可以翻转的位置时，它将保存在PositionFlip对象中。
检查完8个方向后，它将调用SetCell方法翻转单元格。

人工智能部分介绍

Minimax的工作原理

在谈论Minimax之前，我想先向您介绍决策树。下图描绘了井字棋游戏决策节点树的一个示例。

1. 有一个空白状态。
2. O可以放置九个可能的位置。
3. 对于O在#2中放置的每个位置，可以放置八个位置。
4. 对于X在#3中放置的每个位置，可以放置七个位置。

在#3，总共有

• 9 + (8 * 9) = 81个节点
• 9 * 8 = 72种可能性

在#4，总共有

• 9 + (8 * 9) + (72 * 7) = 585个节点
• 9 * 8 * 7 = 504种可能性

总共有362,880种可能性来在3x3棋盘上填充O和X。
这个值可以计算为 x = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2。
然而，井字棋游戏中可能的移动次数会少于这个数字，因为有些游戏会在棋盘满之前结束。

如果节点不多，我们只需遍历树中的每个节点，直到达到我们的最终目标。
然而，黑白棋游戏的树大约有 10 ^ 28 个节点。
我们利用Minimax来搜索一个有限的特定级别，其中节点可能相关，因为计算所有节点是不切实际的。

Minimax算法有两个部分。

1. 评估函数

这是一个接受棋盘值作为参数，然后返回分数的函数。我们使用这个函数是因为我们想知道我们的位置是好是坏。

// This is the concept
int score = Evaluate(board);

2. 搜索树

它是一个递归树，用于找到最优值。

这是一个在树上使用Minimax算法的例子。

假设你需要决定选择最好的武器来攻击你的敌人，而你的敌人将决定选择最好的盾牌来保护自己。你会选择哪种武器？

你应该选择最大值。你的敌人应该选择最小值，这就是Minimax。

评估函数只会在以下六个节点中发生：LShield1、LShield2、FShield1、FShield2、IShield1、IShield2。

这些是进程的顺序。冒号后面的值是处理后的值。

1. LShield1:100
2. LShield2:200
3. 雷电 = 找最小值(LShield1, LShield2) :100
4. FShield1:110
5. FShield2:90
6. 火焰 = 找最小值(FShield1, FShield2) :90
7. IShield1:120
8. IShield2:150
9. 冰 = 找最小值(IShield1, IShield2) : 120
10. 选择哪种魔法攻击 = 找最大值(雷电，火焰，冰) :120

我解释节点执行顺序的原因是，我第一次学习Minimax的时候。
我误以为这是正在处理的顺序。

1. 雷电:100
2. 火焰:90
3. 冰:120
4. LShield1:100
5. LSheidl2:200
   ...

我之所以误解，是因为树形图显示了每个节点计算后的值。所以我不知道哪个先发生。

雷电、火焰、冰等节点从未被评估过。
它们只是使用其子节点的值，只有叶子节点才会被评估。

Alpha Beta 剪枝

请看这棵树。

（我将FShiled1的值调整为90。）

根据这棵树，你不需要评估FSheild2。你可以消除它的原因是因为

Lighting = MIn(100,200)
Fire = Min(90,?)
Result = Max(Lighting,Fire)

我们知道结果将是100，无论FShield2节点的值是多少。

我们怎么知道的？

让我们尝试用50替换？并检查结果。

Result = Max(Min(100,200), Min(90,50))
Result = Max(100,50)
Result = 100

再试一次，这次我们用300。

Result = Max(Min(100,200), Min(90,300))
Result = Max(100,90)
Result = 100

您可以尝试更改?中的值，最终您将得到100作为结果。

您看到，当我们知道这两件事时

1. 火焰节点值为100。
2. “光照”节点的最小值小于90。

我们可以完全消除“照明”。
Alpha-beta剪枝用于在使用minimax算法时消除节点数量。你只需使用它，但在这个例子中，我们只有Beta，因为我们的树不够深，所以它只有Min级节点。

Alpha存储最大化器可以保证的最佳值。其初始值为-Infinity。我们可以直接使用int.MinValue代替-Infinity。
Beta存储最小化器可以保证的最佳值。
其初始值为Infinity。
我们可以直接使用int.MaxValue代替Infinity。

使用Alpha Beta剪枝

1. LShield1:100
2. LShield2:200
3. 照明 = 查找最小值(LShield1, LShield2) :100 将 Beta 设置为 100
4. FShield1:90 由于值是90，它小于Beta，我们可以忽略火节点其余的子节点。

这是我们在Minimax函数中如何使用alpha和beta值的概念。Alpha用于最大化玩家更新。Beta用于最小化玩家更新。您可以查看它，它将帮助您更好地理解。 https://bsmith156.github.io/Alpha-Beta-Visualizer/

//This is a concept, not actual function
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
}

与AI相关的重要类

BasicMiniMaxEvaluate 计算

我们的评估函数是如何工作的？

首先，我想向您介绍PositionScore的概念。
在黑白棋游戏中，角位被认为是好位置，因为它不能被对手翻转。
既然角是好的，那么角旁边的单元格是坏的，因为它允许你的对手占据角。

在这张图片中，黑方可以放置棋子的每个单元格都是一个糟糕的位置，因为黑方将棋子放置在这些位置后，白方将立即能够到达角落。

我们可以像这样设置位置分数。角是好的，我们给它100分，而角旁边是坏的，我们将其设置为-50和-100，对于其他单元格，我们将其设置为1。

这个评估函数足以击败相对不熟练的玩家，但它没有机会与黑白棋专家竞争。

我发现关于这个PositionScore的问题是，它不会选择靠近边界的单元格，尽管它是一个好位置。

这张图片显示，G2单元格对于黑方来说是一个好位置，因为它将允许他在A8处获得一个角。
并非所有靠近边界的单元格都是坏的，有时它们是好的，但程序无法理解。

所以我尝试寻找一种更好的方法来改进AI，我找到了这篇文章，Zdravko Krustev的黑白棋。

对于这两个函数，我遵循了他的相同逻辑。

• GetNumberofStableDiscsFromCorner()
• GetStableDiscsFromFullEdge()

在实现了这两个评估变量后，人工智能有了很大的改进。

Calculate()

• IsEndGame 如果游戏结束，此函数将仅确定结果：赢、输或平局。
• IsUseStatbleDiskScore 如果此值为true，它将调用GetNoStableDisk方法
• IsUseScoreFromPosition - 最后，它将比较BotScore和OpponentScore，然后返回ResultScore。
• 此方法将执行一个评估函数，它将计算双方的分数（Botscore和Opponentscore）。然后它返回BotScore - OpponentScore。
• GetNoofDiskCanBeFlipped() 遍历所有可能的移动。

尝试放置棋子。

检查可以翻转多少个棋子，然后保留，然后添加值。

GetNoStableDisk()

这是一个检查棋盘所有四个角和所有四个边缘的方法。

GetNumberofStableDiscsFromCorner()

然后检查棋盘四边所有完整的边缘。

来自角落的稳定棋子是指我们从每个角落计算稳定棋子的数量。
在这张图片中，我们计算出有5个稳定的棋子，我们没有计算C2上的棋子，因为它不符合模式。

GetStableDiscsFromFullEdge()

来自完整边缘的稳定棋子是指我们计算，如果边缘是完整的，我们有多少棋子在对手之间。
在这张图片中，它是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;
	// bool IsUseScoreFromPosition = true;

	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); // ((Board)board).OpponentTurn;
	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;
    // There is no moveable position from both player
	if (BotScore.NoofPossibleMove == 0 &&
		OpponentScore.NoofPossibleMove == 0)
	{
		IsEndGame = true;
	}
       
	if (IsUseScoreFromPosition)
	{
		GetScoreFromPosition((Board)board, ppositionScore, BotColor, BotScore,
			OpponentScore);
	}
	if (IsEndGame)
	{
		LogDebugL2("IsEndGame is true");
		//In case the game is end
		//We just check the disk of both player
		//To decide to result
		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; //Get score when 
                                                         //we can force to pass
	}
	if (IsINeedtoPass)
	{
		OpponentScore.ScorePassWeight += this.ForcePassSocre; //Opponent get score 
                                                    //when it can force us to pass
	}

	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;
}

如何配置机器人

您可以创建或更新机器人。

非选项卡区域。

1. 选择照片：只需点击选择一张照片

2. 机器人名称：机器人的名称

3. 每步时间限制（秒）：假设值为5，则机器人每回合最多可以使用5秒。

4. 稳定棋子分数：此值将乘以稳定棋子的数量。
   假设这个值是20。
   稳定棋子数量为10。
   总稳定棋子分数为 200 = 20 * 10。

5. 强制跳过分数：在黑白棋游戏中，当对手没有有效走法时，游戏将切换到您的回合。
   如果棋盘位置迫使对手跳过，您可以获得此分数。

6. 勾选使用位置分数：如果未勾选，机器人将不使用位置分数。

选项卡区域。

我们有三个选项卡，每个选项卡代表机器人在游戏过程中将使用的值。
我们允许配置开局、中期、残局阶段的值。
N = 白棋子数 + 黑棋子数；
开局：N <= 20
中期：N <=40
残局：N > 40

1. 位置分数：您看到有一个textbox数组，您可以配置位置分数。
2. 机动性分数：可用移动次数乘以机动性分数。
   如果这个值很高，机器人将尝试尽可能多地获得可用移动。
3. 深度级别：您可以配置深度级别，我建议它不应超过7
   这样机器人就不会花费太长时间进行计算。如果您将此值配置为大于7，请
   确保您已配置每步时间限制。
4. 复制单元格到中期，复制单元格到残局：如果您想将“位置分数”复制到另一个选项卡，只需点击按钮。

UI\PanelPositionBotConfigure.cs

这个类继承自Panel，它包含一个64个Textbox的数组，允许用户输入评估函数的分数。

它允许您只需要配置A1到D4的分数，然后棋盘的其他三个部分将更改值以匹配您的A1到D4值。

UI\PanelBotConfigure.cs

这个类继承自Panel，它包含一个选项卡控件，该控件有三个选项卡页面：Opening（开局）、Middle（中期）和End Game（残局）。

每个页面都包含PanelPositionBotConfigure、机动性分数和深度级别。

AI\MiniMaxBotProto.cs

这个类是一个实现了IPlayer接口的类，所以我们只需要实现
MakeMove(AI.IBoard pBoard) 方法。

您在创建机器人时配置的值将存储在一个文件中，然后将被反序列化并填充到该类的对象中。

这个类的主要目的是仅仅存储评估函数参数，然后
调用Minimax类来执行它，这个类中没有计算。

[Serializable]
public class MiniMaxBotProto : IPlayer
{
	//private IEvaluate Evaluate;
	private BasicMiniMaxEvaluate Evaluate = null;
	public MiniMaxBotProto()
	{

	}
	/*
	 These values will be set to Evaluate object.
	 The main purpose of this class is to hold these value
	 */
	public int ForcePassSocre { get; set; } = 1000;
	public int StableDiskScore { get; set; } = 10;
	public int TimeLimitPermove { get; set; } = 3;// Number of second bot 
                                            // allowed to think in each turn.
	// public Boolean AllowRandom { get; set; } = false;

	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 string PhotoFileName { get; set; }
	// As of now don't use FileName, use Base64Image instead.

	/*
	 These are default value of PostionScore
	 For Open, Mid, End game.
	*/
	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)
	{
		//Select depth level according to the 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.ScoreNumberMoveAtBegingGame = this.ScoreNumberMoveAtBegingGame;

		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)
	{
	    // Using Minimax class to call calulcatNextMove() method
		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,  // Evaluation object
			BotColor,
			this.TimeLimitPermove,
			IsUsingAlphaBeta, 
			IsKeepLastDecisionTree,// For viewing Minimax node later.
			IsAllowRandomDecision, // To prevent bot vs bot playing the same everytime.
			IsSortedNode           // For better performance, 
                                   // sort the node at some depth level
			);
		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()
	{
		//These are default values
		//They will be used in case we don't load Botvalue then FillEvaluateObject
		//
		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;

		//IEvaluate Evu = new BasicMiniMaxEvaluate();
		minimaxBorProto.Evaluate = new BasicMiniMaxEvaluate(minimaxBorProto);
		return minimaxBorProto;
	}
}

将分数保存在缓存中

这张图片显示了一个重复节点的例子。

Hash.cs

当我们为Minimax函数创建搜索树时，树节点有可能与其他树节点具有重复的值。如果发生这种情况，我们不想再次进行评估，所以我们决定将分数保存在哈希对象中。

每次我们调用评估函数来计算棋盘分数时。我们会将分数保存在这个Hash对象中，下次当出现重复节点时，我们只需检索我们已经存储的值。

我们还需要保留深度级别，因为相同的棋盘位置在不同级别有不同的分数。

public class Hash
{
	public static int ScoreForNonExist = int.MaxValue / 2;

	public static int GetHashForBoard(Board board)
	{
	    /* We need to use GetHashCode() multiple with the current turn
		because we need to know if it it black or white  turn.
		GetHashCode is just a function to calculate hash by simply
		multiple with each member value.
		It can be improved to use XOR hash function.		
		*/
		return board.GetHashCode() * (int)board.CurrentTurn ;
	}
	
	/* For DicHash
		int is Hashvalue
		Dictionary<int,int>	is DicDepthScore
	   For DicCepthScore
	        First int is the depth level
		Second int is the score.	
	*/
	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;
	}
	/*
	Add new hash and evaluated score value
	We also need Depth parameter because the same board position
	with different depth return the different value
	*/
	public void Add(int HashCodeForBoard, int Score, int Depth)
	{
		Dictionary<int, int> DicDepthScore = new Dictionary<int, int>();
		if (DicHash.ContainsKey(HashCodeForBoard))
		{
			//if this board value already exist
			//Search for the depth
			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)
	{
		// Dic
		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

我们使用这个类来存储minimax参数的值。
实际上，你不需要这个类来使用minimax函数。
我创建这个类是因为我需要将MinimaxParameterExtend列表作为子项保存，因为
我需要稍后向想学习minimax工作原理的人展示它。

[Serializable]
public class MiniMaxParameterExtend : MiniMaxParameter
{
	public List<MiniMaxParameterExtend> child = 
        new List<MiniMaxParameterExtend>(); //We keep the children nodes here.
	public PositionScore PositionScore { get; set; } = 
        new PositionScore();                // The selected position and its score.
	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()

此方法仅用于准备参数以调用MinimaxAlphaBetaExtend()

MinimaxAlphaBetaExtend()

1. 如果不是最后一步，检查是否需要跳过。
   如果机器人颜色没有有效移动，则切换到对手颜色，然后检查是否有有效移动。
   如果两种颜色都没有有效移动，则set IsFinalMove=true

2. 如果是最终移动，请从哈希中检查此位置是否已计算并存储在哈希中。
   如果是，从哈希中获取Score。
   如果不是，则调用评估板函数，然后将分数存储在哈希中。
   返回score。

3. 它与排序可用移动有关。
   程序将尝试从棋盘评估分数，然后尝试对可用移动进行排序。
   我们不会在每个深度级别上都这样做。
   从#3得到的结果将发送到#4。

4. 这是我们执行minimax的部分。
   遍历可用移动中的所有Position。
   检查是否可以从哈希中获取分数。
   如果不能，只需调用MinimaxAlphaBetaExtend来获取childScore。
   将其存储在hash对象中。
   此方法的结果只是普通的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();

    //This Para object will be sent to MinimaxAlphaBetaExtend()
	MiniMaxParameterExtend Para = new MiniMaxParameterExtend();

	Para.Depth = depth - 1;
	Para.board = (Board)board.Clone();
	Para.IsMax = true; // The initial node is for Maximum player
	Para.Alpha = int.MinValue; // Initial value of Alpha
	Para.Beta = int.MaxValue;  // Initial value of Beta
	Para.BotColor = BotColor;
	NodeCount = 0; 
	EvaluateCount = 0;
	EndTime = DateTime.Now.AddSeconds(SecondsLimitPerMove); // The end time 
                                                            // that allows bot to use 
	Log("CalculateNextMove :: SecondLimitPerMove ::" + SecondsLimitPerMove);
	Log("CalculateNextMove :: Depth ::" + Para.Depth);


	Utility.TimeMeasure timeM = new Utility.TimeMeasure(); // To keep track how long 
                                                           // it takes
	iCountHashCanAccess = 0; //Keep track number of time Hash object can be access
	timeM.Start();
	this.FirstLevelDepth = Para.Depth;
	listFirstLevelDepthMoves = new List<PositionScore>();
	PositionScore score = MinimaxAlphaBetaExtend(Para,
		IsUsingAlphaBeta, 
		IsKeepingChildValue, // To show Minimax later
		IsSortedNode);       // Improve searching by tryting to sort fist
	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)
	{
	    // Random decision if Number of disk on board is <= 14
		// This feature exists to prevent bot vs bot 
        // select the same position everytime
		if (IsUsingRandomIfNodeValueIsTheSame)
		{
			Log("CalculateNextMove ::  IsUsingRandomIfNodeValueIsTheSame");
			score = GetRandomFromMaxScoreNode(listFirstLevelDepthMoves);

			move = new Position(score.Row,
				score.Col);
		}
	}

	//NodeCount = 0;
	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;
	// Save MimimaxFor debug, to show later
	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 it is final move, 
	   calculate the score then return
	*/
	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;
	}
	// For Supporting sort node before doing Minimax
	// We don't sort the node at everydepth 
	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));
		}		
	}
	// End For Supporting sort node before doing Minimax

	//Begin doing Minimax
	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");
		// For Viewing Minimax later
		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);
			//hashTranportable.Add(BoardHash, childScore.Score);
		}
		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;
}

显示 Minimax 最新移动

您可以点击游戏->显示Minimax最新移动菜单。

请确保玩家2是机器人。

解释这张图片中的一些值。
9[F5]Min 表示
9 是以下节点 (9, 10, 10, 10, 10, 10) 的最小值

12[] Max 表示
12 是以下节点 (9, 7, 12, 7) 的最大值

-4[D1] 叶子表示 - 这是一个叶子节点，评估函数在此节点上执行，值为-4。

测试

您可以运行所有单元测试和集成测试。
请确保它们都通过，但您可以跳过BotFightTest，因为它大约需要20秒才能完成。

我们可以做些什么来改进

如果我们需要改进程序，可以做以下几件事来增强人工智能。

1. 将棋盘的数据结构从二维数组更改为bitboard。
2. 包含开局库功能；我们预先计算评估结果并将其保存到文件中，然后我们直接从文件中获取值，无需再次计算。
3. 应使用异或哈希而不是此哈希函数。

看点

有许多功能我最初不打算包含，例如创建棋盘或机器人，但开发它们后，我意识到它们极大地帮助我发现错误和修复程序。

参考文献

• Reversi
• C# 中的黑白棋
• https://github.com/clarkkev/othello-ai/blob/master/src/othellosaurus/Board.java
• https://github.com/BSmith156/Othello-AI
• Minimax
• Alpha–beta 剪枝
• 如何更改组合框背景颜色（不只是下拉列表部分）
• Windows 10 上 WinForms 深色标题栏
• 将图像（按路径选择）转换为base64字符串

历史

• 2022年12月6日：初始版本