《對弈程序基本技術》專題
 
0x88著法產生方法
 
Bruce Moreland /
 
歷史
 
  我在1995年香港舉行的世界電腦國際象棋錦標賽(WCCC)上和 David Kittinger 交流時,他跟我說了這個著法產生的技術,當時我就把它忘了。如今回過頭來看,我已經很多次提到這個技術了。由于當時我還不知道它的名稱,我就給它起了別的名字。它名稱應該是0x88,即十六進制的88
  之所以稱為0x88,是因為0x88概括了這個技術的要點。
  0x88技術的優勢在于:
  (1) 它很容易理解;
  (2) 代碼非常短小,一點也不復雜;
  (3) 很容易檢查棋子是否超出邊界。
 
棋盤表示和基本原理
 
  通常的國際象棋棋盤是8x8的格子,格子的“標準”編號應該從063a1格是0b1格是1a2格是8h8格是63,其余的格子由你自己填上。
  0x88采用稍微不同的棋盤,它有128個格子,a1h1仍舊是07,但是在h列右邊還有從未用到的ip列,簡單地說就是把一個虛的棋盤放在實的棋盤的右邊。
  因此a2被編為16a8112h8119
  任意一個格子都符合下面的公式:
 
指標 = 行號 x 16 + 列號
 
  你可能會問為什么要這樣做,其實有很多理由,這里我們只討論最關鍵的。這個理由就是,這樣做可以檢查射線是否走到了棋盤的左邊界或右邊界。
  你可能仍舊不明白。假設你仍然用8x8的棋盤,并且考慮a3格的車,在8x8的棋盤上它的編號是16。現在來產生這個車的目標格子,先從縱線上的著法開始。在縱線上前進一格,就增加816加上8就得到24。這個格子是否在棋盤上呢?在8x8的棋盤上可以檢查它是否小于64。現在24小于64,所以它在棋盤上。下一個格子是32,然后依次是40486464不小于64,所以它在棋盤外邊,我們就停了下來。
  非常好,現在我們從a3往下走。a316,減去8得到8,它在棋盤上嗎?此時要檢查它是否大于或等于零,而8確實是的。再下一個格子是-8,因為小于零,所以不在棋盤上。
  我們不厭其煩做了兩次測試,如果只需要做一次測試那就更好了。現在測試棋子是否在棋盤上的代碼是:
 
if ((index < 0) || (index >= 64))
 
  其實這就包含了兩次測試,我們遠遠沒有滿足,因為它完全可以只做一次測試:
 
if (!(index & 0x40))
 
  這就涵蓋了判斷棋子超出棋盤下邊界和超出棋盤上邊界的兩種情況。超出棋盤上邊界時,由于大于640x40置為1,超出棋盤下邊界時,用補碼表示負數的機制使得0x40也置為1
  如果你還沒有明白,那么你最好停下來別看下去了,否則下面要說的東西對你來說就是天書。
  如果你留意一下,你會注意到我們只讓車朝上朝下走,而沒有讓它朝左朝右走。我們之所以不讓它朝左朝右走,是因為這套機制不允許這么做,它無法判斷朝左或朝右的射線是否到達棋盤的邊界。如果你從a3開始朝右走,每走一格加1直到h3,此時你可以繼續加1到達a4a4仍就在棋盤上,然而沒有什么技巧可以讓你判斷是否超越了h列。朝左走也一樣,從a3格開始減1,就會到h2,它仍然在棋盤上,但是國際象棋里沒有哪個棋子能這么走。
  而0x88機制恰恰可以解決這個問題。用一個16x8的棋盤,就得到一個標志位,你就能知道棋子是否到了右邊那個沒用的棋盤上,因為在這個棋盤上0x08位置為1。例如h1標號是7,加1后就是8,而0x08位變成了1。左邊的實棋盤上沒有一格的0x08位是1,而右邊的虛棋盤每個格子的0x08位都是1。如果你在a3并且要朝左走,你會到達p2,這是在虛棋盤上,0x08位是1
  可以把0x08的檢測和0x80的檢測結合起來(原來的0x40變成了0x80,因為現在棋盤變成128個格子了),并且兩次測試要同時完成。把0x800x08結合起來就是0x88,這就是這套方案的名稱。
  如果你知道我在說什么,你就明白0x88是怎樣運作的。你的著法產生的循環就應該寫成下面的樣子:
 
while (!(index & 0x88)) {
 GenerateMove(index);
 index += delta;
}
 
  這就非常簡潔了,你可以這么寫:
 
void GenerateMoves(int square, int * ptab) {
 for (; *ptab; ptab++) {
  int index;
  for (index = square; !(index & 0x88); index += *ptab) {
   GenerateMove(index);
  }
 }
}
int argdBishop[] = { 17, 15, -17, -15, 0 };
void GenerateBishopMoves(int square) {
 GenerateMove(square, argdBishop);
}
 
  這樣寫就非常快了,并且代碼很短。車或者后跟象的區別只是表中的數據不同罷了,因此你可以花很短的時間把其他棋子的代碼加上,而且不需要任何改動。
  當然,你仍然需要為兵和王車易位另寫代碼,但每個體系都得如此。0x88體系能給你一點幫助,可是代碼寫出來仍然很丑。
 
獎勵
 
  0x88體系還可以快速判斷攻擊,這就是要使用16x8棋盤的另一個原因。如果你將兩格子的號碼相減,你會得到兩個格子之間的關系。
  例如,如果兩個格子減下來是1,那么第二個格子就在第一個格子的左邊。如果減下來是16,那么第二個格子就在第一個格子的上面。
  這在8x8棋盤上是做不到的。d1 - c1 = 1確實如此,但是a2 - h1也是1。這個“回圈”問題可以在128個格子的棋盤上解決。
  你在寫判斷將軍或者一個子是否在捉另一個子的函數時,可以利用以上這個技巧。
  你可以用一個大約257個元素(-128 ~ +128)的數組,里面存放一些代表棋子的位域,來說明哪些棋子能在某兩格間移動,而移動的增量就是數組的指標。你可以用少于257個的元素,但是我沒有嘗試過。
  例如在增量為1的元素里,應該有王、后、車的位置是置1的。如果增量是17,那么置1的是王、后、象和白兵。
  這樣就可以寫出比較快的檢查將軍的程序了。你把攻擊子的格子和目標格子相減得到增量,加上128以避免負的指標,然后去找預先計算好的攻擊數組,看看是否符合這個攻擊子的類型,以確認它有可能一步到達目標格。
  如果你確認這個子可能到達目標格,那么你還要檢查它是否是長兵器(后、車或象)。如果不是,那就完成判斷了,否則你要沿著從攻擊子到目標格的射線去找有沒有阻擋的棋子。
  我不想提供這個程序的代碼,因為它很容易寫。這個程序的速度是比較快的。
 
  原文:http://www.seanet.com/~brucemo/topics/0x88.htm
  譯者:象棋百科全書網 ([email protected])
  類型:全譯
  • 上一篇 數據結構——著法生成器
  • 下一篇 數據結構——Zobrist鍵值
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果