GOFAI 在党派组合游戏方面的历史弱点?

人工智能 游戏-ai α-β-修剪 象征性的ai 组合游戏
2021-11-04 20:48:19

我最近在阅读论文Some Studies in Machine Learning Using the Game of Checkers II--Recent Progress (AL Samuel, 1967),这在历史上很有趣。

我正在看这个数字,其中涉及 Alpha-Beta 修剪。

在此处输入图像描述

我突然想到,所使用的非平凡、非机会、完美信息、零和、顺序、党派博弈(国际象棋、跳棋、围棋)的类型涉及无法精确量化的博弈状态。例如,没有办法为国际象棋中的棋子或任何给定的棋盘状态赋予客观价值。在某种意义上,值的分配是任意的,由估计组成。

我正在研究的组合游戏是党派数独的形式,它是涉及领土控制的投标/计分(经济)游戏。在这些模型中,任何给定的棋盘状态都会产生一系列比率,从而可以精确量化玩家状态。代币价值和位置可以精确量化。

该项目涉及消费产品,我们目前采取的方法是利用一系列越来越复杂的代理,为人类玩家提供不同级别的挑战。这些代理也反映了所谓的“战略阶梯”。

反射代理(初级)
基于模型的反射代理(中级)
基于模型的效用代理(高级)

目标也可能被纳入这些代理,例如期望的胜利边际(区域结果比率),这可能会对绩效产生影响,因为较窄的胜利边际似乎带来的风险较小。

第一代反射代理的“相当弱”与人类表现相比,表明强大的 GOFAI 可能是可能的。(由于模型的阶乘性质,在游戏的早期和中期,分支因子是极端的,但初步计算表明,即使是幼稚的极小极大前瞻也能够比人类更有效地看远。)党派中的 Alpha-Beta 修剪数独,即使没有学习算法,也应该比以前的价值是估计的组合游戏模型提供更大的效用。

  • GOFAI 在非平凡组合博弈方面的历史弱点是否部分是所研究博弈结构的函数,其中博弈状态和代币值无法精确量化?

寻找任何可能对此主题发表评论的论文,研究可以进行精确量化的组合游戏,以及一般的想法。

我正在尝试确定在升级到学习算法之前是否值得尝试为这些模型开发强大的 GOFAI,以及这样的结果是否具有研究价值。

没有长期记忆的强大 GOFAI 肯定会具有商业价值,这将允许应用程序的本地文件大小最小,这些应用程序必须在最小公分母的智能手机上运行,​​而无需假设连接。

PS-我之前在这方面的工作涉及定义从模型结构中出现的核心启发式方法,我正在慢慢地将我的脚趾浸入前瞻池中。如果我做了任何不正确的假设,请不要犹豫,让我知道。

1个回答

好问题!

我认为这里有几个问题在起作用。

GOFAI 在非平凡组合博弈方面的历史弱点是否部分是所研究博弈结构的函数,其中博弈状态和代币值无法精确量化?

我认为简短的回答是肯定的。真正的问题在最后一部分:

令牌值无法精确量化

这些游戏最成功的 GOFAI 方法都是 A* 搜索的一些变体,将组合搜索与某种形式的启发式函数相结合,该启发式函数可以估计任何给定状态下棋子的价值及其位置。计件可能比不计算任何东西更好的启发式方法,但它仍然明显不正确,因为材料较少的玩家可能仍然具有压倒性的位置优势。然而,一些启发式方法也可以尝试估计这种位置优势。

GOFAI 在这些游戏中遇到的真正问题是,位置优势可能会以需要难以置信的启发式能力来检测的方式出现。跳棋就是一个很好的例子。1990 年代,阿尔伯塔大学的奇努克项目着手彻底解决这个问题。跳棋之所以引人注目,是因为它连续 15 年以上拥有同一个世界冠军,马里昂·廷斯利在 40 年的比赛中,廷斯利总共输掉了 7 场比赛。这使他成为我们研究组合游戏时特别有趣的人。弄清楚 Tinsley 的比赛方式可以帮助我们了解人类智能如何在此类游戏中发挥作用。在解决跳棋的过程中,研究人员指出,廷斯利正在做出最多需要42 向前移动以显示优势(参见Schaeffer 等人,AI 杂志,第 17 卷,第 1 期)。

这强烈表明廷斯利没有系统地考虑每一个可能的举动。相反,据他自己承认,他的思维是由他 40 年职业生涯中的记忆组合引导的(在 1992 年与奇努克的一场比赛中,他表示他试图回忆 30 年前一场比赛的序列,当时他做出了动作(AI 杂志第 14 卷,第 2 期);以及注意力启发式(即不考虑每个移动序列,并且能够可靠地排除搜索空间的某些部分而无需查看它们)。

关键在于,GOFAI 在没有启发式的情况下解决跳棋(即准确地解决它)需要大量的计算能力,因为一些移动产生的位置优势需要 40 多个后续移动。即使是非常简单的游戏(分支因子为 2)在这种约束下也很难。

相比之下,像在TD-Gammon的双陆棋(Tesauro, Comm. of the ACM 1995)中开创的自我对弈技术模仿了 Tinsley 变得如此出色的过程:他们玩了很多游戏,学习了一个很好的启发式估计位置和物质价值,更重要的是,可以学会记住需要小心发挥的奇怪情况。TD-Gammon 取得了世界级的发挥,尽管只明确地展望了 2 步。尽管搜索得更深入,GOFAI 搜索技术甚至还不够接近。

然而,关于注意力的现代研究可以挽救 GOFAI 方法。如果你能学会分辨什么是重要的,那么你可能会从更深入的前瞻中获得更多价值。这似乎更接近于廷斯利的打法:强大的价值估计能力被用来指导对特定动作链的明确分析。