algorithm - 开发西洋跳棋(跳棋)引擎，如何开始？

Question

我是一个相对缺乏经验的程序员，最近我对为学校项目制作西洋跳棋游戏应用产生了兴趣。我不确定我可以从哪里开始(或者我是否应该尝试)创建它。我想到的项目可能只涉及简单的 AI 和多人游戏模式。

谁能给我一些提示/指导让我开始学习？

Answer 1

在某种程度上，我同意一些关于建议“先尝试更简单的东西”的问题的评论，但是西洋跳棋非常简单，您可以得到一个可以工作的程序——而且您肯定会学到有用的东西去吧。

我的建议是将问题分成几个部分，依次解决。例如:

1) 电路板表示 - 可能使用 8x8 阵列来表示电路板。你需要能够用空的、白色的棋子、黑色的棋子、白色的王、黑色的王来填满一个方格。一个更有效的解决方案可能是查看“位板”，其中板的占用由一组 64 位整数描述。您可能希望最终得到可以加载或保存板状态、打印或显示板以及确定某个位置的内容(如果有的话)的函数。

2) 移动表示 - 找到一种计算合法移动的方法。哪些棋子可以移动，可以移动到哪里。您需要考虑 - 离开棋盘边缘、受阻移动、跳跃、多次跳跃、国王“向后”移动等。您可能希望最终得到可以计算一 block 棋子所有合法移动的函数，确定如果建议的移动是合法的，将游戏记录为一系列移动，也许与最终用户交互，以便通过鼠标或输入文本命令，您可以在棋盘上“玩”游戏。因此，即使您只做到这一点，您也拥有了可以展示并且人们可以与之互动的“产品”。

3) 玩电脑——这是比较难的部分——你需要学习极小极大、alpha-beta 剪枝、迭代加深以及所有与电脑游戏 AI 相关的废话——其中一些听起来比实际更难.您还需要开发一种位置评估算法来衡量位置的值(value)，以便计算机可以决定哪个是“最佳”移动。这可以像天真地假设吃掉对手的棋子总比不吃一子好，做王总比不做王好，或者给你留下更多 future 棋子的棋子好于让你留下更多棋子的棋子一样简单。你下一步的选择更少。在实践中，即使是非常简单的“贪心”董事会评估也能很好地发挥作用，前提是您可以提前 2-3 步。

不过，总而言之，看一些比西洋跳棋更简单的东西可能更简单 - 奥赛罗可能是一个不错的选择，并且不难编写一个可以击败没有玩过西洋棋的人的奥赛罗棋手很多游戏。 3D tic-tac-toe 或小型的点和框游戏也可能适合。像这样的游戏更简单，因为没有国王或边界使事情复杂化，所有(大多数) Action 都是合法的，而且它们足够“有趣”，可以作为一个有值(value)的软件演示来玩。