國際象棋程序設(shè)計二數(shù)據(jù)結(jié)構(gòu)(已修改)
2025-05-23 20:03 本頁面
【正文】 國際象棋程序設(shè)計 二 數(shù)據(jù)結(jié)構(gòu) 國際象棋程序設(shè)計 (二 )：數(shù)據(jù)結(jié)構(gòu) 20210507 16： 24Fran ois Dominic Laram233。e/文 上個月我簡要介紹了象棋程序設(shè)計中所需要的知識，其他信息完全的雙人游戲也是一樣的?，F(xiàn)在我們將討論一些細(xì)節(jié) 棋盤的內(nèi)部表示方法。在棋盤表示方法這個理念上，近三十年內(nèi)沒有多大發(fā)展，你可能會覺得很吃驚。它的發(fā)展需要智慧的推動，很早就有人提出過絕妙的方案了，但同時也受到制約，因為這些方案需要數(shù)據(jù)結(jié)構(gòu)的支持，某些數(shù)據(jù)結(jié)構(gòu)至今還沒有實現(xiàn)。盡管如此，我還是會介紹三種數(shù)據(jù)結(jié)構(gòu)，盡管它們并不是必需的，但是對于提高你的下棋水平是大有幫助的。其中兩種可以加快思考速度但是其中一種需要無限多的存儲器，另一種可以加快著法產(chǎn)生速度?！咀g 注：分別指后面要提到的置換表、歷史表和著法生成預(yù)處理的數(shù)據(jù)庫?！吭谖覀兝^續(xù)討論之前，我提一句格言： 無論是象棋還是其他游戲，你通常使用的數(shù)據(jù)結(jié)構(gòu)，應(yīng)該是能達到目的的最簡單的數(shù)據(jù)結(jié)構(gòu)。 然而象棋程序設(shè)計者提出了很多技巧，它們能讓程序運行的更快，其中相當(dāng)多的還適用于其他游戲。如果你對你要設(shè)計的游戲不很了解，而且手頭的資料很有限，那么你應(yīng)該好好掌握我所提到的這些技巧，你可以把這些技巧試驗到你的程序上。 基本的棋盤表示 在上世紀(jì) 70年代，個人電腦的存儲器是稀有資源，所以棋盤表示得越緊湊越好。很多人會很自信地說：用一 個 64字節(jié)的數(shù)組，每個字節(jié)表示棋盤上的一個格子，用一個整數(shù)就可以表示格子的位置了。任何棋盤的數(shù)據(jù)結(jié)構(gòu)都必須用一些額外的字節(jié)，來記錄吃過路兵的目標(biāo)格、王車易位權(quán)利等信息，但是這里我們暫且忽略它，因為這些因素可以獨立處理，而且處理方法大同小異。 后來又流行一些更優(yōu)化的算法： SARGON【一個象棋程序】擴展了 64 字節(jié)的數(shù)組，在它的外圍加了兩圈 虛格 ，并在這些格子上作了非法標(biāo)記。這一技巧能加快著法產(chǎn)生的速度，例如象在走棋時會延斜線滑行，直到走到虛格上才中止。這樣就沒有必要用復(fù)雜的運算來預(yù)先判斷象到達的 格子是否會超出存儲器上的表示了。第二圈虛格是給馬用的，例如位于盤角的馬試圖跳出棋盤，這就必須用兩圈虛格來保護。 用了相反的方法，它只用 32 字節(jié)表示一個棋盤，每個字節(jié)代表一個棋子，例如代表白方王、黑方王翼馬前兵【英文居然是 black King39。s Knight39。s Pawn，一開始讓我大惑不解】等，它存儲的信息是棋盤上的位置，或者已經(jīng)被吃的標(biāo)記。這種技術(shù)有一個缺點，它無法描述由兵升變而來的其他棋子同時這個棋子在棋盤上還有一個。在后來的版本中，這個缺點被修正了?！酒鋵嵾@并不難辦，一個字節(jié)取值從 0到 255，通常 255 表示該子已被吃，從 0到 63 表示該子在棋盤上的位置，兵通常是升變成后的，那么從 64到 127可以表示該子已經(jīng)升變?yōu)楹?，如果升變?yōu)檐嚒ⅠR或象，則需要額外的字節(jié)來處理?！? 如今，這種極端吝嗇的數(shù)據(jù)結(jié)構(gòu)只可能出現(xiàn)在掌上電腦、手機或電視機機頂盒上，它們的 80~90%的資源都被操作系統(tǒng)占用，沒有額外的空間給游戲使用。但是，某些游戲卻別無選擇地使用這種方法【我也不知道什么游戲非得使用這種方法不可】。 想更多地了解
法律信息相關(guān)推薦
鄂ICP備17016276號-1