MinMax算法求解三子棋

2020-03-15

题目

　　利用MinMax算法预测三子棋盘中下一步Ｘ的落子位置，使得执Ｘ的棋手必定能获胜。

求解思路

　　给定某个棋盘状态，当前Ｘ行棋，随后Ｏ行棋。该棋盘状态为博弈树的根结点，以下一步行棋产生的局面为子结点。通过递归建立博弈树，通过博弈树深度的奇偶性来判断Ｘ行棋还是Ｏ行棋，然后递归建立博弈树。
　　建树完毕后，通过实现MinMax算法，计算博弈树中各个节点的效用值。对于根节点来说，效用值为+1，表示X有必胜策略，该策略的下一步行动为子结点效用值为+1的下一步落子，此时我们就找到了解。
　　在这里有几个主要的函数，他们
　　在 buildTree 中，以递归的方式创建一棵博弈树，初始传入参数为博弈树的根结点；
　　在 minmax 中，完成 MinMax 算法主体部分，初始传入参数为博弈树的根结点，返回下一步 X 棋子落位后的棋盘状态（特别的，该棋子落位情况使得执 X 棋子的选手必定能获得胜利）。另外，可能有多个解，所以将所有解存入列表并作为函数返回值，无解则是返回一个空列表。
　　在 max_value 中，计算该博弈树结点的子结点中的最大的评估值，并返回；
　　在 min_value 中，计算该博弈树结点的子结点中的最小的评估值，并返回；
　　在 get_value 中，计算最终棋盘状态执 X 棋子的评估值并返回（ 1 表示胜利，-1 表示失败，0 表示平局）；
　　在 isTerminal 中，判断该博弈树结点的棋盘状态是否为最终棋盘状态，即无空位可以下棋子（或该博弈树结点无子结点）。

实现代码

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

        posList = []
        for i in range(3):
            for j in range(3):
                if root.map[i][j]=='_':
                    posList.append((i,j))

        for (x, y) in posList:
            childNode = GameNode(map=copy.deepcopy(root.map),
                                 val=0, deepID=root.deepID+1, parent=root, children=[])
            if root.deepID%2==0:
                childNode.map[x][y]='x'
            else :
                childNode.map[x][y]='o'
            root.children.append(childNode)

        for childNode in root.children:
            self.buildTree(childNode)


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

        best_val = self.max_value(node)
        best_move = []
        for childNode in node.children:
            if childNode.val == best_val and best_val==1:
                best_move.append(childNode.map)
        return best_move


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


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

        if self.isTerminal(node):
            val = self.get_value(node)
            node.val = val
            return val
        inf_val = float('inf')
        max_val = -inf_val
        for childNode in node.children:
            max_val = max(max_val, self.min_value(childNode))
        node.val = max_val
        return max_val


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


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

        if self.isTerminal(node):
            val = self.get_value(node)
            node.val = val
            return val
        inf_val = float('inf')
        min_val = inf_val
        for childNode in node.children:
            min_val = min(min_val, self.max_value(childNode))
        node.val = min_val
        return min_val


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


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

        for i in range(3):
            if node.map[i][0]=='o' and node.map[i][0]==node.map[i][1] and node.map[i][1]==node.map[i][2]:
                return -1
            if node.map[0][i]=='o' and node.map[0][i]==node.map[1][i] and node.map[1][i]==node.map[2][i]:
                return -1
        if node.map[0][0]=='o' and node.map[0][0]==node.map[1][1] and node.map[1][1]==node.map[2][2]:
            return -1
        if node.map[0][2]=='o' and node.map[0][2]==node.map[1][1] and node.map[1][1]==node.map[2][0]:
            return -1
        for i in range(3):
            if node.map[i][0]=='x' and node.map[i][0]==node.map[i][1] and node.map[i][1]==node.map[i][2]:
                return 1
            if node.map[0][i]=='x' and node.map[0][i]==node.map[1][i] and node.map[1][i]==node.map[2][i]:
                return 1
        if node.map[0][0]=='x' and node.map[0][0]==node.map[1][1] and node.map[1][1]==node.map[2][2]:
            return 1
        if node.map[0][2]=='x' and node.map[0][2]==node.map[1][1] and node.map[1][1]==node.map[2][0]:
            return 1
        return 0


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


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

        assert node is not None
        return len(node.children)==0


        #********** End **********#
if __name__ == '__main__':

    # 读取棋盘状态，下一步执 x
    map = [[raw for raw in raw_input().split('\n')[0]] for i in range(3)]

    # 创建一个根结点
    root = GameNode(map, val=0, deepID=0, parent=None, children=[])

    # 创建一颗博弈树
    game_tree = GameTree(root)
    game_tree.buildTree(game_tree.root)

    # 创建一个MinMax算法解决方案的对象
    min_max = MinMax(game_tree)

    # 调用MinMax算法，获取最优行动
    best_move = min_max.minmax(game_tree.root)

    # 打印最优行动
    for id_, move in enumerate(sorted(best_move)):
        print 'best move way:'
        for i in range(3):
            for j in range(3):
                print move[i][j],
            print ''