如何为游戏创建良好的评估功能?
artificial-intelligence
machine-learning
5
0

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

但是,现在我正在编写一个程序来玩一个全新的棋盘游戏。如何选择良好甚至不错的评估功能?

主要的挑战是相同的棋子总是在棋盘上,因此通常的材质功能不会根据位置而改变,并且游戏已进行了不到一千次左右,因此人类不一定玩得足够还没有提供见解。 (PS。我考虑过采用MoGo方法,但随机游戏不太可能终止。)

游戏详细信息 :游戏以10 x 10的局面进行,每边固定6块。这些棋子有一定的移动规则,并且以某些方式相互作用,但从未捕获到任何棋子。游戏的目标是在棋盘上的某些特殊方块中放置足够的棋子。该计算机程序的目标是提供一种与当前人类玩家竞争或比其更好的玩家。

参考资料:
Stack Overflow
收藏
评论
共 6 个回答
高赞 时间 活跃

为您的评估功能找到一些候选者,例如移动性(可能的动作数)减去对手的移动性,然后尝试为每个指标找到最佳权重。遗传算法似乎可以很好地优化评估函数中的权重。

创建一个具有随机权重的种群,以有限的深度和转弯相互对抗,用获胜者的随机组合替换失败者,随机播放并重复,在每一代之后打印出种群平均值。让它运行,直到您对结果满意为止,或者直到您发现有必要调整某些指标的范围并再试一次(如果一个指标的最佳值可能超出了您的初始范围)。

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

收藏
评论

如果还没有人了解游戏,那么您将无法获得不错的评估功能。不要告诉我带有材料数量的标准alpha-beta对于国际象棋或其变体是好的,甚至是不错的(也许输家的国际象棋是一个例外)。

您可以尝试使用具有反馈或类似机器学习算法的神经网络,但是它们通常会很费劲,直到经过大量训练为止,在这种情况下可能无法使用。即使这样,如果它们不吸吮,您也无法从中获得知识。

我认为,最好的方法是尽一切可能对游戏初学者有所了解,并且,对于初学者,将未知数留在评估功能上是随机的(或者只是在画面之外,直到未知数变得更加知名为止)。

当然,如果您要分享有关游戏的更多信息,则可以从社区中获得更好的想法。

收藏
评论

我将从一些基础知识开始,然后再介绍一些较难的内容。

基本代理和测试框架

无论采用哪种方法,都需要从一个简单而愚蠢的东西开始。愚蠢的代理人最好的方法是随机选择(生成所有可能的动作,随机选择一个)。这将作为比较所有其他代理的起点。您需要一个强大的比较框架。需要采取各种措施的代理人,允许他们之间玩一些游戏并返回性能矩阵。根据结果,您可以计算每个业务代表的适合度。例如,您的函数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是最好的, agent1agent2并没有真正的区别。

因此,一旦完成这两项重要的设置,您就可以尝试使用评估功能了。


让我们从选择功能开始

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

  2. 然后,您可以运用人的才智找到游戏状态的某些功能。首先要做的是与游戏专家交谈,并询问他如何进入该职位。

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

  4. 在这一点上,您实际上不需要知道这些功能如何影响游戏。特征示例:件的价值,件的可移动性,重要位置的控制,安全性,可能移动的总数,完成的接近性。

  5. 在对这些功能进行了编码并分别使用它们以查看最有效的方法(不要急于放弃本身无法正常发挥作用的功能后,它们可能会与其他功能结合使用)之后,您就可以尝试组合使用了。

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

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

  2. 使用神经网络的反向传播思想从游戏结束时反向传播错误,以更新网络的权重。您可以阅读更多有关步步高的操作方法 (我还没有写过类似的东西,为简短而感到抱歉)。

您可以不使用评估功能!对于只听说过minimax / alpha-beta的人来说,这听起来很疯狂,但是有些方法根本不需要评估。其中之一被称为“ 蒙特卡洛树搜索” ,顾名思义,“蒙特卡洛”暗示它使用了大量随机(不应该是随机的,它可以使用您以前的好代理商)游戏来生成一棵树。这本身就是一个巨大的话题,因此,我将为您提供真正的高级解释。您从根开始,创建边界,然后尝试扩展边界。一旦扩展了某些内容,您就可以随意进入叶子。从叶中获取结果,然后反向传播结果。进行多次此操作,并收集有关当前边界每个子级的统计信息。选择最好的一个。那里有一个重要的理论,涉及如何在勘探与开发之间取得平衡,而阅读UCT(上置信度上限算法)是一件好事

收藏
评论

我将研究一种监督式机器学习算法,例如强化学习。查看棋盘游戏中的强化学习 。我认为这将为您提供一些指导。

另外,请查看基于强化学习的游戏《奥赛罗》的策略获取 (PDF链接),其中根据游戏规则给出了良好的“回报功能”。这与TD-Gammon密切相关...

在训练过程中,神经网络本身用于选择双方的动作...令人惊讶的发现是,即使在使用原始板编码的零初始知识实验中,实际上也进行了大量学习。

收藏
评论

据我了解,您希望在min-max树的叶子上使用良好的静态评估函数。如果是这样,最好记住该静态评估功能的目的是提供有关该板对计算机播放器的良好程度的评估。也是

f(板1)> f(板2)

那么,必定是board1对于计算机(最终获胜的可能性)要比board2更好。当然,没有静态功能对所有板卡都完全正确。

因此,您说“游戏的目标是在棋盘上的某些特殊正方形中放置足够的棋子”,因此,首先击中f(board)就是计算计算机在棋盘上拥有的棋子数特殊方块。然后,您可以进行更多处理。

如果不知道游戏的细节,就不可能给出更好的猜测。如果您给我们提供了游戏规则,我相信stackoverflow用户将能够为此类功能提供大量的原始创意。

收藏
评论

尽管您可以使用各种机器学习方法来提供评估功能(在诸如gnubackgammon这样的项目中使用的TD-Learning是这样的示例),但结果肯定取决于游戏本身。对于西洋双陆棋,它的效果非常好,因为游戏的随机性(掷骰子)迫使学习者探索它可能不想做的领域。如果没有这样一个至关重要的组成部分,您可能最终会获得一个评估功能,该功能对自己有利,对其他人不利。

由于物质差异可能不适用,因此流动性的概念是否重要-即您有多少种可能的举动?通常控制电路板的某个区域总比没有好吗?与玩游戏的人交谈,找出一些线索。

虽然最好具有尽可能好的评估功能,但还需要调整搜索算法,以便可以进行尽可能深的搜索。有时,这实际上更值得关注,因为具有medicore评估功能的深度搜索者可以胜过具有良好评估功能的浅层搜索。这一切都取决于领域。 (例如,gnubackgammon通过1层搜索来玩专家级游戏)

您还可以使用其他技术来提高搜索质量,最重要的是,拥有一个换位表来缓存搜索结果以进行合理的修剪。

我强烈建议您浏览这些幻灯片

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号