<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0054)http://www.elephantbase.net/computer/eleeye_struct.htm -->
<HTML><HEAD><TITLE>解剖大象的眼睛——中国象棋程序设计探索(二):棋盘结构和着法生成器</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.536" name=GENERATOR></HEAD>
<BODY background=解剖大象的眼睛——中国象棋程序设计探索(二):棋盘结构和着法生成器_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT><FONT face=隶书 size=6>解剖大象的眼睛</FONT><FONT
size=6><STRONG>——</STRONG></FONT><FONT face=隶书 size=6>中国象棋程序设计探索</FONT>
</CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT>黄晨 <FONT face="Times New Roman">*</FONT> <FONT
face="Times New Roman">2005</FONT>年<FONT
face="Times New Roman">6</FONT>月初稿,<FONT
face="Times New Roman">2005</FONT>年<FONT face="Times New Roman">11</FONT>月修订
</CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">( * </FONT>联系地址:复旦大学化学系表面化学实验室,<FONT
face="Times New Roman">eMail</FONT>:<A
href="mailto:webmaster@elephantbase.net"><FONT
face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT
face="Times New Roman">)</FONT> </CENTER></DT></DIV>
<DT>
<DT><FONT face=Arial size=5><STRONG>(</STRONG></FONT><FONT face=楷体_GB2312
size=5><STRONG>二</STRONG></FONT><FONT face=Arial size=5><STRONG>)
</STRONG></FONT><FONT face=楷体_GB2312 size=5><STRONG>棋盘结构和着法生成器</STRONG></FONT>
<DT>
<DT> 在阅读本章前,建议读者先阅读《<A href="http://www.elephantbase.net/"
target=_blank>象棋百科全书</A>》网站中《<A
href="http://www.elephantbase.net/computer/outline.htm"
target=_blank>对弈程序基本技术</A>》专题的以下几篇译文:
<DT> <FONT face="Times New Roman">(1) </FONT><A
href="http://www.elephantbase.net/computer/struct_intro.htm"
target=_blank>数据结构——简介</A><FONT face="Times New Roman">(David
Eppstein)</FONT>;
<DT> <FONT face="Times New Roman">(2) </FONT><A
href="http://www.elephantbase.net/computer/struct_bitboard.htm"
target=_blank>数据结构——位棋盘</A><FONT face="Times New Roman">(James
Swafford)</FONT>;
<DT> <FONT face="Times New Roman">(3) </FONT><A
href="http://www.elephantbase.net/computer/struct_rotation.htm"
target=_blank>数据结构——旋转的位棋盘</A><FONT face="Times New Roman">(James
Swafford)</FONT>;
<DT> <FONT face="Times New Roman">(4) </FONT><A
href="http://www.elephantbase.net/computer/struct_movegen.htm"
target=_blank>数据结构——着法生成器</A><FONT face="Times New Roman">(James
Swafford)</FONT>;
<DT> <FONT face="Times New Roman">(5) </FONT><A
href="http://www.elephantbase.net/computer/struct_0x88.htm"
target=_blank>数据结构——<FONT face="Times New Roman">0x88</FONT>着法产生方法</A><FONT
face="Times New Roman">(Bruce Moreland)</FONT>;
<DT> <FONT face="Times New Roman">(6) </FONT><A
href="http://www.elephantbase.net/computer/struct_zobrist.htm"
target=_blank>数据结构——<FONT face="Times New Roman">Zobrist</FONT>键值</A><FONT
face="Times New Roman">(Bruce Moreland)</FONT>;
<DT>
<DT><FONT face=Arial size=4><STRONG>2.1 </STRONG></FONT><FONT face=楷体_GB2312
size=4><STRONG>局面和着法的表示</STRONG></FONT>
<DT>
<DT><FONT size=3> 局面是象棋程序的核心数据结构,除了要包括棋盘、棋子、哪方要走、着法生成的辅助结构、</FONT><FONT
face="Times New Roman" size=3>Zobrist</FONT><FONT
size=3>键值等,还要包含一些历史着法,来判断重复局面。</FONT><FONT face="Times New Roman"
size=3>ElephantEye</FONT><FONT size=3>的局面结构很庞大</FONT><FONT
face="Times New Roman" size=3>(</FONT><FONT size=3>见</FONT><FONT
face="Times New Roman" size=3><position.h>)</FONT><FONT
size=3>,其中大部分存储空间是用来记录历史局面的。</FONT>
<DD>
<DD><FONT size=3>struct PositionStruct {</FONT>
<DD><FONT size=3> ……</FONT>
<DD><FONT size=3> int nMoveNum;</FONT>
<DD><FONT size=3> MoveStruct mvMoveList[MAX_MOVE_NUM]; // MAX_MOVE_NUM =
256</FONT>
<DD><FONT size=3> unsigned char ucRepHash[REP_HASH_LEN]; // REP_HASH_LEN =
1024</FONT>
<DD><FONT size=3> ……</FONT>
<DD><FONT size=3>}</FONT>
<DT>
<DT> 其中<FONT face="Times New Roman">MoveStruct</FONT>这个结构记录了四个信息:<FONT
face="Times New Roman">(1) </FONT>着法的起始格<FONT
face="Times New Roman">(Src)</FONT>,<FONT face="Times New Roman">(2)
</FONT>着法的目标格<FONT face="Times New Roman">(Dst)</FONT>,<FONT
face="Times New Roman">(3) </FONT>着法吃掉的棋子<FONT
face="Times New Roman">(Cpt)</FONT>,<FONT face="Times New Roman">(4)
</FONT>着法是否将军<FONT
face="Times New Roman">(Chk)</FONT>。有意思的是,每个部分都只占一个字节,后两个部分<FONT
face="Times New Roman">(Cpt</FONT>和<FONT
face="Times New Roman">Chk)</FONT>与其说有特殊作用,不如说是为了凑一个<FONT
face="Times New Roman">32</FONT>位整数。在<FONT
face="Times New Roman">MoveStruct</FONT>出现的很多地方<FONT
face="Times New Roman">(</FONT>置换表、杀手着法表、着法生成表<FONT
face="Times New Roman">)</FONT>里,这两项都是没作用的,而只有在<FONT
face="Times New Roman">PositionStruct</FONT>结构的记录历史着法的堆栈中才有意义。
<DT> <FONT face="Times New Roman">Cpt</FONT>一项主要用在撤消着法上,它可以用来还原被吃的棋子,而<FONT
face="Times New Roman">Chk</FONT>一项则可以记录当前局面是否处于将军状态。<FONT
face="Times New Roman">ElephantEye</FONT>是用<FONT
face="Times New Roman">MakeMove()</FONT>函数来走棋的,每走完一步棋就做两次将军判断:第一次判断走完子的一方是否被将军,即<FONT
face="Times New Roman">Checked(sdPlayer)</FONT>,如果被将则立即撤消着法,并返回走子失败的信息;第二次判断要走的一方是否被将军,由于交换了走子方<FONT
face="Times New Roman">(</FONT>即执行了<FONT face="Times New Roman">sdPlayer = 1
</FONT><FONT face=Symbol>-</FONT><FONT face="Times New Roman">
sdPlayer)</FONT>,所以仍旧是<FONT
face="Times New Roman">Checked(sdPlayer)</FONT>,如果被将则<FONT
face="Times New Roman">Chk</FONT>置为<FONT
face="Times New Roman">TRUE</FONT>,这个着法被压入历史着法堆栈。因此<FONT
face="Times New Roman">LastMove().Chk</FONT>就表示当前局面是否被将军。
<DT>
<DT><FONT face=Arial size=4><STRONG>2.2 </STRONG></FONT><FONT face=楷体_GB2312
size=4><STRONG>循环着法的检测</STRONG></FONT>
<DT>
<DT> <FONT face="Times New Roman">Cpt</FONT>和<FONT
face="Times New Roman">Chk</FONT>的另一个作用就是判断循环着法:<FONT
face="Times New Roman">ElephantEye</FONT>判断循环着法时,依次从堆栈顶往前读,读到吃过子的着法<FONT
face="Times New Roman">(Cpt</FONT>不为零<FONT
face="Times New Roman">)</FONT>就结束;而是否有单方面长将的情况,则是通过每个着法的<FONT
face="Times New Roman">Chk</FONT>一项来判断的。
<DT> 在循环着法的检测中,我们感兴趣的不是<FONT face="Times New Roman">Cpt</FONT>和<FONT
face="Times New Roman">Chk</FONT>,而是<FONT
face="Times New Roman">RepHash</FONT>结构,这是一个微型的置换表,用来记录历史局面。<FONT
face="Times New Roman">ElephantEye</FONT>在做循环着法的判断这之前,先去探测这个置换表,如果命中置换表,则说明可能存在重复局面<FONT
face="Times New Roman">(</FONT>由于置换表可能有冲突,所以只是有这个可能<FONT
face="Times New Roman">)</FONT>,因而做循环检测;如果没有命中则肯定没有重复局面。
<DT> <FONT
face="Times New Roman">ElephantEye</FONT>使用“归位检测法”来判断循环着法,即从最后一个着法开始,依次向前撤消着法,并记录每个移动过的棋子所在的格子。如果所有移动过的棋子同时归位,那么循环着法就出现了。因此<FONT
face="Times New Roman"><position.cpp></FONT>中的<FONT
face="Times New Roman">IsRep()</FONT>函数建立了两个归位数组,第一个记录了棋子的原始位置,第二个记录了新的位置,当两个位置重合时,
没有合适的资源?快使用搜索试试~ 我知道了~
象棋程序设计全资料集
共200个文件
gif:144个
htm:56个
需积分: 10 33 下载量 46 浏览量
2007-11-15
22:00:44
上传
评论
收藏 399KB RAR 举报
温馨提示
象棋程序设计全资料集,网上资料
资源推荐
资源详情
资源评论
收起资源包目录
象棋程序设计全资料集 (200个子文件)
egtb.gif 32KB
opentrend2.gif 18KB
opentrend3.gif 15KB
opentrend4.gif 14KB
opentrend6.gif 9KB
opentrend5.gif 9KB
search_intro3.gif 8KB
evalue_intro1.gif 8KB
search_intro1.gif 7KB
opentrend1.gif 6KB
struct_intro.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
background.gif 5KB
search_intro2.gif 5KB
advanced_nullmove2.gif 5KB
egtbweak3.gif 4KB
struct_rotation6.gif 4KB
egtbweak4.gif 4KB
advanced_intro1.gif 4KB
egtbweak2.gif 4KB
struct_rotation2.gif 4KB
evalue_intro2.gif 4KB
struct_rotation8.gif 4KB
struct_rotation4.gif 4KB
egtbweak1.gif 4KB
struct_rotation7.gif 4KB
struct_rotation1.gif 4KB
struct_rotation5.gif 4KB
other_winning.gif 4KB
evalue_intro3.gif 4KB
advanced_nullmove1.gif 4KB
struct_rotation3.gif 4KB
elephantbase.gif 3KB
elephantbase.gif 3KB
elephantbase.gif 3KB
elephantbase.gif 3KB
elephantbase.gif 3KB
elephantbase.gif 3KB
elephantbase.gif 3KB
elephantbase.gif 3KB
elephantbase.gif 3KB
elephantbase.gif 3KB
elephantbase.gif 3KB
elephantbase.gif 3KB
elephantbase.gif 3KB
elephantbase.gif 3KB
共 200 条
- 1
- 2
资源评论
wfzdl
- 粉丝: 2
- 资源: 10
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功