小埋,余声-库日天,库里粉丝社区,记录库里的每一步成长

为了演示博弈树的查找和评价算法,我做了一个井字棋(tic-tac-toe)游戏的算法完结。而为了评价游戏AI的智商和可靠性,需求一个渠道可以让用户和游戏的 AI 进行对战博弈,所以我又做了一个支撑棋类游戏对弈的软件结构。

在《算法的趣味》一书的预备进程中,黑白棋(Othello 棋)和五子棋的完结也先后被加入到这个结构中,在此进程中,这个软件结构进行了持续的改善和重构,今日咱们就来说说这个博弈游戏对战结构的规划和重构的思路。

首要说一下规划这个结构的目的,算是需求阐明吧。为了演示博弈树的查找和评价算法,咱们需求一个井字棋(tic-tac-toe)游戏的算法完结。而为了评价微擎游戏 AI 的智商和可靠性,又需求一个渠道可以让用户和游戏的 AI 进行对战博弈。用户经过字符界面输入要落子的方位,AI 经过博弈树的查找得到一个最佳落子方位,记为两边各下一手棋。与此同时,为了可以评价各种查找算法和评价函数的才干,我还需求两个电脑 AI 之间能相互对战。开端想象是经过 1000 局随机对弈模仿,核算各种评价算法取胜的份额,确认pop字体哪种评价算法棋力更强。

归纳考虑了一下,这个结构应该能做到以下几点:

  1. 支撑两种类型的玩家人物,一种是人类玩家,一种是 AI 玩家。人类玩家由人类操控落子,AI 玩家经过博弈树查找确认最佳落子方位;
  2. AI 玩家可以挑选查找算法和估值算法。查找算法可以是“极大极小值”算法、“带 - 剪枝的极大极小值”算法、“负极大值”算法等等。相同评价算法依据估值战略和理论的不同,也可以有多种不同的估值算法;
  3. 需求一个操控器操控两个玩家替换落子,并给出输赢成果。

依据直觉的朴素规划

计划概略

依据需求的描绘,这个体系应该有人类玩家目标、核算机 AI 玩家目标、估值算法目标、查找算法目标和游戏操控器目标 5 个目标。经历通知咱们,估值算法和查找算法需求根底数据模型的支撑,这个根底数据模型便是棋盘状况目标。依据直觉的规划,便是一种“y80s车到山前就修条路”,“船到桥头就把船弄直”的朴素办法。不要小看朴素规划,这是进一步重构演化的根底,比一筹莫展要强很多了。在朴素规划者眼中,这 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::FindBestPl温碧霞走出婚变ay(const GameState& state, int depth)
{
//查找 state 的一切或许子状况
for_each(tryState in searching result of state)
{
//评价这个查找状况 tryState
int value = m_evaluator->Eva荞麦茶luate(tryState);
if (value > 本次查找最好状况的值)
{
用 value 更新本次查找最好状况的值;
记载 tryState 对应的落子方位为本次查找最好方位;
}
}
return 本次查找最好方位;
}

问题在哪里

这个朴素的规划计划存在什么问题呢?首要,这几个目标之间耦合严峻,GameControl 依靠 HumanPlayer 、ComputerPlayer 和 GameState,假如想或换一个查找算法不同的核算机玩家,就有必要修正代码才干替换 ComputerPlayer 目标。关于 GameState 也相同,只支撑井字棋,换一种棋就也得修正代码,也便是用新的游戏状况目标替换 GameState 目标。其次,代码中必定到处是 if(isHumanPlayer)...else... 这样的分支代码来处理人类玩家的操作和核算机 AI 玩家的操作。最终,假如要支撑两个核算机 AI 自己对弈,或两个人类玩家对弈,就需求修正 GameControl 类才干完结,也便是将其间的 Huma通职者第二季nPlayer 替换成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.Ge好久不见歌词tWinner();
return winner;
}

比照图(1)所示的朴素规划计划,可以看出来 GameControl 与 HumanPlayer 以及 ComputerPlayer 的依靠耦合联系被免除了。 GameControl 不知道 HumanPlayer 和 ComputerPlayer 的存在,它不关怀自己操作的 Player 笼统目标究竟是个什么东西,咱们乃至可以做一个 RandomPlayer,它的GetNextPo小埋,余声-库日天,库里粉丝社区,记载库里的每一步生长sition(小埋,余声-库日天,库里粉丝社区,记载库里的每一步生长)接口完结总是回来棋盘上的一个随机方位来“捉弄” 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("T于hinkpad X300");
gc.SetPlayer(&computer2, PLAYER_B);

查找算法目标

依据对题目的了解,AI 玩家可以挑选不同的查找算法和估值算法。查找算法可以是“极大极小值”算法、“带 - 剪枝的极大极小值”算法、“负极大值”算法等等。在朴素规划计划中,ComputerPlayer 类中直接写死(硬编码)了一种查找算法,这使得朴素计划无法完结两个 Compu龙骨的成效与效果terPlayer 类的实例(目标)用不同的查找算法和估值算法相互博弈。为了使 ComputerPlayer 类昨晚星斗的实例可以在运行期间动态设置查找算法和评价算法,咱们需求将 ComputerPlayer 类与详细的查找算法类解耦和,解耦和的办法依然是界说笼统接口。

再一次,咱们需求提取各种查找算法类的共同点。ComputerPlayer 目标关于各种查找算法类的实例(目标)的要求很简略,便是可以从当时的 GameState 中推导出下一步的最佳落子方位。它不需求关怀查找算法的详细完结,所以它只需求查找算法给它一个成果即可。依据这个剖析成果,咱们规划了一个 Searcher 笼统类,并为其规划了一个名为 FindBestPla小埋,余声-库日天,库里粉丝社区,记载库里的每一步生长y() 的笼统办法。


图(3)Searcher 目标的体系规划

ComputerPlayer 类不再依靠某个详细的查找算法类,它也开端“务虚”了,它要操作的目标从详细的查找算法目标变成了 Searcher 笼统类代表的虚接口。图(4-b)展现了务虚之后 ComputerPlayer 类与 Searcher 笼统类的协作联系,与图(4-a)所示的重构之前的协作联系比较,Com小埋,余声-库日天,库里粉丝社区,记载库里的每一步生长puterPlayer 类与查找算法的协作联系更灵敏,两个不同的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 笼统类,它有一个名为 Evaluat布丁e() 的笼统接口,调整后的协作联系如图(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_ppeacelayer_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-迪米特规律(最少常识准则):若两个类不用直接通讯,则不该直接交互,一个目标应该对其他目标有最少的了解。

“高内聚、低耦合”假如仅仅会说说,那没啥意思,关键是要会做。“对接口编程”便是拆耦合的最常用办法,了解了笼统接口的含义,才干了解“对接口编程”的内在,也才干详细施行“高内聚、低耦合”的“普世价值”。

最终,咱们来看一下完好的规划:


更多算法相关的内容请见谈论区下方留言

 关键词: