📄 怎样编制黑白棋(2).htm
字号:
<TD background=怎样编制黑白棋(2).files/ad_bx1.gif colSpan=2 height=6></TD></TR>
<TR>
<TD colSpan=6></TD></TR>
<TR>
<TD id=fontzoom style="WORD-BREAK: break-all" vAlign=top colSpan=2
height=600>
<TABLE cellSpacing=1 cellPadding=8 width="100%" border=0>
<TBODY>
<TR>
<TD
style="BORDER-TOP: rgb(255,255,255) 1px solid; BORDER-LEFT: rgb(255,255,255) 1px solid"
width="100%" bgColor=#ccccff>
<P align=center>剪枝</P></TD></TR>
<TR>
<TD
style="BORDER-TOP: rgb(255,255,255) 1px solid; BORDER-LEFT: rgb(255,255,255) 1px solid"
width="100%"><FONT size=2>Alpha-Beta剪枝(Alpha-Beta
Purning)</FONT>
<P><FONT size=2>
新的问题出现了：对于一般的最大最小搜索，即使每一步只有很少的下法，搜索位置的数目也会随着搜索深度呈级数级增长。在大多数的中局棋形中，每步平均有十种下法，假设电脑搜索九步(程序术语称为搜索深度为九)，就要搜索十亿个位置(十的九次方)，这样极大地限制了电脑的棋力：我们总不能忍受电脑棋手一年才下一步棋。减少搜索结点的最简单的方法是减小搜索深度，但这大大影响了电脑棋手的棋力。是否有办法在不减小搜索深度的前提下将需要搜索的结点减小一些？幸运的是，可以证明，程序不需要考虑所有的位置而找到最佳点，于是人们采用了一个方法，叫"alpha-beta剪枝"，它大为减少了检测的数目，提高电脑搜索的速度。所有的强力黑白棋程序都用到了各种各样的这种算法。(同样用于其他棋类游戏，如国际象棋和跳棋)。为了搜索九步，一个好的程序只用搜索十万到一百万个位置，而不是没用前的十亿次。</FONT>
<P><FONT size=2>
还有几种alpha-beta算法的改进型，最广泛采用的是NegaScout，(Alexander
Reinefeld发明)，但它和一般的alpha-beta剪枝算法没有根本的不同。其他的还有PVS和SSS*。下面举例说明。
</FONT></P></TD></TR>
<TR>
<TD
style="BORDER-TOP: rgb(255,255,255) 1px solid; BORDER-LEFT: rgb(255,255,255) 1px solid"
width="100%"><FONT size=2>
还是基于刚才的棋形，假设先搜索e3-f2 f3 f4 f5 f6、再c3-c2 d3 e6 f5、再c5-b6 c6 d6
e6
f6，即从左至右的顺序的深度优先搜索。则搜索到d3分枝之后，就不用搜索e6和f5了。因为如果接下来的值比d3大，就不会赋值给c3，如果比d3小，赋值给c3后，也不会赋给根节点，因为根节点取最大的值，现在根节点的值是-1，不会取更小的值。同样的，搜索d6后，也不用搜索e6、f6了，也就是说，搜索到比-1还小的值之后，就不用搜索了。
</FONT></TD></TR></TBODY></TABLE><BR><BR>
在搜索过程中，电脑下棋结点的当前最优值被称为α 值（即初始棋局的值），对手下棋结点的当前最优值被称为
β值（即例子中C3的值）。在搜索过程中，α 值递增，
β值递减，两者构成了一个区间。这个区间被称为窗口，而对手下棋的结点最终的最优值将落在这个窗口中。一旦在电脑下棋的结点得到其子结点的返回值大于β
值，则发生剪枝。<BR><BR>
<TABLE cellSpacing=0 cellPadding=0 width="100%" border=1>
<TBODY>
<TR>
<TD width="100%">
<P align=center><FONT size=2>初始棋局(-1)</FONT></P>
<P align=center><FONT
size=2>------------------+------------------</FONT></P>
<P align=center><FONT size=2>|
|
|</FONT></P>
<P align=center><FONT size=2>e3(-1)
c3(-1)
c5(-5)</FONT></P>
<P align=center><FONT size=2>-----+-----
----+----
-----+-----</FONT></P>
<P align=center><FONT size=2>| | | | |
| | | |
| | | |
|</FONT></P>
<P align=center><FONT size=2> f2 f3 f4 f5
f6 c2 d3 e6 f5
b6 c6 d6 e6 f6 </FONT></P>
<P align=center><FONT size=2>+84+36+12 +5
-1 +11 -1 +6 +6
+6 +0 -5 +3 +5 </FONT></P></TD></TR></TBODY></TABLE><BR>
<TABLE cellSpacing=1 cellPadding=8 width="100%" border=0>
<TBODY>
<TR>
<TD
style="BORDER-TOP: rgb(255,255,255) 1px solid; BORDER-LEFT: rgb(255,255,255) 1px solid"
width="100%"><FONT size=2><B>Alpha-Beta搜索：</B></FONT></TD></TR>
<TR>
<TD
style="BORDER-TOP: rgb(255,255,255) 1px solid; BORDER-LEFT: rgb(255,255,255) 1px solid"
width="100%"><FONT size=2>function AlphaBeta(Depth: Integer;
Alpha, Beta: Double; Board: TBoard): Double;<BR>var<BR>
I, J: Integer;<BR> t: Double;<BR>begin<BR> if
Depth = 0
then
//根节点depth=DepthMax；叶子节点depth=0;<BR>
begin<BR> Result :=
估值;
//叶子结点估值返回<BR> Exit;<BR> end;</FONT>
<P><FONT size=2> 对于每一个合法的可下棋的位置(i,j) do<BR>
begin<BR> 保存棋局;<BR>
下棋;<BR> t := -AlphaBeta(Depth - 1, -Beta,
-Alpha, Board); //递归调用<BR> if t > Alpha
then<BR> if t >= Beta
then<BR>
begin<BR> Result :=
t;<BR>
Exit;<BR>
end<BR>
else<BR> Alpha :=
t;</FONT></P>
<P><FONT size=2> if (Depth = DepthMax) and
(t > Alpha) then
//如果值大于根节点值则赋值<BR>
begin<BR> max :=
t;<BR> max_x :=
i;
//x坐标<BR> max_y :=
j;
//y坐标<BR> end;</FONT></P>
<P><FONT size=2> 恢复棋局;<BR>
end;<BR> Result :=
Alpha;<BR>end;</FONT></P></TD></TR></TBODY></TABLE>
<P></P></TD></TR>
<TR class=left_tdbgall align=right>
<TD colSpan=2 height=24>【字体：<A class=top_UserLogin
href="javascript:fontZoomA();">小</A> <A class=top_UserLogin
href="javascript:fontZoomB();">大</A>】【<A
href="http://study.feloo.com/computer/Comment.asp?ArticleID=38230"
target=_blank>发表评论</A>】【<A
href="http://study.feloo.com/User/User_Favorite.asp?Action=Add&ChannelID=25&InfoID=38230"
target=_blank>加入收藏</A>】【<A
href="http://study.feloo.com/computer/SendMail.asp?ArticleID=38230"
target=_blank>告诉好友</A>】【<A
href="http://study.feloo.com/computer/Print.asp?ArticleID=38230"
target=_blank>打印此文</A>】【<A
href="javascript:window.close();">关闭窗口</A>】 </TD></TR>
<TR>
<TD class=left_tdbgall align=right colSpan=2
height=24>电脑文章录入：朱国文 责任编辑：朱国文 </TD></TR><!--文章内容下部广告代码开始-->
<TR>
<TD align=middle colSpan=2>
<SCRIPT src=""></SCRIPT>
</TD></TR><!--文章同容下部广告代码结束-->
<TR>
<TD class=left_tdbgall align=right colSpan=2 height=24><STRONG><FONT
color=#ff0000>百度搜索:<A
href="http://www.baidu.com/baidu?tn=study888&word=怎样编制黑白棋(2)"
target=_blank>怎样编制黑白棋(2)</FONT></A></STRONG>
<SCRIPT src=""></SCRIPT>
</TD></TR>
<TR>
<TD width=5></TD>
<TD width=787>
<LI>上一篇电脑文章： <A
title="电脑文章标题：怎样编制黑白棋(1) 作 者：未知 更新时间：2005-6-7 16:12:47"
href="http://study.feloo.com/computer/pro/c/game/200506/38229.html">怎样编制黑白棋(1)</A><BR>
<LI>下一篇电脑文章： <A
title="电脑文章标题：怎样编制黑白棋(3) 作 者：未知 更新时间：2005-6-7 16:12:48"
href="http://study.feloo.com/computer/pro/c/game/200506/38231.html">怎样编制黑白棋(3)</A></LI></TD></TR><!--文章内容下部广告代码开始-->
<TR>
<TD align=middle colSpan=2>
<SCRIPT src=""></SCRIPT>
</TD></TR><!--文章同容下部广告代码结束--></TBODY></TABLE><!--网页中部左栏文章内容代码结束-->
<TABLE cellSpacing=0 cellPadding=0 width="100%" border=0>
<TBODY>
<TR>
<TD align=middle height=20></TD></TR></TBODY></TABLE></TD>
<TD style="BORDER-LEFT: #a7a9a7 1px solid" vAlign=top width=180
bgColor=#f8f8f8><!--网页中部右栏代码开始-->
<TABLE style="WORD-BREAK: break-all" cellSpacing=0 cellPadding=0
width="100%" border=0>
<TBODY>
<TR>
<TD class=left_title><IMG height=28
src="怎样编制黑白棋(2).files/ad_search.gif" width=174></TD></TR>
<TR>
<TD align=middle>
<SCRIPT src="怎样编制黑白棋(2).files/ShowSearchForm_wen.js"></SCRIPT>
</TD></TR>
<TR>
<TD align=middle>
<SCRIPT src=""></SCRIPT>
</TD></TR>
<TR>
<TD class=left_title><IMG height=28
src="怎样编制黑白棋(2).files/ad_ztlm.gif" width=174></TD></TR>
<TR>
<TD class=left_tdbg1>
<SCRIPT language=javascript
src="怎样编制黑白棋(2).files/com-tjlm.js"></SCRIPT>
</TD></TR>
<TR>
<TD class=left_tdbg2></TD></TR>
<TR>
<TD class=left_title><A class=class
href="http://study.feloo.com/computer/ShowHot.asp"><IMG height=28
src="怎样编制黑白棋(2).files/ad_zxrmwz.gif" width=174 border=0></A></TD></TR>
<TR>
<TD class=left_tdbg1 background=怎样编制黑白棋(2).files/ad_bg2.gif>
<TABLE cellSpacing=0 cellPadding=0 width="100%">
<TBODY>
<TR>
<TD class=listbg vAlign=top width=10><IMG alt=普通电脑文章
src="怎样编制黑白棋(2).files/article_common.gif"></TD>
<TD class=listbg><A class=listA
title="电脑文章标题：文本方式下双链表实现的食豆蛇游戏 作 者：未知 更新时间：2005-6-7 16:12:53"
href="http://study.feloo.com/computer/pro/c/game/200506/38257.html"
target=_self>文本方式下双链表实现的食豆…</A></TD></TR>
<TR>
<TD class=listbg2 vAlign=top width=10><IMG alt=普通电脑文章
src="怎样编制黑白棋(2).files/article_common.gif"></TD>
<TD class=listbg2><A class=listA
title="电脑文章标题：关于文曲星上猜数字游戏的c编程方法 作 者：未知 更新时间：2005-6-7 16:12:52"
href="http://study.feloo.com/computer/pro/c/game/200506/38256.html"
target=_self>关于文曲星上猜数字游戏的c编…</A></TD></TR>
<TR>
<TD class=listbg vAlign=top width=10><IMG alt=普通电脑文章
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -