?? 數據結構——0x88著法產生方法.htm
字號:
<!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>數據結構——0x88著法產生方法</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=數據結構——0x88著法產生方法_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT>《對弈程序基本技術》專題 </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>著法產生方法</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>年香港舉行的世界電腦國際象棋錦標賽<FONT
face="Times New Roman">(WCCC)</FONT>上和 <FONT face="Times New Roman">David
Kittinger
</FONT>交流時，他跟我說了這個著法產生的技術，當時我就把它忘了。如今回過頭來看，我已經很多次提到這個技術了。由于當時我還不知道它的名稱，我就給它起了別的名字。它名稱應該是<FONT
face="Times New Roman">0x88</FONT>，即十六進制的<FONT
face="Times New Roman">88</FONT>。
<DT> 之所以稱為<FONT face="Times New Roman">0x88</FONT>，是因為<FONT
face="Times New Roman">0x88</FONT>概括了這個技術的要點。
<DT> <FONT face="Times New Roman">0x88</FONT>技術的優勢在于：
<DT> <FONT face="Times New Roman">(1) </FONT>它很容易理解；
<DT> <FONT face="Times New Roman">(2) </FONT>代碼非常短小，一點也不復雜；
<DT> <FONT face="Times New Roman">(3) </FONT>很容易檢查棋子是否超出邊界。
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>棋盤表示和基本原理</STRONG></FONT>
<DT>
<DT> 通常的國際象棋棋盤是<FONT face="Times New Roman">8x8</FONT>的格子，格子的“標準”編號應該從<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>個格子，<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>列，簡單地說就是把一個虛的棋盤放在實的棋盤的右邊。
<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> 任意一個格子都符合下面的公式：
<DD>
<DD>指標 = 行號 x 16 + 列號
<DT>
<DT> 你可能會問為什么要這樣做，其實有很多理由，這里我們只討論最關鍵的。這個理由就是，這樣做可以檢查射線是否走到了棋盤的左邊界或右邊界。
<DT> 你可能仍舊不明白。假設你仍然用<FONT face="Times New Roman">8x8</FONT>的棋盤，并且考慮<FONT
face="Times New Roman">a3</FONT>格的車，在<FONT
face="Times New Roman">8x8</FONT>的棋盤上它的編號是<FONT
face="Times New Roman">16</FONT>。現在來產生這個車的目標格子，先從縱線上的著法開始。在縱線上前進一格，就增加<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>。這個格子是否在棋盤上呢？在<FONT
face="Times New Roman">8x8</FONT>的棋盤上可以檢查它是否小于<FONT
face="Times New Roman">64</FONT>。現在<FONT
face="Times New Roman">24</FONT>小于<FONT
face="Times New Roman">64</FONT>，所以它在棋盤上。下一個格子是<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>，所以它在棋盤外邊，我們就停了下來。
<DT> 非常好，現在我們從<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>，它在棋盤上嗎？此時要檢查它是否大于或等于零，而<FONT
face="Times New Roman">8</FONT>確實是的。再下一個格子是<FONT face=Symbol>-</FONT><FONT
face="Times New Roman">8</FONT>，因為小于零，所以不在棋盤上。
<DT> 我們不厭其煩做了兩次測試，如果只需要做一次測試那就更好了。現在測試棋子是否在棋盤上的代碼是：
<DD>
<DD>if ((index < 0) || (index >= 64))
<DT>
<DT> 其實這就包含了兩次測試，我們遠遠沒有滿足，因為它完全可以只做一次測試：
<DD>
<DD>if (!(index & 0x40))
<DT>
<DT> 這就涵蓋了判斷棋子超出棋盤下邊界和超出棋盤上邊界的兩種情況。超出棋盤上邊界時，由于大于<FONT
face="Times New Roman">64</FONT>而<FONT
face="Times New Roman">0x40</FONT>置為<FONT
face="Times New Roman">1</FONT>，超出棋盤下邊界時，用補碼表示負數的機制使得<FONT
face="Times New Roman">0x40</FONT>也置為<FONT face="Times New Roman">1</FONT>。
<DT> 如果你還沒有明白，那么你最好停下來別看下去了，否則下面要說的東西對你來說就是天書。
<DT> 如果你留意一下，你會注意到我們只讓車朝上朝下走，而沒有讓它朝左朝右走。我們之所以不讓它朝左朝右走，是因為這套機制不允許這么做，它無法判斷朝左或朝右的射線是否到達棋盤的邊界。如果你從<FONT
face="Times New Roman">a3</FONT>開始朝右走，每走一格加<FONT
face="Times New Roman">1</FONT>直到<FONT
face="Times New Roman">h3</FONT>，此時你可以繼續加<FONT
face="Times New Roman">1</FONT>到達<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>，就會到<FONT
face="Times New Roman">h2</FONT>，它仍然在棋盤上，但是國際象棋里沒有哪個棋子能這么走。
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -