?? 數(shù)據(jù)結(jié)構(gòu)——0x88著法產(chǎn)生方法.htm
字號(hào):
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0052)http://www.elephantbase.net/computer/struct_0x88.htm -->
<HTML><HEAD><TITLE>數(shù)據(jù)結(jié)構(gòu)——0x88著法產(chǎn)生方法</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=數(shù)據(jù)結(jié)構(gòu)——0x88著法產(chǎn)生方法_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT>《對(duì)弈程序基本技術(shù)》專題 </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face=Arial size=6><STRONG>0x88</STRONG></FONT><FONT face=隸書
size=6>著法產(chǎn)生方法</FONT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">Bruce Moreland (</FONT><A
href="mailto:brucemo@seanet.com"><FONT
face="Times New Roman">brucemo@seanet.com</FONT></A><FONT
face="Times New Roman">) / </FONT>文 </CENTER></DT></DIV>
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>歷史</STRONG></FONT>
<DT>
<DT> 我在<FONT face="Times New Roman">1995</FONT>年香港舉行的世界電腦國(guó)際象棋錦標(biāo)賽<FONT
face="Times New Roman">(WCCC)</FONT>上和 <FONT face="Times New Roman">David
Kittinger
</FONT>交流時(shí)，他跟我說(shuō)了這個(gè)著法產(chǎn)生的技術(shù)，當(dāng)時(shí)我就把它忘了。如今回過(guò)頭來(lái)看，我已經(jīng)很多次提到這個(gè)技術(shù)了。由于當(dāng)時(shí)我還不知道它的名稱，我就給它起了別的名字。它名稱應(yīng)該是<FONT
face="Times New Roman">0x88</FONT>，即十六進(jìn)制的<FONT
face="Times New Roman">88</FONT>。
<DT> 之所以稱為<FONT face="Times New Roman">0x88</FONT>，是因?yàn)?lt;FONT
face="Times New Roman">0x88</FONT>概括了這個(gè)技術(shù)的要點(diǎn)。
<DT> <FONT face="Times New Roman">0x88</FONT>技術(shù)的優(yōu)勢(shì)在于：
<DT> <FONT face="Times New Roman">(1) </FONT>它很容易理解；
<DT> <FONT face="Times New Roman">(2) </FONT>代碼非常短小，一點(diǎn)也不復(fù)雜；
<DT> <FONT face="Times New Roman">(3) </FONT>很容易檢查棋子是否超出邊界。
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>棋盤表示和基本原理</STRONG></FONT>
<DT>
<DT> 通常的國(guó)際象棋棋盤是<FONT face="Times New Roman">8x8</FONT>的格子，格子的“標(biāo)準(zhǔn)”編號(hào)應(yīng)該從<FONT
face="Times New Roman">0</FONT>到<FONT face="Times New Roman">63</FONT>，<FONT
face="Times New Roman">a1</FONT>格是<FONT face="Times New Roman">0</FONT>，<FONT
face="Times New Roman">b1</FONT>格是<FONT face="Times New Roman">1</FONT>，<FONT
face="Times New Roman">a2</FONT>格是<FONT face="Times New Roman">8</FONT>，<FONT
face="Times New Roman">h8</FONT>格是<FONT
face="Times New Roman">63</FONT>，其余的格子由你自己填上。
<DT> <FONT face="Times New Roman">0x88</FONT>采用稍微不同的棋盤，它有<FONT
face="Times New Roman">128</FONT>個(gè)格子，<FONT
face="Times New Roman">a1</FONT>到<FONT
face="Times New Roman">h1</FONT>仍舊是<FONT face="Times New Roman">0</FONT>到<FONT
face="Times New Roman">7</FONT>，但是在<FONT
face="Times New Roman">h</FONT>列右邊還有從未用到的<FONT
face="Times New Roman">i</FONT>到<FONT
face="Times New Roman">p</FONT>列，簡(jiǎn)單地說(shuō)就是把一個(gè)虛的棋盤放在實(shí)的棋盤的右邊。
<DT> 因此<FONT face="Times New Roman">a2</FONT>被編為<FONT
face="Times New Roman">16</FONT>，<FONT face="Times New Roman">a8</FONT>是<FONT
face="Times New Roman">112</FONT>，<FONT face="Times New Roman">h8</FONT>是<FONT
face="Times New Roman">119</FONT>。
<DT> 任意一個(gè)格子都符合下面的公式：
<DD>
<DD>指標(biāo) = 行號(hào) x 16 + 列號(hào)
<DT>
<DT> 你可能會(huì)問為什么要這樣做，其實(shí)有很多理由，這里我們只討論最關(guān)鍵的。這個(gè)理由就是，這樣做可以檢查射線是否走到了棋盤的左邊界或右邊界。
<DT> 你可能仍舊不明白。假設(shè)你仍然用<FONT face="Times New Roman">8x8</FONT>的棋盤，并且考慮<FONT
face="Times New Roman">a3</FONT>格的車，在<FONT
face="Times New Roman">8x8</FONT>的棋盤上它的編號(hào)是<FONT
face="Times New Roman">16</FONT>。現(xiàn)在來(lái)產(chǎn)生這個(gè)車的目標(biāo)格子，先從縱線上的著法開始。在縱線上前進(jìn)一格，就增加<FONT
face="Times New Roman">8</FONT>，<FONT face="Times New Roman">16</FONT>加上<FONT
face="Times New Roman">8</FONT>就得到<FONT
face="Times New Roman">24</FONT>。這個(gè)格子是否在棋盤上呢？在<FONT
face="Times New Roman">8x8</FONT>的棋盤上可以檢查它是否小于<FONT
face="Times New Roman">64</FONT>。現(xiàn)在<FONT
face="Times New Roman">24</FONT>小于<FONT
face="Times New Roman">64</FONT>，所以它在棋盤上。下一個(gè)格子是<FONT
face="Times New Roman">32</FONT>，然后依次是<FONT
face="Times New Roman">40</FONT>、<FONT face="Times New Roman">48</FONT>和<FONT
face="Times New Roman">64</FONT>，<FONT
face="Times New Roman">64</FONT>不小于<FONT
face="Times New Roman">64</FONT>，所以它在棋盤外邊，我們就停了下來(lái)。
<DT> 非常好，現(xiàn)在我們從<FONT face="Times New Roman">a3</FONT>往下走。<FONT
face="Times New Roman">a3</FONT>是<FONT
face="Times New Roman">16</FONT>，減去<FONT
face="Times New Roman">8</FONT>得到<FONT
face="Times New Roman">8</FONT>，它在棋盤上嗎？此時(shí)要檢查它是否大于或等于零，而<FONT
face="Times New Roman">8</FONT>確實(shí)是的。再下一個(gè)格子是<FONT face=Symbol>-</FONT><FONT
face="Times New Roman">8</FONT>，因?yàn)樾∮诹悖圆辉谄灞P上。
<DT> 我們不厭其煩做了兩次測(cè)試，如果只需要做一次測(cè)試那就更好了。現(xiàn)在測(cè)試棋子是否在棋盤上的代碼是：
<DD>
<DD>if ((index < 0) || (index >= 64))
<DT>
<DT> 其實(shí)這就包含了兩次測(cè)試，我們遠(yuǎn)遠(yuǎn)沒有滿足，因?yàn)樗耆梢灾蛔鲆淮螠y(cè)試：
<DD>
<DD>if (!(index & 0x40))
<DT>
<DT> 這就涵蓋了判斷棋子超出棋盤下邊界和超出棋盤上邊界的兩種情況。超出棋盤上邊界時(shí)，由于大于<FONT
face="Times New Roman">64</FONT>而<FONT
face="Times New Roman">0x40</FONT>置為<FONT
face="Times New Roman">1</FONT>，超出棋盤下邊界時(shí)，用補(bǔ)碼表示負(fù)數(shù)的機(jī)制使得<FONT
face="Times New Roman">0x40</FONT>也置為<FONT face="Times New Roman">1</FONT>。
<DT> 如果你還沒有明白，那么你最好停下來(lái)別看下去了，否則下面要說(shuō)的東西對(duì)你來(lái)說(shuō)就是天書。
<DT> 如果你留意一下，你會(huì)注意到我們只讓車朝上朝下走，而沒有讓它朝左朝右走。我們之所以不讓它朝左朝右走，是因?yàn)檫@套機(jī)制不允許這么做，它無(wú)法判斷朝左或朝右的射線是否到達(dá)棋盤的邊界。如果你從<FONT
face="Times New Roman">a3</FONT>開始朝右走，每走一格加<FONT
face="Times New Roman">1</FONT>直到<FONT
face="Times New Roman">h3</FONT>，此時(shí)你可以繼續(xù)加<FONT
face="Times New Roman">1</FONT>到達(dá)<FONT face="Times New Roman">a4</FONT>。<FONT
face="Times New Roman">a4</FONT>仍就在棋盤上，然而沒有什么技巧可以讓你判斷是否超越了<FONT
face="Times New Roman">h</FONT>列。朝左走也一樣，從<FONT
face="Times New Roman">a3</FONT>格開始減<FONT
face="Times New Roman">1</FONT>，就會(huì)到<FONT
face="Times New Roman">h2</FONT>，它仍然在棋盤上，但是國(guó)際象棋里沒有哪個(gè)棋子能這么走。
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -