AI实验四实验报告

实验四 博弈搜索（3学时）班级：计科041班姓名：陆宇海学号：0407100232一 实验目的熟悉和掌握博弈（对抗）搜索基本思想和实现关键技术，使用Python语言实现通用的极大极小算法与Alpha-Beta剪枝算法，并进行实验验证。二 实验原理博弈是人工智能取得巨大成功的领域，著名的有深蓝系统等。所有的计算机博弈程序（或系统）的基础Alpha-Beta剪枝算法，即在极大极小算法基础再进行剪枝。熟练掌握该两种算法，能够解决博弈领域的大部分问题（当然可能需要大型数据库的支撑）。三 实验条件1 Python解释器，及IDLE等程序开发调试环境。2 本实验所提供的几个Python文件，请解压文件gameproject.rar.四 实验内容1 MiniMax算法实现2 AlphaBeta剪枝算法实现3 应用于一字棋游戏(TicTacToe)，进行算法测试4 应用于抓三堆游戏(Nim)，进行算法测试五 实验步骤1 一字棋游戏的搜索问题形式化import tictactoeinitialTTTState = tictactoe.TicTacToeGameState()你先试着和一字棋随机Agent（它只会随机乱走，碰运气）对弈一局import gamesimport gameagentsgames.runGame(initialTTTState, X : gameagents.HumanGameAgent(), O : gameagents.RandomGameAgent(), False, False)#输出结果为： -2 | | | | -1 | | | | -0 | | | | - 0 1 2 Your move? 0,0Opponents move was (1, 1) -2 | | | | -1 | | O | | -0 | X | | | - 0 1 2 Your move? 0,1Opponents move was (2, 0) -2 | | | | -1 | X | O | | -0 | X | | O | - 0 1 2 Your move? 0,2 -2 | X | | | -1 | X | O | | -0 | X | | O | - 0 1 2 Game finished with utilities X: 1, O: -1X: 1, O: -1#由于智能体的行棋策略是随机的，故人可以毫不费力地战胜它2 实现一个简单的Agent，它会抢先占据中心位置，但是之后只会按照格子的顺序下子(其实不能算是智能体)，试着和它玩一局：把步骤1的语句中的RandomGameAgent()替换成SimpleTTTGameAgent()即可。输出结果为： -2 | | | | -1 | | | | -0 | | | | - 0 1 2 Your move? 2,0Opponents move was (1, 1) -2 | | | | -1 | | O | | -0 | | | X | - 0 1 2 Your move? 2,2Opponents move was (0, 0) -2 | | | X | -1 | | O | | -0 | O | | X | - 0 1 2 Your move? 0,2Opponents move was (1, 0) -2 | X | | X | -1 | | O | | -0 | O | O | X | - 0 1 2 Your move? 0,1Opponents move was (2, 1) -2 | X | | X | -1 | X | O | O | -0 | O | O | X | - 0 1 2 Your move? 1,2 -2 | X | X | X | -1 | X | O | O | -0 | O | O | X | - 0 1 2 Game finished with utilities X: 1, O: -1#在以上的下棋步骤中，我有意让棋，才得以观察到智能体的下棋顺序：先下中间的格（1，1），若（1，1）#已被占据，则沿着从第0行到第2行，每行从第0列到第2列的规律探索可下棋的格子然后再让随机Agent和SimpleAgent两个所谓的智能体对弈：把步骤1的语句中的HumanGameAgent()替换成SimpleTTTGameAgent()即可。#输出结果为：#回合1： -2 | X | O | X | -1 | X | O | X | -0 | O | X | O | - 0 1 2 Game finished with utilities X: 0, O: 0#双方平局#回合2： -2 | X | X | X | -1 | X | O | O | -0 | O | O | X | - 0 1 2 Game finished with utilities X: 1, O: -1#随机智能体（RandomGameAgent）获胜#回合3： -2 | O | X | | -1 | X | O | X | -0 | X | O | O | - 0 1 2 Game finished with utilities X: -1, O: 1#固定方式智能体（SimpleTTTGameAgent）获胜#经以上三次对弈，可以看出由于这两种智能体在下棋时都不考虑效用，而在无目的地下棋，故两者对弈#时，获胜的概率是相同的3 实现极大极小算法#极大极小算法是封装在一个名叫Minimax的类里：class Minimax(GameTreeSearcher):def getBestActionAndValue(self, currentState):#通过此函数获得最优行动方案 self.player = currentState.currentPlayer()#获取当前的玩家（“O”或“X”） return self.maximin(currentState)#返回最优行动和此行动的最终效用值def maximin(self, currentState):#轮到Max先生行棋时的最优行动计算函数 utility = currentState.utility()#返回针对Max先生的当前棋盘的效用值 if utility: return None, utilityself.player#若棋局已结束，则直接返回Max先生的最终效用值 bestAction = None#初始化最优行动 bestValue = -9999.0 #负无穷#初始化当前行棋的最终效用值 for (action, succ) in currentState.successors():#检索所有合法的行棋 val = self.minimax(succ)1#将每一种合法行棋所产生的棋局交给Min先生，并获得他的最优行棋效用值 if val bestValue: bestAction, bestValue = action, val#找出Min先生针对Max先生的不同棋局所产生的最优行动和最优（最大针对Max#先生来说）效用值 return bestAction, bestValue#返回Max先生的最优行动和此行动的最终效用值 def minimax(self, currentState): utility = currentState.utility() if utility: return None, utilityself.player bestAction = None bestValue = 9999.0 #正无穷 for (action, succ) in currentState.successors(): val = self.maximin(succ)1 if val alpha: bestAction, alpha = action, val#如果Min先生返回的行棋效用大于当前的最低效用，则更新最优行棋与最低效用 if alpha = beta: break#如果当前的最低效用值大于最高效用值（事实上是上层节点的最高效用值）时，将不考虑#余下未判断的所有行棋可能（即剪枝）。这样做是因为上层节点（Min先生）的最高效用界#值只降不增，此层节点（Max先生）的最低效用界限值增不降，而上层节点（Min先生）#终是选择此层节点中效用最小的节点，若此层节点（Max先生）的最低效用界限值大于上#节点（Min先生）的最高效用界限值，则此层节点（Max先生）的所有后继均无需考虑了 return bestAction, alpha#返回Max先生的最优行棋和行棋效用 def minimax(self, currentState, alpha, beta): utility = currentState.utility() if utility: return None, utilityself.player bestAction = None for (action, succ) in currentState.successors(): val = self.maximin(succ, alpha, beta)1 if val = beta: break return bestAction, beta#此函数是针对Min先生行棋时的最优行棋策略函数，由于它和上面的maxmini函数是对称的，故不#再做过多的说明如上你可以和AlphaBeta剪枝智能体对弈，也可以让它和极大极小智能体对应。注意分析两者的运行效率。#键入如下命令，使AlphaBeta剪枝智能体与极大极小智能体对弈：alphaBetaAgent = gameagents.UtilityDirectedGameAgent(gameagents. AlphaBeta ()minimaxAgent = gameagents.UtilityDirectedGameAgent(gameagents.Minimax()games.runGame(initialTTTState, X :, alphaBetaAgent O : minimaxAgent , True, True)#输出结果： -2 | | | | -1 | | | | -0 | | | | - 0 1 2 Got state value 0 with best action (0, 0)Player X agent returned action (0, 0)actions called 10071 times and successor called 22873 times in 0.892922424498 seconds -2 | | | | -1 | | | | -0 | X | | | - 0 1 2 Got state value 0 with best action (1, 1)Player O agent returned action (1, 1)actions called 31973 times and successor called 59704 times in 2.74003064635 seconds -2 | | | | -1 | | O | | -0 | X | | | - 0 1 2 Got state value 0 with best action (1, 0)Player X agent returned action (1, 0)actions called 441 times and successor called 1055 times in 0.0480130854612 seconds -2 | | | | -1 | | O | | -0 | X | X | | - 0 1 2 Got state value 0 with best action (2, 0)Player O agent returned action (2, 0)actions called 478 times and successor called 934 times in 0.0570916136003 seconds -2 | | | | -1 | | O | | -0 | X | X | O | - 0 1 2 Got state value 0 with best action (0, 2)Player X agent returned action (0, 2)actions called 30 times and successor called 77 times in 0.0154092210032 seconds -2 | X | | | -1 | | O | | -0 | X | X | O | - 0 1 2 Got state value 0 with best action (0, 1)Player O agent returned action (0, 1)actions called 26 times and successor called 46 times in 0.012848280996 seconds -2 | X | | | -1 | O | O | | -0 | X | X | O | - 0 1 2 Got state value 0 with best action (2, 1)Player X agent returned action (2, 1)actions called 6 times and successor called 11 times in 0.00726209616005 seconds -2 | X | | | -1 | O | O | X | -0 | X | X | O | - 0 1 2 Got state value 0 with best action (1, 2)Player O agent returned action (1, 2)actions called 3 times and successor called 4 times in 0.00924698530071 seconds -2 | X | O | | -1 | O | O | X | -0 | X | X | O | - 0 1 2 Got state value 0 with best action (2, 2)Player X agent returned action (2, 2)actions called 1 times and successor called 1 times in 0.00600383568235 seconds -2 | X | O | X | -1 | O | O | X | -0 | X | X | O | - 0 1 2 Game finished with utilities X: 0, O: 0#平局的结果已经不足为怪了，这是由棋盘本身的格局而定的，只要两个智能体不出现失误（根本不可能#发生），则一定能达到平局关键的问题是哪个的效率更高，AlphaBeta剪枝算法体现的非常突出的优越性，#即使让它走第一步棋，也仅花费了它0.892922424498秒的计算时间，相比较Maxmini算法需要使用#10.2226939457秒的时间，#它的效率是相当高的，其原因就在于它将Maxmini算法中许多无需判断的#后继都剪掉了。5 把上述步骤实现的算法应用于抓三堆游戏(Nim)你试着和AlphaBeta剪枝智能体对弈import nimagent = gameagents.UtilityDirectedGameAgent(gameagents.AlphaBeta()games.runGame(nim.NimGameState(1,2,3), 1 : agent, 2 : gameagents.HumanGameAgent(), False, True)#这是一种叫做“尼姆”的数学游戏，游戏规则大概是这样的：有n(n=3)堆火柴,两人轮流拿,每次只能在一#堆中取,数目不限,谁拿到最后一根就输。本游戏的初始情况是：有3堆火柴，每堆分别有1、2、3根火柴#在nim.py文件里的NimGameState类中，效用函数utility的返回值是有问题的def utility(self): Returns None if the game is nonterminal, or a Dictionary associating players to utilities if it is terminal. (currentPlayer, otherPlayer) = self.players for row in self.board: if row 0: return None #return self.players0 : -1, self.players1 : 1#原来的返回语句return self.players0 : 1, self.players1 : -1#修改后的返回语句#最末的返回值的对应关系应该是（玩家1：1，玩家2：-1），因为当棋局行走到此步时，就已经说明玩家#1赢得了比赛，自然效用值应为1#还有一个问题是：由于智能体总是认为对手的行棋是最优的，故对于一些特殊的棋局，如果对手不失误，#则智能体将是必输的。面对这样的情况，智能体将不会返回行棋步骤（因为它认为自己是必输的），为了#避免这种情况的发生，只能让智能体随机选择一种行棋方案（将错就错）。#于是，我对games.py文件中的runGame函数做了一些修改：#将原代码：assert agentAction in currentState.actions()#换为：if agentAction not in currentState.actions() and currentState.actions != None:lst = currentState.actions()agentAction = lstint(random.random()*(len(lst)-1)+0.5)assert agentAction in currentState.actions()#即从行棋列表中随机选择一种行棋方案#运行结果：Got state value -1 with best action Noneactions called 139 times and successor called 263 times in 0.00619492142158 secondsOpponents move was (0, 1)Heap 0: Heap 1: *Heap 2: *Your move? 2,1actions called 1 times and successor called 0 times in 9.07001672 secondsGot state value -1 with best action Noneactions called 15 times and successor