如何为游戏创建良好的评估功能？

Question

我有时会编写程序来玩棋盘游戏.基本策略是标准的alpha-beta修剪或类似的搜索,有时通过终结游戏或开放的常用方法来增强.我主要使用国际象棋变体,所以当需要选择我的评估功能时,我会使用基本的国际象棋评估功能.

但是,现在我正在编写一个程序来玩一个全新的棋盘游戏.我如何选择一个好的甚至是体面的评估函数？

主要的挑战是相同的棋子总是在棋盘上,因此通常的材料功能不会根据位置而改变,并且游戏的播放次数不到一千次左右,所以人类不一定玩得太多还没有给出见解.(PS.我考虑过MoGo方法,但随机游戏不太可能终止.)

游戏细节:游戏在10×10的棋盘上进行,每侧固定6个棋盘.这些作品具有一定的运动规则,并以某种方式相互作用,但没有任何一块被捕获.游戏的目标是在棋盘上的某些特殊方块中放置足够的棋子.计算机程序的目标是提供与当前人类玩家竞争或更好的玩家.

Answer 1

我将从一些基础开始,然后转向更难的东西.

基本代理和测试框架

无论你采取什么方法,你都需要从一些非常简单和愚蠢的事情开始.哑代理的最佳方法是随机的(生成所有可能的移动,随机选择一个).这将作为比较所有其他代理商的起点.你需要一个强大的框架来进行比较.需要各种代理的东西允许在它们之间玩一些游戏并返回性能矩阵.根据结果​​,您可以计算每个代理的适用度.例如,你的函数tournament(agent1, agent2, agent3, 500)将在每对代理之间玩500场比赛(播放第一个/第二个)并返回如下内容:

  x         -0.01       -1.484   |  -1.485
0.01          x         -1.29    |  -1.483
1.484       1.29          x      |  2.774

例如,我使用2点获胜,1点使用抽奖评分功能,最后只需将所有内容相加以找到适合度.这张表立即告诉我这agent3是最好的,并agent1没有真正的不同agent2.

因此,一旦设置了这两个重要的事项,您就可以尝试使用您的评估函数了.

让我们从选择功能开始

1. 首先,您需要创建not a terrible评估功能.通过这个我的意思是这个功能应该正确识别3个重要方面(赢/抽/亏).这听起来很明显,但我已经看到了大量的机器人,创作者无法正确设置这三个方面.

2. 然后你用你的人类聪明才智找到游戏状态的一些特征.首先要做的是与游戏专家交谈并询问他如何获得该职位.

3. 如果您没有专家,或者您甚至在5分钟前创建了游戏规则,请不要低估人类搜索模式的能力.即使在玩了几场比赛之后,一个聪明的人也可以给你一些他应该怎么玩的想法(这并不意味着他可以实现这些想法).将这些想法用作功能.

4. 此时,您并不需要知道这些功能如何影响游戏.特征示例:棋子的价值,棋子的移动性,重要位置的控制,安全性,可能移动的总数,接近终点.

5. 在对这些功能进行编码并单独使用它们以查看哪种功能最佳(不要急于丢弃那些本身不合理的功能,它们可能与其他功能相结合)时,您就可以尝试组合了.

通过组合和加权简单功能来构建更好的评估.有几种标准方法.

1. 根据功能的各种组合创建超级功能.它可以是线性的eval = f_1 * a_1 + ... f_n * a_n(f_i特征,a_i系数),但它可以是任何东西.然后为此评估函数实例化具有绝对随机权重的许多代理,并使用遗传算法相互重复播放它们.使用测试框架比较结果,丢弃几个明显的输家并改变几个赢家.继续相同的过程.(这是一个粗略的概述,阅读有关GA的更多信息)

2. 使用来自神经网络的反向传播思想来反馈从游戏结束传播错误以更新网络的权重.你可以阅读更多关于如何使用步步高完成的事情(我没有写过类似的东西,很抱歉这个简短).

您可以在没有评估功能的情 对于只听过minimax/alpha-beta的人来说,这可能听起来很疯狂,但有些方法根本不需要评估.其中一个被称为蒙特卡罗树搜索,并且作为名称中的蒙特卡罗表示它使用大量随机(它不应该是随机的,它可以使用您之前的好代理)游戏来生成树.这本身就是一个很大的话题,所以我会给你我真正的高级解释.您从root开始,创建您尝试扩展的边界.一旦你展开了什么,你就可以随机地去看看.从叶子中获取结果,您反向传播结果.多次这样做,并收集有关当前边界的每个孩子的统计数据.选择最好的一个.那里有一个重要的理论,它涉及如何在探索和开发之间取得平衡,并且有一个好的东西可以阅读有UCT(上置信界限算法)

Answer 2

为您的评估功能找到一些候选人,例如移动性(可能移动的数量)减去对手的移动性,然后尝试找到每个度量的最佳权重.遗传算法似乎在评估函数中优化权重方面非常有效.

创建一个随机权重的群体,以有限的深度和轮流对抗它们,用获胜者的随机组合替换失败者,随机播放和重复,在每一代后打印出人口平均值.让它一直运行,直到您对结果满意为止,或直到您看到需要调整某些指标的范围并再试一次,如果看起来某个指标的最佳值可能超出了您的初始范围.

后期编辑:当时我不知道的一种更被接受,研究,理解的方法是"差异进化".后代是由3个父母而不是2个父母创建的,这样可以避免过早收敛到平均值的问题.