q-learning计算中的大量状态

我通过 q-learning 实现了一款 3x3 OX 游戏（它在 AI vs AI 和 AI vs Human 中完美运行），但我无法更进一步地进行 4x4 OX 游戏，因为它会耗尽我所有的 PC 内存并崩溃。

这是我当前的问题：大数组中的访问冲突？ https://stackoverflow.com/questions/56231392/access-violation-in-huge-array

根据我的理解，3x3 OX 游戏总共有 3（空间、白色、黑色）^ 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

排除“不可能发生”的配置

接下来考虑当一名玩家获胜时游戏结束。例如，您有 3^3 个配置，全部如下所示

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

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

排除更多“不可能发生”

此外，您大大高估了配置空间的大小9^3因为玩家轮流轮流。例如，您无法达到如下配置：

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

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

简而言之，这就是我解决问题的方法：

• 定义一个operator<为您的董事会
• 使用<您可以为每组“相似”配置选择一个代表（例如，<比集合中的所有其他人都要多）
• 编写一个函数，对于给定的配置返回代表性配置
• brute force iterate all possible moves (only possible moves!, ie by making alternating turns of the players only until the game is won). While doing that you
  • 计算您遇到的每个配置的代表
  • 记住所有代表性配置（请注意，由于对称性，它们出现了多次）

您现在拥有所有模对称配置的列表。在实际游戏中，您只需将棋盘变换为其代表，然后进行移动即可。如果您记得如何旋转/镜像回来，您可以稍后转换回实际配置。

这是相当蛮力的。我的数学有点生疏，否则我会尝试直接获取代表名单。然而，对于每种尺寸的电路板，您只需执行一次此操作。