Q-学习计算中的大量状态

Question

我通过Q学习实现了一个3x3的OX游戏(它在AI v.s AI和AI v.s Human中工作得很好)，但是我不能再深入4x4 OX游戏了，因为它会吞噬我所有的PC内存和崩溃。

下面是我当前的问题：巨大数组中的访问冲突？

据我理解，一个3x3ox游戏总共有3(空格，白色，黑色)^9= 19683的可能状态。(同一图案不同角度仍计数)

对于4x4的牛游戏，总状态为3^ 16 = 43,046,721。

对于普通围棋，15x15棋盘，总状态为3^ 225 ~2.5x10^107。

Q1。我想知道我的计算是否正确。(对于4x4ox游戏，我需要一个3^16数组？)

Q2。因为我需要计算每个Q值(对于每个状态，每个动作)，所以我需要大量的数组，这是预期的吗？有办法避免吗？

Answer 1

如果您跳过重新发明车轮，下面是解决这个问题的方法：

该模型是一个卷积神经网络，使用Q-学习的一个变体进行训练，其输入是原始像素，其输出是估计未来回报的值函数。我们将我们的方法应用于Arcade学习环境中的七个Atari 2600游戏中，没有调整结构或学习算法。

https://arxiv.org/pdf/1312.5602v1.pdf

我们可以用一个神经网络来表示我们的q-函数，它以状态(四个游戏屏幕)和动作作为输入，并输出相应的q值。或者，我们可以只使用游戏屏幕作为输入，并输出每一个可能的动作的Q值。这种方法的优点是，如果我们想要执行Q值更新或选择具有最高Q值的操作，我们只需通过网络进行一次前向传递，并且所有操作的所有q值都立即可用。

https://neuro.cs.ut.ee/demystifying-deep-reinforcement-learning/

Answer 2

考虑对称性。实际可能的配置数比3x3板上的9^3要小得多。例如，基本上只有3种不同的配置，板上只有一个x。

轮调

有许多板配置，都应该导致相同的决定，由你的人工智能，因为他们是相同的模块，一种对称性。例如：

x - -    - - x    - - -    - - -  
- - -    - - -    - - -    - - - 
- - -    - - -    - - x    x - - 

这些都是相同的配置。如果你单独对待他们，就会浪费训练时间。

镜像

不仅有旋转对称，而且你也可以镜像板，而不改变实际情况。以下各点基本上相同：

0 - x    x - 0    - - -    - - -  
- - -    - - -    - - -    - - - 
- - -    - - -    0 - x    x - 0

排除“不能发生”配置

接下来，考虑到游戏结束时，一个人赢了。例如，您有3^3配置，所有这些配置如下所示

x 0 ?
x 0 ?    // cannot happen
x 0 ?

他们永远不会出现在正常的比赛中。你不必为它们预留空间，因为它们根本不可能发生。

排除更多“不可能发生”的

此外，您极大地高估了9^3配置空间的大小，因为玩家会交替使用它们的回合。例如，您无法达到这样的配置：

x x -
x - -    // cannot happen
- - - 

如何获得所有所需的配置？

简而言之，我就是这样处理这个问题的：

• 为您的董事会定义operator<
• 使用<关系，您可以为每组“相似”配置选择一个代表(例如比集合中所有其他配置都具有<的配置)。
• 编写一个函数，该函数对于给定的配置返回代表的配置。
• 蛮力迭代所有可能的动作(只有可能的动作！)。当你这么做的时候你
  • 计算所遇到的每个配置的代表。
  • 记住所有有代表性的配置(注意，由于对称性，它们多次出现)。

​

现在，您有了所有配置模块对称的列表。在实际游戏中，你只需将董事会转换为它的代表，然后采取行动。如果您记得如何将其旋转/镜像回来，则可以在之后将其转换回实际的配置。

这是相当残忍的力量。我的数学有点生疏，否则我会直接得到代表的名单。然而，这是你只需一次的每一个大小的董事会。

Answer 3

我有一个枚举方案，但它需要一个整数数组。如果您可以将一个整数数组压缩为一个q值(并返回)，那么这可能会有效。

首先是N，棋子的数量。

然后是ceil(N/2)项的数组，X片段。每个数字都是前一个X段(或板开始)中空的有效空格的计数。重要:如果空间会导致游戏结束，空间是无效的。这就是5行结束规则帮助我们减少域的地方。

然后是地板(N/2)项目的数组，O块。同样的逻辑适用于X数组。

所以对于这个棋盘和3块规则：

XX.
X.O
..O

我们有以下数组：

编号:5

X: 0(从棋盘开始)，0(来自以前的X)，0(右上角对X无效，因为它会结束游戏)

O: 2(从董事会开始，减去前面的X)，2(来自以前的O)

这是数组5，0，0，0，2，2。给定这个数组，我们可以重新创建上面的板。小数的发生比大数更有可能发生。在与19x19棋盘的常规游戏中，大部分棋子会组合在一起，所以下一行会有大量的零、一、二，用偶尔的“大”数字分隔。

现在，您必须使用这样的事实来压缩这个数组，即小的数字比大的要多。通用压缩算法可能会有所帮助，但一些专门性可能会提供更多帮助。

我对Q-学习一无所知，但这里的所有这些都要求q值可以有可变大小。如果你必须对Q值有恒定的大小，那么这个大小就必须考虑到最坏的情况，而这个大小可能很大，以至于它一开始就违背了进行这种枚举/压缩的目的。

我们使用从左到右和自上而下的方法来枚举部分，但我们也可以使用一些螺旋法，这可能会产生更好的小到大的数字比率。我们只需要为螺旋中心选择最好的起点。但这可能会使算法复杂化，最终会浪费更多的CPU时间。

另外，我们并不需要数组中的第一个数字，数组的长度给出了这个信息。