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