游戏游戏AI -克服转位表占用太多内存的策略？

Question

我制作了一个使用标准搜索算法(minimax、alpha-beta剪枝、迭代深化等)播放Connect 4的引擎。我已经实现了一个转位表，以便引擎可以立即评估通过不同的移动顺序达到的相同位置，并允许移动排序。

TT的问题是，在迭代深化过程的每一步，它占用的字节数至少会增加一倍。TT存储表示给定位置的重要信息的对象。这些对象中的每一个都是288字节。下面，深度限制是引擎在迭代深化的每一步上搜索的距离：

深度限制=1-TT大小= 288字节(因为只查看了一个节点/位置)。

深度限制=2-TT大小= 972字节。

深度限制=3-TT大小= 3708字节。

深度限制=4-tt大小= 11664字节

深度限制=5-TT大小= 28476字节。

……

深度限制=12-TT大小= 11,010,960字节。

深度限制=13-TT大小= 22,645,728字节.

现在，.exe文件崩溃了。

我想知道这个问题能做些什么。在连接四中，分支因子是7(因为通常有7个可能的动作，至少在游戏开始时是这样)。TT没有在每一步上增长7倍的原因是因为我已经实现了修剪方法。

如果引擎只搜索深度8-9，那么这个问题就不是什么大问题了，但是我的目标是让它一直到最后才能反驳Connect 4(所以深度极限= 42)。

Answer 1

从根本上说，您拥有的是一个用于计算昂贵函数的值的缓存。与此类方案一样，您需要为哈希表中的条目确定驱逐策略。选择哪一个将取决于搜索的实际结构(显然您希望最大限度地提高缓存命中率)，但最近使用最少的(或LRU)是一个很好的起点。FIFO和随机策略也很常见。

LRU的全部思想都在名称中:当缓存中的内存耗尽(转位表)时，用新条目覆盖最古老的条目。在alpha-beta搜索的上下文中，仅在表中存储最近计算的上限将保持搜索的声音，同时仍然有效地修剪搜索，并在存储和恢复之间保持良好的平衡。

此外，董事会也有更好的代表性。您可以用49位(7字节打包)来完成它。下面是如何实现的。这些柱子有六个牢房高。用七位表示每一列，因此第一位是列上方的空格。将第一个空空间标记为1，前面为0，其余的位为0或1(分别为黑色或红色)。因此，七列中的每一列都可以明确地以七位表示，整个板(七列)可以用49位表示。

与下面给出的10字节解决方案不同，这些位可以安装在64位CPU寄存器中.因此，等式和哈希操作变得琐碎，计算起来非常便宜。

Answer 2

State

看看这个板，288个字节太大了。

一个典型的板是7x6瓦，每个瓷砖处于三种状态之一:空的，红色的，黄色的。

采用一种简单的位填充方法，每个块可以用2位表示，有42块，允许游戏状态以84位或10字节表示。

非法游戏可以通过将每块设置为第四状态来表示(2位给出了状态00、01、10、11)。我会选择：

enum {
  empty = 0x00,
  yellow = 0x01,
  red = 0x02,
  error = 0x03
}

通过一些比较，可以快速检查游戏是否存在非法状态：

byte[8] game_state;
for (int i = 0; i != 10; ++i)
    if (0 != ((game_state[i] & 0x55) & ((game_state[i] & 0xAA) >> 1))
        return error; //one of the tiles in the game is illegal...
return good;

同样，玩家可以通过计算黄色牌匾的数量来推断出模数2 (xor每一位)，如果答案是0，则是黄色转，否则就是红色。

byte[10] game_state;
byte bcount = (game_state[0] & 0x55)
            ^ (game_state[1] & 0x55)
            ^ (game_state[2] & 0x55)
            ^ (game_state[3] & 0x55)
            ^ (game_state[4] & 0x55)
            ^ (game_state[5] & 0x55)
            ^ (game_state[6] & 0x55)
            ^ (game_state[7] & 0x55)
            ^ (game_state[8] & 0x55)
            ^ (game_state[9] & 0x55)
            ;
bcount = ((bcount & 0x50) >> 4) ^ (bcount & 0x05));
return ((bcount & 0x04) >> 2) == (bcount & 0x01))
    ? yellow_turn
    : red_turn
    ;

由于每个状态在合法(没有瓷砖是错误)和非法(tiles是错误)之间混合了7个移动，那么决策树中的一个节点可以用八个游戏状态来表示。第一个状态是起始条件，另7个表示在ith列中放置令牌的移动，每个10字节状态是下一个决策节点的关键(除非它是一个错误)。这给出了每个决策节点总共80字节。

空间

游戏状态空间很大。

• 7列
• 每个列都可以有0到6块高的堆栈。
• 每个被占领状态瓷砖都有两个状态。

忽略游戏因胜利而终止，游戏状态空间为：(Ex=0..6(2^x))^7.这是532875860165503，其决策节点大小为80字节，最多需要: 38.771 PetaBytes。即使进行了广泛的过滤，这也是很难处理的。

有了你对游戏的更多了解，你可能会在这个上限上统治很多。关键是，没有一个计算机系统具有如此多的主存，甚至是内存周期- 我们大多数人现在都能接触到我们大多数人现在都能接触到。

寻呼

如果你有硬盘空间，那么B树或者B*树来拯救你。最好找到一个第三方库，它提供文件分页节点，只有在必要的情况下才能创建一个。

关键是决策节点所基于的10字节游戏状态。二进制排序应该足够了。

如果B树被设计为纯映射，则可能没有必要用该状态的结果来存储开始游戏状态(键)。

有了这种数据结构，您应该能够缓存许多游戏状态。不幸的是，这可能不足以满足您的需要。

状态模式与压缩

这款游戏有一个单调的棋盘，但当涉及到移动时，唯一有趣的状态是那些可以成为胜利者的瓷砖。您可以将error代码重命名为ignored，并标记无趣的瓷砖。按照定义，每一个标有ignored的瓷砖的游戏都是不可赢的。这将进一步压缩游戏状态空间，增加游戏状态的重叠，减少进一步的计算。

经验法则

考虑启发式，尝试并贪婪地选择最有可能获胜的路径。对胜利有直接贡献的行动，或反失败的行动，应首先考虑.移动的关键在于另一个球员的非理性行为应该被推迟。这将促进不同的广度/深度勘探。

还考虑一个有界的、健忘的、优先级队列。只有最有趣的下一场比赛状态才会排在队列上。如果队列干涸，或者状态的质量下降到最佳遗忘状态以下，请考虑从B树步行中重新组装它。为了简单起见，忘记未处理的游戏状态到日志中，它可以很容易地被重新处理以更新队列。

最后，放弃存储整个决策树的尝试。使用暂存缓存并重新生成遗忘状态.