搜索算法(2)——Minimax搜索

Minimax搜索简介

Minimax Search，直面翻译，即最小最大算法，这里面蕴含这一种对抗的思想，比如多智能体之间在一个task中存在竞争关系，一方想尽办法将这个利益最大化，另一方希望将这个利益最小化。

Minimax算法是Pessimistic的，总是觉得”对手“agent拥有完美的决策能力，所以每次决策时，希望找到对方让我方陷入最坏情况的各种策略中的较好的策略。尽量降低损失。虽然这种方法简单有效，也能返回较优的结果，但是存在很多问题。比如：
---- 对于很复杂的任务情况(Go围棋游戏， $2^{361}$ )，这种若用minimax，问题就大了，因为Minimax算法中蕴含着”穷举“的思想，即尽可能访问到所有应该被访问到的情况，这便无法在有效时间内返回结果了。当然后面也会通过比如alpha-belta剪枝做一些优化，减少一些搜索节点，但本质还都属于”穷举“算法。
---- 由于Minimax的”悲观“性，它不会去找理论最优解，因为其建立在对方很强的基础上行，比如对方每一步都是完美策略，此时我们如何尽可能减小损失，即在最坏的情况中选择最好的情况。

Minimax算法对游戏树执行完整的深度优先探索Depth First，若树的最大深度为m，每个点有b个合法有效的动作方法，则算法的时间复杂度为 $O(b^m)$ 。对于真实的游戏，这个时间复杂度有点夸张了，但是Minimax算法是各种游戏等时机算法的数学基础，下面以一个小游戏为例子，来更深层次的学习Minimax算法。

☺☺☺小游戏——三子棋

1. 游戏特点：

两人对抗，尽力最大化自己利益，最小化对手利益，交替操作，一方先开始；并且两人的操作相互独立，单纯对抗，在3X3的棋盘格上，谁先将同样符号连成一条线，就算赢。
注意：电脑玩家AI算法使用了minmax算法，附带alpha-beta减枝；

2. 算法结构——博弈树Game Tree

博弈树是指由于动态博弈参与者的行动有先后次序，因此可以依次将参与者的行动展开成一个树状图形。这部分，在辅助的references上都有很多解释，就不花篇幅去写了。

通俗地讲就是树状结构，算法会算出游戏所有的结果，每个结果的相应走法就是树的一个枝（Branch），每一个可能的走法就是一个节点（Node），而游戏结束时刻的哪一个走法就是相应的一个根节点（Root）。算法要搜索整个博弈树，获得所有节点分值，选择分值最高的节点。
MAX层： Player操作，期望我的利益最大化；
MIN 层： AI 操作，期望我的利益最小化，其自身利益最大化；
树的底层总是叶子节点，此处每个叶子节点都表示游戏的一种结局，因为游戏结束了，树才不会继续延伸下去

MAX先行，可在初始状态的9个空格中随机选一个，放入"X"；其希望游戏终局的得分高，与MIN期望相反；
所形成游戏树的叶子节点数：
$N = 9!=3.6288e5$
检查“WIN”的标准，三个棋子连成线！

P-code 理解P代码有助于我们理解小Case代码(Minimax)

Initial State --- $S_0$ # 游戏初始状态
Player --- PLAYERS(s) # 玩家
Action --- ACTIONS(s) # 当前状态s下所采取的可能移动
State Transition --- RESULT(s,a) # 当前状态s下，采取行动a，得到的状态
Final State Detection --- Terminal_Test(s) # 检查游戏结束与否
Final Score --- Utility(s,p) # 最终状态s下玩家p的得分
-------------------------------------------------------
Function Minimax-Decision (state) # 输入state

Return action # 输出一个action
$a = argmax_{a\in ACTIONS(a)}MinValue(RESULT(state,a))$

-------------------------------------------------------
Funtion Max_Value(state) # 输入state

if Terminal_Test(s)

Return Utility(s)

v $\Leftarrow$ $-∞$
For each a in ACTIONS(s) do

v $\Leftarrow$ MAX(v,Min_Value(RESULT(s,a)))

Return v # 输出一个最终状态

-------------------------------------------------------
Function Min_Value(state) # 输入状态s

If Terminal_Test(s)

Return Utility(s)

v $\Leftarrow$ ∞
For each a in ACTIONS(s) do

v $\Leftarrow$ MIN(v,Max_Value(RESULT(s,a)))

Return v

CASE 三子棋

原Blog地址，感觉博主写的很好，结构清晰。

1.棋盘

#! /usr/bin/enc python
# -*- coding: utf-8 -*-

"""
三子棋游戏
模式选择：
--- 1. player vs player
--- 2. AI vs AI
--- 3. player vs AI
电脑玩家使用了minimax算法，带alpha-beta剪枝算法
电脑玩家在思考时候，时刻思考"假想敌"，以运转minmax算法
原blog:https://www.cnblogs.com/hhh5460/p/7082112.html
"""

import numpy as np
import math
import time

class Board(object):
    """定义棋盘"""
    def __init__(self):
        self._board = ["-" for _ in range(9)]
        self._history = [] # 保存下过的棋谱

    def _move(self,action,take):
        """按指定动作放入棋子"""
        if self._board[action]=="-": # 检查是否已经落子
            self._board[action] = take
            self._history.append((action,take))

    def _unmove(self,action):
        self._board[action] = "-"
        self._history.pop() # 移除列表中最后一个元素

    def get_board_snapshot(self):
        """输出当前棋盘信息"""
        return self._board[:]

    def get_legal_actions(self):
        """选择合法动作进行落子"""
        actions = []
        for i in range(9):
            if self._board[i] == '-':
                actions.append(i)
        return actions

    def is_legal_action(self,action):
        """判断走法是否合法，是否在'-'上落子"""
        return self._board[action] == '-'

    def terminate(self):
        """终局检测"""
        board = self._board
        # a [1,2,3,4,5,6,7,8,9]
        # a[0::3] -- > [1,4,7] #从0开始每隔3取一个
        # a[1::3] -- > [2,5,8]
        # a[0::4] -- > [1,5,9] # 对角
        # a[2:7:2] -- > 从3到7,每两个取一个，列表基本操作
        self.lines = [board[0:3],board[3:6],board[6:9],board[0::3],board[1::3],board[2::3],board[0::4],board[2:7:2]]
        if ['X']*3 in self.lines or ['O']*3 in self.lines or '-' not in board:
            # 终局检测，3点一线
            return True
        else:
            return False

    def win_or_lose(self):
        """胜负检查"""
        board = self._board
        lines = self.lines
        if ['X']*3 in lines:
            return 0 # 0代表"X"胜利
        elif ['O']*3 in lines:
            return 1 # 1代表"O"胜利
        else:
            return 2 # 2代表平局

    def print_board(self):
        """打印棋盘"""
        board = self._board
        for i in range(len(board)):
            print(board[i],end='')
            if (i+1)%3 == 0:
                print() # 换行

    def print_history(self):
        print("本局棋谱：",self._history)

2.定义玩家

#! /usr/bin/enc python
# -*- coding: utf-8 -*-

"""
玩家的行为很简单：先思考，得到走法，后直接落子，棋盘相应改变即可
"""
from 棋盘类 import Board

class Player(object):
    """玩家"""
    def __init__(self,take='X'):
        """人类玩家执'X'"""
        self.take = take

    def think(self,board):
        pass

    def move(self,board,action):
        board._move(action,self.take)

class HumanPlayer(Player):
    """人类玩家"""
    def __init__(self,take):
        super().__init__(take) # 继承，默认执"X"

    def think(self,board):
        while True:
            action = input("请输入0~8的数字")
            if len(action)==1 and action in '012345678' and board.is_legal_action(int(action)):
                """检测合法性,在9个格子中选一个"""
                return int(action)
            else:
                print("错误，非法输入，请重新选择")

class AIPlayer(Player):
    """电脑"""
    def __init__(self,take):
        super().__init__(take)

    def think(self,board):
        print("等待对手落子...")
        take = ['X','O'][self.take=='X'] # 若take是X,此时take取O,否则取X
        player = AIPlayer(take) # 假想的敌人
        _,action =self.minimax(board,player)
        return action

    def minimax(self,board,player,depth=0):
        """
        Minimax算法本体,附带alpha,beta剪枝
        :param board: 棋盘
        :param player: 玩家
        :param depth: 博弈树深度
        :return: bestVal, bestAction
        """
        if self.take == "O":
            bestVal = -10
        else:
            bestVal = 10

        if board.terminate():
            if board.win_or_lose() == 0:
                # "X"胜利
                return -10 + depth, None
            elif board.win_or_lose() == 1:
                # "O"胜利
                return 10 - depth, None
            elif board.win_or_lose() == 2:
                # 平局
                return 0,None

        # 遍历合法走法
        for action in board.get_legal_actions():
            board._move(action,self.take)
            val,_ = player.minimax(board,self,depth+1) # 切换到假想敌
            board._unmove(action) # 撤销走法，回溯

            if self.take == "O":
                if val > bestVal: # Max
                    bestVal,bestAction = val,action
            else: # Min
                if val < bestVal:
                    bestVal,bestAction = val,action
        return bestVal,bestAction

3. 游戏运行本体

#! /usr/bin/enc python
# -*- coding: utf-8 -*-

from 棋盘类 import Board
from 玩家 import *

class GAME(object):
    def __init__(self):
        self.board = Board() # 棋盘
        self.current_player = None

    # 生产玩家
    def mk_player(self,p,take='X'):
        if p == 0 :
            return HumanPlayer(take) # 人类玩家
        else:
            return AIPlayer(take) # AI玩家

    # 交换玩家 (轮流下棋)
    def switch_player(self,player1,player2):
        if self.current_player == None:
            return player1
        else:
            return [player1,player2][self.current_player==player1]

    # 打印赢家
    def print_winner(self,winner):
        print(['胜利者是player1','胜利者是player2','平局'][winner])

    # 运行游戏
    def run(self):
        ps = input("请选择两个玩家类型: \n\t0.人类玩家\n\t1.AI\n输入方式:0 0\n")
        p1,p2 = [int(p) for p in ps.split(' ')]
        player1,player2 = self.mk_player(p1,'X'),self.mk_player(p2,'O') # 先手执X，后手执O

        print("\n游戏开始...\n")
        self.board.print_board() # 显示棋盘
        while True:
            self.current_player = self.switch_player(player1,player2) # 交换
            action = self.current_player.think(self.board) # 当前玩家对棋局思考，得到落子方法
            self.current_player.move(self.board,action) # 执行，改变棋盘
            self.board.print_board() # 显示棋盘
            if self.board.terminate(): # 判断棋盘是否终止
                winner = self.board.win_or_lose() # 得到赢家
                break
        self.print_winner(winner)
        print("游戏结束")
        self.board.print_history()

if __name__ == '__main__':
    GAME().run()

4.测试Demo

请选择两个玩家类型: 
	0.人类玩家
	1.AI
输入方式:0 0
0 1
游戏开始...

---
---
---
请输入0~8的数字0
X--
---
---
等待对手落子...
X--
-O-
---
请输入0~8的数字1
XX-
-O-
---
等待对手落子...
XXO
-O-
---
请输入0~8的数字3
XXO
XO-
---
等待对手落子...
XXO
XO-
O--
胜利者是player2
游戏结束
本局棋谱： [(0, 'X'), (4, 'O'), (1, 'X'), (2, 'O'), (3, 'X'), (6, 'O')]