📄 阿晖黑白棋天地 - 电脑黑白棋.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0046)http://www.soonghwee.cn/program/alpha_beta.php -->
<HTML><HEAD><TITLE>阿晖黑白棋天地 - 电脑黑白棋</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312"><LINK
href="阿晖黑白棋天地 - 电脑黑白棋.files/text.css" type=text/css rel=stylesheet>
<SCRIPT language=javascript type=text/JavaScript>document.onselectstart = function(){ return false; }</SCRIPT>
<META content="MSHTML 6.00.2900.2180" name=GENERATOR></HEAD>
<BODY>
<TABLE cellSpacing=0 width="100%" align=center>
<TBODY>
<TR>
<TD width=540 height=60><A href="http://www.soonghwee.cn/"><IMG height=60
alt="阿晖黑白棋天地 - Soong's Othello World" src="阿晖黑白棋天地 - 电脑黑白棋.files/logo.gif"
width=540 border=0></A></TD>
<TD noWrap align=right><A href="http://www.soonghwee.cn/en/">English</A>
</TD></TR></TBODY></TABLE>
<TABLE class=bar cellSpacing=0 width="100%">
<TBODY>
<TR>
<TD noWrap align=middle><A href="http://www.soonghwee.cn/">首页</A> | 基础知识 |
<A href="http://www.soonghwee.cn/strategy1/">基本策略</A> | <A
href="http://www.soonghwee.cn/game/">赛事</A> | <A
href="http://www.soonghwee.cn/database/">棋局鉴赏</A> | <A
href="http://www.soonghwee.cn/program/">电脑黑白棋</A> | <A
href="http://www.soonghwee.cn/link/">链接</A> | <A
href="http://www.soonghwee.cn/download/">下载</A> | <A
href="http://www.soonghwee.cn/other/guestbook.php">留言</A> | <A
href="http://www.othello.cn/bbs">论坛</A></TD></TR></TBODY></TABLE>
<TABLE height="80%" cellSpacing=0 cellPadding=10 width="100%">
<TBODY>
<TR vAlign=top>
<TD width=120>
<TABLE class=menu height="100%" cellSpacing=0 width=120>
<TBODY>
<TR>
<TD class=title noWrap height=16>电脑黑白棋</TD></TR>
<TR>
<TD noWrap height=16><A
href="http://www.soonghwee.cn/program/index.php">前言</A></TD></TR>
<TR>
<TD noWrap height=16><A
href="http://www.soonghwee.cn/program/search.php">基本搜索</A></TD></TR>
<TR>
<TD noWrap height=16><A
href="http://www.soonghwee.cn/program/alpha_beta.php">α-β剪枝</A></TD></TR>
<TR>
<TD noWrap height=16><A
href="http://www.soonghwee.cn/program/pvs.php">主要变化搜索</A></TD></TR>
<TR>
<TD noWrap height=16><A
href="http://www.soonghwee.cn/program/hashtable.php">散列表</A></TD></TR>
<TR>
<TD noWrap height=16><A
href="http://www.soonghwee.cn/program/zobrist.php">Zobrist散列</A></TD></TR>
<TR>
<TD noWrap height=16>棋步排序</TD></TR>
<TR>
<TD noWrap height=16>估值函数</TD></TR>
<TR>
<TD noWrap height=16>逐层深入</TD></TR>
<TR>
<TD noWrap height=16>MTD</TD></TR>
<TR>
<TD noWrap height=16>概率剪枝</TD></TR>
<TR>
<TD noWrap height=16>利用对方的时间</TD></TR>
<TR>
<TD noWrap height=16>终盘解算</TD></TR>
<TR>
<TD noWrap height=16>开局库</TD></TR>
<TR>
<TD noWrap height=16>模式自动运算</TD></TR>
<TR>
<TD noWrap height=16>棋盘表示法</TD></TR>
<TR>
<TD noWrap height=16>连接GGS</TD></TR>
<TR>
<TD noWrap> </TD></TR></TBODY></TABLE></TD>
<TD>
<H3>α-β剪枝</H3>
<P>前面介绍的<A
href="http://www.soonghwee.cn/program/search.php">基本搜索</A>十分费时，如果直接应用到实际中，则显得效率太低。有没有更好的办法呢？研究表明，要想找出最佳棋步，并不需要考虑所有局面，有些局面完全可以忽略。</P>
<P>在整个搜索工作完成之前，虽然无从知道最佳的估值是多少，但是可以确定出估值的上、下限。在搜索过程中，如果搜索到一个当前最佳估值，它就构成最终估值的下限，这个下限就称为α值。如果在后续搜索中有更好的估值，下限将被提高，直到形成最终的估值。由于估值是相对的，一方的下限就是另一方的上限(在数值上取负)，这个上限就称为β值。</P>
<P>这看起来似乎很矛盾，程序总是努力搜索尽可能高的估值，为什么还会有上限？但事实上就是如此，只有估值落在区间内的变化才是程序真正感兴趣的。对于估值不超过下限α的变化，程序当然弃之不用。而当估值达到或超过上限β时，情形会如何呢？</P>
<P>双方都在各自的层面上搜索各自的最佳棋步，如果一方的估值达到或超过其上限，就意味着从对家角度看，估值不会超过其下限，这会导致对家放弃形成当前局面的那个变化。对家是不会给你选择这步好棋的机会，因为这步棋对你太有利了。</P>
<P>事实上，程序只是在(α,β)区间内努力寻找尽可能高的估值，而一旦搜索到一个变化的估值达到或超过其上限，就意味着当前层面的后续搜索工作将变得多余。即使在后续搜索中还会有更高的估值，也只能说明该估值更低于对家的下限，最终的结局都是一样，会被对家弃之不用。这时就没有必要再浪费时间去搜索其余变化，这就称为α-β剪枝(alpha-beta
pruning)。</P>
<P>上述过程可以用程序代码描述如下：</P><PRE> int alpha_beta(int alpha, int beta, int depth){
int best_eval = -INF_SCORE; //当前搜索到的最好估值，预设为负无穷大
int square, eval;
//如果到达搜索深度，直接给出估值
if (depth <= 0) return evaluation();
//尝试每一个可能的位置
for (square=A1; square<=H8; square++) {
//试着在这个位置下棋
if (flip(square)) {
//递归评估变化后的局面
eval = -search(-beta, -alpha, depth-1); //这时轮到对手下棋，应取负
//返原上一步棋
undo_flip();
//保存更好的结果
if (eval > best_eval) {
best_eval = eval;
//更新下限
if (eval > alpha) {
alpha = eval;
//剪枝
if (eval >= beta) return eval;
}
}
}
}
//处理没有合法棋步的情况
if (best_eval == -INF_SCORE) {
//弃权一步
pass();
//如果对方也没有合法棋步，对局结束
if (have_no_valid_move()) {
best_eval = -get_score();
} else {
best_eval = -search(depth-1); //这时轮到对手下棋，应取负
}
//返原弃权前的状态
undo_pass();
}
return best_eval;
}
</PRE>
<P>在最外层调用α-β剪枝算法时，α和β的初始值可以取正负最大估值：</P>
<P>alpha_beta(-MAX_SCORE, MAX_SCORE, depth);</P>
<P>对于黑白棋，MAX_SCORE可以取64。</P>
<P>由于剪枝时，一些多余的搜索工作被跳过去，需要搜索的局面数量将大大减少。有数据表明，加入α-β剪枝后，同样是中盘向前搜索10步棋，程序平均只需考虑大约3亿个局面。相对于没有α-β剪枝时的600亿个局面来说，搜索效率明显提高。正是由于这种高效性，当今强大的黑白棋程序(也包括其他的棋类程序)，都无不例外地采用α-β剪枝算法及其变形，并在此基础上进行改进、增强。</P>
<P>值得注意的是，采用α-β剪枝技术之后，程序只关心搜索窗口(α,β)内的变化。对于超出窗口之外的变化，程序会进行不同程度的剪枝，这时函数的返回值可能不是精确的最佳估值，而只是估值的上限或下限。即对于如下函数调用：</P>
<P>eval = alpha_beta(alpha, beta, depth);</P>
<P>返回值分3种情况：</P>
<P>(1) eval >=
beta，这是剪枝的结果。它说明肯定有个估值能达到beta，但是否还有更好的估值呢？不得而知。在这种情况下，eval只是表示最佳估值的下限。</P>
<P>(2) alpha < eval < beta，在这种情况下，eval就是精确的最佳估值。</P>
<P>(3) eval <=
alpha，这种情况比较难分清楚，但从双方α、β互换的情况来考虑，这很可能也是剪枝带来的结果。因此与第一种情况相反，eval只是表示最佳估值的上限。</P>
<P align=center><A
href="http://www.soonghwee.cn/program/alpha_beta.php#">页首</A></P></TD></TR></TBODY></TABLE>
<TABLE class=bar cellSpacing=0 width="100%">
<TBODY>
<TR>
<TD noWrap align=middle>© 2005-2006 <A href="http://www.soonghwee.cn/">阿
晖</A> 版权所有 <A href="mailto:soonghwee@gmail.com">联系我们</A> <!--<a href="http://t.extreme-dm.com/?login=caprone" target="_blank"><img src="http://t1.extreme-dm.com/i.gif" alt="eXTReMe Tracker" name="EXim" width="41" height="38" border="0" align="absmiddle"></a> <script type="text/javascript" language="javascript1.2"> EXs = screen; EXw = EXs.width; navigator.appName!="Netscape" ? EXb=EXs.colorDepth : EXb=EXs.pixelDepth; </script> <script type="text/javascript"> var EXlogin='caprone' // Login var EXvsrv='s9' // VServer navigator.javaEnabled()==1 ? EXjv="y" : EXjv="n"; EXd=document; EXw? "" : EXw="na"; EXb? "" : EXb="na"; EXd.write("<img src=\"http://e0.extreme-dm.com", "/"+EXvsrv+".g?login="+EXlogin+"&", "jv="+EXjv+"&j=y&srw="+EXw+"&srb="+EXb+"&", "l="+escape(EXd.referrer)+"\" height=1 width=1>"); </script>--></TD></TR></TBODY></TABLE></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -