纸牌游戏的遗传算法(Dominion)

Question

我有一个运行F#程序,运行Dominion,一款纸牌游戏.我想用遗传算法来确定最佳的游戏策略.但是,我对AI或遗传算法知之甚少.你能指点我一些好的文学入门吗？

比赛的策略包括对特定牌的反应.在每个回合中,机器人都会获得一手牌.它可以根据已经处理的内容选择玩动作卡或购买新卡.目标是尽可能多的胜利点卡结束游戏.

硬编码方法可能类似于:

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对抗各种其他机器人的平均分数.(一个机器人的分数取决于它与谁对抗,但希望通过对许多机器人玩很多游戏,这甚至可以解决.)

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

Answer 1

Dominion是一款出色的游戏,但使用遗传算法很难进行优化,因为任何给定游戏的输入在游戏(使用的卡集),游戏过程中的最佳策略变化以及游戏的最佳游戏方面都有所不同.任何给定的情况只会慢慢地出现在遗传搜索中(直觉上,基于我对GA和游戏的非常好的理解).

我认为,对Dominion更好的方法是直接启发式(基于规则)方法,或者非常有趣的是,蒙特卡罗搜索(例如,参见http://cacm.acm.org/magazines/2012/3)/146245-the-grand-challenge-of-computer-go/fulltext).蒙托卡罗搜索吸引人的正是因为:

• 在Dominion中生成随机但合法的移动序列很容易.
• 判断这样一个序列的"价值"至少是直截了当的(增加VP)
• 先行建立"最佳游戏"规则很难(这就是让游戏如此优秀的原因)

这是一个非常好的挑战 - 你应该博客你的经历.

Answer 2

您从哪里绘制其他机器人？你让它们保持静态吗？如果是这样，经过训练的机器人本身不会变得“擅长”游戏，而只是擅长利用虚拟机器人。如果不是，那么其他机器人也会进化，并且获胜百分比不会成为质量的良好指标，除非存在其他一些限制。永远要意识到，当机器人群体中充满了技能完美的机器人时，它们彼此之间的表现就会显得平庸！

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

• 使足够大的群体中的所有机器人发生变异。
• 让他们在循环赛中反复比赛，例如100次
• 消除一些表现最差的机器人，
• 保持一些最好的机器人不变（精英主义）
• 用好机器人的突变和交叉来补充剩余的人口。

或者您可以根据固定基准进行训练：

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