策略棋盘游戏AI的有效棋盘表示

Question

在不到64个位置的低级象棋策略游戏中，位板表示是否仍然有效，或者更简单的基于数组的邮箱实现是否更实用？

我们学校的AI班级每年都会举行一次竞赛，教授会制作一个棋盘游戏，我们有四周的时间来创建一个玩这个游戏的AI。通常，棋子是具有类似规则的国际象棋棋子的子集，并且在较小的棋盘上玩。例如，8x5，7x7，等等。我根本不确定只使用40位与国际象棋中典型的64位相比如何。

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

我的计划是使用Negamax搜索与AB剪枝，quiessence搜索，转换表，杀手移动等取决于时间。在这么短的时间内创建一个有竞争力的人工智能还有其他的技巧吗？

Answer 1

位板可以工作，但在我看来，仅仅为了让它正常工作而增加的努力和复杂性并不值得以后在计算效率上获得任何可能的收益。

从整体上看，通过位掩码(&或|)获取数组元素(甚至是List或Map)的效率将在很大程度上被您打算使用的任何AI或搜索算法所掩盖。

也就是说，指数或多项式复杂度的算法仍将占用O(e^n)或O(n^d)，并且使用二进制算法比指针解引用节省的几个CPU周期将变得微不足道。

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

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

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

Answer 2

在大学里，我有过类似于你的游戏AI编写比赛，当我担心一些小细节时，比如“静态编码是不是更快了”或者“理智检查会不会减慢我的程序？”但是“如果我把我的人工智能写得更智能/更高效，它会把的性能提高一个数量级，所以我要实现我发现的这个很酷的新技巧”。

令人吃惊的加速的常见例子是α-beta修剪，杀手启发式和选择一个好的算法来计算游戏状态的强度(请注意，好!=更准确-它也可能意味着更快和仍然准确。毕竟，如果你的得分计算更简单，它可以让你向前看更多的动作，这意味着你可以用黑桃来弥补它)。

Answer 3

你也可以使用位板。这并不是真的那么复杂，而且在移动生成和静态交换计算中得到了显著的加速。你的人工智能算法，无论多么聪明，仍然需要做大量这样的事情。

在这个主题上有一个非常好的网站：chessprogramming.wikispaces.com/Bitboards

由于你的棋盘大小不同，一些技巧可能不适用，这取决于你给方块分配比特的方式。另一方面，由于它只是片段的一个子集，所以一些传统上难以用bitboards解决的问题可能不存在。