第1关：AlphaBeta剪枝算法求解博弈树最优选择

# -*- coding:utf-8 -*-

import copy     # 注意对象的深拷贝和浅拷贝的使用！！！

class GameNode:
    '''博弈树结点数据结构
    成员变量：
    name - string 结点名字
    val - int  结点值
    children - list[GameNode] 子结点列表
    '''
    def __init__(self, name='', val=0):
        self.name = name        # char
        self.val = val          # int
        self.children = []      # list of nodes

class GameTree:
    '''博弈树结点数据结构
    成员变量：
    root - GameNode 博弈树根结点
    成员函数：
    buildTree - 创建博弈树
    '''
    def __init__(self):
        self.root = None                # GameNode 博弈树根结点

    def buildTree(self, data_list, root):
        '''递归法创建博弈树
        参数：
        data_list - list[] like this ['A', ['B', ('E', 3), ('F', 12)], ['C', ('H', 2)], ['D', ('K', 14)]]
        root - GameNode
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        del data_list[0]
        for i in data_list:
            if isinstance(i,int):
                root.val=i
            else:
                new_data_list=list(i)
                new_node=GameNode(name=new_data_list[0],val=0)
                self.buildTree(new_data_list,new_node)
                root.children.append(new_node)
        return root
        #********** End **********#


class AlphaBeta:
    '''博弈树结点数据结构
    成员变量：
    game_tree - GameTree 博弈树
    成员函数：
    minmax_with_alphabeta - 带AlphaBeta剪枝的极大极小值算法，计算最优行动
    max_value - 计算最大值
    min_value - 计算最小值
    get_value - 返回结点的值
    isTerminal - 判断某结点是否为最终结点
    '''
    def __init__(self, game_tree):
        self.game_tree = game_tree      # GameTree 博弈树

    def minmax_with_alphabeta(self, node):
        '''带AlphaBeta剪枝的极大极小值算法，计算最优行动
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - GameNode 最优行动的结点
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        self.max_value(node,1000,-1000)
        for i in node.children:
            if i.val==node.val:
                return i

        #********** End **********#


    def max_value(self, node, alpha, beta):
        '''计算最大值
        参数：
        node - GameNode 博弈树结点
        alpha - int 剪枝区间下限值
        beta - int 剪枝区间上限值
        返回值：
        clf - int 子结点中的最大的评估值
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#

        if self.isTerminal(node):
            return node.val
        
        for i in node.children:
            new_beta=self.min_value(i,alpha,beta)
            beta=new_beta if new_beta>beta else beta
            if alpha<beta:
                break
        node.val=beta
        return beta

        #********** End **********#


    def min_value(self, node, alpha, beta):
        '''计算最小值
        参数：
        node - GameNode 博弈树结点
        alpha - int 剪枝区间下限值
        beta - int 剪枝区间上限值
        返回值：
        clf - int 子结点中的最小的评估值
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#

        if self.isTerminal(node):
            return node.val
        
        for i in node.children:
            new_alpha=self.max_value(i,alpha,beta)
            alpha=new_alpha if new_alpha<alpha else alpha
            if alpha<beta:
                break
        node.val=alpha
        return alpha

        #********** End **********#


    def get_value(self, node):
        '''返回结点的值
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - int 结点的值，即 node.val
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        return  node.val

        #********** End **********#


    def isTerminal(self, node):
        '''判断某结点是否为最终结点（无子结点）
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - bool 是最终状态，返回True，否则返回False
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        if len(node.children)>0:
            return False
        return True
        #********** End **********#