目前我正在 Eralang 中实现一个草稿在线游戏服务器。（手机游戏）。我对 AI 方法有疑问。（无论是最小最大方法、遗传算法还是其他）。在定义适当的启发式函数时也存在问题。基本上我需要的是一个想法，如何在考虑语言、有限数量的资源和服务器响应时间（TIME OUT）的同时开始实施，因为这是一款在线手机游戏。
需要一些关于算法和启发式函数的想法。
问问题
2296 次
1 回答
3
正如我的人工智能教授曾经说过的那样：在游戏 AI 中，程序性能的主要区别在于细节而不是使用的算法。这种棋盘游戏使用的算法通常有 20-30 行长，人工智能引擎的强弱之处在于开发人员通过游戏细节利用来减少搜索空间的能力。只有对特定游戏有很好的了解，才能有效地做到这一点。
Checkers 有一个中等的搜索空间（事实上它已经完全解决了），但它是一个很好的起点，可以从棋盘游戏 AI 编程开始。出于这个原因，我建议您从经典的alpha-beta 剪枝算法开始。
但是，正如我之前所说，选择算法只是 10% 的工作。细节更为重要，让我们来看看它们：
启发式函数：这是一个关键点。启发式函数必须是：快速且易于计算并很好地描述给定状态的值。通常，启发式函数只是一组特征的加权和。在本文中，您可以找到一个简单的启发式函数（加上一种遗传方式来调整它），它使用诸如棋子数、国王数和移动性值（每个玩家的合法移动数）等特征。另一个提示：启发式函数应该返回整数值：只选择一个相差 0.0003 的分支是愚蠢的，因此最好将启发式四舍五入为整数值。
利用对称性：如果您可以在棋盘位置找到对称性，则必须将其考虑在内！在跳棋中没有太多的对称性，但我认为你仍然可以做一些事情。
预计算：这就是检查器已解决的方式。:) 但显然您不必存储所有内容。国际象棋 AI 通常有一个开局库和一个终局库。这些是预先计算的操作（或基于规则的操作），允许您的软件在开始和结束阶段避免大量计算。
探索轻松（被骗）问题：这是一个巨大的提示，对我有很大帮助。例如，你可以假设你可以连续做两步，而你的对手什么都不做。如果你作弊不能达到一个好位置，那么你在正常的游戏中就无法达到一个好位置（与试图反击你的对手），你可以简单地放弃这条路。
这只是我可以针对这个问题给你的一些小建议。我不能完整，因为这是一个非常大的领域，但我希望你明白这一点。你会通过经验找到新的更好的想法。:)
对于时间相关的问题：有时间限制的 AI 引擎使用alpha-beta 剪枝算法的迭代深化版本（本文中有详细信息和进一步的材料）。这种方法有两个主要优点：您可以随时停止计算，并且可以使用之前的迭代来改进下一次的搜索启发式。此外，如果您必须多次重新启动搜索，这绝对优于传统的 alpha-beta 修剪算法。
我希望你能发现这很有用。
于 2014-01-05T12:16:07.663 回答