如何提高解决 Steffen Benndorf 的单人版纸牌游戏“The Game”的方法的性能?

人工智能 游戏-ai 蒙特卡罗树搜索 算法请求 极小极大 启发式
2021-10-24 10:22:32

我想为 Steffen Benndorf 的名为“The Game”的纸牌游戏的 1 人版本创建一个 AI(此处的规则:https ://nsv.de/wp-content/uploads/2018/05/the-game-英文.pdf)。

该游戏适用于四行卡片。两行按升序排列(数字 1-99),两行按降序排列(数字 100-2)。我们的目标是在四排卡片中放置尽可能多的卡片,如果可能的话,全部放置 98 张卡片。玩家最多可以有 8 张牌,并且必须至少打出 2 张牌才能再次抽牌。他只能在上升行打出较大的值,而在下降行打出较小的值,但有一个例外允许他以相反的顺序进行游戏:只要数字卡的值正好高或低 10 时。

我已经实现了一个非常简单的硬编码 AI,它只选择差异最小的牌,并在可能的情况下优先考虑 +10/-10 游戏。通过一些优化,我可以让 AI 平均得分 20 分(剩余的牌数),这是不错的(不到 10 分的优秀分数),但我被困在那里,我想走得更远。

由于抽牌堆存在随机性,我想知道是否有可能实现一个健壮且非硬编码的 AI 来玩这个游戏。

目前,我的 AI 正在使用一个非常简单的启发式算法。我不知道如何改进这种启发式,所以我想知道是否可以通过查看几个回合来提高性能。但我不知道如何模拟下一轮,因为它们将取决于抽出的牌。

1个回答

有几种不同的方法可以改进您的简单启发式方法,但它们主要解决以下三件事:

  • 找到更好的启发式这可以通过计算结果概率,或运行大量训练模拟并以某种方式调整启发式函数来完成。

  • 前瞻搜索/规划有许多可能的搜索算法。大多数人依赖于您能够在做出未来决定之前模拟它们的影响。

  • 考虑到更多的玩家知识到目前为止,您的简单启发式方法并未考虑已经打出的牌(因此还有哪些值要绘制)。

目前,我的 AI 正在使用一个非常简单的启发式算法。我不知道如何改进这种启发式方法,所以我想知道是否可以通过查看几个回合来提高性能。但我不知道如何模拟下一轮,因为它们将取决于抽出的牌。

我认为你必须改进的主要概念障碍是如何解释绘制特定有用卡片的概率的复杂行为。有几种方法可以做到这一点,但我认为最简单的是某种推出(模拟前瞻),这可能会导致更复杂的算法,如蒙特卡洛树搜索(MCTS)

以下是一个非常简单的变体如何工作:

  1. 对于您当前正在查看的游戏中每种可能的玩法选择:

    1. 模拟剩余的牌组(将已知剩余牌的副本洗牌)

    2. 使用简单的启发式对模拟套牌进行模拟(“推出”)直到游戏结束(您当前的贪婪选择版本应该是好的,只要它足够快,但即使是随机选择也可以工作)。记下最后的分数。

    3. 尽可能多地重复 1.1 和 1.2(给定允许的决策时间)。平均结果并将其保存为正在考虑的游戏选择的分数。

  2. 与其按照你的启发式方法选择下一场比赛,不如从所有模拟中选择得分最高的一场。

这种样本的统计平均值在很多情况下都有效,因为它避免了从概率论分析做出完美决策所需的复杂性和耗时的计算。在您的情况下,它所做的重要事情是前瞻性计划以及考虑玩家对游戏状态的额外了解。

MCTS 与上述类似,但嵌套,因此模拟是从多个起点进行的。

就稳健性而言,如果您在每个决策中运行足够的部署以对平均分数有信心,那么应该没问题。