记忆化搜索在ab剪枝中的问题

Question

对于对抗搜索的情况，如果用ab剪枝的话，再加记忆化搜索就会出现不正确的结果，目前没有解决思路，望老师指点一二，谢谢！

Answer 1

liuyubobobo 2022-09-26 12:16:26

记忆化搜索的前提是：搜索的状态是有重叠子问题的，而不是任何搜索都可以记忆化。你的问题大概率是没有重叠字问题的。

虽然我不知道你说的“对抗搜索”具体指什么，但是大多数人工智能中的搜索都是没有重叠字问题的（否则人工智能就太简单了。因为有重叠子问题意味着可以把指数级的搜索降到多项式级别。）

继续加油！：）

• 提问者 慕粉2011219583 #1

  老师，是这样，我在尝试用算法解决一个黑白棋的残局，目前测试的结果是这样的
  1、纯最大最小搜索，耗时 8 秒，结果正确
  2、加入记忆化搜索的最大最小，耗时 1 秒，结果正确
  3、纯ab搜索，耗时 0.5 秒，结果正确
  4、加入记忆化搜索的ab搜索，结果 不正确

• liuyubobobo 回复 提问者 慕粉2011219583 #2

  依然是，大概率是你的 ab 搜索的状态没有构成重叠子问题，所以直接加记忆化是错误的。依然是：不是所有的搜索都可以直接加记忆化。（或者说没有重叠子问题的情况下，正确的加记忆化和没有加区别不大。因为记忆空间和搜索空间一样大。）

• 提问者 慕粉2011219583 回复 liuyubobobo #3

  奥，这么说我好像明白了，感谢老师解答！

Answer 2

提问者 慕粉2011219583 2022-09-26 11:37:34

猜测可能是当前重叠子问题的结果并不是其他子问题的最终结果