在非零和游戏中,在蒙特卡洛树搜索中传播哪个值?

人工智能 游戏-ai 蒙特卡罗树搜索 棋盘游戏
2021-11-09 03:53:58

通常,当我阅读蒙特卡洛树搜索时,0 和 1 之间的值(或 -1 和 1 之间的值)会被反向传播,具体取决于模拟是赢还是输。

现在,假设你有一个 AI 需要玩一个游戏,其中尽可能高的得分也很重要。例如,它需要在卡尔卡松的比赛中与其他球员的比赛中获得尽可能多的分数。

在这种情况下,反向传播的值有哪些选择?您能否仅反向传播点数,然后根据节点,仅使用 UCT 中玩家的点数?或者这会导致搜索收敛到比最优移动更糟糕的移动吗?

1个回答

理论上:是的,您可以反向传播任何想要最大化的分数。它们不必局限于一组小的离散值,例如{1,0,1},也不必在任何特定范围内,例如[1,1]或者[0,1].

但是,在实践中,如果您可以将您拥有的任何“原始”分数归一化到某个较小的范围(如上面提到的范围),它可能仍然有用。主要用于超参数调整例如,考虑我们在树遍历期间通常在 UCT 中使用的 UCB1 方程:

a=argmaxa(Q(s,a)+Cln(aN(s,a))N(s,a)).

我们通常有一个C那里的超参数/常数,它控制着我们在探索和利用之间的权衡。更高C意味着更多的探索,更低的C意味着更多的剥削。Q(s,a)term 是到目前为止反向传播的分数的平均值a处于状态s. 在这个等式中,Q(s,a)C术语之间存在某种“竞争”,因此它们的最佳值彼此密切相关。如果你处理一个现有的问题并将所有的分值乘以,比如说,100,你可能还想乘以你的C常数曾经是100从树搜索中再次获得相同的行为。

实际上,这个故事真正重要的甚至不是你的原始大小Q值,而是您看到的典型差异的大小Q同一状态下不同动作的值。所以,如果你的问题只有Q范围内的值[99,101],你实际上会想要一个类似的C保持不变Q范围内的值[1,1],但如果你的问题有Q范围内的值[100,100],你可能会想要100大一倍C也值。

如果您可以将您的值大致标准化到大约[1,1]或者[0,1]范围内,您可以相对自信地认为类似的种类C其他人在零和设置中通常使用的值也可以正常工作(例如,C范围内某处的值[0,2], 经常低于1.... 但理想常数也经常取决于许多其他因素)。


除此之外,我通常也倾向于选择没有疯狂高幅度的值,因为这让我觉得在对来自许多不同迭代的大量值求和时,我不必担心数值溢出等烦人的事情通过同一个节点。