國際象棋程序設計二數(shù)據結構-文庫吧
2025-04-17 20:03 本頁面
【正文】 以前的象棋程序，可以看一下 David Welsh 在 1984 年寫的《計算機象棋》 (Computer Chess)一書。 位棋盤 用一個數(shù)組來表示棋盤，對于很多游戲來說，就找不到更好的辦法了。但是對于像象棋、西洋跳棋之類在 64格棋盤上的游戲來說，有一個高明的技巧 位棋盤 首先由蘇聯(lián)的 KAISSA 制作組提出，在上世紀 60 年代末誕生了。 KAISSA 是運行在 64 位處理器上的程序【我很懷疑當時就有 64位處理器，或許當時處理器字長的概念和現(xiàn)在的有所不同】。 64恰巧是象棋棋盤格子的數(shù)目，所以這就有可能讓一個字來表示一個棋盤，以判斷某個格子的狀態(tài)是 是或者 非 。例如，一個位棋盤可以回答棋盤的每個格子 是否有白子 ?！景盐黄灞P運用到中國象棋上，這是我將要進行的一個課題，中國象棋的棋盤有 90 個格點，可以用 3個 32位的字來表示?！恳虼耍粋€完整的局面需要用 12個位棋盤表示：白兵、白車、黑兵等等。再加上兩個用來表示 所有白子 和 所有黑子 的位棋盤，以加快運算速度?！酒鋵嵵恍枰?8個就可以了，同一兵種不管黑白用一個位棋盤，一共是 6個，再加上代表 所有白子 和 所有黑子 的。做得更過分的是，有人把象和后并作一個位棋盤，車和后并作一個位棋盤，這樣又可以減少一個。如果要表示白方的象，只要 所有白子 、 所有車或后 的 補集用 非 運算、 所有象或后 這三個位棋盤作 與 運算就可以了?！炕蛟S你還想用一個位棋盤表示被某種子力攻擊到的格子，諸如此類，這些位棋可以盤靈活運用在著法產生的運算過程中。 位棋盤之所以有效，是因為很多運算可以轉化為處理器的一個邏輯指令。例如，假設你需要確認黑王被白后將軍，如果用簡單的數(shù)組來表示棋盤，那么你需要這樣做： ，這需要從 64個字節(jié)中一個一個地找； ，直到找到王或者找到后走不到的格子為止。 這些運算是相當花費時間的，如果后碰巧是在數(shù)組的最后一格，更 糟的是，將軍只會發(fā)生在少數(shù)情況下【這種運算純粹是白費時間！】。如果用位棋盤，那你只要這樣做： 白方后的位置 的位棋盤； ，從索引數(shù)據庫中找到被后攻擊的位棋盤； 黑方王的位置 的位棋盤作 與 運算。 如果結果不是零，則說明黑王被白后將軍。假設被后攻擊的位棋盤是儲藏于存儲器中的【這是上面提到的第二步的前提】，那么整個操作只需要 3到 4個時鐘周期【通常計算機執(zhí)行 1 條指令需要 1(算術或邏輯運算到 2(尋址操作個時鐘周期】。【這里允許我發(fā)揮一下，原作所說的 從索引的數(shù)據庫中找 到 即上面提到的第二步，其實并非是簡單的一步，對于后的每個位置，都有一定的攻擊格子從邊線到中心依次是 2 2 25和 27格，但是要考慮被別的子阻擋的情況，程序無法為所有的情況都作索引，最多只能對某條線橫線、縱線或斜線的棋子占有情況作索引，這也需要 28=256 種情況，再加后本身有 64 種位置，所以即使這樣，數(shù)據庫中也至少要保存 256x64=16384 個位棋盤。另外，橫線、縱線和兩條斜線的處理方法各不相同，橫線只要作簡單的 移位運算 就可以了，而縱線和兩條斜線都要用到 位棋盤旋轉 的技術，為了提高運算效率，程序 的復雜程度是驚人的，細節(jié)可
法律信息相關推薦
鄂ICP備17016276號-1