我已经想出了一些适用于大型（高维度）井字棋游戏的启发式策略。如何检查它们中哪些实际上是一致的?
“一致性”究竟是什么意思呢？
游戏编程中，我该如何测试所使用的启发式算法是否一致？
11
- Lazer
2
2这是一个真正的问题。 - Stefan Kendall
3有两个人标记此问题为“不是一个真正的问题”。我也不同意他们的看法。 - Kylotan
2个回答
1
启发式算法会为给定状态产生某种成本值。在这个语境中，一致性意味着一个状态的估计加上移动到下一个状态的成本小于或等于那个新状态的估计。如果这不成立，那么它意味着 - 如果启发式准确的话 - 从一个状态到另一个状态的转换可能会产生负成本，这通常是不可能或不正确的。
当涉及到路径查找时，这很容易证明，因为你期望路径上的每一步都需要一些时间，因此步骤1的估计必须低于任何步骤2的估计。对于井字游戏来说可能更复杂，因为你可能不得不任意决定在你的系统中什么构成了“成本”。如果你的启发式可以由于玩一次棋而向上或向下，例如，因为你用正数编码好的走法和用负数编码坏的走法，那么你的启发式就不能保持一致。
然而，缺乏一致的启发式并不总是一个问题。你可能无法保证没有一种最优解，但相比于暴力的状态搜索，它可能仍然能够加速搜索。
- Kylotan
0
编辑：此答案混淆了可接受性和一致性。我已经更正为指称可接受性，但原问题是关于一致性的，这个答案并不能完全回答问题。
你可以通过分析区分所有不同情况，从而“证明”你的启发式确实是可接受的。
对于有信息的搜索，如果一个搜索问题（比如在游戏中寻找最佳移动）的启发式是可接受的，那么它只有在低估到达目标状态的“距离”时才能成立。
示例：在城市之间的高速公路网络上搜索到达目标城市的最短路径。在这里，可以使用欧几里得距离作为启发式：直线到目标的长度总是比最佳路径短或者等长。
算法如 A*需要启发式函数是可接受的，这样就保证了算法的最优性（即，如果存在最佳路径，则会找到最佳路径）。
我建议你在人工智能教材中查找这个主题。
- Roland Ewald
1
8启：区分可接受和一致的启发式函数，尽管所有一致的启发式函数都是可接受的。可接受的意思是启发式函数低估了总路径成本，而如果在经过一步后启发式函数减少的不超过此步费用，则为一致的。 - Mark McDonald
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接