[教你做小遊戲] 一種記錄象棋曆史記錄的方案：平均每步僅占10bit位

背景

兄弟們，之前我開發了支援聯機對戰的五子棋、鬥地主、UNO。在大家的呼籲之下，我準備開發「象棋」啦！

😄 不出意外，國慶假期，聯機象棋就能跟大家見面了！

之前的進展：

• 《用SVG畫一個象棋棋盤》。
• 《基于svg和ttf(字型檔案)，我僅用6kb就畫完了象棋所有棋子》。
• 《我用43個字元，就存下了象棋的棋盤狀态》。
• 《JS實作象棋移動規則》。

繼續給大家同步進展：今天，設計了象棋曆史記錄的儲存方案，盡可能降低了空間的占用。

基于該方案，我們可以實作悔棋操作，非常實用。

思考

我之前開發的五子棋，是支援悔棋的，并且可以無限悔棋直到第一步。

但是象棋不一樣。象棋的步驟是無限的。随着步數增多，曆史記錄的空間占用一定是線性增長的，并且永不止境。是以我隻會儲存最近1000步（或者9999步等）。

這裡羅列一些方案：

方案	優點	缺點
記錄每次操作後，目前棋局所有棋子的位置	比較無腦，開發快	占用空間大
從初始局面開始，順序記錄使用者操作的棋子、移動後該棋子的位置	占用空間很小	本方案不适用，因為每一次記錄都依賴上一步的局面（不然不知道吃了誰、也不知道移動前的位置）
從現狀局面開始，逆序記錄使用者操作的棋子、移動前該棋子的位置、吃了誰	占用空間相對小

我選了第三個方案，因為它是逆序記錄，可以從目前局面非常快的推演出悔棋後的局面。

資料結構

确定了方案：從現狀局面開始，逆序記錄使用者操作的棋子、移動前該棋子的位置、吃了誰。

還需要決策，具體怎麼存。

初步的方案

• 棋子一共有32個，辨別一個棋子需要用5個二進制位。但是因為紅黑是輪流進行的，是以辨別棋子可以縮短到16個數字，即4個二進制位。
• 而辨別吃掉了誰（也可能沒吃掉），需要17個數字，隻能用5個二進制位了。
• 棋子移動前的位置一共有90個，需要7位二進制來存儲。

共計每一步操作需要4+5+7=16個二進制位。

改進：優化吃掉了誰

其實吃掉将帥後 遊戲就結束了。将帥是否被吃掉，可以通過目前棋盤狀态來看。是以我們可以優化「吃掉了誰」這個變量：把​

​0​

​改為沒吃掉任何人或吃掉了将帥。

這樣每一步操作需要4+4+7=15個二進制位。

改進：優化移動前的位置

我還是不夠滿意，因為每個棋子移動的範圍是有限的：

• 将帥最多有4個可移動範圍。隻需要2位。
• 士最多有4個可移動範圍。隻需要2位。
• 象最多有4個可移動範圍。隻需要2位。
• 兵最多有3個可移動範圍。隻需要2位。
• 馬最多有8個可移動範圍。隻需要3位。
• 車最多有17個可移動範圍。隻需要5位。
• 炮最多有17個可移動範圍。隻需要5位。

而我們知道了使用者操作的棋子是誰，就知道了它的可移動範圍了。

這樣每一步操作需要4+4+2=10至4+4+5=13個二進制位。

改進：優化吃掉了誰