头歌题目

任务描述

本关任务：学习人工智能博弈算法中的 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 = children

class 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 **********#