如何将MinMax树与Q-Learning结合使用？

Question

如何将MinMax树与Q-Learning结合使用？

我想实现一个Q-Learning connect four代理，并听说将MinMax树添加到其中会有所帮助。

Answer 1

Q学习是一种Temporal difference learning算法。对于每个可能的状态(棋盘)，它学习可用动作(移动)的值。但是，它不适合与Minimax一起使用，因为Minimax算法需要一个计算函数来返回位置的值，而不是该位置上的动作的值。

然而，可以使用时间差分方法来学习这样的评估函数。最值得注意的是，Gerald Tesauro使用TD(λ) ("TD lambda")算法创建了TD-Gammon，这是一个与人类竞争的双陆棋游戏程序。他写了一篇文章描述了这种方法，你可以在here上找到。

TD(λ)后来扩展到TDLeaf(λ)，特别是为了更好地处理Minimax搜索。例如，在国际象棋程序KnightCap中已经使用了TDLeaf(λ)。您可以在this paper中阅读有关TDLeaf的内容。

Answer 2

Minimax允许你展望未来的一些走法，并以一种方式发挥，以最大限度地增加你在该时间跨度内得分的机会。这对于Connect-4是好的，在Connect-4中，游戏几乎可以在任何时刻结束，并且每个回合可用的移动数量并不是很大。Q-Learning将为您提供一个值函数来指导Minimax搜索。

Answer 3

Littman使用了带有Q学习的极小极大。因此，在他著名的开创性工作Markov Games as a framework for multiagent reinforcement learning中提出了Minimix-Q学习算法。他的工作是关于多智能体环境下的零和博弈。后来，Hu & Wellman将他的工作扩展到开发您可以找到here的NashQ学习。