國際象棋程序設計(二):數據結構
 
François Dominic Laramée/
 
  上個月我簡要介紹了象棋程序設計中所需要的知識,其他信息完全的雙人游戲也是一樣的。現在我們將討論一些細節——棋盤的內部表示方法。
  在棋盤表示方法這個理念上,近三十年內沒有多大發展,你可能會覺得很吃驚。它的發展需要智慧的推動,很早就有人提出過絕妙的方案了,但同時也受到制約,因為這些方案需要數據結構的支持,某些數據結構至今還沒有實現。
  盡管如此,我還是會介紹三種數據結構,盡管它們并不是必需的,但是對于提高你的下棋水平是大有幫助的。其中兩種可以加快思考速度(但是其中一種需要無限多的存儲器),另一種可以加快著法產生速度。【譯注:分別指后面要提到的置換表、歷史表和著法生成預處理的數據庫。】
  在我們繼續討論之前,我提一句格言:“無論是象棋還是其他游戲,你通常使用的數據結構,應該是能達到目的的最簡單的數據結構。”然而象棋程序設計者提出了很多技巧,它們能讓程序運行的更快,其中相當多的還適用于其他游戲。如果你對你要設計的游戲不很了解,而且手頭的資料很有限,那么你應該好好掌握我所提到的這些技巧,你可以把這些技巧試驗到你的程序上。
 
基本的棋盤表示
 
  在上世紀70年代,個人電腦的存儲器是稀有資源,所以棋盤表示得越緊湊越好。很多人會很自信地說:用一個64字節的數組,每個字節表示棋盤上的一個格子,用一個整數就可以表示格子的位置了。(任何棋盤的數據結構都必須用一些額外的字節,來記錄吃過路兵的目標格、王車易位權利等信息,但是這里我們暫且忽略它,因為這些因素可以獨立處理,而且處理方法大同小異。)
  后來又流行一些更優化的算法:
 
  1. 早期的SARGON【一個象棋程序】擴展了64字節的數組,在它的外圍加了兩圈“虛格”,并在這些格子上作了非法標記。這一技巧能加快著法產生的速度,例如象在走棋時會延斜線滑行,直到走到虛格上才中止。這樣就沒有必要用復雜的運算來預先判斷象到達的格子是否會超出存儲器上的表示了。第二圈虛格是給馬用的,例如位于盤角的馬試圖跳出棋盤,這就必須用兩圈虛格來保護。
  2. MYCHESS用了相反的方法,它只用32字節表示一個棋盤,每個字節代表一個棋子,例如代表白方王、黑方王翼馬前兵【英文居然是black King's Knight's Pawn,一開始讓我大惑不解】等,它存儲的信息是棋盤上的位置,或者已經被吃的標記。這種技術有一個缺點,它無法描述由兵升變而來的其他棋子(同時這個棋子在棋盤上還有一個)。在后來的版本中,這個缺點被修正了。【其實這并不難辦,一個字節取值從0255,通常255表示該子已被吃,從063表示該子在棋盤上的位置,兵通常是升變成后的,那么從64127可以表示該子已經升變為后,如果升變為車、馬或象,則需要額外的字節來處理。】
 
  如今,這種極端吝嗇的數據結構只可能出現在掌上電腦、手機或電視機機頂盒上,它們的80~90%的資源都被操作系統占用,沒有額外的空間給游戲使用。但是,某些游戲卻別無選擇地使用這種方法【我也不知道什么游戲非得使用這種方法不可】
  想更多地了解以前的象棋程序,可以看一下David Welsh1984年寫的《計算機象棋》(Computer Chess)一書。
 
位棋盤
 
  用一個數組來表示棋盤,對于很多游戲來說,就找不到更好的辦法了。但是對于像象棋、西洋跳棋之類在64格棋盤上的游戲來說,有一個高明的技巧——“位棋盤” (首先由蘇聯的KAISSA制作組提出),在上世紀60年代末誕生了。
  KAISSA是運行在64位處理器上的程序【我很懷疑當時就有64位處理器,或許當時處理器字長的概念和現在的有所不同】。“64”恰巧是象棋棋盤格子的數目,所以這就有可能讓一個字來表示一個棋盤,以判斷某個格子的狀態是“是”或者“非”。例如,一個位棋盤可以回答棋盤的每個格子“是否有白子”。【把位棋盤運用到中國象棋上,這是我將要進行的一個課題,中國象棋的棋盤有90個格點,可以用332位的字來表示。】
  因此,一個完整的局面需要用12個位棋盤表示:白兵、白車、黑兵等等。再加上兩個用來表示“所有白子”和“所有黑子”的位棋盤,以加快運算速度。【其實只需要8個就可以了,同一兵種(不管黑白)用一個位棋盤,一共是6個,再加上代表“所有白子”和“所有黑子”的。做得更過分的是,有人把象和后并作一個位棋盤,車和后并作一個位棋盤,這樣又可以減少一個。如果要表示白方的象,只要“所有白子”、“所有車或后”的補集(用“非”運算)、“所有象或后”這三個位棋盤作“與”運算就可以了。】或許你還想用一個位棋盤表示被某種子力攻擊到的格子,諸如此類,這些位棋可以盤靈活運用在著法產生的運算過程中。
  位棋盤之所以有效,是因為很多運算可以轉化為處理器的一個邏輯指令。例如,假設你需要確認黑王被白后將軍,如果用簡單的數組來表示棋盤,那么你需要這樣做:
 
  1. 首先找到后的位置,這需要從64個字節中一個一個地找;
  2. 然后在后所能走的八個方向找,直到找到王或者找到后走不到的格子為止。
 
  這些運算是相當花費時間的,如果后碰巧是在數組的最后一格,更糟的是,將軍只會發生在少數情況下【這種運算純粹是白費時間!】
  如果用位棋盤,那你只要這樣做:
 
  1. 載入“白方后的位置”的位棋盤;
  2. 根據這個位置,從索引數據庫中找到被后攻擊的位棋盤;
  3. 用這個位棋盤和“黑方王的位置”的位棋盤作“與”運算。
 
  如果結果不是零,則說明黑王被白后將軍。假設被后攻擊的位棋盤是儲藏于存儲器中的【這是上面提到的第二步的前提】,那么整個操作只需要34個時鐘周期【通常計算機執行1條指令需要1(算術或邏輯運算)2(尋址操作)個時鐘周期】
  【這里允許我發揮一下,原作所說的“從索引的數據庫中找到”(即上面提到的第二步),其實并非是簡單的一步,對于后的每個位置,都有一定的攻擊格子(從邊線到中心依次是21232527),但是要考慮被別的子阻擋的情況,程序無法為所有的情況都作索引,最多只能對某條線(橫線、縱線或斜線)的棋子占有情況作索引,這也需要28 = 256 種情況,再加后本身有64種位置,所以即使這樣,數據庫中也至少要保存256x64 = 16384個位棋盤。另外,橫線、縱線和兩條斜線的處理方法各不相同,橫線只要作簡單的“移位運算”就可以了,而縱線和兩條斜線都要用到“位棋盤旋轉”的技術,為了提高運算效率,程序的復雜程度是驚人的,細節可以參考《對弈程序基本技術》專題之《數據結構——旋轉的位棋盤》一文,文中作者多次提示讀者用咖啡來提神,以完成煩瑣的程序。】
  再舉一個例子,如果在當前的棋盤上,你要產生白馬的所有著法,那么你只要找到當與前位置相關聯的“馬能走到的格子”的位棋盤,并“與”(AND)上“所有被白方占有的格子”的位棋盤的補集(就是對這個位棋盤作“非”(NOT)運算),因為馬的著法限制僅僅在于它不能去吃自己的子。【國際象棋比較簡單,而中國象棋中還有“絆馬腿”的限制(還有象也是),這種情況該怎樣使用位棋盤,也是我將要研究的課題。】
  如果你想更詳細地了解位棋盤(也只是稍微詳細一點而已),可以去看看描述CHESS 4.5 (它是由美國西北大學開發的)的文章——Peter Frey寫的《人腦和電腦的象棋技巧》(Ches Skill in Man and Machine),現在至少已經出了兩版了,分別出版于1977年和1981年。
  值得注意的事,到今天為止,幾乎還沒有真正意義上使用64位處理器的個人電腦,所以位棋盤的速度優勢是要打折扣的。盡管如此,位棋盤的技術仍是行之有效的。【蘋果公司的Macintosh圖形工作站據說是64位處理器,但不知有沒有針對這種電腦的象棋軟件。時隔4年,到我翻譯這篇文章時,還沒有什么別的64位處理器用在個人電腦上。因為畢竟沒這個必要,除非你專門用它來玩國際象棋。】
 
置換表
 
  在象棋里,有很多著法可以到達相同的位置。例如,不管你先走 1. P-K4 ... 2. P-Q4或者1. P-Q4... 2.P-K4【這里K4Q4e4d4的,在實戰中有這樣的例子,1. e4 e6 2. d41. d4 e6, 2. e4是形成法蘭西防御一種變例的兩種途徑。】最終局面是一樣的。有不同的路線可以達到同樣位置的,這種現象稱為“置換”(Transposing)【在中國象棋中,置換現象更為普遍,通常用成語“殊途同歸”來稱呼這種現象。】
  如果你的程序已經對1. P-Q4... 2.P-K4產生的結果竭盡全力作了搜索和評估,那么你最好記住這個結果,以避免碰到1. P-K4... 2.P-Q4時再作同樣的運算。自上世紀60年代Richard GreenblattMac Hack VI問世以來,所有的對弈程序都會吸納“置換表”這一技術,這就是原因所在。
  置換表存儲的是已經搜索過的結果,它通常使用類似于散列表(Hash Dictionary)的數據結構來達到最快的查詢速度。在搜索某個局面時,結果(包括局面分析的值、搜索深度、最佳著法等)就存儲到置換表里。當搜索新的局面時,我們先從置換表里找,如果已經有這種局面,那么就可以利用它,省去重復的搜索。
  這種處理有以下很多好處:
 
  1. 加快速度。在置換情況發生得很多時(特別是殘局局面里,棋盤上棋子很少時)90%以上的局面可以在表中找到。【在中國象棋中,這優勢時更為明顯,因為它的子力密度小,在開局階段就有很多“殊途同歸”的現象。】
  2. 任意深度。假設你需要對某個局面搜索到一個指定的深度,例如4(也就是兩個回合),如果置換表里有這個局面而且已經搜索了6步,那么你不僅可以跳過這次搜索,還可以得到比預期更精確的結果。
  3. 用途廣泛。通常每個象棋程序都配有“開局庫”(Opening Book),即包含一些常見局面及其最好的著法,這些通常是從已有的記載中提煉的【例如特級大師們寫的“象棋開局大全”或“象棋開局手冊”之類的書,而我本人更傾向于從大量對局記錄中提煉的結果】。有了開局庫,程序就不必在開局階段就做傻事了【因為前人已經做過無數次的計算了】。既然開局庫的操作過程和置換表是一樣的(即搜索局面),那么為什么不在棋局一開始就把開局庫裝入我們的置換表里去呢?如果這樣做,即使棋局暫時脫離了開局庫,后來又回到開局庫里的局面【要注意,這個局面可以是棋局過程中出現的局面,但更多的情況是搜索程序推演到的】,那么置換表里保留了這樣的局面,我們仍舊有機會用到它。
 
  置換表唯一的缺點就是它貪婪地占用著存儲器,無論如何它至少需要存儲成千上萬個局面,百萬甚至上億就更好了。如果每個局面用16字節【用最緊湊的辦法至少也需要32字節(MYCHESS這種吝嗇的辦法),但是這里可以存放“散列鍵值”,下面會提到這個技術】,那么在存儲器緊缺的時候這將成為很嚴重的問題。
  置換表還有其他用途。
  CHESS 4.5還用散列表來存儲其他的局面計算結果【指下面提到的兵型、子力平衡等】,這些計算結果在多數情況下是不會變動的,例如:
  1. 兵型(Pawn Structure)。散列表只存儲兵的位置,這需要較小的存儲空間,由于兵的移動不會很頻繁,所以99%的兵型局面可以在散列表中找到;【國際象棋的局面分析中,需要考慮連兵、疊兵、孤兵、通路兵等因素,這些計算是相當費時的,而中國象棋就沒有這個必要了。】
  2. 子力平衡(Material Balance),即棋盤上子力的相對強弱,它只在吃子或兵升變時變動。
  在CPU速度不快的今天,這些方法或許看來用處不是很大,但是它們還是有指導意義的,一些稍微花費存儲器的預處理可以節省相當多的計算。【因為尋址操作(特別指在若干M的大范圍區域內尋址)所占用的時間要遠多于簡單的運算指令,如果哪天尋址操作的速度接近于基本運算了,那么這種技術將會對程序運行速度有很大的提升。】如果你仔細研究你的程序,或許你會發現這方面是值得改進的。
 
為棋盤產生散列鍵值
 
  上面提到的置換表的結構,是由散列表來實現的,由此引發了以下課題:你如何快速而有效地從棋盤來產生散列鍵值(Hash Key)
  以下是1970Zobrist的方案。
  1. 產生12x64N位的隨機數(如果置換表能儲存2N個局面),并把他們做成一張表。每個隨機數只跟某個位置上的某種棋子有關(例如H4格的黑車),空的格子用零表示;【因為棋子總共有12種,棋盤總共有64格,所以是12x64個數,空的格子不用隨機數而用0表示。】
  2. 先把散列鍵值設為零;
  3. 搜索整個棋盤,每遇到一個子,就在原來的散列鍵值上“異或”(XOR)它所對應的隨機數,重復這個過程直到整個棋盤被檢查一遍。
  這個方案有趣的一面在于,每走一步,散列鍵值的更新都非常容易,不需要重新搜索整個棋盤。你知道“XOR圖形處理”(XOR-Graphics)嗎?某個圖形用XOR運算作用到背景上,然后再作同樣一次運算,不就又回到背景了嗎?這里也同樣這么做。【如果你熟悉圖形操作中的技術,就不難理解了,原文把這個過程比作“位圖”(Bitmap)操作,12x64個棋子的狀態就對應12x64張位圖,原先的散列鍵值被比作“背景”(Background),只要在背景上作位圖的粘貼操作(用的是XOR處理)就可以了。】舉個H1格的白車吃掉了H4格的黑兵的例子,要產生這個散列鍵值,先XOR“在H1格的白車”這個隨機數(把這個圖形擦掉),然后是“在H4格的黑兵”(把這個圖形也擦掉)和“在H4格的白車”(粘貼一個新的圖形,代表新的車的位置)【其實順序是無關緊要的】
  用相同的方法,不同的隨機數,可以產生第二個散列鍵值,或稱“散列鎖”(Hash Lock)【在英語中Lock()Key(鑰匙)是對應的】,它是在置換表中存儲的真正有用的信息。這個技術是用來檢測沖突的,如果恰巧有兩個局面具有相同的散列鍵值,那么他們具有同樣的散列鎖的幾率是微乎其微的。
 
歷史表
 
  “歷史啟發”(History Heuristic)是“殺手著法”(Killer Move)【殺手著法指能產生截斷的著法,以后的連載會提到的】技術的衍生技術。一篇研究性的文章是這么解釋的,歷史表用來保存這些著法,在過去的搜中非常有意義(因為使用高效搜索技術的而對它進行了很深的搜索),這個著法今后還可能用到。歷史表由一個64x64的整數數組構成【著法的起始格和到達格,共有64x64種組合】,記錄每種著法的數值,當搜索算法認為某個著法很有用時,它會讓歷史表增加這步的數值。表中的數值是用來對著法排序的,“歷史上占優勢”的著法會優先考慮。
 
著法產生的預處理
 
  著法的產生(即決定特定位置下那些著法是合理的)和局面的估計一樣,是象棋程序設計中計算量最大的部分。因此,在這個方面的一點預處理會對提高速度大有幫助。
  我個人喜歡Jean Goulet1984年寫的《象棋的數據結構》(Data Structures for ChessMcGill大學出版社)一書中提到的方案,它概括為:
 
  1. 出于著法產生的目的,棋子的顏色是無關緊要的,除了兵以外,它只朝對面走;
  2. 對于基本的子力和它的位置,有64x5=320種組合【指除了兵以外的5種棋子,根據上一條,這些棋子是不分黑白的】,黑兵有48個格子可以放(他們后面一行是走不到的,并且一到第八行就會變成別的棋子),白兵也有48個格子;
  3. 從某個格子沿某個方向,可以確定一條著法“射線”,例如,后從H3格朝北走,這就是一條“射線”;
  4. 每個格子上的每個棋子,都有確定的幾條射線可以走,例如位于中央的王可以朝8個方向走,而位于盤角的象卻只有一條逃生的路;
  5. 在開始游戲之前,要計算數據庫里在所有格子的所有棋子的所有射線,假設棋盤是空的(即著法只受到棋盤邊緣的限制,不受其他棋子的限制)
  6. 當你為某個格子的某個棋子產生著法時,朝每個方向搜索直到碰到棋子為止。如果是對方的棋子,最后一種著法就是吃子的著法,如果是本方的棋子,最后一種著法就是不合理的。
 
  有了恰當的數據庫,著法的產生就變成簡單得接近于線性的尋找了,幾乎用不著什么計算。整個事情就掌握在這么幾千個字節里,只是置換表的一個零頭。
 
  以上提到的所有技術(位棋盤、置換表、歷史表和預處理數據庫)都會反映在我自己的程序中,當我寫完這個連載以后就會發布出來。下個月我會詳細介紹著法產生的方法。
 
  François Dominic Laramée20006
 
  原文:http://www.gamedev.net/reference/programming/features/chess2/
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 國際象棋程序設計():引言
  • 下一篇 國際象棋程序設計():著法的產生
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果