alpha-beta搜索是个很好的搜索方法，在这基础之上为了加快搜索速度，为了让程序搜索到更深的局面中去，才引入了置换表（实际上大部分棋类程序是离不开置换表的，像象棋，我可以让车左右重复走动，那相同的局面会一直出现，直接搜索真是费尽了力气）。

置换表实际上就是一个哈希表，它存储的是之前搜索过的局面，可以是一次搜索时遇到的相同局面，也可以是多次搜索时遇到的相同局面。它工作的时候，简单的来说，就是当搜索一个局面时，首先看是否在哈希表中，如果是直接取出来，而不进行搜索，同时每当完成一次搜索后，就把搜索出的结果存进哈希表。

这个表中要放些什么？
首先是评价值，在alpha-beta搜索中，有三种不同类型的评价值，alpha型：它在搜索的子结点中没有找到比当前最好的更好，也就是说至多是那么多，beta型：它在搜索的子结点中有比当前最差的更差，也就是说至少是那么多（差），如果搜出的评价值落在alpha-beta之间，那就是exact型，精确型。其次要放搜索深度，如果当前要对局面进行d层搜索，而发现该局面在置换表中存在，且搜索过d'层（d'>=d），那就可以直接取出来不进行搜索了。最后还有最佳着法。

置换表如何哈希？
比较常见的是使用Zobrist键值，这只是一种哈希方法，简单来看就是随机哈希。一个局面有哪些因素：当前谁走棋，每一格上有哪种类型棋，棋子的颜色，等等，我们把所有因素全部用随机数表示，然后将它们进行模2加得到的结果就看成是当前局面的一个key。拿黑白棋来说，可以这样表示Zobrist[pos][color]来表示局面上的棋子，pos取0~63,color取0~1，将局面上所有值模2加起来，然后如果是黑先就得到key，如果是白先就将它取反得到key，整个Zobrist[][]以64位的随机数填满。将得到的key再模上哈希表表长就得到了哈希值。哈希表最重要的是进行冲突处理，我看到一些程序根本没有冲突处理，想了好久不得其解，细细思来：冲突产生的原因在哪？可能是不同的局面得到了相同的key，也可能是不同的key存到了相同的哈希表位置，如果是前者，大可以不必担心，采用64位的Zobrist键值，随机性很大，如果随机数取得好，‘撞’到相同key的机率非常之低，如果是后者那就会产生非常严重的后果，当前局面分明没有搜索过，却和另外一个局面的哈希值一样，而误以为搜索过，而产生了截断，大错特错！解决的方法是在表项中增加一项校验值，同样是64位的ZobristKey。在搜索的过程中不进行冲突处理，如果发现冲突，或者不处理，或者直接覆盖掉，置换表的作用是在加快搜索速度，那些搜索过的局面在我们看来未必重要，使用了置换表同样是alpha-beta，并没有更多的剪枝。但是，效果是非常明显的，它可以大大加深搜索的深度，在黑白棋里尤其在残局中，它可以到达的深度让电脑在离结束20多步时就知道了对局的结果！

迭代加深的策略一开始提出来，是为了控制搜索的深度，因为我不知道到底要搜索多深，或者搜索多深合适（如果搜索到20层需要1年时间显然不合适），于是我们可以设定一个超时计时器，伪代码像这样：

for(depth = 1 to MaxDepth)
{
   val=AlphaBeta(depth,-INFINITY,INFINITY);
   if(TIMEOUT())
      break;
}

事实上的实现，需要多线程，搜索函数由另一个线程启动，当超时时，由主线程通知搜索线程的结束，最好是让线程自己结束而不是强制结束。我的程序中用的是一个伪函数反射，用一个变量保存真正的搜索函数的地址，当要通知搜索结束的时候，只需要将这个变量的值改成另外一个函数的地址就会促使搜索的结束，这个函数什么事都不干，我称它为伪函数。这样搜索函数中就不需要多一些判断来决定是否退出或抛出异常了。

然而，迭代加深真正的目的却是很好的启发更深一层的搜索！我们知道，alpha-beta搜索过程中，对搜索的顺序是很重要的，如果一开始就搜到了很好的结点，那后面就会有大量的较差的结点很早的产生截断，这种优势会提高alpha-beta搜索的平均效率，分支因子会更大的降低！那如何获得这里的启发值？在那些着法中，怎么从较好的着法开始搜索呢？你大可以用估值函数来启发，这相当于搜索了一层的评价值，其实更好的做法是从置换表中得到较好的搜索顺序，置换表中有以前搜索过局面。可以这样做，如果置换表中的局面深度大于1层，那就用置换表中的启发，否则用估值函数启发。OK，那需要向置换表中增加另外的表项，这里的额外开销或许很大，这要看你如何表示棋盘，如何表示着法了。也就是说，如果没有置换表，迭代加深只是一种时间控制方法，如果有了转换表，那迭代加深就不仅仅是一种时间控制方法了（废话~^@^）！

rickone 2006/08/02

评论