65.9K
CodeProject 正在变化。 阅读更多。
Home

测试驱动的国际象棋人工智能

KristianEkman
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.92/5 (76投票s)

2017年2月3日

Ms-RL

11分钟阅读

viewsIcon

102050

downloadIcon

4753

国际象棋引擎和简单的国际象棋用户界面。

有关更改列表，请参阅下面的“历史记录”部分。

引言

这是一个功能齐全但简单的国际象棋程序，旨在帮助您了解国际象棋引擎的工作原理。互联网上已经有一些开源的国际象棋引擎，它们专注于高性能。这是一个标准的面向对象的C#解决方案，旨在更易于理解。重点不在于制造一个快速且评分很高的国际象棋引擎。我开发了一个可行的国际象棋AI，它能下出不错的棋，代码也希望您喜欢阅读。一些更具体的目标是使用C# 6正确实现Alpha Beta Pruning和Zobrist Hashing。

目录

背景
代码
如何开始
特点
国际象棋引擎
   棋盘和对局
   移动
   评估版
   搜索
性能
我学到的东西
历史

背景

大约十年前，我曾尝试实现一个国际象棋引擎但失败了。这次，我决定采用测试驱动开发（TDD）的先写测试的方法。我喜欢TDD，并且我认为使用TDD是这次引擎能够成功的主要原因。100%正确地实现国际象棋规则非常重要。同样重要的是，撤销走法要精确地恢复到先前的状态。我也认为TDD有助于形成良好的代码结构和可维护的系统设计。

代码

该解决方案包含两个主要项目。引擎（chess.dll）和用户界面。Chess.dll包含有关对局、棋盘、规则和引擎的所有内容。它还包含所有测试。在此实现中，我认为没有必要将单元测试放在单独的项目中。这样，人们可以轻松地看到哪些单元测试属于哪个类。

目前有82个测试。其中大多数测试速度都很快，代码覆盖率约为100%。代码总行数不到4000行，包括测试和用户界面。包含大部分逻辑的引擎和对局类代码不足900行。

还有一个名为BitChess的小项目正在开发中。

国际象棋UI是一个Windows Forms应用程序，只有加载、保存和设置计算机思考时间等几个功能。您还可以编辑和设置自定义棋盘位置，并保存和加载FEN位置。

如何开始

如果您是TDD新手，经常会想：“我该从哪里开始？！”以及“我如何测试一个不存在的东西？”解决方案是编写甚至无法编译的测试，您将驱动设计和程序朝着正确的方向发展。我开始这个项目时写的第一个测试是

[TestMethod]
public void BoardHasSquaresTest()
{
     var board = new Board();
     Assert.AreEqual(64, board.Squares.Length);
}

在Visual Studio中，您可以使用内置的快捷方式生成您的测试用例编译所需的缺失类型和成员。

互联网上有很多免费且优质的文献，解释了国际象棋引擎中的各种算法和技术。下面，您可以找到对我有所帮助的页面的链接。

特点

  • 迭代 Alpha-Beta Pruning，它极大地减少了需要分析的位置数量。在深度零时，还会执行深度为二的 Quiescence Search，以防止 Horizon Effect 的风险。这是国际象棋引擎的一个非常重要的功能，我在本文中没有过多涉及。但如果您不通过Quiescence Search扩展搜索，引擎有时可能会下出非常糟糕的棋。
  • Zobrist Hashing，用于快速查找已评估的位置。我将几百万个位置保存在数据库中，因此每个位置只需要计算一次。
  • 并行线程，如果可用多个核心，则提高引擎性能。
  • 国际象棋棋盘由一个64个格子的数组表示。（位棋盘速度更快，但可能有点复杂。）
  • 位置的得分基于子力以及每个棋子的位置得分。在开局阶段，一些基本的开局原则会获得额外分数。在残局阶段也会进行特殊计算。
  • 也评估了重复和棋、子力不足、50步规则和逼和。
  • 开局库尚未实现。

国际象棋引擎

这就是我的国际象棋引擎的实现方式。

棋盘和对局

引擎当然必须理解什么是国际象棋。一局棋有两个玩家。玩家拥有棋子，每种棋子都有其属性。棋局在棋盘上进行，棋盘由格子组成。一个格子可以有一个棋子，也可以没有。下面是这些类型的类图。点击放大。

移动

每种棋子类型都有其走法模式。用于生成走法。为所有玩家的棋子生成一个伪合法走法的列表。保留合法走法。下面的代码片段来自对局类。

internal List<move> GetPseudoLegalMoves() {
    var moves = new List<move>();
    foreach (var piece in CurrentPlayer.Pieces)
        piece.AddPseudoLegalMoves(this, moves);

    AddCastling(moves);
    return moves;
}

在走了一个伪合法走法后，会测试己方王是否被将军。己方王在走法后不能被将军，因此这些走法是非法的。

private bool KingChecked(Player checkedPlayer) {
    var kingSquare = checkedPlayer.King.Square;
    var otherPlayer = checkedPlayer == WhitePlayer ? BlackPlayer : WhitePlayer;
    foreach (var piece in otherPlayer.Pieces) {
        if (piece.Attacks(kingSquare, Board))
            return true;
    }
    return false;
}

评估版

实际上，最好在走法生成时立即评估走法，而不是在引擎搜索过程中。这是因为当走法有序时，搜索会更有效。当先评估较好的走法时，搜索更有可能排除许多走法。稍后将详细介绍。

评估给出分数。如果黑方占优，则为正，对白方有利的位置为负。每个棋子都有一个值。后是九。车是五。象和马是三，兵是一。子力得分是黑方棋子总数减去白方棋子总数。棋子的位置也很重要。引擎评估

  • 控制中心（白方在第四行，黑方在第五行的d和e兵）
  • 车在开放线上
  • 开局时后方的移动是不利的
  • 易位以保护王是好的
  • 坏的马靠近边界
  • 双兵
  • 在开局阶段移动一次象和马是好的

评估还涉及到残局以及谁是赢家。当一方被将军且没有合法走法时，就是将死，如果黑方获胜，得分将设置为一个非常大的数字，如果白方获胜，得分将非常低。

private int NoChildrenEval(Game gameCopy, Move node) {
    if (gameCopy.CurrentPlayer.IsChecked) {
        node.ScoreInfo |= ScoreInfo.Mate;
        node.ScoreAfterMove = 8000;
        gameCopy.Winner = gameCopy.OtherPlayer;
    } else {
        node.ScoreInfo |= ScoreInfo.StaleMate;
        node.ScoreAfterMove = 0;
    }
    gameCopy.Ended = true;
    PositionsDatabase.Instance.Store(gameCopy, node);
    return node.ScoreAfterMove.Value;
}

您可能知道，国际象棋也可以以和棋结束，如果一方没有合法走法（逼和）或如果棋局重复了三次相同的局面。如果过去50步没有发生吃子或兵的移动，棋局也以和棋结束。

现在我们可以区分坏走法和好走法了，我们可以搜索好走法。搜索从深度一。白方走子，在白方每一步棋之后，黑方也为每一步白棋走子。由于黑方会尽力争取最大的分数，白方的最佳走法是导致黑方应手走法列表具有最低最大值的走法。这种min max搜索也通过一个称为alpha beta pruning的算法得到很大改进，该算法可以剪掉许多明显糟糕的走法。

这是一个解释Alpha Beta Pruning的精彩动画链接.

下面是递归alpha-beta函数的简化伪代码版本。

int alphaBeta(Move node, int alpha, int beta, bool maximisingPlayer) {
    int bestValue;
    if (node.children.length === 0) {
        bestValue = node.data;
    }
    else if (maximisingPlayer) {
        bestValue = alpha;       
        for (var i=0, c=node.children.length; i < c; i++) {
            var childValue = alphaBeta(node.children[i], bestValue, beta, false);
            bestValue = Math.max(bestValue, childValue);
            if (beta <= bestValue) {
                break;
            }
        }
    } else {
        bestValue = beta;        
        // Recurse for all children of node.
        for (var i=0, c=node.children.length; i<c; i++) {
            var childValue = alphaBeta(node.children[i], alpha, bestValue, true);
            bestValue = Math.min(bestValue, childValue);
            if (bestValue <= alpha) {
                break;
            }
        }
    }
    return bestValue;
}

如果走法有序且最佳走法先执行，则剪枝机制效率更高。通过将深度增加一，重复相同的搜索，直到设定的时间耗尽。每次迭代后，都会对走法进行排序，以便先评估好的走法。这看起来效率很低，但实际上，与从一开始就确定深度相比，它是一种更快地找到最佳走法的方法。

如果您设法将所有内容都做对了，现在会发生一些非常酷的事情。您的程序突然开始展现出一些智能。但您远未完成。您可能希望使搜索更有效率，搜索更深的深度并提高性能。可能花费计算机时间最多的是得分评估，并且可以通过 Zobrist Hash Key 存储在内存中以便快速查找。

性能

为了进一步提高性能，目标是为国际象棋棋盘的任何设置创建尽可能唯一的键。该键可用于存储信息，并在评估相同局面时快速加载。

问题在于，国际象棋棋盘可以处于无数种不同的状态。64个格子中的每一个都可以有十二种不同的棋子类型之一。定义独特状态的还有轮到哪位玩家走棋以及每位玩家有哪些易位权利（后翼或王翼）。据说国际象棋棋盘状态的组合数量比宇宙中电子的数量还要多！

Zobrist Hashing通过创建仅八个字节的键来出色地解决这个问题。在游戏开始时，会生成768（64个格子乘以12种棋子类型）个不同的数字。当玩家移动棋子时，通过几个 异或运算(xor) 使用状态变化的随机数来改变先前的游戏哈希。在大多数情况下，只有两次运算。

在更新哈希键时，您还应该考虑升变、吃子和易位，但这两行在Zobrist Hash Key实现中是最重要的。

game.Hash ^= ZobristArray[piece, fromSquareIndex]; //piece off
game.Hash ^= ZobristArray[piece, toSquareIndex]; //piece on new square

如果您两次应用相同的异或运算，您实际上会回到相同的哈希键。这在撤销走法时非常有用。

在 Zobrist Hash Key 存储在内存数据库中，并附带一个包含有关该局面少量数据的整数。这些数据只需计算一次。下次出现相同的哈希键时，将使用该键查询数据库。

这是打包在32位整数中的数据。数据被打包以减小尺寸并增加数据库的访问速度，使用位移位。

  1. 命令编号（7位），用于清理不需要的旧局面
  2. 如果走法合法，即己方王被将军（1位）
  3. 对手王被将军（1位）
  4. 棋盘得分（13位）
  5. 未使用空闲位。（5位）
  6. 重复和棋、子力不足、逼和及将死（4位，每种1位）

将一些对局数据打包成整数的函数。

int Pack(byte commandNo, bool legal, bool check, int score, ScoreInfo scorInfo) {
    var freeBits = 5;
    var build = (int)commandNo;
    build <<= 1;
    build |= (legal ? 1 : 0);
    build <<= 1;
    build |= (check ? 1 : 0);
    build <<= 1;
    build |= score < 0 ? 1 : 0;
    build <<= 13;
    build |= Math.Abs(score);
    build <<= 5;
    build |= freeBits;
    build <<= 4;
    build |= (byte)scorInfo;
    return build;
}

解包对局数据。

void Unpack(int build, out byte oCommandNo, out bool oLegal, out bool check,
    out ScoreInfo oScoreInfo, out int oScore) {
    oCommandNo = (byte)((build >> 25) & 0x7F); //7 bits
    oLegal = ((build >> 24) & 1) == 1;
    check = ((build >> 23) & 1) == 1;
    var negScore = ((build >> 22) & 1) == 1;
    oScore = (build >> 9) & 0x1FFF; //13bits
    oScore = negScore ? oScore * -1 : oScore;
    var freeBytes = (byte)((build >> 4) & 0x1F); //5bits
    oScoreInfo = (ScoreInfo)(build & 0xF); //4 bits
}

我的双核2.7Ghz笔记本电脑每秒分析约50k个局面。这在对局中期足够看到五到六步棋。大多数普通水平的棋手（比如我）在相同思考时间内应该很难击败这个引擎。在chess.com的CPU对局中测试时，我估计其评分约为1300。我认为提高其性能的最佳方法是用位棋盘替换棋盘表示。这可以提高走法生成和局面评估，从而可以进行更深的搜索。

我在本项目中学到的东西

编写单元测试非常重要，甚至可以先编写它们。在TDD中，您必须有一个失败的测试才能编写函数。这是确保一切都经过测试的绝佳方法。

Alpha Beta算法可能是国际象棋引擎中最具挑战性的部分。互联网上有许多伪代码示例。我只设法让其中一个成功运行。它来自 Algorithm Wiki。

哈希是国际象棋编程的重要组成部分。棋盘必须保存局面得分以便快速访问。哈希存储在64位数据类型中，但国际象棋局面有更多可能的组合。我发现，在我实现了Zobrist哈希，它非常有效地分散了哈希冲突的风险后，没有发生哈希冲突，这相当令人惊讶。

运行性能分析很重要。分析速度越快，每秒分析的局面越多，即使是很小的改进也会对整体性能产生巨大影响。

另一个很好的学习网站是 Chess Programming Wiki。

国际象棋引擎是一个很大的课题，几个世纪以来已经进行了很多研究。我不确定您仅通过阅读本文就能写出自己的国际象棋引擎，但希望它是一个很好的介绍，并且如果您有兴趣成为一名国际象棋引擎开发者，它能为您指明正确的方向。

历史

  • 2017年1月31日 - 版本1.0
  • 2017年2月10日 - 版本1.1
  • 2017年2月12日 - 版本1.1.1 （Bug和性能修复）
  • 2017年2月19日 - 在文本中添加了代码示例，并重写了一些部分以提高理解度。
  • 2017年3月5日 - 撰写了更多关于Zobrist Hash的内容。添加了目录。
  • 2017年5月23日 - 版本1.2
    • 50步规则
    • 编辑FEN
    • 性能和稳定性

如果您受到本文的启发，开始深入研究这个主题并成为一名国际象棋引擎开发者，请给我留下评论、提问或只是打个招呼。:)

祝您代码阅读愉快，并祝您在国际象棋编程学习中好运！

© . All rights reserved.