Reversi

• 下载源代码 - 57.8 KB

引言

本项目是对 Reversi 游戏的实现，带有简单的人工智能。

背景

我有一个任务，使用alpha-beta 剪枝算法为Reversi游戏编写人工智能。这项任务是我在索非亚大学数学与计算机科学系学习的人工智能课程的一部分。这是结果。

使用代码

该项目包括几个实现游戏内部结构的类，以及用于用户界面的几个控件和窗体。

根据功能，这些类是

• DiscColor - 表示棋盘上棋子的可能颜色：黑色、白色和无 - 棋盘区域为空。
• Board - 实现一个二维数组，每个元素代表游戏棋盘的一个区域（带有 DiscColor）。该类提供了一些方法，用于确定玩家是否可以在指定位置进行移动、进行移动以及转换对手的棋子等。
• Game - 提供整个游戏过程：设置玩家属性、开始新游戏、玩家切换以及游戏完成。Game 类的一个实例是使用 Board 类的一个实例创建的（就像在现实世界中一样 - 要玩游戏，你必须先有一个棋盘）。
• PlayerProperties – 顾名思义，这个类描述了游戏中每个玩家的属性。特定游戏的玩家由 Game 类的 CreatePlayer1(PlayerProperties properties) 和 CreatePlayer2(PlayerProperties properties) 方法创建。PlayerProperties 类支持序列化，并且两个玩家的属性存储在配置文件中，如下所述。这允许下一场游戏使用相同的玩家属性进行。
• Player – 抽象类，提供游戏中玩家的基本功能。该类的 Type 属性指示玩家类型，StartMove() 方法允许在派生类中添加一些在玩家开始新移动时执行的功能。
• HumanPlayer, ComputerPlayer – 目前游戏中可用的玩家类型类。继承自 Player 类。
• MoveSolver – 为电脑玩家提供人工智能。

窗体和控件如下

• BoardFieldControl – 表示游戏棋盘的一个区域。当玩家可以在指定区域进行移动时，该区域会高亮显示。
• PlayerInfoControl – 显示指定玩家的信息 - 名称、类型、颜色、棋盘上的棋子。
• BoardControl – 这个控件提供了游戏的整体外观 - 一个棋盘，以及关于玩家和结果的信息面板。
• PlayerPropertiesControl – 允许用户在开始新游戏时选择玩家的属性。
• StartNewGameForm – 显而易见，在这个窗体中，你输入开始新游戏所需的信息。两个玩家的属性存储在一个名为“PlayersInfo”的配置文件中，StartNewGameForm 在加载时从该文件中初始化其字段。相应地，当单击“确定”按钮时，它会将它们存储回那里。
• MainForm – 包含一个 BoardControl，并在加载时调用 StartNewGameForm。

游戏过程

1. 创建一个新的 Game 类实例，使用一个 Board 类实例；
2. 使用 Game 实例的 CreatePlayer1() 和 CreatePlayer2() 方法创建两个玩家；
3. 通过 Game 实例的 Start() 方法开始新游戏。
4. Player1 轮到他下棋。
5. 调用 Player1 的 StartMove() 方法。当使用 SetFieldColor() 方法设置游戏 Board 属性的元素时，移动结束。
6. 如果 Player2 可以移动，则 Player2 轮到他下棋。对 Player2 执行的操作与上一步对 Player1 执行的操作相同。
7. 如果 Player1 可以移动，则 Player1 轮到他下棋。

重复步骤 5-7，直到两个玩家都无法移动为止。此时游戏结束，并触发 Game 的 Finished 事件。

新游戏的创建过程可以在 MainForm 类的 StartNewGame() 方法中看到。

Game game = new Game(new Board());
game.CreatePlayer1(frmStartNewGame.Player1Properties);
game.CreatePlayer2(frmStartNewGame.Player2Properties);

this.ctrlBoard.SetGame(game);
game.Start();

人工智能

由于这是人工智能课程的项目，所以人工智能应该是其中最重要的部分。如上所述，程序使用 alpha-beta 剪枝算法来取得胜利。正如你所知，创建整个搜索树（包含从游戏开始到结束的所有可能移动）需要大量的内存。因此，当达到搜索树中的指定深度时，当前节点将使用启发式函数进行评估。这发生在 MoveSolver 类的以下方法中：

private int EvaluateBoard(Board board)
{
    DiscColor color = this.Player.Color;
    DiscColor oppositeColor = DiscColor.GetOpposite(this.Player.Color);

    List<int[]> oppositePlayerPossibleMoves = this.GetPossibleMoves(board, oppositeColor);
    List<int[]> possibleMoves = this.GetPossibleMoves(board, color);

    if ((possibleMoves.Count == 0) && (oppositePlayerPossibleMoves.Count == 0))
    {
        int result = board.GetDiscsCount(color) - board.GetDiscsCount(oppositeColor);
        int addend = (int)Math.Pow(board.Size, 4) + (int)Math.Pow(board.Size, 3); 
        // because it is a terminal state, its weight must be bigger than the heuristic ones
        if (result < 0)
        {
            addend = -addend;
        }
        return result + addend;
    }
    else
    {
        int mobility = this.GetPossibleConvertions(board, color, possibleMoves) 
            - this.GetPossibleConvertions(board, oppositeColor, oppositePlayerPossibleMoves);
        int stability = (this.GetStableDiscsCount(board, color)
            - this.GetStableDiscsCount(board, oppositeColor)) * board.Size * 2 / 3;

        return mobility + stability;
    }
}

正如你所见（如果你尝试弄清楚这段代码到底做了什么），指定节点（board 参数代表游戏当前状态的整个棋盘）的启发式值由两个标准构成 - 稳定性（玩家棋盘上稳定棋子的数量）和机动性（可以翻转的对手棋子的数量）。最终值使用一些“魔法数字”作为系数进行评估。这些系数的灵感来自我做的一些测试，并没有“合理”的解释。

如果当前节点是叶节点，这意味着我们处于游戏结束阶段，并且可以轻松判断该状态是获胜还是失败。只需从玩家棋子数中减去对手棋子数，然后加上一个相当大的数字（正或负），这样结果就会大于在搜索树的同一深度进行的任何启发式评估。这是因为游戏结束时的评估是绝对正确的，并且比我们进行的任何启发式评估都更重要。