為了演示博弈樹的搜索和評估算法，我做了一個井字棋（tic-tac-toe）遊戲的算法實現。而為了評估遊戲AI的智商和可靠性，需要一個平臺可以讓用戶和遊戲的 AI 進行對戰博弈，於是我又做了一個支持棋類遊戲對弈的軟件框架。
在《算法的樂趣》一書的準備過程中，黑白棋（Othello 棋）和五子棋的實現也先後被加入到這個框架中，在此過程中，這個軟件框架進行了持續的改進和重構，今天我們就來說說這個博弈遊戲對戰框架的設計和重構的思路。
首先說一下設計這個框架的目的，算是需求說明吧。為了演示博弈樹的搜索和評估算法，我們需要一個井字棋（tic-tac-toe）遊戲的算法實現。而為了評估遊戲 AI 的智商和可靠性，又需要一個平臺可以讓用戶和遊戲的 AI 進行對戰博弈。用戶通過字符界面輸入要落子的位置，AI 通過博弈樹的搜索得到一個最佳落子位置，記為雙方各下一手棋。與此同時，為了能夠評估各種搜索算法和評估函數的能力，我還需要兩個電腦 AI 之間能互相對戰。初步設想是通過 1000 局隨機對弈模擬，統計各種評估算法獲勝的比例，確定哪種評估算法棋力更強。
綜合考慮了一下，這個框架應該能做到以下幾點：
- 支持兩種類型的玩家角色，一種是人類玩家，一種是 AI 玩家。人類玩家由人類控制落子，AI 玩家通過博弈樹搜索確定最佳落子位置；
- AI 玩家可以選擇搜索算法和估值算法。搜索算法可以是“極大極小值”算法、“帶 α-β 剪枝的極大極小值”算法、“負極大值”算法等等。同樣評估算法根據估值策略和理論的不同，也可以有多種不同的估值算法；
- 需要一個控制器控制兩個玩家交替落子，並給出輸贏結果。
根據直覺的樸素設計
方案概況
根據需求的描述，這個系統應該有人類玩家對象、計算機 AI 玩家對象、估值算法對象、搜索算法對象和遊戲控制器對象 5 個對象。經驗告訴我們，估值算法和搜索算法需要基礎數據模型的支撐，這個基礎數據模型就是棋盤狀態對象。基於直覺的設計，就是一種“車到山前就修條路”，“船到橋頭就把船弄直”的樸素方法。不要小看樸素設計，這是進一步重構演化的基礎，比束手無措要強很多了。在樸素設計者眼中，這 6 個對象的關係非常簡單，如下圖所示：
圖（1）樸素的設計架構
實現
GameControl 對象控制一個人類玩家對象和一個計算機 AI 玩家對象，讓雙方輪流選擇一個位置落子。因為 m_player1 和 m_player2 是兩個不同的對象，它們之間沒有公共的抽象接口，所以Run()函數不得不分別處理它們兩個。
int GameControl::Run()
{
while(!m_gameState.IsGameOver())
{
if(m_player1 是人類玩家)
np = m_player1.GetNextPosition();
else
np = m_player1.SearchBestPosition(m_gameState);
m_gameState.PlayAt(np, m_player1);
...
if(m_player2 是人類玩家)
np = m_player2.GetNextPosition();
else
np = m_player2.SearchBestPosition(m_gameState);
m_gameState.PlayAt(np, m_player2);
...
}
return m_gameState.GetWinner();
}
人類玩家對象和計算機 AI 玩家對象都需要提供一個獲取落子位置的接口，在樸素設計方案中，這兩個接口可以有不同的名字，甚至有不同的接口參數，因為 GameControl 無論如何都要單獨處理它們，所以也沒必要統一接口。兩種不同的玩家對象，獲取落子位置的方法不同。人類玩家由用戶輸入，可以是圖形界面通過鼠標輸入，也可以是控制檯界面，用戶直接輸入數字代表位置。計算機 AI 玩家則需要依靠搜索算法對象搜索和評估一個最好的落子位置，代碼實現大概是這個樣子：
int HumanPlayer::ChooseNextPosition()
{
...通過用戶界面控制獲取用戶選擇的落子位置
}
int ComputerPlayer::SearchBestPosition(GameState& state)
{
// 由搜索算法獲取一個最佳落子位置
int np = m_searcher->FindBestPlay(state, m_depth);
return np;
}
搜索算法對象和評估算法對象之間也是簡單的聚合關係，搜索對象每確定一個新的 GameState 狀態，就委託評估算法對象（Evaluator）對這個狀態進行估值計算，搜索對象根據估值選擇最好的一個位置。
int xxxSearcher::FindBestPlay(const GameState& state, int depth)
{
//搜索 state 的所有可能子狀態
for_each(tryState in searching result of state)
{
//評估這個搜索狀態 tryState
int value = m_evaluator->Evaluate(tryState);
if (value > 本次搜索最好狀態的值)
{
用 value 更新本次搜索最好狀態的值;
記錄 tryState 對應的落子位置為本次搜索最好位置;
}
}
return 本次搜索最好位置;
}
問題在哪裡
這個樸素的設計方案存在什麼問題呢？首先，這幾個對象之間耦合嚴重，GameControl 依賴 HumanPlayer 、ComputerPlayer 和 GameState，如果想或換一個搜索算法不同的計算機玩家，就必須修改代碼才能替換 ComputerPlayer 對象。對於 GameState 也一樣，只支持井字棋，換一種棋就也得修改代碼，也就是用新的遊戲狀態對象替換 GameState 對象。其次，代碼中必然到處是 if(isHumanPlayer)...else... 這樣的分支代碼來處理人類玩家的操作和計算機 AI 玩家的操作。最後，如果要支持兩個計算機 AI 自己對弈，或兩個人類玩家對弈，就需要修改 GameControl 類才能實現，也就是將其中的 HumanPlayer 替換成ComputerPlayer，或者反過來。
在樸素的實現方案種，就是搜索算法和估值算法對象都是寫死的實現對象，如果要修改和調整算法對象，也需要改代碼，不能做到根據配置文件或用戶選擇直接切換算法對象。總之，樸素的方案雖然實現了面向對象的封裝，但是實現起來對象之間耦合嚴重，代碼僵硬，既不靈活，也沒有可擴展性。
開始重構：加上抽象設計
關於抽象
軟件設計的一個基本原則就是要對“接口編程而不是對實現編程”，這裡說的接口就是根據對象的特徵抽象出來的一組共有方法或模型，這些方法或模型更多的體現為一種約束，一種規則，或者是一種統一的處理流程。抽象的目的是抓住問題的關鍵因素，忽略次要因素，迅速建立起一個事物模型的框架。如果我們觀察一下《設計模式》這本書裡介紹的 23 個模式，會發現幾乎每個模式都是圍繞一個抽象的接口（或抽象類）來設計實現方案的。比如“抽象工廠”模式中的 AbstractFactory 和 AbstractProduct，“生成器模式”中的 Builder，“工廠模式”中的 Product，“適配器模式”中的 Adapter，“橋模式”中的 Implementor，“組合模式”中的 Component······
抽象到底是什麼？抽象就是對於我要操作的對象實例，我只需要知道它是某一類對象，並不需要知道它具體是哪個對象，只要它們實現了相同的接口就行。反映在寫代碼的過程中，如果你必須確定地知道你要操作的對象類型，才能調用它的某個特定方法完成某個業務邏輯，那麼你的設計就是不抽象的，你在面向實現編程。相反，如果你只需要知道你要操作的對象是哪一類對象，就可以根據此類對象的共有行為（接口方法）完成你的業務邏輯，那麼你的設計就是抽象的。換句話說，抽象就是務虛，在軟件設計的過程中，越務實，其實現就越僵化，適當的務虛，可以增加靈活性和柔韌性。
為什麼要抽象？普通的類的繼承，更多是為了擴展或實現代碼的重用，但是對接口或抽象類的繼承則是面向對象體系中多態的體現。接口和抽象類的作用之一，就是規定子類的行為，所有要支持這個接口的對象或者從這個抽象類派生的類，都要按照接口或抽象類的約束定義自己的實現方法。接口或抽象類的另一個作用，就是解除系統之間存在的耦合，其實現原則就是我們常說的“接口與實現分離”技術。
怎麼實現抽象？在各種面向對象的編程語言中，抽象的承載形式就是接口和抽象類。有些編程語言可能沒有接口類型，但是都有與之等價的結構，比如 C++ 就沒有接口，但是純虛的抽象類往往被理解為接口。接下來我們即將開始的重構，就是一個給現有的簡單對象體系增加抽象的過程。
玩家對象
GameControl 對象的最佳狀態是不知道它的兩個玩家到底是人類玩家還是計算機 AI 玩家，它只需要按照一個統一（被約束）的接口操作這兩個玩家對象即可。也只有這樣的設計，才能使得 GameControl 對象既能操作兩個人類玩家對弈，也能操作兩個計算機 AI 玩家比拼搜索算法和評估算法。
所以我們要對所有玩家對象進行抽象。我們有兩類玩家對象，分別是電腦玩家和人類玩家，我們要做的抽象就是尋找它們的共同點。那麼這兩類玩家對象有沒有共同點呢？GameControl 對象對於玩家對象的要求很簡單，就是在變更 GameState 對象狀態的時候，需要玩家提供落子位置。人類玩家和計算機 AI 玩家提供落子位置的方法不同，但是卻可以抽象出一個相同的方法（Method），就是 GetNextPosition()函數。我們把落子位置量化成一個整數表示的位置編碼，那麼玩家對象只要按照這個接口的約定返回一個落子位置給 GameControl 就可以了。經過這樣抽象之後，GameControl 就不用再關心玩家對象到底是人類玩家還是電腦 AI 玩家，只要是個 Player 類型的對象就可以了。
到這裡，應該明確了，我們需要設計一個 Player 抽象類，它定義了一個獲取下一步落子位置的抽象方法（Method），接口函數的名字是GetNextPosition()。GameControl 對象通過這個虛的抽象方法與具體的玩家對象協作，獲取玩家對象下一次的落子位置。HumanPlayer 類和 ComputerPlayer 類分別用自己的方法實現 GetNextPosition() 接口函數，這三個類的協作關係如圖（2）所示：
圖（2）Player 接口的抽象
通過 Player 這個抽象類，GameControl 對象原來對具體的 HumanPlayer 類和 ComputerPlayer 類的實現編程，就變成了對 Player 抽象類的接口編程。GameControl::Run()的實現就不再關注具體是 HumanPlayer 類還是 ComputerPlayer 類，它只需與 Player 協作就可以實現自己的邏輯處理流程，這就是我們前面提到的務虛。
int GameControl::Run()
{
while(!m_gameState.IsGameOver())
{
//根據棋局狀態獲取當前執手的玩家ID
int playerId = m_gameState.GetCurrentPlayer();
Player *currentPlayer = GetPlayer(playerId);
int np = currentPlayer->GetNextPosition(); //獲得當前玩家的落子位置
......
m_gameState.SwitchPlayer(); //棋局狀態切換到另一個玩家
}
int winner = m_gameState.GetWinner();
return winner;
}
對比圖（1）所示的樸素設計方案，可以看出來 GameControl 與 HumanPlayer 以及 ComputerPlayer 的依賴耦合關係被解除了。 GameControl 不知道 HumanPlayer 和 ComputerPlayer 的存在，它不關心自己操作的 Player 抽象對象到底是個什麼東西，我們甚至可以做一個 RandomPlayer，它的GetNextPosition()接口實現總是返回棋盤上的一個隨機位置來“愚弄” GameControl 。當然，一個更有意義的行為就是設計一個 TestPlayer 類，它的GetNextPosition()接口返回一些特殊的位置，用於 GameControl 測試自己的邏輯控制流程代碼是否正確，這也是提高軟件可測試性的常用技巧。
經過這個抽象設計之後，GameControl 就可以輕鬆地支持各種對戰模式，比如人機對戰，可以這樣初始化 GameControl 對象：
HumanPlayer human("張三");
ComputerPlayer computer("DELL 7577");
GameControl gc;
gc.SetPlayer(&computer, PLAYER_A);
gc.SetPlayer(&human, PLAYER_B);
假如要改成兩個人互弈，只需將 PLAYER_A 替換成兩外一個 HumanPlayer 對象實例即可：
HumanPlayer human2("李四");
gc.SetPlayer(&human2, PLAYER_A);
同樣，如果想換成兩個 ComputerPlayer 對象實例，比拼搜索算法和評估算法，將 PLAYER_B 替換成 ComputerPlayer 即可。
ComputerPlayer computer2("Thinkpad X300");
gc.SetPlayer(&computer2, PLAYER_B);
搜索算法對象
根據對題目的理解，AI 玩家可以選擇不同的搜索算法和估值算法。搜索算法可以是“極大極小值”算法、“帶 α-β 剪枝的極大極小值”算法、“負極大值”算法等等。在樸素設計方案中，ComputerPlayer 類中直接寫死（硬編碼）了一種搜索算法，這使得樸素方案無法實現兩個 ComputerPlayer 類的實例（對象）用不同的搜索算法和估值算法互相博弈。為了使 ComputerPlayer 類的實例能夠在運行期間動態設置搜索算法和評估算法，我們需要將 ComputerPlayer 類與具體的搜索算法類解耦和，解耦和的方法依然是定義抽象接口。
再一次，我們需要提取各種搜索算法類的共同點。ComputerPlayer 對象對於各種搜索算法類的實例（對象）的要求很簡單，就是能夠從當前的 GameState 中推導出下一步的最佳落子位置。它不需要關心搜索算法的具體實現，所以它只需要搜索算法給它一個結果即可。根據這個分析結果，我們設計了一個 Searcher 抽象類，併為其設計了一個名為 FindBestPlay() 的抽象方法。
圖（3）Searcher 對象的體系設計
ComputerPlayer 類不再依賴某個具體的搜索算法類，它也開始“務虛”了，它要操作的對象從具體的搜索算法對象變成了 Searcher 抽象類代表的虛接口。圖（4-b）展示了務虛之後 ComputerPlayer 類與 Searcher 抽象類的協作關係，與圖（4-a）所示的重構之前的協作關係相比，ComputerPlayer 類與搜索算法的協作關係更靈活，兩個不同的ComputerPlayer 類的實例，可以分別使用不同的搜索算法，只需控制其成員變量 m_searcher 所指代的具體搜索算法即可。
圖（4）ComputerPlayer 類與搜索算法類的協作變化
下面的代碼就是分別給兩個 ComputerPlayer 類的實例指定了不同的搜索算法，並交給 GameControl 控制這兩個電腦玩家下棋。
AlphaBetaSearcher abs();
NegamaxAlphaBetaSearcher nabs();
ComputerPlayer computer1("DELL 7577");
computer1.SetSearcher(&abs, SEARCH_DEPTH);
ComputerPlayer computer2("KA47");
computer2.SetSearcher(&nabs, SEARCH_DEPTH);
GameControl gc;
gc.SetPlayer(&computer1, PLAYER_A);
gc.SetPlayer(&computer2, PLAYER_B);
估值算法對象
具體的 Searcher 對象實例在搜索到一個 GameState 時，需要估值算法對這個 GameState 進行估值，以便確定哪個 GameState 是對自己最有利的局面。估值算法根據估值策略和理論的不同，也可以有多種不同的實現。樸素的設計方案中，每個搜索算法對象也是直接寫死（硬編碼）了依賴某種具體的估值算法對象。我們多次強調，軟件設計越務實越僵化，樸素方案的缺點我們就不再囉嗦了，直接講講怎麼修改吧。
再一次（已經是第三次了，重要的事情，要說三遍），我們需要結合 Searcher 對象的需要提取各種估值算法類的共同點，抽象設計就是找共同點（暫時忽略次要的差異）。估值算法需要對指定的 GameState 進行估值計算，同一個 GameState 對不同的玩家來說估值結果也是不一樣的。所以我們設計了一個 Evaluator 抽象類，它有一個名為 Evaluate() 的抽象接口，調整後的協作關係如圖（5）所示：
圖（5）Evaluate 對象的設計
搜索算法對象現在只需要對 Evaluator 抽象類的抽象接口編程即可，每種搜索算法對象都可以藉助 Evaluator 抽象類這個“佔位符”，實現對具體估值算法對象的解耦和。
繼續重構：模式
重構就是不怕折騰，上述方案已經能夠實現我們的設計目的，但是還是要折騰。因為這個方案實現以後，我們發現每個搜索算法類的實現中，對 FindBestPlay() 接口的實現代碼都大同小異，就如前面展示的 xxxSearcher::FindBestPlay() 偽代碼一樣，基本上都是相同的套路：遍歷棋盤上所有可以落子的空位，對每個位置上進行落子的評估，然後取估值最大的那個位置作為最後的最佳落子位置。
幾個搜索類的實現代碼中都有這段重複的代碼，壞味道的感覺就出來了。整塊重複出現的代碼，常被稱為“C - V”代碼，既“複製-粘貼”代碼。程序員寫代碼的時候使用複製-粘貼重複使用某一段代碼，被認為是沒有成熟思考的行為，也意味著沒有設計。如果複製-粘貼的處理邏輯中存在 BUG，就需要找出所有複製-粘貼的地方修改 BUG，漏掉任何一處都會造成潛在的故障。
模板方法（Template Method）模式
上述代碼中的幾個步驟都是固定的行為，類似一個行為框架，只有“對 tryState 進行博弈樹搜索，得到一個估值 value ”這一步是具體搜索算法做的事情，對於這種結構，迅速想到了一個模式，就是“模板方法（Template Method）”行為模式。
圖（6）GOF 模板方法模式示意圖
我們來看看《GOF》對“模板方法”模式的意圖說明：定義一個操作中的算法骨架，而將一些步驟延遲到子類中。模板方法使得子類可以不改變一個算法的結構即可重定義該算法的某些特定步驟。進一步解釋這句話，首先 AbatractClass 中通過抽象接口定義了一個算法中的一些步驟，然後實現一個模板方法確定了它們的先後順序（也可以是某種更復雜的組合邏輯），但是 ConcreteClass 中可以改變抽象接口的具體步驟，滿足 ConcreteClass 自己的需求。
模板方法模式適用於下列情況：
- 一次性實現一個算法的不變的部分，並將可變的行為留給子類來實現。
- 各個子類中公共的行為應被提取出來並集中到一個公共父類中以避免代碼重複。
- 控制子類擴展，模板方法只在特定的點提供一種類似鉤子（Hook）的操作，允許子類在這些點擴展自己的行為。
實現
於是，我們將 FindBestPlay() 函數定義成上述模式中的模板方法（TemplateMethod()函數），新增一個抽象接口 SearchAndEvaluate() 對應模式中的 PrimitiveOperation() 方法，給子類提供一個定製行為的鉤子。將每個搜索算法類中的重複代碼提取到 Searcher 抽象類中，應用模板方法模式後，Searcher 抽象類的定義如下：
class Searcher
{
public:
Searcher();
virtual ~Searcher();
int FindBestPlay(const GameState& state, int depth);
protected:
virtual int SearchAndEvaluate(GameState& state, int depth, int max_player_id) = 0;
};
//模板方法的實現
int Searcher::FindBestPlay(const GameState& state, int depth)
{
...
//搜索 state 的所有可能子狀態
for_each(tryState in searching result of state)
{
//調用子類提供的具體搜索評估算法評估新狀態
int value = SearchAndEvaluate(tryState, depth - 1, player_id);
if (value > 本次搜索最好狀態的值)
{
用 value 更新本次搜索最好狀態的值;
記錄 tryState 對應的落子位置為本次搜索最好位置;
}
}
return 本次搜索最好位置;
}
具體的搜索算法子類根據自己的算法特點定製 SearchAndEvaluate() 方法的行為，以帶 α-β 剪枝的極大極小值算法實現為例，其定製的行為是：
class AlphaBetaSearcher : public Searcher
{
....
protected:
virtual int SearchAndEvaluate(GameState& state, int depth, int max_player_id);
int AlphaBeta(GameState& state, int depth, int alpha, int beta, int max_player_id);
....
};
int AlphaBetaSearcher::SearchAndEvaluate(GameState& state, int depth, int max_player_id)
{
return AlphaBeta(state, depth, -GAME_INF, GAME_INF, max_player_id);
}
總結
好了，總結一下吧。我們前面說過，接口和抽象類都是面向對象體系中多態的體現，那為何本文中的重構用的都是抽象基類？這就要說說抽象類和接口的區別了，抽象類和它的繼承者之間是“IS-A”關係，接口和它的“繼承者”（注意用了括號）則是一種實現或“CAN-DO”的關係。某個類繼承了一個接口，意味著這個類承諾要實現這個接口，支持這個接口定義的規則，但是它和接口不是“IS-A”關係。本文講述的重構方案，每個抽象接口的載體是抽象基類，因為它們和繼承者之間是同類關係，而不僅僅是“按照你的要求做了某件事情”這樣的關係。
我們常說的軟件設計，不僅僅是面向對象的封裝，因為這只是基礎。軟件設計的核心是釐清每個對象的角色、職責和（與其他對象的）協作關係，巧妙的組織對象之間的關係以及它們之間的相互協作（通信），使得整個系統滿足軟件設計的“普世價值”。我們說的軟件“普世價值”包含，但不限於以下內容：
- OCP-開放封閉原則：對新功能的擴展是開放的，對業務邏輯的修改是封閉的；
- LSP-里氏代換原則：子類必須能夠替換其父類（完全實現父類的方法）；
- DIP-依賴倒置原則：抽象不應依賴細節，細節應依賴抽象（面向接口）；
- ISP-接口隔離原則：一個類對另外一個類的依賴（協作）應當建立在最小的接口上；
- SRP-單一職責原則：就一個類而言，應該僅有一個引起它變化的原因（對象職責的一種理想期望） ；
- CARP-合成/聚合複用原則：儘量使用合成/聚合，儘量不要使用繼承（因繼承是強偶合）；
- LoD-迪米特法則（最少知識原則）：若兩個類不必直接通信，則不應直接交互，一個對象應該對其他對象有最少的瞭解。
“高內聚、低耦合”如果只是會說說，那沒啥意思，關鍵是要會做。“對接口編程”就是拆耦合的最常用方法，理解了抽象接口的意義，才能理解“對接口編程”的內涵，也才能具體實施“高內聚、低耦合”的“普世價值”。
最後，我們來看一下完整的設計：
更多算法相關的內容請見評論區下方留言
閱讀更多 程序猿說 的文章
