第3期 黄晨：棋类游戏中的先行权 ·93· 续表1 深度分值 主要变例 累积节点数分枝因子 81马八进七马2进3马二进三马8进7兵七进一车9进1马七进六车9平4 999417 3.4 96马八进七马2进3马二进三马8进7兵七进一车9进1车九进一车9平4车九平四 2751341 2.8 101马八进比马8进9马二进三车9进1车九进一马2进3车九平四车9平4兵七进一车1进1119867464.4 当程序搜索奇数层时，先行方总比后行方多走 if (bWhite Turn) 一步，而当程序搜索偶数层时，先行方走的着数和后 return nWhite Value nBlack Value 行方一样多，因此奇数层的搜索分值总是比偶数层 else 略大.这种现象称为奇偶层效应 return nBlack Value-nWhite Value; 如果博弈程序运用了窗口搜索技术（如期望窗 口、PVS MTD(f)等)，那么搜索效率就会因奇偶层 为了消除奇偶层效应，可以在局面评价函数中 效应而降低.MTD(f)算法的创始人Plaat甚至建 增加了“先行权分值” 议，为克服奇偶层效应的影响，在迭代加深时把深度 define ADVANCED 3 步长改成2) int EvaluateAdjust (void){ 2.2先行权分值 return Evaluate()+ADVANCED: 既然奇偶层效应是由于先行权引起的，那么可 以考虑在局面评价函数上作先行权的调整，让奇偶 使用了调整后的局面评价函数，各层的分值、分 层的评价尽可能地接近.例如，表1的搜索结果，采 枝因子都会比较接近，而搜索的节点数则有明显的 用的局面评价函数是： 下降，可见搜索效率有了充分的提高，见表2. int Evaluate(void) 表2削弱的奇偶层效应 Table 2 Weakened everodd effect 深度分值 主要变例 累积节点数分枝因子 1 6 马八进七 97 2 3 马八进七马2进3 563 5.8 3 6 马八进七马2进3马二进三 2109 3.7 4 3 马八进七马2进3马二进三马8进7 7812 3.7 5 6 马八进七马2进3车九进一马8进7车九平四 18284 2.3 6 3 马八进七马2进3车九进一车1进1车九平四车1平4 59725 3.3 7 6 马八进七马2进3车九进一车1进1车九平四车1平4马二进三 190052 3.2 8 3 马八进七马2进3车九进一车1进1车九平四车1平4马二进三马8进7 596068 3.1 9 3马八进七马2进3车九进一车1进1车九平四车1平4马二进三马8进7车一进一2099191 3.5 103马八进七马2进3车九进一车1进1车九平四车1平4马二进三马8进7车一进一 5782475 2.8 每一着棋都会有一个价值，使局势朝有利于自 右1.随着棋局进入收官阶段，先行权分值锐减，收 己的方向发展，这个价值的一半就是先行权分值.然 到单官就是零了， 而，先行权分值并不是始终不变的，一般情况下，开 2.3空着裁剪 局的先行权分值最大随着棋局渐渐进入残局，先行 空着裁剪(null-move pruning)的思想是，假设 权分值会减小甚至丧失.中国象棋和国际象棋中还 对手连走2着，如果本方在浅层的搜索中仍旧具有 有“无等着”局面(Zugzwang),此时走任何一着棋都 良好表现（产生Beta截断），那么就不需要进行完全 会让自己的局势更糟，在这种情况下，先行权分值就 深度的搜索了.写成伪代码，就是： 相当于负值」 if (can do null()) 围棋的局势最容易被量化，布局和中盘阶段可 do null(); 认为先行权分值是5.5目（因为先手方贴目5.5 value =-search(-beta,1-beta,depth R-1); 目)，由此可认定平均每一着棋的价值在11目左 undo_null(); if (value >beta)f 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net续表 1 深度 分值 主要变例 累积节点数 分枝因子 8 1 马八进七 马 2 进 3 马二进三 马 8 进 7 兵七进一 车 9 进 1 马七进六 车 9 平 4 999417 3. 4 9 6 马八进七 马 2 进 3 马二进三 马 8 进 7 兵七进一 车 9 进 1 车九进一 车 9 平 4 车九平四 2751341 2. 8 10 1 马八进七 马 8 进 9 马二进三 车 9 进 1 车九进一 马 2 进 3 车九平四 车 9 平 4 兵七进一 车 1 进 1 11986746 4. 4 当程序搜索奇数层时 ,先行方总比后行方多走 一步 ,而当程序搜索偶数层时 ,先行方走的着数和后 行方一样多 ,因此奇数层的搜索分值总是比偶数层 略大. 这种现象称为奇偶层效应. 如果博弈程序运用了窗口搜索技术 (如期望窗 口、PVS、M TD (f) 等) ,那么搜索效率就会因奇偶层 效应而降低. M TD (f) 算法的创始人 Plaat 甚至建 议 ,为克服奇偶层效应的影响 ,在迭代加深时把深度 步长改成 2 [5 ] . 2. 2 先行权分值 既然奇偶层效应是由于先行权引起的 ,那么可 以考虑在局面评价函数上作先行权的调整 ,让奇偶 层的评价尽可能地接近. 例如 ,表 1 的搜索结果 ,采 用的局面评价函数是 : int Evaluate (void) { if (bWhiteTurn) { return nWhiteValue2nBlackValue ; } else { return nBlackValue2nWhiteValue ; } } 为了消除奇偶层效应 ,可以在局面评价函数中 增加了“先行权分值”: # define ADVANCED 3 int EvaluateAdjust (void) { return Evaluate () + ADVANCED ; } 使用了调整后的局面评价函数 ,各层的分值、分 枝因子都会比较接近 ,而搜索的节点数则有明显的 下降 ,可见搜索效率有了充分的提高 ,见表 2. 表 2 削弱的奇偶层效应 Table 2 Weakened even2odd effect 深度 分值 主要变例 累积节点数 分枝因子 1 6 马八进七 97 2 3 马八进七 马 2 进 3 563 5. 8 3 6 马八进七 马 2 进 3 马二进三 2109 3. 7 4 3 马八进七 马 2 进 3 马二进三 马 8 进 7 7812 3. 7 5 6 马八进七 马 2 进 3 车九进一 马 8 进 7 车九平四 18284 2. 3 6 3 马八进七 马 2 进 3 车九进一 车 1 进 1 车九平四 车 1 平 4 59725 3. 3 7 6 马八进七 马 2 进 3 车九进一 车 1 进 1 车九平四 车 1 平 4 马二进三 190052 3. 2 8 3 马八进七 马 2 进 3 车九进一 车 1 进 1 车九平四 车 1 平 4 马二进三 马 8 进 7 596068 3. 1 9 3 马八进七 马 2 进 3 车九进一 车 1 进 1 车九平四 车 1 平 4 马二进三 马 8 进 7 车一进一 2099191 3. 5 10 3 马八进七 马 2 进 3 车九进一 车 1 进 1 车九平四 车 1 平 4 马二进三 马 8 进 7 车一进一 5782475 2. 8 每一着棋都会有一个价值 ,使局势朝有利于自 己的方向发展 ,这个价值的一半就是先行权分值. 然 而 ,先行权分值并不是始终不变的 ,一般情况下 ,开 局的先行权分值最大 ,随着棋局渐渐进入残局 ,先行 权分值会减小甚至丧失. 中国象棋和国际象棋中还 有“无等着”局面(Zugzwang) ,此时走任何一着棋都 会让自己的局势更糟 ,在这种情况下 ,先行权分值就 相当于负值. 围棋的局势最容易被量化 ,布局和中盘阶段可 认为先行权分值是 5. 5 目 (因为先手方贴目 5. 5 目) ,由此可认定平均每一着棋的价值在 11 目左 右[6 ] . 随着棋局进入收官阶段 ,先行权分值锐减 ,收 到单官就是零了. 2. 3 空着裁剪 空着裁剪 ( null2move pruning) 的思想是 ,假设 对手连走 2 着 ,如果本方在浅层的搜索中仍旧具有 良好表现(产生 Beta 截断) ,那么就不需要进行完全 深度的搜索了. 写成伪代码 ,就是 : if (can_do_null() ) { do_null() ; value =2search (2beta ,12beta , depth2R21) ; undo_null() ; if (value > = beta) { 第 3 期 黄 晨 :棋类游戏中的先行权 · 39 ·