Introduction
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
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.
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.
There is also a small project called BitChess that is under construction.
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
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 donrsquo;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:
Hide Copy Code
[TestMethod]
public void BoardHasSquaresTest()
{
var board = new Board();
Assert.AreEqual(64, board.Squares.Length);
}
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 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 donrsquo;t cover so much in this article. But if you donrsquo;t extend the search with a Quiescence Search, itrsquo;s a high risk that the engine sometimes will make very bad moves.
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.
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.
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.
Hide Copy Code
internal Listlt;movegt; GetPseudoLegalMoves() {
var moves = new Listlt;movegt;();
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 canacute;t be in check after a move so those moves are illegal.
Hide Copy Code
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 m
全文共15013字，剩余内容已隐藏，支付完成后下载完整资料
介绍
这是一个功能齐全但也简单的国际象棋程序，旨在帮助您了解象棋引擎的工作原理。网上已经有很多专注于高性能的国际象棋引擎了。笔者采用了标准的面向对象的基于C#的解决方案，这使它更容易理解，而不是着重于制作一个快速和高评分的国际象棋引擎。同时笔者已经开发了一个棋术精湛的国际象棋AI代码，感兴趣的读者可以了解一下（译注：作者此处指的应当是文章开头的GitHub中的项目）。具体的功能使用C# 6，目前正处于Alpha Beta调试和哈希值计算阶段。
大约十年前，笔者试图实现一个象棋引擎，但失败了。这一次，笔者决定使用测试驱动开发（TDD）的第一种方法。笔者喜欢TDD，并认为TDD是这一次引擎得以成功的主要原因。将国际象棋的规则100％地正确实施是非常重要的。同样重要的是，悔棋之后的结果不变。同时我也认为TDD有助于建立良好的代码结构和可维护的系统设计。
代码
解决方案由两个主要项目组成：引擎（chess.dll）和用户界面。_Chess.dll_拥有关于棋局，棋盘，规则和引擎的一切，同时也包含了所有的测试。在这个实现过程中，完全没有必要在项目中单独使用单元测试。因为通过这样的方法，可以很容易地看出单元测试都各自属于哪个类。
目前共有有82个测试，其中大部分速度非常快，并拥有几乎100%的代码覆盖率。代码行数将近4000，包括测试和用户界面。大部分逻辑所在的引擎和游戏类都少于900行代码。
Chess UI是一个Windows窗体应用程序，它只包含少量的功能，如加载、保存和设置电脑思考的时间。您还可以编辑和设置自定义棋盘位置并保存并加载FEN位置（译注：福斯夫－爱德华兹记号法（Forsyth–Edwards Notation），简称FEN，是苏格兰人David Forsyth发明的国际象棋可完整叙述局面的记谱法，也可用于中国象棋）。
从何开始
如果你是TDD的新手，那么你很有可能会想：“我应该从哪里开始？！”。以及 - “我要如何才能测试一些不存在的东西？”解决方案是编写测试，甚至不需要编译，就会使设计和程序朝着正确的方向发展。我在开始这个项目时写的第一个测试是：
[TestMethod]
public void BoardHasSquaresTest()
{
var board = new Board();
Assert.AreEqual(64, board.Squares.Length);
}
在Visual Studio中，可以使用内置的快捷方式来生成缺少的类型和测试用例需要编译的成员。
在网上有很多优质的免费文献来解释象棋引擎中不同的算法和技术。文末有笔者所参考的一些链接。
特征
迭代Alpha-Beta调试，大大减少了需要分析的位置数量。在深度为零时，还执行深度为2的静态搜索以防止地平线效应所带来的风险。这是一个国际象棋引擎的关键特性所在，本文中不过多赘述（译注：详细信息请参照相关关键字的链接）。如果你没有使用静态搜索扩展搜索方式，引擎很有可能会时不时在棋局上犯一些错误。
Zobrist Hashing为已评估的位置执行快速查找。笔者在数据库中保留了几百万个位置，所以每个位置只需计算一次。
如果处理器有多个内核可用，则使用并发线程来提高引擎的性能。
国际象棋棋盘是由一个单一的方阵64阵列。（比特板速度要快得多，但可能稍微复杂一点。）
得分基于棋子的种类和位置。在开局时上，一些基本的开局走法会有加分，在棋局在最后也将加入特殊的得分计算。
若出现重复走棋和棋子不足的平局时，将使用50步规则以及困毙规则来进行分数的评估。
残局库尚未实施。
国际象棋引擎
以下是笔者的象棋引擎实施方案
棋盘和游戏
显然，引擎需要知道什么是一场象棋棋局。一场棋局有两个玩家，玩家有棋子，每种棋子有其固有的属性。国际象棋的棋局在充满方格的棋盘上进行，每个方格上面可以放置棋子。以下是这些棋子类型的类图。
落子
每种棋子有固定的移动规则。为所有棋子生成一个合法移动的列表，以保留合法的走棋。下面的代码片段来自游戏类。
internal Listlt;movegt; GetPseudoLegalMoves() {
var moves = new Listlt;movegt;();
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;
}
评估
在移动的一代中，而不是在引擎搜索期间，评估移动实际上是更好的。这是因为在移动命令时搜索更有效。如果首先评估更好的移动，则搜索可能会忽略许多移动。更多关于那以后。
评价给出一个分数。如果黑色比较好，那么对于有利于白色的头寸是正面的和负面的。每件都有一个价值。女王是九。车五。主教和骑士三和兵是一个。材料分数是黑色棋子减去白色总和的总和。件的位置也很重要。引擎评估：
控制中锋（白4和黑5中的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次动作中没有获得进球或者棋子移动，游戏也以平局结束。
搜索
现在我们可以从好的方面讲出不好的举动，我们可以寻找好的举措。搜索从深处开始。白方球员做出动作，在每一次白方移动之间黑方球员为每一次白方移动。由于黑人玩家会尽可能获得尽可能高的分数，所以白棋的最佳举动就是移动到最低值的黑色响应棋子列表中。这种最小最大搜索也大大改善了一个算法，称为alpha beta修剪，切断了许多明显的不良行为。
这是一个不错的动画解释Alpha Beta修剪的链接。
下面是作为伪代码的递归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 lt; c; i ) {
var childValue = alphaBeta(node.children[i], bestValue, beta, false);
bestValue = Math.max(bestValue, childValue);
if (beta lt;= bestValue) {
break;
}
}
} else {
bestValue = beta;
// Recurse for all children of node.
for (var i=0, c=node.children.length; ilt;c; i ) {
var childValue = alphaBeta(node.children[i], alpha, bestValue, true);
bestValue = Math.min(bestValue, childValue);
if (bestValue lt;= alpha) {
break;
}
}
}
return bestValue;
}
如果移动是有序的，最好的移动是先执行的，那么中断机制就更有效率。再次重复相同的搜索，深度增加1，直到设定的时间结束。在每次迭代之后，这些移动被排序，所以首先评估好的移动。这看起来可能效率很低，但实际上，从一开始就找到最好的方法来迭代地增加深度，而不是从一个确定的深度开始。
如果你设法把事情做好，现在就会发生一些非常酷的事情。你的程序突然开始显示一些情报。但是你还没有完成。您可能想要使搜索更有效率，更深入地搜索并提高性能。计算机大部分时间可能需要的是分数评估，并且可以使用Zobrist Hash Key存储在内存中以进行快速查找。
性能
为了进一步提高性能，目标是为棋盘的任何设置创建一个尽可能独特的密钥。然后可以使用该键来存储信息并在评估相同位置时快速加载它。
问题是国际象棋棋盘可能处于巨大的不同状态。64个方格中的每一个都可以有十二种不同的类型之一。什么也定义了独特的状态是哪个球员轮流打出什么角色以及每个球员拥有什么样的权利（女王方面或王方面）。据说国际象棋表状态可以组合的数量大于宇宙中估计的电子数量！
Zobrist Hashing通过创建一个只有八个字节的密钥来显着地解决这个问题。在游戏开始时，生成768个（64平方乘以12个类型）不同的数字。当一个玩家移动一个棋子时，前一个游戏的哈希值被改变了一些排他或操作（XOR）使用状态改变随机数。在大多数情况下，只有两个操作。
更新散列键时，您还应该考虑升级，捕获和Castling，但这两行是Zobrist Hash Key实现中最重要的。
隐藏 复制代码
game.Hash ^= ZobristArray[piece, fromSquareIndex]; //piece off
game.Hash ^= ZobristArray[piece, toSquareIndex]; //piece on new square
如果你应用相同的排他操作两次，你实际上回到相同的哈希键。这在撤消移动时非常有用。
所述佐布里斯特散列密钥与包含关于该位置的小数据的整数存储在存储器中的数据库在一起。这些数据只需要计算一次。下一次显示相同的散列键时，将使用键查询数据库。
这是以32位整
全文共7070字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11219]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
