头歌：博弈中的搜索（Python实现）

头歌：博弈中的搜索（Python实现） 第2关：极小极大算法（无剪枝） 原理就不说了，头歌上面都有

注意事项

1.建树，建树的时候要注意Python中深拷贝和浅拷贝的区别，在很多赋值的地方都应该用深拷贝。还有就是递归建树。
2.核心minmax函数，这个也是递归，不得不说递归真的是一个好东西，人理解迭代 神理解递归。从博弈树的根节点开始向下递归，从叶子节点往回开始求最大值。
3.写这篇博客的目的，主要就是我在网上没有找到在针对于头歌平台的代码，让我在写这道题的时候很是不爽，我希望后面的学弟学妹能通过我的这一篇简单的博客，至少可以过这道题。

# -*- 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=[],child=[]):
        self.map = map
        self.val = val
        self.deepID = deepID
        self.parent = parent
        self.children = children
        self.child = child


class GameTree:
    '''博弈树结点数据结构
    成员变量：
    root - GameNode 博弈树根结点
    成员函数：
    buildTree - 创建博弈树
    '''

    def __init__(self, root):
        self.root = root  # GameNode 博弈树根结点

    def buildTree(self, root):
        '''递归法创建博弈树
        参数：
        root - GameNode 初始为博弈树根结点
        '''
        # 请在这里补充代码，完成本关任务
        # ********** Begin **********#
        if root.deepID > 5:
            return
        # 精华
        map = copy.deepcopy(root.map)
        for i in range(0,3):
            for j in range(0,3):
                if(map[i][j] == '_' or map[i][j] == ' '):
                    if root.deepID % 2 == 0:
                        map[i][j] = 'x'
                        node = GameNode(copy.deepcopy(map),deepID=root.deepID+1,parent=root,children=[],val=0,child=[])
                        root.children.append(node)
                        self.buildTree(node)
                        if len(node.children) == 0:
                            node.val = self.get_value(node)
                        map[i][j] = '_'
                    else:
                        map[i][j] = 'o'
                        node = GameNode(copy.deepcopy(map),deepID=root.deepID+1,parent=root,children=[],val=0,child=[])
                        root.children.append(node)
                        self.buildTree(node)
                        if len(node.children) == 0:
                            node.val = self.get_value(node)
                        map[i][j] = '_'
        # ********** End **********#

    def get_value(self, node):
        '''计算某棋盘状态中：执x棋子的评估值，1表示胜利，-1表示失败，0表示平局
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - int 执x棋子的评估值，1表示胜利，-1表示失败，0表示平局
        '''
        # 请在这里补充代码，完成本关任务
        # ********** Begin **********#
        for i in range(0, 3):
            if node.map[i][0] == node.map[i][1] == node.map[i][2]:
                if node.map[i][0] == 'x':
                    return 1
                else:
                    return -1
        for i in range(0, 3):
            if node.map[0][i] == node.map[0][i] == node.map[0][i] == 'x':
                if node.map[0][i] == 'x':
                    return 1
                else:
                    return -1

        if node.map[0][0] == node.map[1][1] == node.map[2][2]:
            if node.map[0][0] == 'x':
                return 1
            else:
                return -1
        if node.map[2][0] == node.map[1][1] == node.map[0][2]:
            if node.map[2][0] == 'x':
                return 1
            else:
                return -1

        return 0


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 **********#
        if len(node.children) != 0:
            for n in node.children:
                self.minmax(n)
        if node.deepID % 2 == 0:
            node.child,node.val = self.max_value(node)
            # if child != None:
            #     node.child.append(child.map)
            # else:
            #     node.child = []
        else:
            node.child,node.val = self.min_value(node)
            # if child != None:
            #     print(child.map)
            #     node.child.append(child.map)
            # else:
            #     node.child = []

        if node.deepID == 0:
            # print(child.map)
            ans_list = []
            for n in self.game_tree.root.child:
                ans_list.append(n.map)
            return ans_list
        # ********** End **********#

    def max_value(self, node):
        '''计算最大值
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - int 子结点中的最大的评估值
        '''
        # 请在这里补充代码，完成本关任务
        # ********** Begin **********#
        max = -2
        max_list = []
        for n in node.children:
            if self.get_value(n) >= max:
                max = self.get_value(n)
        for n in node.children:
            if n.val == max:
                max_list.append(n)
        return max_list,max
        # ********** End **********#

    def min_value(self, node):
        '''计算最小值
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - int 子结点中的最小的评估值
        '''
        # 请在这里补充代码，完成本关任务
        # ********** Begin **********#
        min_list = []
        min = 100000
        for n in node.children:
            if self.get_value(n) <= min:
                min = self.get_value(n)

        for n in node.children:
            if n.val == min:
                min_list.append(n)
        return min_list,min
        # ********** End **********#

    def get_value(self, node):
        '''计算某棋盘状态中：执x棋子的评估值，1表示胜利，-1表示失败，0表示平局
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - int 执x棋子的评估值，1表示胜利，-1表示失败，0表示平局
        '''
        # 请在这里补充代码，完成本关任务
        # ********** Begin **********#
        for i in range(0,3):
            if node.map[i][0] == node.map[i][1] == node.map[i][2]:
                if node.map[i][0] == 'x':
                    return 1
                else:
                    return -1
        for i in range(0, 3):
            if node.map[0][i] == node.map[0][i] == node.map[0][i] == 'x':
                if node.map[0][i] == 'x':
                    return 1
                else:
                    return -1

        if node.map[0][0] == node.map[1][1] == node.map[2][2]:
            if node.map[0][0] == 'x':
                return 1
            else:
                return -1
        if node.map[2][0] == node.map[1][1] == node.map[0][2]:
            if node.map[2][0] == 'x':
                return 1
            else:
                return -1

        return 0
        # ********** End **********#

    def isTerminal(self, node):
        '''判断某状态是否为最终状态：无空闲棋可走（无子结点）
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - bool 是最终状态，返回True，否则返回False
        '''
        # 请在这里补充代码，完成本关任务
        # ********** Begin **********#
        for i in range(0,3):
            for j in range(0,3):
                if map[i][j] == '_':
                    return True
        return False
        # ********** End **********#