C#中的国际象棋程序(译文)
By robot-v1.0
本文链接 https://www.kyfws.com/games/chess-program-in-c-zh/
版权声明 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
- 15 分钟阅读 - 7354 个词 阅读量 0C#中的国际象棋程序(译文)
原文地址:https://www.codeproject.com/Articles/36112/Chess-Program-in-C
原文作者:Jacques Fournier
译文由本站 robot-v1.0 翻译
前言
SrcChess is a chess program built in C#
SrcChess是用C#内置的国际象棋程序
介绍(Introduction)
SrcChess
是用C#构建的国际象棋程序.尽管它与商业象棋程序不符,(is a chess program built in C#. Although it is not on par with commercial chess programs,) SrcChess
毫无问题地击败我,因此对于休闲玩家而言,它可能是一个严重的对手.该程序支持合理数量的功能.它最大的弱点可能是缺乏良好的棋盘评估功能和最终游戏数据库.它的优势之一是在可用时利用多个处理器.该程序还包括一个PGN筛选器,使您可以导入PGN格式的游戏并构建自己的开幕书.(is beating me without any problem and therefore can be a serious opponent for casual players. The program supports a reasonable number of functions. Its biggest weaknesses are probably the lack of a good board evaluation function and of an end game database. One of its strengths is that it takes advantage of multiple processors when available. The program also includes a PGN filter that lets you import games in PGN format and build your own openings book.)
我决定提供我的程序,以便程序员可以了解国际象棋程序的工作方式.我也希望有人能改善它.(I decided to make my program available so programmers can understand how a chess program works. I also hope some people will improve it.)
特征(Features)
该国际象棋程序具有以下特点:(This chess program features:)
- 视觉界面(Visual interface)
- 多种难度等级(Multiple difficulty levels)
- 开本数据库(Database of book openings)
- 载入/保存游戏(Loading / saving of game)
- 撤消/重做功能(Undo / redo functions)
- 反转板(Reversing the board)
- 玩家对电脑(Player against computer)
- 电脑对电脑(Computer against computer)
- 玩家对玩家(Player against player)
- 创建自己的棋盘(手动或通过PGN)(Creating your own chess board (manually or from PGN))
- 给玩家的提示(Hints for the player)
- 等等.(Etc.)
版本控制(Versioning)
|3.0版(Version 3.0)|增加难度等级(Added difficulty levels) 初学者:使用较弱的评估板(所有部件都具有相同的价值)(Beginner: Use a weak evaluation board (all pieces have the same value)) 2层搜索(2-Ply search) 没有开本(No opening book) 简易:使用基本评估板(Easy: Use basic evaluation board) 2层搜索(2-Ply search) 没有开本(No opening book) 中级:使用基本评估板(Intermediate: Use basic evaluation board) 4层搜索(4-Ply search) 未分级的开幕书(Unrated opening book) 高级:使用基本评估板(Advance: Use basic evaluation board) 4层搜索(4-Ply search) 大师开书(Master opening book) 更多进步:使用基本评估板(More Advance: Use basic evaluation board) 6层搜索(6-Ply search) 大师开书(Master opening book) 手册:定义您自己的设置(Manual: Define your own settings) 简化了用户界面(Simplified the user interface) 向FICS(免费Internet Chess服务器)添加了接口.您现在可以观察到(Added interface to the FICS (Free Internet Chess Server). You can now observe) 实时以下游戏:(the following games in real time:) 闪电/闪电战/无定时和标准时间(Lightning / Blitz / Untimed and Standard time) 在许多对话框和主界面中添加了工具提示(Added tooltips in many dialog boxes and in the main interface) 在N次Move游戏中增加了100多名队友.(Added more than 100 mates in N move games.) 添加了在离开游戏前保存棋盘的警告.(Added a warning for saving a board before leaving a game.) 将棋盘移近中心(Moved the chessboard closer to the center) 重写了PGN解析器,以处理更大的PGN文件并更加兼容(Rewrote the PGN parser to handle bigger PGN files and to be more compliant) 符合PGN规范.(with PGN specifications.) 新的解析器带有改进的高级书籍和新的中级书籍.新书是从277万个TWIC游戏中创建的.感谢Chess.com提供的SCID文件.高级书籍包括ELO评分为2500或更高的玩家的游戏.(The new parser comes with an improved advanced book and a new intermediate one. The new books have been created from a 2.77 millions TWIC games. Thank you to chess.com for the SCID file. The advanced book includes games from players with ELO rating of 2500 or more.) 简化的状态栏(Simplified status bar) 查找最佳动作或等待来自FICS服务器的动作时,添加了进度条.(Added a progress bar when finding a best move or waiting for a move from FICS server.) 做了重大的代码清理(Did a major code clean-up) 游戏现在正在保存其最后的位置和大小.(The game is now saving its last position and size.) 即将推出:让用户通过FICS服务器玩游戏.(To come: Let users play game via FICS server.)
版本2.05(Version 2.05) | 错误更正. Readme.txt中的更多信息(Bugs corrections. More information in Readme.txt) | |
添加刷新选项.(Add the Refresh option.) | ||
版本2.04(Version 2.04) | 错误更正. Readme.txt中的更多信息(Bugs corrections. More information in Readme.txt) | |
新菜单可创建游戏快照,以帮助修复错误.(New menu to create a snapshot of a game to help fixing bugs.) | ||
版本2.03(Version 2.03) | 添加一个按钮以在不移动的情况下加载PGN游戏(Add a button to load a PGN games without the moves) | |
版本2.02(Version 2.02) | 错误更正:读取/解析PGN文件时出现无限循环(Bugs correction: Endless loop when reading/parsing PGN files) | |
版本2.01(Version 2.01) | 错误修正. Readme.txt中的更多信息(Bugs correction. More information in Readme.txt) | |
版本2.00(Version 2.00) | 移至WPF(Move to WPF) | |
新的用户界面.(New user interface.) | ||
添加零件集列表以供选择(Add list of piece sets to choose from) | ||
感谢Ilya Margolin提供的XAML套件(Thank you to Ilya Margolin for the XAML piece sets) | ||
版本1.10(Version 1.10) | 移至.NET Framework V4(Move to .NET Framework V4) | |
Use <font face="Courier New">System.Threading.Tasks </font> 简化多线程实现(to simplify the multi-threading implementation) |
||
改进了搜索引擎和董事会评估界面(Improves the search engine and the board evaluation interface) | ||
调整大小时更正异常(Correct exception when resizing the) <font face="Courier New">ChessControl</font> |
||
有关更详尽的列表,请查看(For a more exhaustive list, look at the)readme.txtfile. | ||
1.00版(Version 1.00) | 改善使用者介面(Improves the user interface) | |
改善搜索引擎和董事会评估(Improves the search engine and the board evaluation) | ||
添加新的深度优先迭代图层搜索方法(Add a new iterative depth-first fix ply search method) | ||
正确的深度优先,以便正确执行(Correct depth-first so it perform correctly) | ||
添加计时器(Add timer) | ||
现在可以将游戏保存为PGN格式(Games can now be saved in PGN format) | ||
保存的格式与以前的版本不兼容(Saved format is NOT compatible with previous version) | ||
有关更详尽的列表,请查看(For a more exhaustive list, look at the)readme.txtfile. | ||
版本0.943.000(Version 0.943.000) | 增加对三重重复规则的支持(Add support for the threefold repetition rule) | |
添加对五十步法则的支持(Add support for the fifty-move rule) | ||
添加新界面,以帮助向游戏添加新的棋盘评估方法.有关更多信息,请阅读(Add a new interface to help adding new board evaluation methods to the game. For more information, reads the)BoardEvaluator.txtfile. | ||
添加测试模式以比较电路板评估方法的性能和效率(工具->测试评估方法…).(Add a test mode to compare the performance and the efficiency of board evaluation method (Tool -> Test Evaluation Method…).) | ||
清理一下代码…(Clean-up the code a little…) | ||
版本0.942.000(Version 0.942.000) | 层数已更正,因此代表一位球员的移动.(Ply count has been corrected so it represents a move by one player.) | |
添加一个选项来配置移动混洗(向游戏添加一些随机性).现在可以禁用它以使调试更容易.(Adds an option to configure move shuffling (to add some random to game). It’s now possible to disable it to make debug easier.) | ||
添加有关搜索的时间信息.(Add timing information about search.) | ||
版本0.941.000(Version 0.941.000) | 迭代加深深度优先搜索现在正在工作.现在,您可以选择固定的时间来找到最佳的移动方式,而不必选择多个层.(Iterative deepening depth-first search is now working. You can now choose a fixed amount of time for finding a best move instead of a number of ply.) | |
开幕书会选择更多常用的开头.(The opening book will choose more often usual openings.) | ||
版本0.940.000(Version 0.940.000) | 添加选项以启用/禁用开书(Add an option to enable/disable book opening) | |
添加一个选项以选择多线程模式(Add an option to select the multi-threading mode) | ||
添加一个选项来设置转置表的大小(Add an option to set the size of the transposition table) | ||
搜索设置现已保留(Search setting is now persisted) | ||
更正换位表算法(Correct the transposition table algorithm) | ||
减少董事会评估中的重要分数(Decrease the points given for castling in the board evaluation) | ||
迭代加深深度优先搜索已接近功能…但还没有.(Iterative deepening depth-first search is close to be functional… but not yet.) | ||
版本0.930.002(Version 0.930.002) | 纠正游戏结束时发生的异常.(Corrects exception occurring at the end of a game.) | |
启用/禁用转置表的新选项. (此选项默认情况下处于关闭状态以更正错误.下一版本将默认启用它).(New option to enable/disable the transposition table. (The option is off by default to correct a bug. Next version will enable it by default).) | ||
版本0.930.001(Version 0.930.001) | ||
原始发布版本.(Original posted version.) | ||
董事会背后(Behind the Board)
该程序是使用Visual Studio 2010在C#中开发的.它使用alpha-beta修剪搜索算法(以及用于调试的minimax)搜索下一个最佳方法.为了减少要评估的移动次数,搜索算法使用通过Zobrist哈希实现的换位表.(The program is developed in C# using Visual Studio 2010. It uses the alpha-beta pruning search algorithm (and minimax for debugging) to search for the next best move. To decrease the number of moves to evaluate, the search algorithm uses a transposition table implemented with Zobrist hashing.) 为了进一步提高搜索性能,该程序在计算机上找到的每个处理器使用一个线程,并将搜索划分为多个线程(最终用于我的计算机上的多个处理器…).搜索线程的优先级较低,以免干扰太多计算机响应.(To further improve the performance of the search, the program uses one thread per processor found on the computer and splits the search among them (finally a use for the multiple processors on my computer…). The search threads are low priority so as not to disturb too much the computer response.) 该程序使用书籍开场数据库.游戏随附的游戏是根据PGN文件构建的.该程序还提供了PGN解析器,因此您可以使用"工具"菜单上的选项来建立自己的空缺数据库.解析器还允许您重播从Web下载的PGN格式的国际象棋游戏.(The program uses a database of book openings. The one provided with the game was built from PGN files. The program also provides a PGN parser so you can build your own openings database using an option on the Tool menu. The parser also allows you to replay chess games downloaded from the Web in PGN format.)
建立开场书(Building an Openings Book)
该程序提供了一个书开数据库.您可以从任何PGN文件(可在Web上轻松找到)中创建自己的开幕书.(A database of book openings is provided with the program. You can build your own openings book from any PGN file (easily found on the Web).) 该程序包括一个解析器,该解析器使您可以根据播放器或排名等参数来导入和过滤PGN文件的内容. PGN文件的此过滤后的版本也可以保存并用于创建开幕书.(The program includes a parser that allows you to import and filter the content of a PGN file according to parameters such as players or rankings. This filtered version of the PGN file can also be saved and used to create an openings book.) 开幕书必须位于包含可执行文件的目录中,并命名为(The openings book must be located in the directory containing the executable and named)book.bin(book.bin).(.)
需要改进什么?(What Needs to be Improved?)
评估板功能极简.此功能的改进将大大提高程序的播放水平.类似地,程序的最终游戏阶段可以受益于最终游戏数据库的包含.(The board evaluation function is minimalist. Improvements on this function will greatly enhance the level of playing of the program. Similarly, the end game stage of the program could benefit from the inclusion of an end game database.) 不同的开口之间没有等级;因此,随机选择一个开口.(There is no rating among the different openings; an opening is thus chosen randomly.) 还可以在用户界面上进行改进.欢迎向游戏中添加帮助文件.(Improvements can also be made on the user interface. Adding a help file to the game would be welcome.)
来源描述(Source Description)
国际象棋程序本身不是很复杂.但是像许多软件一样,细节在于魔鬼.这个国际象棋程序包含大约10,000行代码(包括备注).用户界面与其他类别分开,因此可以轻松进行更改.(A chess program is not very complex in itself. But like a lot of software, the devil is in the details. This chess program contains around 10,000 lines of codes (including remarks). The user interface is separated from the other classes so it can easily be changed.)
的(The) ChessBoard
类是最重要的,因为它包含板子抽象.它还包含建立合法举动列表并搜索最佳举动的逻辑.添加了一些额外的复杂性以支持多线程.但是,该类相对较小(少于2000行).为了提高搜索速度,每个{piece,piece position}的合法动作列表在(class is the most important since it contains the board abstraction. It also contains the logic to build the list of legal moves and to search for the best move. A little extra complexity was added to support multi-threading. However, the class is relatively small (less than 2000 lines). To improve the speed of the search, a list of legal moves for each {piece, piece position} is created once in the) static
类的构造函数.(constructor of the class.)
-
ChessBoard
:类的构造函数(: Class constructor) -
CopyFrom
:将板复制到另一个板上(: Copy a board into another one) -
Clone
:创建板的副本(: Create a clone of the board) -
ReadBook
:从文件中阅读开幕书(: Read an openings book from a file) -
SaveBoard
:将开发板保存到流中(: Save the board to a stream) -
LoadBoard
:将开发板加载到流中(: Load the board to a stream) -
ResetBoard
:将板复位到初始位置(: Reset the board to initial position) -
this[int iPos]
:默认索引器,获取或放置在板上(: Default indexer, get or set a piece on the board) -
GetEatedPieceCount
:返回为给定颜色捕获的件数(: Return the number of pieces which have been captured for a given color) -
DoMove
:执行指定的动作(: Do the specified move) -
UndoMove
:撤消指定的动作(: Undo the specified move) -
WhitePieceCount
:白板上的白块数量(: Number of white pieces on the board) -
BlackPieceCount
:板上的黑色块数(: Number of black pieces on the board) -
IsCheck
:确定给定的颜色王是否被直接攻击(: Determine if a given color king is being directly attacked) -
EnumMoveList
:列举给定颜色的所有可能动作(: Enumerate all the possible moves for a given color) -
FindBestMove
:使用alpha-beta或minimax查找给定颜色的最佳移动(: Find the best move for a given color using alpha-beta or minimax) -
FindBookMove
:在职位空缺书中找到一个动作(: Find a move in the openings book) -
GetHumanPos
:从移动结构返回人类可读的移动(: Return a human readable move from a move structure) -
CancelPlay
:取消后台搜索(: Cancel the background search) 搜索的核心逻辑在于alpha-beta修剪功能.此功能可以在两种模式下使用:(The core logic of the search lies in the alpha-beta pruning function. This function can be used in two modes:) -
特定层数(Specific number of ply)
-
迭代加深深度优先搜索(Iterative deepening depth-first search) 第一种方法在指定的层数中搜索最佳移动.(The first method searches for the best move in a specified number of ply.) 第二种尝试使用迭代的深度优先搜索来找到特定时间段内的最佳移动,从而增加每次搜索的层数,直到时间耗尽为止.乍一看,此方法的效率似乎较低,因为它会重复执行相同的搜索.但实际上,该方法对每次搜索之间的移动进行重新排序,以优化alpha-beta截止值.这种方法的另一个主要优点是可以根据游戏的阶段来调整层数.特别是,最终游戏在棋盘上的棋子更少,因此增加层数不会像在游戏中途那样产生相同的影响.(The second one tries to find the best move in a specific amount of time using an iterative depth-first search, increasing the number of ply for each search up to the moment when time is exhausted. At first glance, this method may seem less efficient since it performs the same search repeatedly. But in practice, the method reorders the moves between each search to optimize the alpha-beta cut-off. Another big advantage of this method is that the number of ply can be adjusted depending on the stage of the game. In particular, the end game holds fewer pieces on the board, so increasing the number of ply doesn’t have the same impact as doing so in the middle of the game.) 以下列出了源文件和说明.行数显示在文件名后的方括号中.该代码共有9836行.(The following lists the source files and description. The number of lines appears in brackets after the name of the file. The code has a total of 9836 lines.)
-
Assembly.cs(Assembly.cs)(34)((34)) .NET应用程序的程序集文件.(Assembly file for .NET application.)
-
Book.cs(Book.cs)(359)((359)) 实现开书.(Implements the book openings.)
-
国际象棋棋盘(ChessBoard.cs)(1990)((1990)) 不管用户界面如何,都实现棋盘.这就是程序的核心逻辑所在(搜索,合法举动等).搜索功能是使用minimax和alpha-beta算法实现的,并在可能的情况下使用多线程.(Implements the chess board regardless of the user interface. This is where the core logic of the program lies (search, legal moves, etc.). The search function is implemented using minimax and alpha-beta algorithms, using multi-threading when possible.)
-
ChessControl.cs(ChessControl.cs)(1510)((1510)) 棋盘的用户界面.实施为(User interface for the chess board. Implemented as a)
UserControl
.(.) -
ChessControl.Designer.cs(ChessControl.Designer.cs)(86)((86)) Visual Studio为该控件生成了代码.(Visual Studio generated code for the control.)
-
frmAbout.cs(frmAbout.cs)(16)((16)) 关于对话框.(About dialog box.)
-
frmAbout.Designer.cs(frmAbout.Designer.cs)(110)((110)) Visual Studio为该表单生成了代码.(Visual Studio generated code for the form.)
-
frmChessBoard.cs(frmChessBoard.cs)(1236)((1236)) 包含所有其他控件的主窗体((Main form containing all the other controls ()
ChessControl
,(,)MoveViewer
等).(, etc.).) -
frmChessBoard.Designer.cs(frmChessBoard.Designer.cs)(499)((499)) Visual Studio为表单生成了代码.(Visual Studio generated code for form.)
-
frmCreatePGNGame.cs(frmCreatePGNGame.cs)(114)((114)) 用于将PGN文件转换为书籍开口数据库的界面.(Interface to convert a PGN file into a book openings database.)
-
frmCreatePGNGame.Designer.cs(frmCreatePGNGame.Designer.cs)(97)((97)) Visual Studio为该表单生成了代码.(Visual Studio generated code for the form.)
-
frmGameParameter.cs(frmGameParameter.cs)(165)((165)) 游戏参数.(Parameters of the game.)
-
frmGameParameter.Designer.cs(frmGameParameter.Designer.cs)(218)((218)) Visual Studio为该表单生成了代码.(Visual Studio generated code for the form.)
-
frmPGNFilter.cs(frmPGNFilter.cs)(340)((340)) 用于过滤PGN文件的参数.(Parameters for filtering a PGN file.)
-
frmPGNFilter.Designer.cs(frmPGNFilter.Designer.cs)(309)((309)) Visual Studio为该表单生成了代码.(Visual Studio generated code for the form.)
-
frmPGNGamePicker.cs(frmPGNGamePicker.cs)(209)((209)) 从PGN游戏中选择.(Choosing from PGN game.)
-
frmPGNGamePicker.Designer.cs(frmPGNGamePicker.Designer.cs)(103)((103)) Visual Studio为该表单生成了代码.(Visual Studio generated code for the form.)
-
LostPiecesControl.cs(LostPiecesControl.cs)(299)((299)) 用于显示捕获的片段的控件.(Control used to show the captured pieces.)
-
LostPiecesControl.Designer.cs(LostPiecesControl.Designer.cs)(63)((63)) Visual Studio为该控件生成了代码.(Visual Studio generated code for the control.)
-
MoveViewer.cs(MoveViewer.cs)(192)((192)) 用于显示移动的控件.(Control used to show the moves.)
-
MoveViewer.Designer.cs(MoveViewer.Designer.cs)(87)((87)) Visual Studio为该控件生成了代码.(Visual Studio generated code for the control.)
-
PGNParser.cs(PGNParser.cs)(765)((765)) 用于PGN表示法的解析器.(Parser for PGN notation.)
-
PgnUtil.cs(PgnUtil.cs)(816)((816)) PGN文件的实用程序类.(Utility class for PGN files.)
-
Program.cs(Program.cs)(21)((21)) 主程序.(Main program.)
-
TransTable.cs(TransTable.cs)(232)((232)) 换位表的实现.(Transposition table implementation.)
简短词汇(Short Glossary)
所有术语都可以在网上轻松找到(维基百科是一个很好的来源).(All terms can be easily found on the Web (Wikipedia is a good source).)
层板(Ply)
一层由半个动作组成(仅一侧移动).四层搜索意味着可以提前搜索2个动作.(A ply consists of a half move (a move of one side only). A 4-ply search means to search 2 moves in advance.)
PGN(PGN)
便携式游戏符号(PGN)是一种用于记录国际象棋游戏的符号. PGN由于易于用户阅读和计算机处理而被广泛使用.许多国际象棋游戏和事件均以PGN格式发布.解析器允许国际象棋程序读取这些文件.(Portable Game Notation, or PGN, is a notation used to record chess games. PGN is widely used as it is easy to read by users and to process by computers. Many chess games and events are published in the PGN format. The parser allows the chess program to read these files.)
极小值(Minimax)
Minimax是一种递归算法,用于选择游戏中的下一个动作.建立并发挥法律行动的作用.每个移动都使用评估功能进行评估.计算机进行移动,使对手的后续移动可能导致的位置最小值最大化.(Minimax is a recursive algorithm use for choosing the next move in a game. A tree of legal moves is built and played. Each move is evaluated using an evaluation function. The computer makes the move that maximizes the minimum value of the position resulting from the opponent’s possible following moves.)
Alpha-beta修剪(Alpha-beta Pruning)
alpha-beta修剪功能是对minimax搜索方法的改进.当至少一种可能性被证明比以前评估的可能性差时,它通过消除移动来减少要评估的节点数.(The alpha-beta pruning function is an improvement of the minimax search method. It reduces the number of nodes to evaluate by eliminating a move when at least one possibility was proved worse than a previously evaluated one.)
换位表(Transposition Table)
换位表是一个哈希表,记录以前的移动的评估,因此不必重新评估它们.换位表用于加快游戏树的搜索.它们使用Zobrist哈希实现.(A transposition table is a hashing table that records the previous moves' evaluations so they will not have to be re-evaluated. Transposition tables are used to speed up the search of the game tree. They are implemented using Zobrist hashing .)
Zobrist Keys,Zobrist Hashing(Zobrist Keys, Zobrist Hashing)
要实现换位表,重要的是确定两个板的配置和潜在移动是否相等.为此,我们可以只比较两个板的各个部分,但是我们还必须考虑到卡式推举和被动移动,因为它们限制了可能的移动.唯一的问题是,这种方法在考虑必须使用数百万次才能评估每次移动时相当长. Zobrist哈希通过为每个电路板位置分配一个64位签名来简化此过程.我们只比较两个64位值,而不是一一检查每个电路板是否已经评估过.(To implement a transposition table, it is important to determine if two boards are equivalent in configuration and in potential moves. To do so, we can just compare the pieces of the two boards, but we must also take into account castling and en-passant moves, as they constrain possible moves. The only problem is that this method is a quite long when considering it has to be used millions of times to evaluate each move. Zobrist hashing simplifies this process by assigning each board position a 64-bit signature; instead of checking each piece one by one to see if the board has already been evaluated, we just compare the two 64-bit values.)
许可
本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。
C# .NET4.5 .NET WPF VS2010 VS2013 Visual-Studio Dev Architect 新闻 翻译