3

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

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

  • 我不认为你会有一个包含很多董事会职位之间转换的表示，因为那只会强制它，对吧？
  • 决策树的分支会是什么样子？我提出的任何表示都没有可互换的分支......如果我要使用显然也很常见的位串，那么这些位代表什么？
  • 我是否为某些片段之间的距离打分？我将如何表示？

我想这些东西我应该经过三年多的学习才知道，所以我觉得很愚蠢——这一定看起来我一点头绪都没有。尽管如此，任何关于谷歌的帮助或提示将不胜感激！

4

5 回答 5

5

我认为，您可以定义一个决策模型，然后尝试优化该模型的参数。您也可以创建多阶段决策模型。我曾经通过将其建模为两阶段线性决策问题来解决动态拨号问题（此处为论文）。举个例子，你可以：

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

  2. 与您选择的人物一起行动。同样，可以采取一定数量的行动，每个行动都有一定的特点。同样，您可以将它们组合起来并对其进行排名，并且一项操作将具有最高优先级。这是您选择执行的。

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

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

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

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

于 2012-01-04T11:51:32.220 回答
4

文森特，

首先，不要觉得自己很傻。你已经（我推断）学习基础计算机科学三年了；现在你正在将这些基本技术应用到一些非常专业的东西上——一个狭窄领域（人工智能）中的特定应用程序（Stratego）。

其次，确保您的顾问完全理解 Stratego 的规则。Stratego 在更大的棋盘上进行，棋子比国际象棋更多（和更多类型的棋子）。这给了它更大的合法位置空间，以及更大的合法移动空间。这也是一个隐藏信息的游戏，再次增加了难度。您的顾问可能希望限制项目的范围，例如，专注于具有全面观察的变体。我不知道你为什么认为这更简单，除了棋子的移动更简单一点。

第三，我认为首先要做的正确的事情是看看游戏在人工智能领域是如何处理的。Russell 和 Norvig，第 3 章（用于一般背景）和第 5 章（用于两人游戏）非常容易理解并且写得很好。你会看到两个基本的想法：第一，你基本上是在树中执行一个巨大的搜索来寻找胜利，第二，对于任何不平凡的游戏，树都太大了，所以你搜索到某个深度，然后用“董事会评估功能”解决并寻找其中之一。我认为你的第三个要点就是这样。

棋盘评估函数很神奇，可能是使用遗传算法或遗传程序的一个很好的候选者，其中任何一个都可以与神经网络结合使用。基本思想是您正在尝试设计（或实际上演变）一个将棋盘位置作为输入并输出单个数字的函数。大数字对应强位置，小数字对应弱位置。Chellapilla 和 Fogel 有一篇著名的论文展示了如何为跳棋游戏做到这一点：

http://library.natural-selection.com/Library/1999/Evolving_NN_Checkers.pdf

我认为这是一篇很棒的论文，将三大 AI 链联系在一起：对抗性搜索、遗传算法和神经网络。它应该会给你一些关于如何代表你的董事会、如何考虑董事会评估等方面的灵感。

但是请注意，您尝试做的事情比 Chellapilla 和 Fogel 的工作要复杂得多。没关系——毕竟这是 13 年后的事了，你会在这一段时间。你仍然会遇到代表棋盘的问题，因为 AI 玩家对其对手的状态不完全了解；最初，除了位置之外一无所知，但最终随着棋子在冲突中被淘汰，人们可以开始使用一阶逻辑或相关技术来缩小单个棋子的范围，甚至可能使用概率方法来推断有关整个集合的信息。（其中一些可能超出了本科项目的范围。）

于 2012-01-04T20:26:04.597 回答
2

您在提出实际策略的表示时遇到问题这一事实并不令人惊讶。事实上，我认为这是您正在尝试的最具挑战性的部分。不幸的是，我还没有听说过 Stratego，所以有点懒惰，我假设你说的是国际象棋。

问题在于国际象棋策略相当复杂。您在回答中建议在 GA 中包含棋盘位置之间的大量转换，但是棋盘的可能位置比宇宙中的原子数量多，这显然不会很好地工作。您可能需要做的是在 GA 中编码一系列权重/参数，这些权重/参数附加到获取棋盘位置并触发移动的东西，我相信这就是您在第二个建议中暗示的内容。

可能最简单的建议是使用某种通用函数逼近，例如神经网络；感知器或径向基函数是两种可能性。您可以将各个节点的权重编码到 GA 中，尽管还有其他相当合理的方法来训练神经网络，请参阅反向传播。您或许也可以对网络结构进行编码，这也有一个优势，我很确定已经对使用遗传算法开发神经网络进行了大量研究，因此您不会完全从头开始。

你仍然需要想出如何将电路板呈现给神经网络并解释它的结果。特别是，对于国际象棋，您必须注意很多动作都是非法的。如果您可以对棋盘进行编码并解释结果以便只显示合法的动作，那将是非常有益的。我建议实现系统的机制，然后使用不同的板表示来看看什么能带来好的结果。一些让你开始的想法可能是最重要的想法，尽管我不太相信它们中的任何一个都是特别好的方法：

  • 一个包含所有 64 个方格的位串，其中一个数字表示每个方格中存在的内容。最明显，但可能是一个相当糟糕的表示，因为需要做大量工作才能过滤掉非法动作。
  • 一个由所有 64 个方格依次组成的位串，其中一个数字表示可以移动到每个方格的内容。这样做的好处是体现了国际象棋的覆盖概念，您可以用自己的棋子尽可能多地覆盖棋盘，但仍然存在非法移动和处理友/敌棋子的问题。
  • 所有 32 块一个接一个的位串，其中一个数字表示该块在每个方格中的位置。

总的来说，虽然我认为国际象棋一开始是一个相当复杂的游戏，但我认为很难让一些东西达到标准，明显优于随机。我不知道 Stratego 是否更简单，但我强烈建议您选择一款相当简单的游戏。这将使您专注于获得正确的实现机制和游戏状态的表示。

无论如何希望这对你有一些帮助。

编辑：作为一个快速补充，值得研究一下标准国际象棋 AI 的工作方式，我相信大多数人都使用某种Minimax 系统。

于 2012-01-04T11:14:17.773 回答
1

当你说“战术”时，你的意思是你想让 GA 给你一个玩游戏的通用算法（即进化一个 AI）还是你想让游戏使用一个 GA 来搜索可能移动的空间来生成一个每回合移动？

如果你想做前者，那么考虑使用遗传编程（GP）。您可以尝试使用它为固定的树大小生成最好的 AI。JGAP 也已经提供了对 GP 的支持。有关此示例，请参阅JGAP Robocode 示例。这种方法确实意味着您需要一种针对 Stratego AI 的领域特定语言，因此您需要仔细考虑如何将电路板和部件暴露给它。

使用 GP 意味着您的健身功能可以是 AI 在固定数量的预编程游戏中的表现，但这需要一个好的 AI 玩家（或非常有耐心的人）开始。

于 2012-01-04T11:35:15.813 回答
0

@DonAndre 的回答对于运动是绝对正确的。一般来说，涉及基于状态的决策的问题很难用 GA 建模，需要某种形式的 GP（显式或如@DonAndre 建议的那样，本质上是声明性程序的树）。

在我看来，一个普通的 Stratego 玩家似乎很有挑战性，但如果你有一个合理的 Stratego 游戏程序，“设置你的 Stratego 板”将是一个很好的 GA 问题。您的棋子的初始位置将是表型，外部战略播放代码的结果将是适应度。直觉上，随机设置可能会比具有一些“好主意”的设置处于不利地位，并且可以将小的“好主意”组合成更合适的设置。

...

关于什么决策树的一般问题，即使试图提出一个简单的例子，我一直发现很难提出一个足够小的例子，但也许在你评估是否攻击同等级的情况下一块（哪个，IIRC 摧毁了你和另一块？）：

double locationNeed = aVeryComplexDecisionTree();
if(thatRank == thisRank){
   double sacrificeWillingness = SACRIFICE_GENETIC_BASE; //Assume range 0.0 - 1.0
   double sacrificeNeed = anotherComplexTree(); //0.0 - 1.0
   double sacrificeInContext = sacrificeNeed * SACRIFICE_NEED_GENETIC_DISCOUNT; //0.0 - 1.0  
   if(sacrificeInContext > sacrificeNeed){
      ...OK, this piece is "willing" to sacrifice itself

一种或另一种方式，基本思想是你仍然有很多战略游戏的编码，你只是在寻找可以插入会改变结果的参数的地方。在这里，我想到了牺牲自己的“基本”倾向（可能在普通作品中更高）和“折扣”基因决定的参数，该参数将衡量该作品是否会“接受或拒绝”牺牲的需要。

于 2012-01-04T20:00:15.860 回答