时间戳

首页 > 解决方案 > q-learning 计算中的大量状态

c++ - q-learning 计算中的大量状态

问题描述

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

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

据我了解，一个 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值（对于每个状态，每个动作），我需要这么多的数组，是预期的吗？有什么办法可以避免吗？

标签： c++machine-learningreinforcement-learning

解决方案

考虑对称性。实际可能的配置数量远小于 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<为您的董事会定义一个
  • 使用该<关系，您可以为每组“相似”配置选择一个代表（例如，<比集合中所有其他配置的代表）
  • 编写一个函数，为给定的配置返回代表配置
  • 蛮力迭代所有可能的动作（只有可能的动作！，即只让玩家交替轮流直到游戏获胜）。这样做的时候你
    • 计算您遇到的每种配置的代表
    • 记住所有有代表性的配置（注意它们出现了好几次，因为对称）

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

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

推荐阅读