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

Question

对于我的学士论文,我想写一个学习玩Stratego游戏的遗传算法(如果你不知道这个游戏,假设我说国际象棋可能是安全的).我以前从未做过实际的人工智能项目,所以看到我实际上对实现的了解有点少,这让人大开眼界.

我坚持的事情是为实际策略提供一个很好的代表.我可能会犯一些思考错误,但遇到的一些问题:

• 我不认为你会有一个包含董事会职位之间很多转换的表示,因为那只会强制它,对吧？
• 决策树的分支看起来像什么？我提出的任何表示都没有可互换的分支......如果我要使用一个字符串,这显然也很常见,这些位代表什么？
• 我是否将分数分配给某些部分之间的距离？我怎么代表那个？

我认为经过三年多的学习后我应该知道这些事情,所以我觉得很愚蠢 - 这看起来像我根本没有任何线索.仍然,任何关于谷歌的帮助或提示将不胜感激!

Answer 1

我认为,您可以定义决策模型,然后尝试优化该模型的参数.您也可以创建多阶段决策模型.我曾经做过类似的事情,通过将其建模为两阶段线性决策问题来解决动态拨号问题(此处为纸).举个例子,您可以:

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

2. 用你选择的数字行事.同样,可以采取一定数量的行动,每个行动都有某些特征.您可以再次对它们进行组合和排名,并且一个操作将具有最高优先级.这是您选择执行的操作.

您提取的功能可能非常简单或非常复杂,它取决于您认为最佳效果与计算时间长度相关的功能.

为了评估和改善决策模型的质量,您可以在几个游戏中针对对手模拟这些决策,并训练组合这些特征的模型参数以对移动进行排名(例如使用GA).通过这种方式,您可以调整模型以赢得尽可能多的游戏以对抗指定的对手.您可以通过对抗前所未见的对手来测试该模型的一般性.

正如Mathew Hall所说,你可以使用GP(如果你的模型是一个复杂的规则),但这只是一种模型.在我的例子中,权重的线性组合非常好.

顺便说一下,如果你感兴趣我们还有一个启发式优化软件,它为你提供GA,GP和那些东西.它叫做HeuristicLab.它是GPL和开源,但附带一个GUI(Windows).我们有一些关于如何评估外部程序中的适应度函数(使用协议缓冲区进行数据交换)的方法,因此您可以处理模拟和决策模型,并让HeuristicLab中的算法优化您的参数.