在游戏编程中，如何测试所使用的启发式是否一致？
我想到了一些针对大型（更高维度）井字游戏的启发式。如何检查其中哪些实际上一致？
无论如何，一致性是什么意思？
I have thought of some heuristics for a big (higher dimensions) tic-tac-toe game. How do I check which of them are actually consistent?
What is meant by consistency anyways?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
启发法为给定状态产生某种成本值。在这种情况下，一致性意味着一个状态的估计加上移动到下一个状态的成本小于或等于该新状态的估计。如果这不是真的，那么这意味着——如果启发式是准确的——从一种状态转换到下一种状态可能会产生负成本，这通常是不可能或不正确的。
当涉及到寻路时，这是直观的证明，因为您预计路径上的每一步都需要一些时间，因此步骤 1 的估计必须低于任何步骤 2 的估计。对于 tic- 来说可能有点复杂因为您可能必须任意决定系统中的“成本”是什么。如果您的启发式可以因走棋而上升或下降 - 例如。因为你用正数编码好的动作，用负数编码坏的动作——那么你的启发式就不能保持一致。
然而，缺乏一致的启发并不总是一个问题。如果没有最佳解决方案，您可能无法保证达到最佳解决方案，但与强力状态搜索相比，它仍然可以加快搜索速度。
Heuristics produce some sort of cost value for a given state. Consistency in this context means the estimate for a state plus the cost of moving to the next state is less than or equal to the estimate for that new state. If this wasn't true then it would imply that - if the heuristic was accurate - that transitioning from one state to the next could incur negative cost, which is typically impossible or incorrect.
This is intuitive to prove when it comes to pathfinding, as you expect every step along the path to take some time, therefore the estimate at step 1 must be lower than the estimate at any step 2. It's probably a bit more complex for tic-tac-toe since you probably have to arbitrarily decide what constitutes a 'cost' in your system. If your heuristic can go both up or down as a result of playing a move - eg. because you encode good moves with positive numbers and bad moves with negative numbers - then your heuristic cannot be consistent.
However, lack of a consistent heuristic is not always a problem. You may not be guaranteed of reaching an optimal solution without one, but it may still speed up the search compared to a brute force state search.
编辑：这个答案混淆了可采性和一致性。我已将其更正为可受理性，但最初的问题是关于一致性的，这个答案并没有完全回答问题。
您可以通过区分所有不同的情况来进行分析，从而证明您的启发式确实是可接受的。
对于知情搜索，当且仅当它低估到合适状态的“距离”时，对于搜索问题（例如，搜索游戏中的最佳移动），启发式才是可接受的。
示例：搜索通过城市之间的高速公路网络到达目标城市的最短路线。在这里，人们可以使用欧几里得距离作为一种启发：到目标的直线长度总是比最佳路径短或等长。
像 A* 这样的算法需要可接纳性，然后保证你是最优的（即它们将找到到达目标状态的最佳“路线”（如果存在）。
我建议您在 AI 教科书中查找该主题。
EDITED: This answer confused admissibility and consistency. I have corrected it to refer to admissibility, but the original question was about consistency, and this answer does not fully answer the question.
You could do it analytically, by distinguishing all different cases and thereby proving that your heuristic is indeed admissible.
For informed search, a heuristic is admissible with a search problem (say, the search for the best move in a game) if and only if it underestimates the 'distance' to a suitable state.
EXAMPLE: Search for the shortest route to a target city via a network of highways between cities. Here, one could use the Eucidean distance as a heuristic: the length of a straight line to the goal is always shorter or equally long than the best possible way.
Admissibility is required by algorithms like A*, which then quarantuee you to be optimal (i.e. they will find the best 'route' to a goal state if one exists).
I would recommend to look the topic up in an AI textbook.