q-learning计算中的海量状态
The huge amount of states in q-learning calculation
我通过 q-learning 实现了一个 3x3 OX 游戏（它在 AI v.s AI 和 AI v.s Human 中完美运行），但我不能更进一步到 4x4 OX 游戏因为它会耗尽我所有的 PC 内存并崩溃。
这是我目前的问题：
据我了解，一个3x3的OX游戏一共有3(space, white, black) ^ 9 = 19683种可能的状态。 (同样的图案不同的角度也算)
对于 4x4 OX 游戏，总状态将为 3 ^ 16 = 43,046,721
对于常规的围棋游戏，15x15 的棋盘，总状态将为 3 ^ 225 ~ 2.5 x 10^107
Q1。我想知道我的计算是否正确。 （对于 4x4 OX 游戏，我需要一个 3^16 数组？）
Q2。由于我需要计算每个Q值（针对每个状态，每个动作），我需要这么大的数组，这是预期的吗？有什么办法可以避免吗？
考虑对称性。可能配置的实际数量远小于 3x3 板上的 9^3。例如基本上只有 3 种不同的配置，板上有一个 x。
旋转
有许多电路板配置都应该导致您的 AI 做出相同的决定，因为它们是相同的模对称性。例如：
x - - - - x - - - - - -
- - - - - - - - - - - -
- - - - - - - - x x - -
这些都是相同的配置。如果你单独对待他们，你会浪费训练时间。
镜像
不仅有旋转对称，还可以在不改变实际情况的情况下镜像板子。以下基本都是一样的：
0 - x x - 0 - - - - - -
- - - - - - - - - - - -
- - - - - - 0 - x x - 0
排除 "cannot happen" 配置
接下来考虑当一个玩家获胜时游戏结束。例如，您有 3^3 个配置，看起来都像这样
x 0 ?
x 0 ? // cannot happen
x 0 ?
他们永远不会出现在正常比赛中。您不必为它们保留 space，因为它们根本不可能发生。
排除更多"cannot happen"
此外，您大大高估了配置 space 和 9^3 的大小，因为玩家轮流交替进行。例如，您无法达到这样的配置：
x x -
x - - // cannot happen
- - -
如何获取所有需要的配置？
简而言之，这就是我处理问题的方式：
- 为您的看板定义一个
operator<
- 使用
< 关系，您可以 select 每组 "similar" 配置的一个代表（例如，< 比该组中的所有其他配置）
- 编写一个函数，针对给定的配置 returns 你的代表性配置
- 蛮力迭代所有可能的动作（只有可能的动作！，即通过交替轮流玩家直到赢得比赛）。这样做的时候你
- 计算你遇到的每个配置的代表
- 记住所有有代表性的配置（注意它们出现多次，因为对称）
您现在拥有所有配置模对称的列表。在实际游戏中，您只需将棋盘转换为它的代表，然后下棋即可。如果您还记得如何 rotate/mirror 恢复原状，您可以在之后转换回实际配置。
这是蛮力。我的数学有点生疏，否则我会尝试直接获取代表名单。但是，对于每种尺寸的电路板，您只需要做一次。
我有一个枚举方案，但它需要一个整数数组。如果您可以将整数数组压缩为单个 Q 值（并返回），那么这可能会起作用。
N在前，棋盘上的棋子数
然后是 ceil(N/2) 个项目的数组，X 件。每个数字都是从前一个 X 块（或板开始）开始的空有效 spaces 的计数。重要提示：如果 space 会导致游戏结束，则无效。这是 5 in a row 结束规则帮助我们减少域的地方。
然后是 floor(N/2) 个项目的数组，即 O 件。相同的逻辑适用于 X 数组。
所以对于这个棋盘和 3 件规则：
XX.
X.O
..O
我们有以下数组：
N: 5
X：0（从棋盘开始），0（从前一个X），0（右上角对X无效，因为它会结束游戏）
O：2（从棋盘开始，减去所有前面的 X），2（从前面的 O）
这就是数组 [5, 0, 0, 0, 2, 2]。给定这个数组，我们可以重新创建上面的板。小数字出现的概率比大数字出现的概率大。在 19x19 棋盘的常规游戏中，大部分棋子会组合在一起，因此会有很多零、一、二，下一行偶尔用 "big" 数字分隔。
您现在必须使用小数字比大数字出现得更多的事实来压缩这个数组。通用压缩算法可能有帮助，但一些 specialized 可能更有帮助。
我对q-learning一无所知，但这一切都要求q-value可以有可变大小。如果您必须为 q-value 设置恒定大小，那么该大小必须考虑最差的板，并且该大小可能太大，以至于它首先违背了使用此 enumeration/compression 的目的.
我们使用 left-to-right 和 top-to-bottom 方法来枚举棋子，但我们也可以使用一些螺旋方法，可能会产生更好的 small-to-big 数字比。我们只需要为螺旋中心选择最佳起点。但这可能会使算法复杂化并最终浪费更多CPU时间。
此外，我们实际上并不需要数组中的第一个数字 N。数组的长度提供了此信息。
如果你跳过重新发明轮子，这里是解决这个问题的方法：
The model is a convolutional neural network, trained with a variant of
Q-learning, whose input is raw pixels and whose output is a value
function estimating future rewards. We apply our method to seven Atari
2600 games from the Arcade Learning Environment, with no adjustment of
the architecture or learning algorithm.
https://arxiv.org/pdf/1312.5602v1.pdf
We could represent our Q-function with a neural network, that takes
the state (four game screens) and action as input and outputs the
corresponding Q-value. Alternatively we could take only game screens
as input and output the Q-value for each possible action. This
approach has the advantage, that if we want to perform a Q-value
update or pick the action with highest Q-value, we only have to do one
forward pass through the network and have all Q-values for all actions
immediately available.
https://neuro.cs.ut.ee/demystifying-deep-reinforcement-learning/
我通过 q-learning 实现了一个 3x3 OX 游戏（它在 AI v.s AI 和 AI v.s Human 中完美运行），但我不能更进一步到 4x4 OX 游戏因为它会耗尽我所有的 PC 内存并崩溃。
这是我目前的问题：
据我了解，一个3x3的OX游戏一共有3(space, white, black) ^ 9 = 19683种可能的状态。 (同样的图案不同的角度也算)
对于 4x4 OX 游戏，总状态将为 3 ^ 16 = 43,046,721
对于常规的围棋游戏，15x15 的棋盘，总状态将为 3 ^ 225 ~ 2.5 x 10^107
Q1。我想知道我的计算是否正确。 （对于 4x4 OX 游戏，我需要一个 3^16 数组？）
Q2。由于我需要计算每个Q值（针对每个状态，每个动作），我需要这么大的数组，这是预期的吗？有什么办法可以避免吗？
考虑对称性。可能配置的实际数量远小于 3x3 板上的 9^3。例如基本上只有 3 种不同的配置，板上有一个 x。
旋转
有许多电路板配置都应该导致您的 AI 做出相同的决定，因为它们是相同的模对称性。例如：
x - - - - x - - - - - -
- - - - - - - - - - - -
- - - - - - - - x x - -
这些都是相同的配置。如果你单独对待他们，你会浪费训练时间。
镜像
不仅有旋转对称，还可以在不改变实际情况的情况下镜像板子。以下基本都是一样的：
0 - x x - 0 - - - - - -
- - - - - - - - - - - -
- - - - - - 0 - x x - 0
排除 "cannot happen" 配置
接下来考虑当一个玩家获胜时游戏结束。例如，您有 3^3 个配置，看起来都像这样
x 0 ?
x 0 ? // cannot happen
x 0 ?
他们永远不会出现在正常比赛中。您不必为它们保留 space，因为它们根本不可能发生。
排除更多"cannot happen"
此外，您大大高估了配置 space 和 9^3 的大小，因为玩家轮流交替进行。例如，您无法达到这样的配置：
x x -
x - - // cannot happen
- - -
如何获取所有需要的配置？
简而言之，这就是我处理问题的方式：
- 为您的看板定义一个
operator< - 使用
<关系，您可以 select 每组 "similar" 配置的一个代表（例如，<比该组中的所有其他配置） - 编写一个函数，针对给定的配置 returns 你的代表性配置
- 蛮力迭代所有可能的动作（只有可能的动作！，即通过交替轮流玩家直到赢得比赛）。这样做的时候你
- 计算你遇到的每个配置的代表
- 记住所有有代表性的配置（注意它们出现多次，因为对称）
您现在拥有所有配置模对称的列表。在实际游戏中，您只需将棋盘转换为它的代表，然后下棋即可。如果您还记得如何 rotate/mirror 恢复原状，您可以在之后转换回实际配置。
这是蛮力。我的数学有点生疏，否则我会尝试直接获取代表名单。但是，对于每种尺寸的电路板，您只需要做一次。
我有一个枚举方案，但它需要一个整数数组。如果您可以将整数数组压缩为单个 Q 值（并返回），那么这可能会起作用。
N在前，棋盘上的棋子数
然后是 ceil(N/2) 个项目的数组，X 件。每个数字都是从前一个 X 块（或板开始）开始的空有效 spaces 的计数。重要提示：如果 space 会导致游戏结束，则无效。这是 5 in a row 结束规则帮助我们减少域的地方。
然后是 floor(N/2) 个项目的数组，即 O 件。相同的逻辑适用于 X 数组。
所以对于这个棋盘和 3 件规则：
XX.
X.O
..O
我们有以下数组：
N: 5
X：0（从棋盘开始），0（从前一个X），0（右上角对X无效，因为它会结束游戏）
O：2（从棋盘开始，减去所有前面的 X），2（从前面的 O）
这就是数组 [5, 0, 0, 0, 2, 2]。给定这个数组，我们可以重新创建上面的板。小数字出现的概率比大数字出现的概率大。在 19x19 棋盘的常规游戏中，大部分棋子会组合在一起，因此会有很多零、一、二，下一行偶尔用 "big" 数字分隔。
您现在必须使用小数字比大数字出现得更多的事实来压缩这个数组。通用压缩算法可能有帮助，但一些 specialized 可能更有帮助。
我对q-learning一无所知，但这一切都要求q-value可以有可变大小。如果您必须为 q-value 设置恒定大小，那么该大小必须考虑最差的板，并且该大小可能太大，以至于它首先违背了使用此 enumeration/compression 的目的.
我们使用 left-to-right 和 top-to-bottom 方法来枚举棋子，但我们也可以使用一些螺旋方法，可能会产生更好的 small-to-big 数字比。我们只需要为螺旋中心选择最佳起点。但这可能会使算法复杂化并最终浪费更多CPU时间。
此外，我们实际上并不需要数组中的第一个数字 N。数组的长度提供了此信息。
如果你跳过重新发明轮子，这里是解决这个问题的方法：
The model is a convolutional neural network, trained with a variant of Q-learning, whose input is raw pixels and whose output is a value function estimating future rewards. We apply our method to seven Atari 2600 games from the Arcade Learning Environment, with no adjustment of the architecture or learning algorithm.
https://arxiv.org/pdf/1312.5602v1.pdf
We could represent our Q-function with a neural network, that takes the state (four game screens) and action as input and outputs the corresponding Q-value. Alternatively we could take only game screens as input and output the Q-value for each possible action. This approach has the advantage, that if we want to perform a Q-value update or pick the action with highest Q-value, we only have to do one forward pass through the network and have all Q-values for all actions immediately available.
https://neuro.cs.ut.ee/demystifying-deep-reinforcement-learning/