我有时会编写程序来玩棋盘游戏。基本策略是标准的 alpha-beta 修剪或类似搜索，有时会通过通常的残局或开局方法来增强。我主要玩国际象棋变体，所以当需要选择我的评估函数时，我使用基本的国际象棋评估函数。
但是，现在我正在编写一个程序来玩一个全新的棋盘游戏。如何选择一个好的甚至像样的评估函数？
主要挑战是相同的棋子总是在棋盘上，所以通常的材质函数不会因位置而改变，而且游戏已经玩了不到一千次左右，所以人类不一定会玩够还没有给出见解。（PS。我考虑过 MoGo 方法，但随机游戏不太可能终止。）
游戏详情：游戏在 10×10 棋盘上进行，每边固定 6 个棋子。这些棋子有一定的运动规则，并以一定的方式相互作用，但从来没有一个棋子被捕获。游戏的目标是在棋盘上的某些特殊方格中有足够的棋子。计算机程序的目标是提供与当前人类玩家竞争或更好的玩家。
我将从一些基础开始，然后再转向更难的东西。
基本代理和测试框架
无论你采取什么方法，你都需要从一些非常简单和愚蠢的事情开始。哑代理的最佳方法是随机的（生成所有可能的动作，随机选择一个）。这将作为比较所有其他代理的起点。您需要一个强大的比较框架。需要各种代理的东西，允许在它们之间玩一些游戏并返回性能矩阵。根据结果，您可以计算每个代理的适应度。例如，您的函数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.
因此，一旦设置了这两个重要的东西，您就可以尝试使用您的评估功能了。
让我们从选择特征开始
首先，您需要创建not a terrible评估函数。我的意思是这个函数应该正确识别 3 个重要方面（赢/平/输）。这听起来很明显，但我见过大量的机器人，其中创建者无法正确设置这三个方面。
然后你用你人类的聪明才智去寻找游戏状态的一些特征。首先要做的是与游戏专家交谈并询问他如何获得该职位。
如果您没有专家，或者您只是在 5 分钟前创建了游戏规则，请不要低估人类搜索模式的能力。即使在玩了几场比赛之后，一个聪明的人也可以给你他应该怎么玩的想法（这并不意味着他可以实现这些想法）。将这些想法用作特征。
此时，您实际上并不需要知道这些功能如何影响游戏。特征示例：棋子的价值、棋子的移动性、重要位置的控制、安全性、可能的移动总数、接近终点。
在您对这些功能进行编码并分别使用它们以查看最有效的功能之后（不要急于丢弃本身性能不合理的功能，它们可能会与其他功能一起使用），您就可以尝试组合了。
通过组合和加权简单特征来构建更好的评估。有几种标准方法。
根据您的功能的各种组合创建一个超级功能。它可以是线性的eval = f_1 * a_1 + ... f_n * a_n（f_i特征、a_i系数），但它可以是任何东西。然后为这个评估函数实例化许多具有绝对随机权重的代理，并使用遗传算法让它们相互竞争。使用测试框架比较结果，丢弃几个明显的失败者并改变几个获胜者。继续相同的过程。（这是一个粗略的大纲，请阅读有关 GA 的更多信息）
使用神经网络的反向传播思想从游戏结束时反向传播错误以更新网络的权重。你可以阅读更多关于步步高是如何完成的（我没有写过类似的东西，很抱歉简短了）。
您可以在没有评估功能的情况下工作！对于只听说过 minimax/alpha-beta 的人来说，这可能听起来很疯狂，但有些方法根本不需要评估。其中之一称为蒙特卡洛树搜索正如名字中的蒙特卡洛所暗示的那样，它使用大量随机（它不应该是随机的，它可以使用你以前的好代理）游戏来生成一棵树。这本身就是一个巨大的话题，所以我会给你我的高层次的解释。你从一个根开始，创建你的边界，你试图扩展它。一旦你扩展了一些东西，你只是随机地去叶子。从叶子中获取结果，然后反向传播结果。多次这样做，并收集有关当前边界的每个孩子的统计信息。选择最好的。那里有一个重要的理论，它与你如何在探索和利用之间取得平衡有关，还有一个值得阅读的好东西是 UCT（上限置信度算法）
为您的评估函数找到一些候选者，例如移动性（可能移动的数量）减去对手的移动性，然后尝试为每个指标找到最佳权重。遗传算法似乎可以很好地优化评估函数中的权重。
创建一个具有随机权重的种群，在有限的深度和回合中相互对抗，用获胜者的随机组合替换失败者，洗牌并重复，在每一代之后打印出总体平均值。让它一直运行，直到您对结果感到满意，或者直到您发现需要调整某些指标的范围，然后再试一次，如果某个指标的最佳值可能超出您的初始范围。
后期编辑：我当时不知道的一种更被接受、研究和理解的方法是所谓的“差异进化”。后代是由 3 个父母而不是 2 个创建的，这样可以避免过早收敛到平均值的问题。
我会研究一种有监督的机器学习算法，例如强化学习。查看棋盘游戏中的强化学习。我认为这会给你一些很好的研究方向。
此外，查看基于强化学习的黑白棋游戏策略获取（PDF 链接），在给定游戏规则的情况下，可以学习良好的“支付函数”。这与TD-Gammon密切相关...
在训练过程中，神经网络本身用于为双方选择动作......相当令人惊讶的发现是，实际上发生了大量的学习，即使在使用原始棋盘编码的零初始知识实验中也是如此。
如果还没有人了解游戏，那么您就无法获得像样的评估功能。不要告诉我具有材料数量的标准 alpha-beta 对于国际象棋或其变体来说是好的甚至是体面的（也许失败者的国际象棋是一个例外）。
您可以尝试带有反馈或类似机器学习算法的神经网络，但它们通常很糟糕，直到它们进行大量训练，在这种情况下可能不可用。即使那样，如果他们不烂，你也无法从他们那里获得知识。
我认为你必须尽你所能地理解游戏，并且对于初学者来说，在评估函数中让未知数随机出现（或者在未知数变得更广为人知之前将其排除在外）。
当然，如果你想分享更多关于游戏的信息，你可以从社区中获得更好的想法。
据我了解，您希望在 min-max 树的叶子上使用一个好的静态评估函数。如果是这样，最好记住这个静态评估函数的目的是提供一个关于该板对计算机玩家有多好的评级。也是
f(板1) > f(板2)
那么 board1 肯定比 board2 更适合计算机（最终获胜的可能性更大）。当然，没有任何静态函数对所有电路板都是完全正确的。
因此，您说“游戏的目标是在棋盘上的某些特殊方格中拥有足够多的棋子”，因此 f(board) 的第一次尝试就是计算计算机在这些棋盘上的棋子数特殊的方格。然后，您可以更巧妙地处理它。
在不了解游戏细节的情况下，不可能给出更好的猜测。如果您向我们提供游戏规则，我相信 stackoverflow 用户将能够为此类功能提出大量原创想法。
虽然您可以使用各种机器学习方法来提出评估函数（TD-Learning，在 gnubackgammon 等项目中使用，就是这样一个例子），但结果肯定取决于游戏本身。对于西洋双陆棋来说，它的效果非常好，因为游戏的随机性（掷骰子）迫使学习者去探索它可能不想做的领域。如果没有这样一个关键组件，您最终可能会得到一个对自己有利但对他人不利的评估函数。
由于物质差异可能不适用，移动性的概念是否重要——即你有多少可能的移动？控制董事会的某个区域通常比不控制更好吗？与玩游戏的人交谈以找出一些线索。
虽然最好拥有尽可能好的评估函数，但您还需要调整搜索算法，以便尽可能深入地搜索。有时，这实际上更令人担忧，因为具有 medicore 评估功能的深度搜索器可以胜过具有良好评估功能的浅层搜索。这完全取决于域。（例如，gnubackgammon 使用 1 层搜索玩专家游戏）
您可以使用其他技术来提高搜索质量，最重要的是，拥有一个转置表来缓存搜索结果以进行健全的前向修剪。
我强烈建议您查看这些幻灯片。
您还需要谨慎选择。如果您的算法与实际值没有已知关系，则标准 AI 函数将无法正常工作。为了有效，您的评估函数或启发式必须始终与实际值相同或低于实际值，否则它会以一种奇怪的方式指导您的决定（即使我认为标准点很好，也可能会为国际象棋争论） ）。
我通常做的是找出什么是有能力的，什么是需要的。对于某些游戏，例如推箱子，我使用了将一个盒子（孤立地）从当前位置移到任何目标位置所需的最少盒子移动次数。这不是所需移动数量的准确答案，但我认为这是一个很好的启发式方法，因为它永远不会高估并且可以为整个棋盘预先计算。当对棋盘的分数求和时，它只是每个当前框位置的值的总和。
在我编写的用于进化猎群和猎群防御的人工生命模拟中，我使用的评分系统仅用于指导进化而不进行任何修剪。我给每个生物一个出生点。对于他们在生活中消耗的每一点能量，我给了他们一分。然后，我使用它们产生的点的总和来确定每个点的繁殖可能性。在我的情况下，我只是使用了他们获得的这一代总积分的比例。如果我想进化出擅长躲避的生物，我会因为从它们身上吃掉分数而得分。
您还应该注意您的功能不是太难实现的目标。如果你想进化一些东西，你要确保解决方案空间有一个合适的斜率。你要引导进化朝着一个方向发展，而不是在碰巧随机命中时宣布胜利。
如果不了解您的游戏的更多信息，我将很难告诉您如何构建功能。是否有明确的价值表明胜利或失败？你有办法估算缩小差距的最低成本吗？
如果您提供更多信息，我很乐意尝试提供更多见解。也有很多关于这个主题的优秀书籍。
雅各布
请记住，一个体面的评估函数甚至不一定存在。对于这个陈述，我假设，评估函数必须具有低复杂度 (P)。