测试驱动的国际象棋人工智能（译文）

原文地址：https://www.codeproject.com/Articles/1168892/Test-Driven-Chess-Artificial-Intelligence

原文作者：KristianEkman

译文由本站 robot-v1.0 翻译

前言

Chess engine and simple chess user interface

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

• 下载源-636.3 KB(Download source - 636.3 KB)
• 下载演示-135.2 KB(Download demo - 135.2 KB)
• 来源Git(Source on Git) 有关更改列表,请参见下面的"历史记录"部分.(See History section below for list of changes.)

介绍(Introduction)

这是一个功能齐全但简单的国际象棋程序,旨在帮助您了解国际象棋引擎的工作方式.互联网上已经有专注于高性能的开源国际象棋引擎.这是一个标准的面向对象的C#解决方案,旨在使其更易于理解.重点不是制造快速和高评级的国际象棋引擎.我已经开发了一种可运行的国际象棋AI,可以使用您希望阅读的代码进行良好的下降动作.一些更具体的目标是使用C#6正确实现Alpha Beta修剪和Zobrist哈希.(This is a fully functional yet simple chess program that aims to help you understand how a chess engine works. There are already open source chess engines on the Internet which focus on high performance. This is a standard object oriented C# solution that is meant to be easier to comprehend. The focus has not been to make a fast and high rated chess engine. I have developed a working chess AI that plays descent good moves with code that you hopefully like to read. A few of the more specific goals have been to correctly implement Alpha Beta Pruning and Zobrist Hashing using C# 6.)

目录(Table of Contents)

背景(Background) 代码(The Code) 如何开始(How to Start) 特征(Features) 象棋引擎(The Chess Engine) 董事会与游戏(The Board and the Game) 动作(Moves) 评价(Evaluation) 搜索(Search) 性能(Performance) 我学到(What I have learned) 历史(History)

背景(Background)

大约十年前,我尝试实施国际象棋引擎,但失败了.这次,我决定使用"测试驱动开发"(TDD)测试优先方法.我喜欢TDD,我认为使用TDD是这次引擎正常工作的主要原因.正确执行国际象棋规则十分重要.同样重要的是,撤消动作会准确地进入先前的状态.我还认为TDD有助于良好的代码结构和可维护的系统设计.(About ten years ago, I tried to implement a chess engine and failed. This time, I decided to use Test Driven Development (TDD) test first approach. I like TDD and I think using TDD was the main reason the engine worked this time. It is very important that the rules of chess are 100% correctly implemented. Equally important is that undoing moves result exactly into the previous state. I also think that TDD contributes to good code structure and a maintainable system design.)

代码(The Code)

该解决方案包括两个主要项目.引擎 ((The solution consists of two main projects. The engine ()国际象棋(chess.dll))和用户界面.() and the user interface.)**国际象棋(Chess.dll)**包含有关游戏,董事会,规则和引擎的所有信息.它还包含所有测试.在该实现中,我没有理由在单独的项目中进行单元测试.这样,就可以轻松查看哪些单元测试属于哪个类.(has everything about the game, the board, the rules and the engine. It also contains all tests. I saw no reason for having unit-tests in a separate project in this implementation. This way, one can easily see what unit-tests belongs to which class.)

目前有82个测试.它们中的大多数都非常快,并且代码覆盖率约为100%.包括测试和用户界面在内的代码行总数不到4000.大多数逻辑所在的引擎和游戏类少于900行代码.(There are currently 82 tests. Most of them are very fast and code coverage is about 100%. Total number of lines of code are just under 4000, including tests and user interface. The engine and game class where most of the logic is, is less than 900 lines of code.)

还有一个名为BitChess的小项目正在建设中.(There is also a small project called BitChess that is under construction.)

Chess UI是Windows Forms应用程序,仅具有一些功能,例如加载,保存和设置计算机思考的时间.您还可以编辑和设置自定义电路板位置,以及保存和加载FEN位置.(The Chess UI is a Windows Forms application with only a few features like load, save and setting the time for computer to think. You can also edit and setup custom board positions and save and load FEN-positions.)

如何开始(How to Start)

如果您不熟悉TDD,通常会想到:-(If you are new to TDD, it is very common to think: -)“我应该从哪里开始？!"(“Where should I start?!”).还有-(. And -)“如何测试不存在的东西？"(“How can I test something that does not exist?”*)*解决方案是编写甚至无法编译的测试,您将朝着正确的方向推动设计和程序.启动该项目时,我编写的第一个测试是:(The solution is to write tests that don’t even compile and you will drive the design and the program in the right direction. The first test I wrote when starting this project was:)

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

然后,在Visual Studio中,您可以使用内置的快捷方式来生成缺少的类型和测试用例需要编译的成员.(In Visual Studio, you can then use the built-in short-cuts for generating the missing types and members your test case needs to compile.)

网络上有很多免费的优秀文献,对国际象棋引擎中的不同算法和技术进行了说明.在下面,您可以找到指向对我有帮助的页面的链接.(There is a lot of free and good literature on the web explaining the different algorithms and techniques in a chess engine. Below, you can find links to pages that have helped me.)

特征(Features)

• 迭代式(Iterative) Alpha-Beta修剪(Alpha-Beta Pruning) ,从而大大减少了需要分析的职位数量.深度为零,深度为二(, which drastically decrease the number of positions that need to be analyzed. At depth zero, a depth two) 静态搜索(Quiescence Search) 也是为了防止(is also performed to prevent the risk of) 地平线效应(Horizon Effect) .这是国际象棋引擎的一个非常重要的功能,在本文中我不会介绍太多.但是,如果您不使用"静态搜索"扩展搜索范围,则很可能会导致引擎有时会做出非常差的动作.(. This is a very important feature of a chess engine that I don’t cover so much in this article. But if you don’t extend the search with a Quiescence Search, it’s a high risk that the engine sometimes will make very bad moves.)
• Zobrist Hashing(Zobrist Hashing) 为已评估的职位创建快速查找.我在数据库中保留了几百万个职位,因此每个职位只需要计算一次.(to create fast lookup for already evaluated positions. I keep a few million positions in a database so every position only has to be calculated once.)
• 如果有多个内核,则并行线程可提高引擎性能.(Parallel threads to increase performance of engine if multiple cores are available.)
• 棋盘由单个正方形[64]阵列表示. (位板速度要快得多,但可能要复杂一些.)(The chess board is represented by a single square[64] array. (Bit-boards are a lot faster but perhaps little bit more complicated.))
• 位置分数基于材料和每件的位置分数.在开幕式中,一些基本的开幕式原则给出了额外的要点.最终游戏中还会执行特殊的计算.(Score of the position is based on material and a positional score for each piece. In the opening, a few basic opening principles give extra points. Special calculations are also performed in the end game.)
• 反复抽奖,材料不足,50步移动规则和陈旧的配合也会被评估.(Draw by repetition, insufficient material, 50 move rule and stale mate are also evaluated.)
• 开本尚未实施.(Opening book is not yet implemented.)

象棋引擎(The Chess Engine)

这就是我的国际象棋引擎的实现方式.(This is how my chess engine is implemented.)

董事会与游戏(The Board and the Game)

引擎当然必须了解什么是国际象棋游戏.一个游戏有两个玩家.玩家有棋子,每种棋子都有其属性.游戏在带有正方形的板上进行.正方形可以有一块,也可以没有一块.下面是这些类型的类图.点击放大.(The engine must of course understand what a chess game is. A game has two players. Players have pieces and each piece type has its properties. The game is played on a board which has squares. A square can have a piece on it or not. Below is the class diagram of those types. Click to enlarge.)

动作(Moves)

每种棋子都有移动模式.它用于生成移动.将为玩家的所有棋子生成伪合法举动列表.法律行动得以保留.下面的代码段来自游戏类.(Each piece type has a move pattern. It is used to generate moves. A list of pseudo legal moves is generated for all pieces of a player. The legal moves are kept. The code snippets below are from the game class.)

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

    AddCastling(moves);
    return moves;
}

在采取伪法律行动之后,将测试自己的国王是否受到检查.自己的国王在举动之后无法受到控制,因此这些举动都是非法的.(After a pseudo legal move is made, it is tested whether the own king is in check. Own king can´t be in check after a move so those moves are illegal.)

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

评价(Evaluation)

实际上,最好在移动生成时而不是在引擎搜索期间立即评估移动.这是因为在命令移动时搜索会更加有效.首先评估更好的动作时,搜索很可能会忽略许多动作.以后再说.(It is actually better to evaluate moves right away in move generation and not during engine search. This is because the search is much more effective when moves are ordered. When better moves are evaluated first, it is more likely that the search can disregard many moves. More about that later.)

评价给出一个分数.如果黑色更好,则有利于白人的立场是正面和负面的.每一块都有价值.女王九岁.骗了五个.主教和骑士三和典当是其中之一.物质分数是黑色的总和减去白色的总和.件的位置也很重要.引擎评估:(Evaluation gives a score. If black is better, it is positive and negative for positions in favor of white. Each piece has a value. Queen is nine. Rook five. Bishops and knight three and pawns are one. The material score is sum of black’s pieces subtracted by sum of whites. Position of pieces are also important. The engine evaluates:)

• 中心控制(白色和白色在等级4上为黑色的d和e典当)(Control of center (d and e pawn on rank 4 for white and rank 5 for black))
• 乌鸦打开文件(Rooks on open files)
• 皇后运动在开幕式不好(Queen movement in the opening is bad)
• 卡斯特让国王安全是好的(Castling to get the king safe is good)
• 边境附近的坏骑士(Bad knights close to the border)
• 双兵(Double Pawns)
• 在开幕式中一次移动主教和骑士是一件好事(Moving bishops and knights once and only once in the opening is good) 评估也与游戏的结局以及谁是赢家有关.当玩家处于检查状态且没有合法移动时,则为检查队友,如果黑方获胜,则分数设置为非常大的数字,而白方则为非常低的分数.(Evaluation is also about the game ending and who is the winner. When a player is in check and has no legal moves, it is check mate and the score is set to a very large number if black wins and very low for white.)

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

如您所知,如果玩家没有合法举动(陈旧伴侣)或游戏重复相同的位置3次,则象棋游戏也可以以平局结束.如果最后50步未进行任何捕获或典当移动,则游戏也将以平局结束.(As you probably know, a chess game can also end in draw if a player has no legal moves (Stale mate) or if a game has repeated the same position three times. The game also ends in a draw if no capture or pawn move has been made the last 50 moves.)

搜索(Search)

既然我们可以分辨出好运,就可以搜索好运.搜索从深度一开始.白人球员做出自己的举动,而白人球员之间做出的每一步移动,黑人球员做出每一步的移动.由于黑人玩家会尽力获得尽可能大的分数,因此白色棋手最好的棋步是将其结果以最低值的黑色棋牌动作列表的形式显示出来.最小最大搜索也通过称为alpha beta修剪的算法得到了极大的改进,该算法可以消除许多明显的错误动作.(Now that we can tell bad moves from good, we can search for good moves. The search starts at depth one. White player makes his moves and between every white move black player makes his moves for every white move. Since black player will try its best to get as large score as possible, the best move for white is the move that results into a list of black response moves with the lowest max value. This min max search is also greatly improved by an algorithm called alpha beta pruning, which cuts off many obviously bad moves.)

这是一个不错的动画的链接,解释了Alpha Beta修剪(This is a link to a nice animation explaining Alpha Beta Pruning) .(.)

以下也是递归alpha-beta函数作为伪代码的简化版本.(Below is also the simplified version of the recursive alpha-beta function as pseudo code.)

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

如果移动是有序的,并且首先执行最佳移动,则切断机制会更加有效.再次重复相同的搜索,深度增加一倍,直到设置的时间用完.每次迭代后,将对移动进行排序,以便首先评估良好的移动.这似乎效率很低,但实际上它是找到最佳方法来迭代地增加深度的方法,比从一开始就确定深度要快得多.(The cut off mechanism is much more efficient if moves are order and the best moves are performed first. The same search is repeated again with the depth increased by one until the set time runs out. After each iteration, the moves are ordered so good moves are evaluated first. It might seem very inefficient, but it is actually a much faster way to find the best move to iteratively increasing the depth than going for a decided depth from the beginning.)

如果您成功解决了所有问题,那么现在会发生一些非常酷的事情.您的程序突然开始显示一些智能.但是,您还远远没有完成.您可能想使搜索更有效,更深入地搜索并提高性能.可能需要花费大部分计算机时间的是分数评估,并且可以使用(If you managed to get everything right, something very cool happens now. Your program suddenly starts to show some intelligence. But you are far from finished. You probably want to make the search more efficient, searching at greater depth and improving performance. What will probably take most of the computer time is score evaluation, and that can be stored in memory with a) Zobrist哈希键(Zobrist Hash Key) 快速查找.(for fast lookup.)

性能(Performance)

为了进一步提高性能,目标是为任何棋盘设置创建尽可能唯一的键.然后,可以使用该密钥存储信息并在评估相同位置时快速加载它.(To further improve performance the goal is to create a key as unique as possible for any setup of the chess board. That key could then be used to store information and quickly load it when the same position is evaluated.)

问题在于,国际象棋棋盘可能处于多种不同状态. 64个方块中的每个方块都可以具有十二种不同的棋子类型之一.还定义了唯一状态的是依次播放哪个玩家以及每个玩家具有哪些castling权限(皇后方或国王方).据说国际象棋桌状态中可以存在的组合数大于宇宙中估计的电子数!(The problem is that the chess board can be in an enormous amount of different states. Each of the 64 squares can have one of twelve different piece types. What also defines the unique state is which player is in turn to play and what castling rights each player has (queen side or king side). It is said that the number of combinations a chess table state can be in, is greater than the estimated number of electrons in the universe!)

Zobrist Hashing通过仅创建八个字节的密钥来显着解决了这一问题.在游戏开始时,会生成768个(64平方乘以12件类型)不同的数字.当玩家移动棋子时,先前的游戏哈希值会改变几(Zobrist Hashing remarkably solves this by creating a key of just eight bytes. At game start, 768 (64 squares times 12 piece types) different numbers are generated. When a player moves a pieces the previous game hash is changed with a few) 异或运算(exclusive or operations) (xor)使用状态更改随机数.在大多数情况下,只有两个操作.((xor) using the state changing random numbers. In most cases, there are only two operations.)

在更新哈希键时,您还应该考虑提升,捕获和强制转换,但是这两行在Zobrist哈希键实现中最重要.(When updating the hash-key you should also think of promotion, capturing and castling but these two lines are the most important in the Zobrist Hash Key implementation.)

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

如果两次应用相同的排他运算,您实际上将返回到相同的哈希键.这在撤消移动时非常有用.(If you apply the same exclusive operations twice you actually get back to the same Hash Key. That is very useful when undoing moves.)

的(The) Zobrist哈希键(Zobrist Hash Key) 被存储在内存数据库中的整数与包含有关位置的少量数据的整数.这些数据只需要计算一次.下次出现相同的哈希键时,将使用该键查询数据库.(is stored in a memory database together with an integer containing a little data about the position. These data only have to be calculated once. Next time the same hash key shows up, the database is queried with the key.)

这是打包为32位整数的数据.打包数据以减小大小并使用移位来增加对数据库的访问.(This is the data that is packed in an 32 bit integer. The data is packed to decrease size and increase access to the database using bit shifts.)

• 命令编号(7位),用于清洁不需要的旧位置(Command Number (7 bits), used for cleaning old positions not needed)
• 如果此举是合法的,即自己的国王在位(1位)(If the move was legal, i.e., own king in check (1 bit))
• 对手国王检查(1位)(Opponent king check (1 bit))
• 董事会分数(13位)(The score of the board (13 bits))
• 空闲位未使用. (5位)(Free bits not used. (5 bits))
• 重复绘制,材料不足,过时的配合和配合(4位,各一位)(Draw by Repetition, Insufficient Material, Stale Mate and Mate (4 bits, one bit each)) 将一些游戏数据打包为整数的函数.(Function for packing some game data into an integer.)

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

解压缩游戏数据.(Unpacking the game data.)

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笔记本电脑上每秒分析约5万个位置.在中间比赛中,这足以看到大约五六步.在考虑同一时间的情况下,大多数普通的国际象棋棋手(像我一样)在击败引擎方面应该有一些困难.当在Chess.com CPU游戏中对其进行测试时,我估计它的等级约为1300.我认为提高其性能的最佳方法是用一块木板代替木板表示.这可以增加移动生成和位置评估,因此可以执行更深入的搜索.(The engine analyzes about 50k positions/sec on my dual core 2.7Ghz laptop. Which is mostly enough to see about five or six moves ahead in the middle game. Most average skilled chess players (like me) should have quite some difficulty beating the engine given the same time to think. When testing it in a chess.com CPU game, I estimate it has a rating around 1300. I think the best way to improve its performance would be to replace board representation with a bit board. That could increase move generation and position evaluation so even deeper searches could be performed.)

我在这个项目中学到了什么(What I Have Learned During this Project)

编写单元测试,甚至可能首先编写它们非常重要.在TDD中,必须先测试失败,然后才能编写函数.这是确保所有内容都经过测试的绝佳方法.(It is very important to write unit tests and perhaps even write them first. In TDD, you have to have a failing test before you can write the function. This is an excellent way of assuring everything is tested.)

Alpha Beta算法可能是国际象棋引擎中最具挑战性的部分.互联网上有许多伪代码示例.我只设法让其中之一工作.这是来自(The Alpha Beta algorithm is probably the most challenging part of a chess engine. There are many pseudo code examples on the Internet. I only managed to get one of them to work. It is the one from) 算法维基(Algorithm Wiki) .(.)

哈希是国际象棋编程的重要组成部分.董事会必须保存位置分数,以加快访问速度.哈希存储在64位数据类型中,但象棋游戏可能处于更多状态.我发现在实施Zobrist哈希后,没有哈希冲突非常有效,这非常有效地分散了拥有哈希的风险碰撞.(Hashing is an important part of Chess programming. The board has to save a position score for faster access. The hash is stored in a 64 bit datatype but there are many more possible states that a chess game can be in. I find it quite remarkable that there were no hash collisions after I implemented the Zobrist hashing that very effectively spreads the risk of having hash collisions.)

运行性能分析很重要.分析速度越快,每秒分析的职位就越多,即使是一些小的改进也会对整体性能产生重大影响.(It is important to run performance profiling. The faster the analysis becomes, more positions are analyzed every second and even some small improvements can have large effects on overall performance.)

另一个学习的好网站是(Another good site for learning is the) 国际象棋编程维基(Chess Programming Wiki) .(.)

国际象棋引擎是一个很大的话题,并且在过去的几个世纪中已经进行了很多研究.我不确定您仅通过阅读本文就能编写自己的国际象棋引擎,但希望它是一个很好的介绍,如果您有兴趣成为国际象棋引擎开发人员,它将为您指明正确的方向.(Chess engines are a big topic and a lot of research has been done on the subject during the centuries. I’m not sure you will be able to write your own chess engine just by reading this article, but hopefully it is a good introduction and it will point you in the right directions if you are interested in becoming a chess engine developer.)

历史(History)

• 2017年1月31日-1.0版(Jan 31, 2017 - Version 1.0)

• 2017年2月10日-版本1.1(Feb 10, 2017 - Version 1.1)

  • 编辑板功能(Edit board functionality)
  • 皮条客的UI-感谢(Pimped UI - Thanks to) 丹妮拉`迪莉娜(Daniella Di Lena)(Daniella Di Lena) 免费图片(for the free pictures)

• 2017年2月12日-版本1.1.1(Feb 12, 2017 - Version 1.1.1)(错误和性能修复)((Bugs and performance fixes))

• 2017年2月19日-在文本中添加了代码示例,并重写了一些部分以更好地理解.(Feb 19, 2017 - Added code examples in the text and rewrote some parts for better understanding.)

• 2017年3月5日-撰写有关Zobrist Hash的更多信息.添加了目录.(Mar 5, 2017 - Wrote more about Zobrist Hash. Added a TOC.)

• 2017年5月23日-版本1.2(May 23, 2017 - Version 1.2)

  • 50步法则(50 move rule)
  • 编辑FEN(Edit FEN)
  • 性能稳定(Performance and stability)

如果本文启发您开始研究该主题并成为国际象棋引擎开发人员,请给我发送评论,问题或直接打个招呼. :)(In case this article has inspired you to start digging into this subject and become a chess engine developer, please send me a comment, a question or just say Hello. :))

快乐阅读代码,祝您好运(Happy code reading and good luck on)你的(your)国际象棋编程学习!(chess programming learning!)

许可

本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。