java - 策略棋盘游戏 AI 的高效棋盘表示

Question

位板表示在少于 64 个位置的类似国际象棋的简化策略游戏中是否仍然有效，或者更简单的基于数组的邮箱实现是否更实用？

我们学校的 AI 类(class)每年都会举行一次比赛，教授会编出棋盘游戏，我们有四个星期的时间来创造一个玩这个游戏的 AI。通常，这些棋子是具有相似规则的棋子的子集，并且在较小的棋盘上进行。即 8x5、7x7 等。我完全不确定仅使用 40 位与国际象棋的典型 64 位相比如何。

我唯一的问题是我对 C 或 C++ 不是很熟悉，用 Java 实现程序会更舒服。他们在 Java 中对位操作的支持是否足够，我可以在其中实现位板表示，如果这会提高效率，是否值得增加复杂性？学习曲线会不会太陡峭？

我的计划是根据时间使用带 AB 剪枝的 Negamax 搜索、静止搜索、换位表、 killer 移动等。在如此短的时间内创建具有竞争力的 AI 的任何其他技巧？

Answer 1

位板可以工作，但在我看来，仅仅为了让它正常工作而付出的额外努力和复杂性不值得以后在计算效率方面获得任何可能的提高。

在事物的整体规模上，按位掩码(& 或 |)的效率高于获取数组(甚至 List 或 Map) 将在很大程度上被您打算使用的任何 AI 或搜索算法所掩盖。

也就是说，指数或多项式复杂度的算法仍然需要 O(e^n) 或 O(n^d) 并且您节省了多少 CPU 周期使用二进制算法对指针取消引用将是微不足道的。

此时只需使用您可以使用的最简单的数据结构(可能是数组，或任何Collection)并专注于让您的算法发挥作用。

稍后，如果您有时间，您可以分析您的程序，如果您发现数组查找占用了例如 20% 的运行时间，那么也许，只是也许，考虑将所有内容重构为按位操作。

就个人而言，我会研究并行搜索解决方案空间的可能方法，以最大化多个 CPU 内核，或者更好的是，以一种可以分布在多个计算节点上的方式。是的，如果你发现了一些真正聪明的东西，那你可能至少有资格获得硕士学位。 :)