artificial-intelligence - 如何为遗传算法的棋盘游戏策略选择一个好的表示？

Question

对于我的学士论文，我想编写一个遗传算法来学习玩 Stratego 游戏(如果你不知道这个游戏，可以假设我说的是国际象棋)。我以前从未做过实际的 AI 项目，所以看到我实际上对实现事物知之甚少，这让我大开眼界。

我坚持的事情是为实际策略提出一个很好的表示。我可能犯了一些思维错误，但我遇到了一些问题:

我不认为你会有一个包含很多的表示
董事会职位之间的过渡，因为那只是
蛮力吧？

决策树的分支看起来像什么
喜欢？我想出的任何表示都不能互换
分支...如果我要使用一个位串，这显然也是
常见的，这些位代表什么？

我是否为某些作品之间的距离分配分数？我将如何表示？

我觉得我学了三年多就应该知道这些了，所以我觉得自己很傻——这看起来我好像一点头绪都没有。尽管如此，任何关于谷歌什么的帮助或提示将不胜感激!

Answer 1

我认为，您可以定义一个决策模型，然后尝试优化该模型的参数。您还可以创建多阶段决策模型。我曾经做过类似的事情来解决动态拨号问题 (paper here)，将其建模为两阶段线性决策问题。举个例子，你可以:

对于你的每个数字，决定下一步移动哪个。每个图形都以其在棋盘上的位置衍生出的某些特征为特征，例如得分能力、危险、保护其他人物等。这些特征中的每一个都可以组合(例如，在线性模型中，通过神经网络，通过符号表达式树，决策树，......)并为您提供下一步行动的排名。

与您选择的人偶一起表演。同样，可以采取一定数量的行动，每个行动都有特定的特征。同样，您可以对它们进行组合和排名，一项操作将具有最高优先级。这是您选择执行的一项。

您提取的特征可以非常简单，也可以非常复杂，这取决于您认为最有效的功能与需要多长时间计算的功能。

为了评估和提高决策模型的质量，您可以在与对手的几场比赛中模拟这些决策，并训练结合这些特征的模型参数来对 Action 进行排名(例如使用 GA)。通过这种方式，您可以调整模型以赢得尽可能多的与指定对手的比赛。您可以通过与以前从未见过的对手比赛来测试该模型的通用性。

正如Mathew Hall 刚才所说，您可以为此使用GP(如果您的模型是复杂规则)，但这只是一种模型。在我的情况下，权重的线性组合做得很好。

顺便说一句，如果您有兴趣，我们还有一个关于启发式优化的软件，它为您提供 GA、GP 和那些东西。它叫HeuristicLab .它是 GPL 和开源的，但带有 GUI (Windows)。我们有一些关于如何在外部程序中评估适应度函数的 Howto(使用 Protocol Buffer 的数据交换)，因此您可以处理您的模拟和决策模型，并让 HeuristicLab 中的算法优化您的参数。