为了演示博弈树的搜索和评估算法，我做了一个井字棋（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-迪米特法则（最少知识原则）：若两个类不必直接通信，则不应直接交互，一个对象应该对其他对象有最少的了解。
“高内聚、低耦合”如果只是会说说，那没啥意思，关键是要会做。“对接口编程”就是拆耦合的最常用方法，理解了抽象接口的意义，才能理解“对接口编程”的内涵，也才能具体实施“高内聚、低耦合”的“普世价值”。
最后，我们来看一下完整的设计：
更多算法相关的内容请见评论区下方留言
閱讀更多 程序猿說 的文章
