一种用于卡牌游戏（Dominion）的遗传算法

Question

我有一个运行Dominion（一款卡牌游戏）的F#程序。我想使用遗传算法确定最佳游戏策略，但我对人工智能或遗传算法不太了解。你能指点我一些好的文献来入门吗？

游戏策略是针对特定手牌的反应。每回合，机器人会被发一手牌。它可以根据所得到的牌选择出牌或购买新牌。目标是以尽可能多的胜利点卡结束游戏。

硬编码方法可能看起来像：

def play(hand, totalDeck):
    if hand contains Smithy then use Smithy
    if hand contains enough coins for Province then buy Province
    if more than 30% of the totalDeck is Smithy, then buy coins

我在考虑用每张牌的目标占整副牌的比例向量来描述一种策略：

[Smithy, Province, Copper, ...]
[.3, .2, .1, ...]

然后要改变机器人，我只需改变那个向量，看变异版本是否更好。适应函数是平均得分，与其他机器人玩Dominion。(一个机器人的得分取决于它与谁对战，但希望通过与许多机器人进行多场比赛来平衡。) 这有意义吗？我走的方向正确吗？

- Nick Heiner

---

抱歉，但我认为这是你问题的一个非常糟糕的描述。我甚至不知道你为什么想要“合并”两个机器人或者你想要合并哪些机器人。我假设行动卡是在游戏过程中会发生变化的动态属性。请用目标函数和决策变量更清晰地陈述问题。我假设你想要训练一些通用机器人的参数，而你编写了这个机器人。也许你可以再详细解释一下。你用什么编程语言编写了纸牌游戏的模拟器？ - Andreas

我同意我之前没有很好地表达问题。我再试一次，这样看起来怎么样？ - Nick Heiner

绝对值得花费一点额外的时间。 - Andreas

Answer 1

Dominion是一款很棒的游戏，但使用遗传算法进行优化将会很困难，因为任何给定游戏的输入都不同（使用的卡牌集合不同），最佳策略在游戏过程中也会发生变化，并且对于任何给定情况的最佳操作只会在遗传搜索中缓慢出现（根据我对GAs和游戏的相当好的理解直觉得出）。

我认为更好的方法是采用直接启发式（基于规则）方法或者非常有趣的蒙特卡罗搜索（见例如http://cacm.acm.org/magazines/2012/3/146245-the-grand-challenge-of-computer-go/fulltext）。蒙特卡罗搜索之所以吸引人，是因为：

• 在Dominion中生成一个随机但合法的移动序列很容易。
• 至少可以直接判断这样一个序列的“价值”（VP的增加）
• 先验建立“最佳玩法”规则很难（这就是使游戏如此出色的地方）

这是一个非常好的挑战 - 你应该记录下你的经验。

- Larry OBrien

Answer 2

你从哪里获取其他机器人？你是否保持它们静态不变？如果是这样，那么训练出的机器人并不会真正变得“好”玩，只是擅长利用虚拟机器人。如果不是这样，那么其他机器人也会进化，胜率将不能成为质量的良好指标，除非应用其他约束条件。请始终注意，对于一个充满完美技能机器人的种群，它们相互之间的表现将显得平庸！

您可以采取共同进化的方法：

- 在足够大的种群中突变所有机器人。 - 让它们反复在循环赛中竞争，例如100次。 - 淘汰一些表现最差的机器人， - 保留一些最好的机器人不变（精英主义）。 - 用好机器人的突变和交叉填充其余种群。

或者您可以针对固定基准进行训练：

- 制作一个具有手工制作策略的机器人，该策略看起来很好，您对游戏有了解。 - 或者，让人类玩家（您自己？）提供动作。这可能是您的机器人获得训练经验的好来源，但除非您可以访问大量（专家）人类动作的数据库，否则速度非常慢。 - 针对基准进行训练。 - 选择最佳表现者，进行突变等操作。

- Junuxx

Answer 3

我认为向量法只有在游戏非常线性的情况下才能真正产生好的结果。我建议采用以下基于规则的方法：

每回合你手里有一组牌，你需要确定要打出哪张牌，或者如果你不打出任何牌，你想要抽一张新牌。你需要的是一种优先级函数，告诉你哪张牌是最好打的。这样的优先级函数可以通过遗传编程来描述。除非没有一张牌的优先级高于设定的水平（例如0），否则你总是会打出优先级最高的牌，否则你就会抽一张新牌。遗传编程可以用来演化这个优先级函数。

由于您正在使用F#，尝试使用C＃编写的HeuristicLab可能是一个好主意。您可以将程序实现为该问题，并让评估函数执行该游戏的模拟。编写规则和解释器。定义一些参数，使您的优先级规则能够做出有意义的决策，例如某些通用游戏信息，如已播放的卡牌数量，剩余的省份等，以及某些与卡片相关的信息，例如播放该卡牌的影响（以胜利点数表示）等。这些是解释器的输入变量，它将计算优先值。具有最佳优先级值的卡片是您选择的卡片。然后，在创建此类问题时定义例如10个随机解决方案，并在评估中让每个解决方案与那些随机机器人竞争。测量您击败每个随机机器人的程度，您赢得越多，击败的机器人越多，适应度就越好，他们赢得越多，分数就越差。您还可以向问题添加分析器，该分析器将使用表现最佳的随机解决方案更新问题，因此您也会随着时间的推移发展这些解决方案。

您也可以使用目标部分的想法。在这种情况下，您的编码将是一个RealVector。您还可以使用HeuristicLab进行优化（使用进化策略、粒子群算法或遗传算法）。

- Andreas