5

我有一个运行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 对抗各种其他机器人的平均得分。（一个机器人的分数取决于它与谁比赛，但希望通过与许多机器人进行多次比赛，这可以平衡。）

这有意义吗？我走在正确的道路上吗？

4

3 回答 3

5

Dominion 是一款很棒的游戏，但很难使用遗传算法进行优化，因为任何给定游戏的输入因游戏（使用的卡组）而异，最佳策略在游戏过程中会发生变化，以及最佳玩法任何给定的情况只会慢慢地出现在基因搜索中（直觉上，基于我对 GA 和游戏的非常好的理解）。

我认为，更好的 Dominion 方法要么是直接启发式（基于规则）的方法，要么是非常有趣的 Monte Carlo Search（例如，参见http://cacm.acm.org/magazines/2012/3 /146245-the-grand-challenge-of-computer-go/fulltext）。蒙托卡洛搜索之所以吸引人，正是因为：

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

这是一个很好的挑战——你应该在博客上写下你的经历。

于 2012-06-04T18:54:10.207 回答
4

你从哪里画出其他机器人？你让它们保持静止吗？如果是这样，受过训练的机器人本身不会变得“擅长”游戏，只会擅长利用虚拟机器人。如果不是，那么其他机器人也会进化，除非应用一些其他限制，否则胜率将不是质量的良好指标。始终意识到，在一群拥有完美技能的机器人的情况下，他们的表现将显得平庸！

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

  • 突变足够大的种群中的所有机器人。
  • 让他们在循环赛中反复竞争，例如 100 次
  • 消除一些表现最差的机器人，
  • 保持一些最好的机器人不变（精英主义）
  • 用优秀机器人的突变和交叉来补充其他人口。

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

  • 使用您对游戏的了解，制作一个看起来不错的手工策略的机器人
  • 或者，让人类玩家（你自己？）提供动作。这可能是您的机器人训练经验的良好来源，但除非您可以访问（专家）人类动作的大型数据库，否则它非常慢。
  • 根据您的基准进行训练
  • 选择表现最好的人，变异等
于 2012-06-03T15:27:58.770 回答
2

我认为除非游戏非常线性，否则向量不会真正带来好的结果。我建议采用以下基于规则的方法：

在每个回合中，您都持有一组牌，并且您想确定要打出的牌，或者在您不打出一张牌的情况下，您想抽一张新牌。你需要的是某种优先级函数，它告诉你哪张牌最好玩。这样的优先功能可以通过遗传编程来描述。你总是会打出优先级最高的牌，除非没有牌的优先级高于设定的等级（例如 0），在这种情况下你会抽一张新牌。遗传编程可用于进化该优先功能。

由于您使用的是 F#，因此使用HeuristicLab尝试这种方法可能是个好主意这是用 C# 编写的。您可以在那里将您的程序作为一个问题来实现，并让评估函数执行该游戏的模拟。为您的规则编写语法和解释器。定义一些参数，使您的优先级规则能够做出有意义的决定，例如一些通用的游戏信息，例如打出的牌数、剩余的省份等，以及一些与牌相关的信息，例如打出该牌的影响（以获胜的形式） -points）等。这些是解释器的输入变量，它将计算优先级值。具有最高优先级值的卡是您选择的卡。然后评估您的策略，例如在您创建此类问题时定义 10 个随机解决方案，并在评估中让每个解决方案与该随机机器人竞争。测量你击败每个随机机器人的数量，你赢的越高，你击败的机器人越多，适应性越好，他们赢的越多，得分越差。然后，您还可以为您的问题添加一个分析器，该分析器将使用性能最佳的解决方案更新问题的随机解决方案，因此您也可以随着时间的推移对这些解决方案进行改进。

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

于 2012-06-03T20:26:07.287 回答