c# - 如何用 C# 编写类似象棋的游戏？

Question

我有个问题。我想编写一个类似象棋的程序，应用如下规则：

• 它的一侧应该只有国王和王后，另一侧应该只有国王。
• 第一方应以尽可能少的移动次数与第二方配对。

我想知道你对如何制作这个项目的想法。例如，我想知道哪种编写代码的方式更容易（面向对象或结构化，...）（我有一些关于面向对象的信息）并且可以告诉我编写它的算法吗？例如，我应该从哪里开始编写代码？

Answer 1

看看这个 SO 问题（编程国际象棋 AI）。

从这个问题的答案来看，我认为这个C# Chess Game Starter Kit将是一个好的开始，但我也会查看其他引用的文章以获取一些有趣的历史/信息。

Answer 2

这里的好消息是您的问题范围非常有限，因为您只有三个要解决的问题。您在这里并没有真正实现游戏，而是解决逻辑难题。我会这样处理它：

1. 弄清楚如何以简单的方式表示这三个部分。您在这里真的不需要 UI（除了用于测试），因为您只是想解决一个难题。最简单的方法可能是三个部分中的每一个的简单行、列位置。

2. 如果您以前没有编写过面向对象的程序，您可能希望坚持使用过程模型并简单地为您需要表示的数据定义变量。问题范围很小，所以你可以摆脱这个。如果您有一些 OOP 经验，则可以适当地拆分问题，尽管您可能不需要任何继承关系。

3. 编写代码以生成可能的移动并确定给定的移动是否有意义。合法的King 移动是任何不检查King 的移动。大多数皇后动作应该是允许的，但您可能还想排除那些会让敌方国王夺取皇后的动作。

4. 现在你需要确定一个策略，如何组合一系列动作来解决这个难题。如果您需要找到真正的最佳解决方案（不仅仅是一个好的解决方案），您可能需要进行蛮力搜索。对于这个问题，这可能是可行的。您可能希望执行深度优先搜索（如果您不知道这意味着什么，这是您要研究的第一个主题），因为一旦找到可能的解决方案，它就会限制所有其他解决方案必须达到的深度经过考虑的。

5. 如果您可以使蛮力发挥作用并且需要使事情变得更快，请考虑是否有可以证明没有好处的动作。如果是这样，您可以立即从搜索中排除这些移动，从而节省您需要考虑的分支数量。您还可以努力优化您的评估功能，因为当您进行数十亿次评估时，更快的评估是非常有益的。最后，您可能会想出一些启发式方法来评估首先尝试哪个分支。收敛到“好”解决方案的速度越快，找到最佳解决方案所需考虑的案例就越少。

---

我意识到的一个旁注是，如果您假设敌人的国王试图避免将死，那么问题就大不相同了。简单的深度优先修剪只有在你被允许以最好的方式移动敌方国王时才有效。如果敌方国王试图避免将死，这会使问题复杂化，因为您有相互冲突的优化目标（您希望它发生在尽可能少的移动中，但您的敌方国王希望尽可能推迟。）您可能会仅限于描述一系列可能性（例如，如果 King 完全合作，3 步是最好的情况，如果 King 完全回避，8 步是最好的最坏情况。）

Answer 3

这是残局数据库的最简单示例。少于 64^3 = 262144 个位置，因此您可以轻松存储每个位置的分数。在这种情况下，我们可以将得分定义为将死的移动次数，以获得获胜位置；或 255 用于绘制位置。这是一个大纲：

1. 将所有分数设置为 255。
2. 查找所有将死位置，并将其评分为 0。
3. 设置深度 = 1。
4. 对于每个绘制的位置（分数=255），查看是否存在进入获胜位置的移动（更准确地说，查看是否存在移动到所有对手的移动都失败的位置。）如果是，将其分数设置为深度.
5. 如果在第 4 步中没有找到新位置，那么您就完成了。
6. 增加深度，然后转到步骤 4。

现在您有一个可以保存到磁盘的 250k 表（并不是说从头开始生成它需要很多秒）。如果空间很重要，您可以通过各种技巧显着减少空间。维基百科有一篇关于这一切的好文章——搜索“Endgame tablebase”。

Answer 4

这里的海报建议 Stockfish 将是一个好的开始，但它是一个 C++ 项目，而您要求使用 C#。

解决方案取决于您的要求。如果您对“让它工作”感兴趣，您可以在不编写超过 200 行代码的情况下完成该项目。您可以嵌入一个开源 C# 项目，并要求引擎向您报告要配对的移动次数。如果开源项目支持 UCI，则以下命令将完成这项工作：

go mate x

其中 x 是要配对的移动次数。

但是，如果您需要自己进行思考。您将需要在高效的位板或面向对象的表示之间进行选择。Bitboard 是一种更好的表示，它非常快但更难编程。所有国际象棋引擎都使用位板。在您的项目中，表示效率不是太关心，所以您可以选择OO表示。