C# 国际象棋程序






4.95/5 (373投票s)
SrcChess 是一个用 C# 构建的国际象棋程序
引言
SrcChess
是一款用 C# 构建的国际象棋程序。虽然它无法与商业国际象棋程序相媲美,但 SrcChess
能够轻松击败我,因此对于休闲玩家来说,它是一个不错的对手。该程序支持相当多的功能。它最大的弱点可能是缺乏一个好的棋盘评估函数和一个残局数据库。它的优点之一是利用了多处理器(如果可用)。该程序还包含一个 PGN 过滤器,允许您导入 PGN 格式的游戏并构建自己的开局库。
我决定公开我的程序,以便程序员能够理解国际象棋程序的工作原理。我也希望有人能够改进它。
特点
这款国际象棋程序具有以下特点:
- 可视化界面
- 多难度级别
- 开局库数据库
- 加载/保存对局
- 撤销/重做功能
- 翻转棋盘
- 玩家对电脑
- 电脑对电脑
- 玩家对玩家
- 创建您自己的棋盘(手动或从 PGN)
- 给玩家提示
- 等等。
版本控制
版本 3.24 |
| |
版本 3.23 |
| |
版本 3.22 |
| |
版本 3.21 |
| |
版本 3.20
|
| |
版本 3.03 | 纠正了使用置换表时的多线程问题。
| |
版本 3.02 |
| |
版本 3.01 |
| |
版本 3.0 | 添加了难度级别:
| |
版本 2.05 |
| |
版本 2.04 |
| |
版本 2.03 |
| |
版本 2.02 |
| |
版本 2.01 |
| |
版本 2.00 |
| |
版本 1.10 |
| |
版本 1.00 |
| |
版本 0.943.000 |
| |
版本 0.942.000 |
| |
版本 0.941.000 |
| |
版本 0.940.000 |
| |
版本 0.930.002 |
| |
版本 0.930.001 |
|
幕后
该程序使用 Visual Studio 2010 以 C# 开发。它使用 alpha-beta 剪枝搜索算法(以及用于调试的 minimax)来搜索下一个最佳着法。为了减少需要评估的着法数量,搜索算法使用了一个用 Zobrist hashing 实现的置换表。
为了进一步提高搜索性能,该程序为找到的每个处理器使用一个线程,并将搜索分配给它们(终于可以利用我电脑上的多处理器了...)。搜索线程的优先级较低,以免过多干扰计算机的响应。
该程序使用开局库数据库。游戏中提供的数据库是从 PGN 文件构建的。该程序还提供了一个 PGN 解析器,因此您可以使用“工具”菜单上的选项来构建自己的开局数据库。该解析器还允许您重放从网上下载的 PGN 格式的国际象棋对局。
构建开局库
程序提供了一个开局库数据库。您可以从任何 PGN 文件(网上很容易找到)构建自己的开局库。
该程序包含一个解析器,允许您根据玩家或排名等参数导入和过滤 PGN 文件内容。此过滤后的 PGN 文件版本也可以保存并用于创建开局库。
开局库必须位于包含可执行文件的目录中,并命名为 book.bin。
需要改进的地方?
棋盘评估函数非常基础。改进此函数将极大地提升程序的对弈水平。同样,通过包含一个残局数据库,程序的残局阶段也能得到改进。
不同的开局之间没有评分;因此,开局的选择是随机的。
用户界面也可以进行改进。为游戏添加帮助文件也将很受欢迎。
源代码描述
一个国际象棋程序本身并不复杂。但与许多软件一样,细节决定成败。这个国际象棋程序包含大约 10,000 行代码(包括注释)。用户界面与其他类分离,因此可以轻松更改。
ChessBoard
类最为重要,因为它包含了棋盘抽象。它还包含了构建合法着法列表和搜索最佳着法的逻辑。为了支持多线程,增加了一些额外的复杂性。但是,该类相对较小(不到 2000 行)。为了提高搜索速度,在类的 static
构造函数中创建了一个每个 {棋子, 棋子位置} 的合法着法列表。
ChessBoard
: 类构造函数CopyFrom
: 将一个棋盘复制到另一个棋盘Clone
: 创建棋盘的克隆ReadBook
: 从文件中读取开局库SaveBoard
: 将棋盘保存到流LoadBoard
: 将棋盘加载到流ResetBoard
: 将棋盘重置到初始位置this[int iPos]
: 默认索引器,获取或设置棋盘上的棋子GetEatedPieceCount
: 返回给定颜色棋子被吃掉的数量DoMove
: 执行指定的着法UndoMove
: 撤销指定的着法WhitePieceCount
: 棋盘上的白棋数量BlackPieceCount
: 棋盘上的黑棋数量IsCheck
: 判断给定颜色的王是否受到直接攻击EnumMoveList
: 枚举给定颜色所有可能的着法FindBestMove
: 使用 alpha-beta 或 minimax 查找给定颜色的最佳着法FindBookMove
: 在开局库中查找着法GetHumanPos
: 从着法结构返回人类可读的着法CancelPlay
: 取消后台搜索
搜索的核心逻辑在于 alpha-beta 剪枝函数。此函数可用于两种模式:
- 特定步数
- 迭代深度优先搜索
第一种方法搜索指定步数内的最佳着法。
第二种方法尝试在特定时间内找到最佳着法,使用迭代深度优先搜索,每次搜索增加步数,直到时间耗尽。乍一看,这种方法效率似乎较低,因为它会重复执行相同的搜索。但实际上,该方法会在每次搜索之间重新排序着法,以优化 alpha-beta 剪枝。这种方法的另一个巨大优势是步数可以根据游戏的阶段进行调整。特别是,残局中棋盘上的棋子较少,因此增加步数的影响与在中局时不同。
以下列出了不同文件夹的内容。有关更多信息,请参阅根文件夹中的 readme.txt 文件。
- 根文件夹:游戏用户界面
- Core: 包含棋盘、着法、着法历史和棋盘评估的实现。
- FicsInterface: 连接 FICS(Free Internet Chess Server)的接口。
- GenericSearchEngine: 包含使用 MinMax 或 AlphaBeta 算法的通用搜索引擎。
- Properties: 定义不同的设置。
- PgnParsing: 解析以标准对局记谱法(PGN)表示的国际象棋对局。
- PieceSets: 不同的棋子集。
- Resources: 二进制资源。
简短词汇表
所有术语都可以在网上轻松找到(维基百科是一个很好的来源)。
Ply
Ply 指的是半步(只有一方的一个着法)。4-Ply 搜索意味着提前搜索 2 步。
PGN
Portable Game Notation,简称 PGN,是一种用于记录国际象棋对局的记谱法。PGN 被广泛使用,因为它易于人类阅读和计算机处理。许多国际象棋对局和赛事都以 PGN 格式发布。解析器允许国际象棋程序读取这些文件。
Minimax
Minimax 是一种递归算法,用于在游戏中选择下一个着法。构建并玩出一个合法着法的树。每个着法都使用评估函数进行评估。计算机选择能最大化对手可能后续着法所产生位置的最小值的着法。
Alpha-Beta 剪枝
Alpha-beta 剪枝函数是 minimax 搜索方法的改进。它通过排除一个着法来减少需要评估的节点数量,当至少有一种可能性被证明比之前评估过的要差时。
置换表
置换表是一个哈希表,它记录了先前着法的评估,这样它们就不需要被重新评估。置换表用于加速游戏树的搜索。它们使用 Zobrist hashing 实现。
Zobrist 密钥,Zobrist Hashing
为了实现置换表,重要的是确定两个棋盘在配置和潜在着法上是否等效。为了做到这一点,我们可以简单地比较两个棋盘的棋子,但我们还必须考虑易位和吃过路兵的着法,因为它们会限制可能的着法。唯一的问题是,在考虑它需要数百万次来评估每个着法时,这种方法相当耗时。Zobrist hashing 通过为每个棋盘位置分配一个 64 位签名来简化此过程;无需逐一检查每个棋子来查看棋盘是否已被评估过,只需比较两个 64 位值即可。
历史
- 2024 年 1 月 2 日:初始版本