头歌题目
任务描述
本关任务：学习人工智能博弈算法中的 MinMax 算法，并实现三子棋在人机对战中的下一步棋的预测。
三子棋，相当有意思的传统民间游戏，又名九宫棋、圈圈叉叉等。在一个3×3的棋盘上，初始为空，每次 X 先下一棋子，然后 O 下一棋子，例如下图棋盘状态，下一步轮到 X 下棋子，落在中间，第2列的 X 形成了一条直线，则判定执 X 棋子的选手获得了胜利（胜利的状态为 X 或者 O 率先由3个棋子完成一条直线，可以是水平、垂直和对角线）。
在本关卡中，空白3×3棋盘先下 X 棋子，然后 O 棋子，给定一个中间棋盘状态，预测下一步 X 的落子位置，使得执 X 棋子的选手必定能获得胜利。
相关知识
为了完成本关任务，你需要掌握：1. MinMax 搜索，2.评估函数，3.构造函数，4.求解思路。
MinMax 搜索
类似三子棋的游戏都是两人参与的游戏，假设 MAX 选手先行，随后 MIN 选手，两人轮流出招，直到游戏结束，其中游戏可以用形式化方法表示为如下的一类搜索问题：
S0：初始状态，规范游戏开始时的情况；
PLAYER(s)：定义此时该谁行动；
ACTION(s)：返回此状态下的合法移动集合；
RESULT(s,a)：转移模型，定义行动的结果；
TERMINAL−TEST(s)：终止测试，游戏结束返回真，否则返回假。游戏结束的状态称为终止状态；
UTILITY(s,p)：效用函数（也可以称之为评估函数或收益函数），定义游戏者p在终止状态s下的数值。一般的，在国际象棋或三字棋的游戏中，结果是赢、输或平，分别赋予数值+1、−1或0。
初始状态、ACTION和RESULT定义了游戏的博弈树，其中结点是状态，边是移动。如下图三字棋的部分博弈树，初始状态下 MAX 有九种可能的棋招，游戏轮流进行， MAX 下 X ， MIN 下 O ，直到博弈树达到了树的终止状态，叶子结点上的数字是该终止状态下对于 MAX 来说的效用值，值越大对 MAX 越有利。
给定一棵博弈树，最优策略可以通过检查每个结点的 极小极大值 来决定，记为 MINMAX(n) 。假设两个游戏者始终按照最优策略行棋，那么结点的极小极大值就是对应状态的效用值（对于 MAX 而言）。显然，最终状态的极小极大值就是它的效用值自身。进一步，对于给定的选择， MAX 喜欢移动到有极大值的状态，而 MIN 喜欢移动到有极小值的状态，因此算法得名为极大极小值算法（或极小极大值算法），所以得到如下公式：
极小极大值算法从当前状态计算极小极大决策，借助递归算法计算每个后继的极小极大值，可以实现上图公式的定义。递归算法自上而下一直前进到树的叶子结点，然后随着递归回溯通过搜索树把极小极大值回传。算法伪代码如下：
极小极大值算法对博弈树执行完整的深度优先搜索，如果树的最大深度为m，在每个结点合法的行棋有b个，那么极小极大值算法的时间复杂度为O(bm)，空间复杂度为O(bm)。显然，这种指数级的时间开销是非常巨大的，通常需要制定一些剪枝策略。
评估函数
根据上面效用值的定义，评估函数实际上就是计算终止状态下 MAX 的效用值，不同的游戏有着不同的评估策略，在本关的三子棋中，一个简单的评估策略就是MAX赢了效用值为+1，输了效用值为−1，平局则是0。
构造函数
在行棋的游戏博弈中，每一次行棋都会改变棋盘的状态，棋盘中的空闲格子也会随之减少，直接对应着博弈树中的结点的子结点的变换，因此在构造博弈树时需要考虑结点的后继的产生，另外，一个合理的后继序列会很大程度上减少时间开销，例如在围棋等大的棋盘游戏中，处于边缘的空闲棋子可以忽略不计。
求解思路
本关卡为三子棋博弈，给定某个棋盘状态，当前 X 行棋， O 随后轮流行棋，因此，该棋盘状态为博弈树的根结点，以空闲格子为根结点的后继子结点，对每个子结点改变棋盘的状态，即 X 落子（随后在递归建树的过程中，判断是 X 还是 O 落子可以借助博弈树的深度的奇偶性来决定），依次类推，递归建树。
然后实现 MINMAX 算法，计算博弈树中各个结点的效用值。对于根结点来说，效用值为+1，则说明 X 有必胜策略，该策略的下一步行动为子结点中效用值为+1的落子，此时的棋盘状态即为本关所求。
编程要求
本关的编程任务是补全右侧代码片段 buildTree 、minmax 、max_value 、 min_value 、get_value 和 isTerminal 中 Begin 至 End 中间的代码，具体要求如下：
在 buildTree 中，以递归的方式创建一棵博弈树，初始传入参数为博弈树的根结点；
在 minmax 中，完成 MinMax 算法主体部分，初始传入参数为博弈树的根结点，返回下一步 X 棋子落位后的棋盘状态（特别的，该棋子落位情况使得执 X 棋子的选手必定能获得胜利）。另外，可能有多个解，所以将所有解存入列表并作为函数返回值，无解则是返回一个空列表； 例如以下测试案例，X 落位于中间位置，不管之后 O 如何下棋子，X 都能获得胜利。
在 max_value 中，计算该博弈树结点的子结点中的最大的评估值，并返回；
在 min_value 中，计算该博弈树结点的子结点中的最小的评估值，并返回；
在 get_value 中，计算最终棋盘状态执 X 棋子的评估值并返回（ 1 表示胜利，-1 表示失败，0 表示平局）；
在 isTerminal 中，判断该博弈树结点的棋盘状态是否为最终棋盘状态，即无空位可以下棋子（或该博弈树结点无子结点）。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输入： xox o_o x 预期输出： best move way: x o x
o x o
_ x _
特别提醒，注意对象的深拷贝和浅拷贝的使用！！！
# -*- coding:utf-8 -*-import copy # 注意对象的深拷贝和浅拷贝的使用！！！class GameNode: '''博弈树结点数据结构 成员变量： map - list[[]] 二维列表，三子棋盘状态 val - int 该棋盘状态对执x棋子的评估值，1表示胜利，-1表示失败，0表示平局 deepID - int 博弈树的层次深度，根节点deepID=0 parent - GameNode，父结点 children - list[GameNode] 子结点列表 ''' def __init__(self, map, val=0, deepID=0, parent=None, children=[]): self.map = map self.val = val self.deepID = deepID self.parent = parent self.children = childrenclass GameTree: '''博弈树结点数据结构 成员变量： root - GameNode 博弈树根结点 成员函数： buildTree - 创建博弈树 ''' def __init__(self, root): self.root = root # GameNode 博弈树根结点 def buildTree(self, root): '''递归法创建博弈树 参数： root - GameNode 初始为博弈树根结点 ''' #请在这里补充代码，完成本关任务 #********** Begin **********# ##创建root的子节点 ###fuc用来调用判断是否最终状态的函数 mm=MinMax(False) if mm.isTerminal(root): root.val=mm.get_value(root) return ##递归遍历创造新的节点 li=root.map val=0 for i in range(3): for j in range(3): if li[i][j]=='x' or li[i][j]=='o': continue newLi=copy.deepcopy(li) newLi[i][j]='o' if root.deepID%2>0 else 'x' newNode=GameNode(map=newLi,parent=root,deepID=(root.deepID+1),children=[],val=0) root.children.append(newNode) self.buildTree(newNode) if root.deepID%2>0: root.val=mm.min_value(root) else: root.val=mm.max_value(root) #********** End **********#class MinMax: '''博弈树结点数据结构 成员变量： game_tree - GameTree 博弈树 成员函数： minmax - 极大极小值算法，计算最优行动 max_val - 计算最大值 min_val - 计算最小值 get_val - 计算某棋盘状态中：执x棋子的评估值，1表示胜利，-1表示失败，0表示平局 isTerminal - 判断某状态是否为最终状态：无空闲棋可走 ''' def __init__(self, game_tree): self.game_tree = game_tree # GameTree 博弈树 def minmax(self, node): '''极大极小值算法，计算最优行动 参数： node - GameNode 博弈树结点 返回值： clf - list[map] 最优行动，即x棋子的下一个棋盘状态GameNode.map 其中，map - list[[]] 二维列表，三子棋盘状态 ''' #请在这里补充代码，完成本关任务 #********** Begin **********# val=node.val result=[] if val>0: for i in node.children: if i.val==val: result.append(i.map) return result #********** End **********# def max_value(self, node): '''计算最大值 参数： node - GameNode 博弈树结点 返回值： clf - int 子结点中的最大的评估值 ''' #请在这里补充代码，完成本关任务 #********** Begin **********# li=node.children max=-1 for i in node.children: max=i.val if i.val>max else max return max #********** End **********# def min_value(self, node): '''计算最小值 参数： node - GameNode 博弈树结点 返回值： clf - int 子结点中的最小的评估值 ''' #请在这里补充代码，完成本关任务 #********** Begin **********# li=node.children min=1 for i in node.children: min=i.val if i.val<min else min return min #********** End **********# def get_value(self, node): '''计算某棋盘状态中：执x棋子的评估值，1表示胜利，-1表示失败，0表示平局 参数： node - GameNode 博弈树结点 返回值： clf - int 执x棋子的评估值，1表示胜利，-1表示失败，0表示平局 ''' #请在这里补充代码，完成本关任务 #********** Begin **********# li=node.map isEndI=1 isEndJ=1 ##判断行列上是否存在直线 for i in range(3): isEndI=0 if li[i][0]=='_' else 1 isEndJ=0 if li[0][i]=='_' else 1 for j in range(3): if li[i][j]=='_' or (isEndI>0 and li[i][j]!=li[i][0]): isEndI=0 if li[j][i]=='_' or (isEndJ>0 and li[j][i]!=li[0][i]): isEndJ=0 if isEndI+isEndJ<1: break if isEndI>0: return 1 if li[i][0]=='x' else -1 if isEndJ>0: return 1 if li[0][i]=='x' else -1 ##判断斜线上是否存在直线 isEndR=0 if li[0][0]=='_' else 1 isEndL=0 if li[2][0]=='_' else 1 for i in range(3): if li[i][i]=='_' or (isEndR>0 and li[i][i]!=li[0][0]): isEndR=0 if li[2-i][i]=='_' or (isEndL>0 and li[2-i][i]!=li[2][0]): isEndL=0 if isEndR+isEndL<0: break if isEndR>0: return 1 if li[0][0]=='x' else -1 if isEndL>0: return 1 if li[2][0]=='x' else -1 return 0 #********** End **********# def isTerminal(self, node): '''判断某状态是否为最终状态：无空闲棋可走（无子结点） 参数： node - GameNode 博弈树结点 返回值： clf - bool 是最终状态，返回True，否则返回False ''' #请在这里补充代码，完成本关任务 #********** Begin **********# li=node.map ##判断是否还有空位 isFull=1 for i in range(3): for j in range(3): if li[i][j]=='_': isFull=0 break if isFull==0: break if isFull>0: return True isEndI=1 isEndJ=1 ##判断行列上是否存在直线 for i in range(3): isEndI=1 isEndJ=1 for j in range(3): if li[i][j]=='_' or (isEndI>0 and li[i][j]!=li[i][0]): isEndI=0 if li[j][i]=='_' or (isEndJ>0 and li[j][i]!=li[0][i]): isEndJ=0 if isEndI+isEndJ<1: break if isEndI+isEndJ>0: return True ##判断斜线上是否存在直线 isEndR=1 isEndL=1 for i in range(3): if li[i][i]=='_' or (isEndR>0 and li[i][i]!=li[0][0]): isEndR=0 if li[2-i][i]=='_' or (isEndL>0 and li[2-i][i]!=li[0][2]): isEndL=0 if isEndR+isEndL<0: break if isEndR+isEndL>1: return True return False #********** End **********#