`
sjl599
  • 浏览: 17317 次
  • 性别: Icon_minigender_1
  • 来自: 北京
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

基本搜索算法-置换表

阅读更多
《对弈程序基本技术》专题
 
置换表
 
Bruce Moreland / 文
 
一个多功能的数据结构
 
  国际象棋的搜索树可以用图来表示,而置换结点可以引向以前搜索过的子树上。置换表可以用来检测这种情况,从而避免重复劳动。如果“1. e4 d6 2. d4”以后的局面已经搜索过了,那就没有必要再搜索“1. d4 d6 2. e4”以后的局面了。
  这个原因可能鼓舞着早期的电脑国际象棋程序的设计师们,而现在事实上这还是置换表的次要用途。在某些局面,例如在没有通路兵的王兵残局中,检查到的置换的数量是惊人的,以至于搜索可以在短达时间内达到很深的深度。
  省去重复的工作,这是置换表的一大特色,但是在一般的中局局面里,置换表的另一个作用更为重要。每个散列项里都有局面中最好的着法,我在“迭代加深”这一章里解释过,首先搜索好的着法可以大幅度提高搜索效率。因此如果你在散列项里找到最好的着法,那么你首先搜索这个着法,这样会改进你的着法顺序,减少分枝因子,从而在短的时间内搜索得更深。
 
实现
 
  主置换表是一个散列数组,每个散列项看上去像这样:
 
#define hashfEXACT 0
#define hashfALPHA 1
#define hashfBETA 2
typedef struct tagHASHE {
 U64 key;
 int depth;
 int flags;
 int value;
 MOVE best;
} HASHE;
 
  这个散列数组是以“Zobrist键值”为指标的。你求得局面的键值,除以散列表的项数得到余数,这个散列项就代表该局面。由于很多局面都有可能跟散列表中同一项作用,因此散列项需要包含一个校验值,它可以用来确认该项就是你要找的。通常校验值是一个64位的数,也就是上面那个例子的第一个域。
  你从搜索中得到结果后,要保存到散列表中。如果你打算用散列表来避免重复工作,那么重要的是记住搜索有多深。如果你在一个结点上搜索了3层,后来又打算做10层搜索,你就不能认为散列项里的信息是准确的。因此子树的搜索深度也要记录。
  在Alpha-Beta搜索中,你很少能得到搜索结点的准确值。Alpha和Beta的存在有助你裁剪掉没有用的子树,但是用Alpha-Beta有个小的缺点,你通常不会知道一个结点到底有多坏或者有多好,你只是知道它足够坏或足够好,从而不需要浪费更多的时间。
  当然,这就引发了一个问题,散列项里到底要保存什么值,并且当你要获取它时怎样来做。答案是储存一个值,另加一个标志来说明这个值是什么含义。在我上面的例子中,比方说你在评价域中保存了16,并且在标志域保存了“hashfEXACT”,这就意味着该结点的评价是准确值16;如果你在标志域中保存了“hashfALPHA”,那么结点的值最多是16;如果保存了“hashfBETA”,这个值就至少是16。
  当你在搜索中遇到特定情况时,很容易决定评价和标志应该保存哪些内容。然而避免错误是非常重要的,散列表是非常容易犯错误的,而且一旦犯下错误就很难捕捉出来。
  我的散列项的最后一个域,保存着上次搜索到这个局面时的最佳着法。有时我没有得到最佳着法,比如任何低出边界的情况(返回一个小于或等于Alpha的值),而其他情况必定有最佳着法,比如高出边界的情况(返回一个大于或等于Beta的值)。【译注:只有叶子结点才没有最佳着法,即便是Alpha结点,所有的着法都是差的,也应该从中找一个最好的着法,它对更深一层的搜索会带来很大的好处。】
  如果找到最佳着法,那么它应该首先被搜索。
  下面是示范程序,是根据Alpha-Beta函数修改的,改动的地方用醒目的字标出:
 
int AlphaBeta(int depth, int alpha, int beta) {
 int hashf = hashfALPHA;
 if ((val = ProbeHash(depth, alpha, beta)) != valUNKNOWN) {
  // 【valUNKNOWN必须小于-INFINITY或大于INFINITY,否则会跟评价值混淆。】
  return val;
 }
 if (depth == 0) {
  val = Evaluate();
  RecordHash(depth, val, hashfEXACT);
  return val;
 }
 GenerateLegalMoves();
 while (MovesLeft()) {
  MakeNextMove();
  val = -AlphaBeta(depth - 1, -beta, -alpha);
  UnmakeMove();
  if (val >= beta) {
   RecordHash(depth, beta, hashfBETA);
   return beta;
  }
  if (val > alpha) {
   hashf = hashfEXACT;
   alpha = val;
  }
 }
 RecordHash(depth, alpha, hashf);
 return alpha;
}
 
  以下就是两个新的函数的代码:
 
int ProbeHash(int depth, int alpha, int beta) {
 HASHE *phashe = &hash_table[ZobristKey() % TableSize()];
 if (phashe->key == ZobristKey()) {
  if (phashe->depth >= depth) {
   if (phashe->flags == hashfEXACT) {
    return phashe->val;
   }
   if ((phashe->flags == hashfALPHA) && (phashe->val <= alpha)) {
    return alpha;
   }
   if ((phashe->flags == hashfBETA) && (phashe->val >= beta)) {
    return beta;
   }
  }
  RememberBestMove();
 }
 return valUNKNOWN;
}
 
void RecordHash(int depth, int val, int hashf) {
 HASHE *phashe = &hash_table[ZobristKey() % TableSize()];
 phashe->key = ZobristKey();
 phashe->best = BestMove();
 phashe->val = val;
 phashe->hashf = hashf;
 phashe->depth = depth;
}
 
  你所看到的代码,并不像航天科学一样准确,而是很可能有错误的,而且细节上的问题我还没有讨论。如果你的程序中有错误,或许就是很严重的错误。
  【以上代码有个速度上的瓶颈,即“ZobristKey() % TableSize()”这个表达式。由于“电脑一做除法就成了傻瓜”,所以“TableSize”最好是一个2n的常量,只有当除数是2n时除法才可以由右移指令取代。最好的方法是设一个“TableSizeMask”的变量:
 
int TableSizeMask = TableSize() - 1;
HASHE *phashe = &hash_table[ZobristKey() & TableSizeMask];
 
  而这里“TableSize()”也必须是2n。正是这个道理,在很多可以设定置换表大小的国际象棋程序中,允许的设定值总是呈倍数增长的,要么是3M、6M、12M、24M等等(如果每个散列项有12字节),要么是4M、8M、16M、32M等等(如果每个散列项有16字节)。】
 
替换策略
 
  最主要的细节就包括,什么时候该覆盖散列项。在上面的例子中,我用了“始终替换”的策略,即简单地覆盖已经存在的值。这或许不是最好的策略,事实上已经有大量的工作试图找出哪个策略是最好的。
  另一个策略是“同样深度或更深时替换”。除非新局面的深度大于或等于散列表中已经有的值,否则已经存在的结点将被保留。
  还有很多试验的余地。1994年我在Usenet(新闻组网络系统)的新闻组rec.games.chess(如今是rec.games.chess.computer)上问了这个问题,得到了Ken Thompson的答复。
  他的回答是使用两个散列表。一个使用“始终替换”策略,另一个使用“同样深度或更深时替换”。当你做试探时,两个散列表都去试探,如果其中一个可以产生截断,那就可以了。如果两者都不能产生截断,那么你可能至少得到一个最佳着法,实际上更多的可能是得到两个不同的着法,两者都应该首先(或第二个)尝试。
  记录的时候,你只要简单地根据替换策略来执行。
  如果你使用“同样深度或更深时替换”的策略,那么你的散列表可能最终会被过期的但很深的结点所占满。解决方案就是每次你走棋时都清除散列表,或者在散列项中加入“顺序”这个域,从而使这个策略变成变成“同样深度,或更深,或原来是旧的搜索,才替换”。
  我在我的程序Ferret中使用了Thompson的策略,并且运行得很好。另一个程序Gerbil也使用这个策略,你可以去看它的源代码。
  【根据译者研究的结果,只用“深度优先覆盖”策略(即“同样深度或更深时替换”),效果会比“始终替换”好得多,而代码则并不复杂,只有醒目的部分是新增的:
 
void RecordHash(int depth, int val, int hashf) {
 HASHE *phashe = &hash_table[ZobristKey() & (TableSize() - 1)];
 if (phashe->hashf != hashfEMPTY && phashe->depth > depth) {
  return;
 }
 phashe->key = ZobristKey();
 phashe->best = BestMove();
 phashe->val = val;
 phashe->hashf = hashf;
 phashe->depth = depth;
}
 
  如果使用这个代码,那么每走一步以前都必须把散列表中所有的标志项置为“hashfEMPTY”。】
 
不稳定性的问题
 
  当你用置换表时,如果你允许搜索过程根据散列项来截断,那就会产生另一个问题,你的搜索会受“不稳定性”的捆扰。
  不稳定性至少是由以下因素引起的:
  1. 你可能在做6层的搜索,但是如果你在散列项中得到10层搜索的结果,就可能根据这个值来截断。在后来的搜索中,这个散列项被覆盖了,因此你在这个结点上得到了两个不同的值。
  2. Zobrist键值无法记录到达结点的线路,这个结点上不是每条线路都有相同结果的。如果某条线路遇到重复局面,那么散列项的值就会跟路线有关。因为重复局面会导致和局的分值,或者至少不一样的分值。
  就我所知,还没有什么办法能处理这些问题。
  【另外,如果搜索过程中找到杀棋,那么评价值会接近“INFINITY”或“-INFINITY”,此时记录散列表时不能简单地记录这些评价值,在后面介绍的“胜利局面”的处理中,会谈到这个问题。】
 
  原文:http://www.seanet.com/~brucemo/topics/hashing.htm
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注

分享到:
评论

相关推荐

    论文研究-博弈树置换表启发式算法研究.pdf

    论文以中国象棋计算机博弈作为背景,在alpha-beta基本搜索算法上,详细阐述了置换表启发算法的原理和哈希冲突,引进了双层置换表的概念及其替换策略,增强了引擎的搜索效率。实验结果表明了该算法的有效性。

    用c语言模拟先进先出页面置换算法

    2. **先进先出(FIFO)页面置换算法**:这是一种简单的页面置换策略,其基本原则是替换最先进入内存的页面。换句话说,当需要替换一个页面时,系统会选择最早进入内存的页面进行替换。 3. **代码解析**:本部分将详细...

    大数据-算法-一种基于育种思想的全局优化算法原理性能及应用.pdf

    在算法设计中,通过自由采样选种实现广度搜索,以基因置换技术执行局部搜索,从而克服了常规遗传算法在全局性和精确性上的不足。实验结果显示,育种算法在达到相同全局优化概率时,所需的计算代价通常只有常规遗传...

    论文研究-求解置换流水车间调度问题的改进遗传算法.pdf

    针对置换流水车间调度问题的基本特征和传统遗传算法易早熟的缺陷,设计了改进遗传算法来求解此问题。采用NEH和Palmer启发式算法进行种群初始化,以提高初始解的质量;根据Metropolis准则对染色体进行选择操作,避免...

    五子棋Ai整合算杀置换表多种算法

    《五子棋Ai整合算杀置换表多种算法详解》 五子棋,作为一种深受人们喜爱的智力游戏,其人工智能(Ai)的开发一直备受关注。本文将深入探讨一个基于C++实现的五子棋Ai系统,它融合了算杀置换表等多种算法,实现了从...

    页面置换算法 fifo opt lru

    通过以上分析可以看出,给定代码试图通过C++语言实现页面置换算法中的FIFO和LRU算法,并且包含了基本的输入处理和打印功能。然而,由于代码存在大量乱码,无法直接运行。在实际开发中,还需要进一步完善代码结构和...

    IOI国家集训队论文集1999-2019

    楼天城 -《匹配算法在搜索问题中的应用》 贝小辉 -《浅析树的划分问题》 林 涛 -《线段树的应用》 杨思雨 -《伸展树的基本操作与应用》 许智磊 -《后缀数组》 朱泽园 -《多串匹配算法及其启示》 韩文弢 -《论...

    操作系统页面置换算法.pdf

    这些函数可能分别用于初始化页面置换算法的数据结构、打印当前页面状态、在内存中搜索特定页面、改变页面置换策略(包括OPT、FIFO和LRU算法)等。 例如,changeFIFO()函数实现了先进先出的页面置换逻辑,当内存中的...

    算法 for Acmer

    - DFS(深度优先搜索):用于遍历或搜索树或图的算法。 - BFS(广度优先搜索):按层次顺序遍历或搜索。 8. 图论: - 生成树:包含最小生成树算法如Kruskal和Prim算法。 - 最短路:包括Dijkstra算法和Bellman-...

    ACM_算法模板集.pdf

    根据给定文件的信息,我们可以将主要内容分为以下几个部分:数学与公式、大数处理与字符读入、数论算法、图论算法、几何算法以及专题讨论等。下面将逐一展开介绍这些知识点。 ### 一、数学与公式 #### 常用数学...

    一种新的求解置换Flowshop问题的粒子群算法.pdf

    其创新之处在于保留了PSO的基本结构,同时通过位置排序和局部搜索策略,显著提升了PSO算法在离散问题上的适用性。该算法不仅扩展了粒子群算法的应用范围,而且对于实际生产环境中的调度优化具有重大的应用价值。在...

    算法分析一,字符串基础操作

    字符串是计算机科学中最基本的数据结构之一,字符串基础操作是指对字符串进行赋值、复制、比较、连接、取子串、子串在主串中定位、子串置换、子串插入、子串删除等操作。 在字符串基础操作中,字符串模式匹配算法是...

    ACM算法竞赛常用代码

    这些类别包括但不限于时间复杂度、排序算法、数论、指针操作、按位运算、图论、计算几何、数据结构、组合数学、概率论、矩阵运算、字符串处理、动态规划、博弈论以及搜索算法等。 ### 时间复杂度 - **渐近时间...

    组合数学及其算法

    11.8 深度优先搜索法--dfs算法 11.9 项目网络与关键路径法 11.10 网络最大流算法 11.11 状态转移法 11.12 好算法、坏算法和np类问题 11.13 npc类问题 11.14 货郎问题的近似解 习 题... 参考文献

    算法课程设计报告-中国象棋的人机博弈的算法.doc

    - **置换表**:用于存储已计算过的局面评价值,避免重复计算,从而提高搜索效率。 #### 五、调试运行结果 - 该环节主要关注于测试软件的实际运行效果,包括但不限于: - **功能验证**:确保软件能够按照预期完成...

    求解置换流水车间调度问题的一种混合算法.pdf

    【模糊逻辑控制】模糊逻辑控制系统能根据算法性能自动调整混合算法中两种基本算法的比例,以实现更高效的全局和局部搜索平衡,避免过度依赖固定或简单的动态比例规则。 综上所述,本文提出的混合算法结合了遗传算法...

    一篇讲alpha-beta 剪枝及其算法分析的论文

    在描述Alpha-Beta剪枝的过程中,论文提供了一种方法,即使用置换表和散列技术来记录已经评估过的节点,以及他们的评估结果。此外,文章还探讨了不同的节点评估顺序对算法效率的影响,并证明了Alpha-Beta剪枝在某些...

Global site tag (gtag.js) - Google Analytics