ChessVista開發日記之二：核心問題

2019-11-17 03:51:51

字體：大中小

來源：轉載

供稿：網友

核心問題

好的，我們已經有一個關于ChessVista的基本架構了，現在要看看接下來有哪些核心問題、關鍵任務要解決。

對于一個國際象棋程序，或者也可以說是對所有的棋類博弈程序來說吧，通常有哪些關鍵的問題要解決呢？首先，核心算法——即局面表示、著法生成、搜索算法和局面評估——應該是最關鍵的部分，此外，針對ChessVista的設計目標，還應包括設計博弈引擎的加載、通訊，設計圖形界面用的棋盤控件這兩個任務。

由于國際象棋游戲是所謂的“信息完備”游戲，即對于所有游戲參與者來說，面對的局面是同一個，而且任何一方所掌握的棋盤、棋子的信息是一樣的（相對而言，紙牌類游戲、麻將就不是“信息完備”的，因為你不知道對方手里的牌），所以核心算法也僅針對這類游戲設計，暫不考慮非“信息完備”類游戲。

局面表示

局面是指某個特定時刻，棋盤上棋子的數量和位置的一個“快照”。與我們實際情況下使用的棋盤、棋子不同，在程序中必須要有特定的數據結構來表示它們，并且還要具備有效的算法來獲取、處理這些信息。

一個高效的局面表示方法和處理算法非常重要，因為一旦游戲雙方的對弈開始，在后面的整個過程中，局面數據是不可或缺的信息，包括著法生成、搜索算法、局面評估和界面顯示都離不開它。舉例來說，當對方走了一步棋，ChessVista的引擎必須知道對方走了那個棋子、之前的位置在哪里、新的位置在哪里，然后它要判斷自己有哪些子可以走、可以走到哪里、哪一種走法是最優的，最后它還要把走的結果反映到當前局面上，并通知界面做出相應的修改，可以看出，這些過程中，隨時都要用到棋盤和棋子的局面數據。

當前局面的維護以及基本的局面算法都由ChessVista的棋盤服務負責并提供相應的API。

著法生成

一旦一方的引擎確定了一步走法，ChessVista必須根據國際象棋的規則判斷該走法是否合法，因為若不做這樣的檢查，任何一個引擎都可以通過某種方式欺騙程序。

另一方面，當一個引擎得到走棋的通知，它必須遍歷當前局面，判斷自己有哪些棋子可以走，同樣要根據規則判斷哪些走法是合法的，為后面的搜索算法提供基礎。

雖然上述過程一個是由ChessVista的對弈服務負責，一個由引擎自己負責，但他們依據的都是同一個算法——著法生成，而且實踐也證明，在國際象棋的整個設計中，著法生成是最復雜、最費時的事。

搜索算法

人類棋手在從眾多可選著法中，決定選擇某一個時，通常會在大腦中進行推演，只有盡可能縝密地推演出后繼自己和對手的著法，才能最大限度地選出最好的著法。對于程序來說，這一方法同樣是不二選擇，只不過是不同的程序使用的搜索算法不同罷了。

實際應用中，針對國際象棋的搜索算法有很多種，各有優缺點，這些不同的算法和設計中會遇到的種種值得思考的事，在后面會進一步探討。

局面評估

最后，當要判斷出某一著法是否優于另一種時，或者要判斷當前局面是處于優勢還是劣勢時，必須要有一種評估局面的方法，在象棋程序中，“子力平衡”通常是一個關鍵的評估因素。

考慮到引擎必須在有限的時間內做出評估，選出“最佳”（這里僅指在一定約束條件下做出的最佳判斷）著法，局面評估通常要考慮和搜索算法同時輪流進行，才能保證即使是在有限時間下，也一定有解（有一個不是最佳的解，也比沒有解要強，好像敏捷開發中的迭代也是這個理 ^_^）。

博弈引擎

ChessVista環境和引擎相當于一個小型的C/S結構，初步設想將引擎設計為ChessVista環境的進程內模塊，即設計為DLL，由ChessVista環境動態加載。雙方之間的通訊采用通用的UCI引擎協議，因此要考慮設計一個UCI協議解析模塊，由ChessVista的博弈引擎服務負責，并提供相應接口。同時，還要確定出環境和引擎之間的交互接口規范。

棋盤控件

考慮到棋盤擴展的設計目標，將棋盤單獨做成一個獨立控件，用它來實現棋盤擴展的可視部分邏輯。

好了，在ChessVista這幅圖上，重要的拼圖都已經找出來了，后面，我們就會進入逐個核心問題的實際設計、開發中了，在這個令人激動的探索中，希望大家能一起探討，共同進步。

上一篇：Net 應用程序如何在32位操作系統下申請超過2G的內存

下一篇：List在搜索和排序時采用不同方法的性能比較