在游戏编程，我怎么可以测试使用的启发式是否一致或不？

Question

我已经想到一些的启发式作为一个大的（更高的维度）井字棋游戏。如何检查哪些是真正的 一致的的

何谓的稠度反正？

Answer 1

EDITED：此答案混淆受理和一致性。我已经改正它来指受理，但原来的问题是关于一致性，这个答案并不完全回答这个问题。

您可以做到这一点分析，通过区分各种不同的情况，从而证明的你的启发确实是可接受的。

有关知情搜索，启发式是受理与搜索问题（比如说，搜索用于在游戏中最好的移动），当且仅当它的低估的“距离”，以一个合适的状态。

例如：检索用于通过城市之间的高速公路的网络到目标城市的最短路线。在这里，人们可以使用Eucidean距离作为启发：直线目标的长度总是短或同样长比最好的方式。

容许由算法所需如 A * ，然后quarantuee你是最佳（即，它们将找到最好的“路线到一个目标状态如果存在）。

我会建议找话题了在 AI教科书。

Answer 2

启发式产生某种成本值的对于给定的状态。一致性在本文中是指一个状态加上移动到下一个状态的成本的估计小于或等于所述估计为新的状态。如果这不是真的，那么这将意味着 - 如果启发式是准确的。 - 从一个状态转换到下一个可能招致负成本，这通常是不可能的或不正确的

这是直观的证明，当涉及到寻路，像您期望的路径上每一步都需要一定的时间，因此在步骤1中的估计必须比在任何步骤2.估计下这可能是一个更复杂一点对于井字棋，因为你可能有随意决定什么是在你的系统中的“成本”。如果你的启发式可以去两个向上或向下打一招的结果 - 例如。因为你与编码正数和负数坏移动好棋 - 那么你的启发不能保持一致。

然而，缺乏一致的启发式的并不总是一个问题。你可能不被保证没有一个达到最佳的解决方案，但它仍可能加快搜索相比蛮力搜索状态