介紹

實驗介紹：https://inst.eecs.berkeley.edu/~cs188/sp21/project2/
實驗所需代碼下載地址：https://inst.eecs.berkeley.edu/~cs188/sp21/assets/files/multiagent.zip
在專案的介紹頁面有具體的資訊，可以通過不同的指令進行不同的操作和測驗，在此就不多贅述了，

專案解決方案

question2：Minimax演算法

Minimax演算法又名極小化極大演算法，是一種找出失敗的最大可能性中的最小值的演算法，Minimax演算法常用于棋類等由兩方較量的游戲和程式，這類程式由兩個游戲者輪流，每次執行一個步驟，我們眾所周知的五子棋、象棋等都屬于這類程式，所以說Minimax演算法是基于搜索的博弈演算法的基礎，該演算法是一種零總和演算法，即一方要在可選的選項中選擇將其優勢最大化的選擇，而另一方則選擇令對手優勢最小化的方法，

• Minimax是一種悲觀演算法，即假設對手每一步都會將我方引入從當前看理論上價值最小的格局方向，即對手具有完美決策能力，因此我方的策略應該是選擇那些對方所能達到的讓我方最差情況中最好的，也就是讓對方在完美決策下所對我造成的損失最小，
• Minimax不找理論最優解，因為理論最優解往往依賴于對手是否足夠愚蠢，Minimax中我方完全掌握主動，如果對方每一步決策都是完美的，則我方可以達到預計的最小損失格局，如果對方沒有走出完美決策，則我方可能達到比預計的最悲觀情況更好的結局，總之我方就是要在最壞情況中選擇最好的，¹

在本問題中，我們需要實作經典的Minimax演算法，我們可以選擇構建一個mini函式和一個max函式進行互相呼叫，也可以選擇使用一個函式來進行遞回實作（我選擇了后者），
要實作一個函式，就要先知道我們要用它實作什么功能，它有什么引數，需要回傳什么值，
下面是專案注釋中提供的一些 可能用的到的函式，

        Here are some method calls that might be useful when implementing minimax.

        gameState.getLegalActions(agentIndex):
        Returns a list of legal actions for an agent
        agentIndex=0 means Pacman, ghosts are >= 1

        gameState.getNextState(agentIndex, action):
        Returns the child game state after an agent takes an action

        gameState.getNumAgents():
        Returns the total number of agents in the game

        gameState.isWin():
        Returns whether or not the game state is a winning state

        gameState.isLose():
        Returns whether or not the game state is a losing state

• 實作功能：通過Minimax函式獲取Pacman可以獲取最高分數的策略，并通過getAction函式回傳下一步動作
• 引數：Minimax(self, agentIndex, gameState, Depth)
  agentIndex == 0 表示吃豆人，>= 1 表示幽靈，gameState 表示當前狀態，depth表示深度
• 回傳值：在mini或者max層獲取的最小或最大分數

我們先實作getAction函式

def getAction(self, gameState):
	bestAction = "stop"
	#由于是為吃豆人作決策，故將該層作為根結點（第0層），并設立最大值
	maxVal = float('-inf')
   		# 從吃豆人所有合法動作中選則一個最佳的動作
   		for nextAction in gameState.getLegalActions(0):
       		successor = gameState.getNextState(0,nextAction)
       		val = self.minimax(agentIndex=1,gameState=successor,Depth=1)
       		# 假如評估值比目前最大值大，則此動作為最佳動作
       		if val is not None and maxVal < val:
            	maxVal = val
            	bestAction = nextAction
   		return bestAction

再實作minimax演算法，(關鍵核心演算法)

def minimax(self, agentIndex, gameState, Depth):
   	# 如果超過了限制的深度，或者已經輸了或者贏了，就可以直接回傳評估值
  	# Depth達到depth*2時就可以停止了，對于解決本問題足夠了
    if Depth >= self.depth * 2 or gameState.isWin() or gameState.isLose():
        return self.evaluationFunction(gameState)  # minimax() 函式回傳的是評估值

    if agentIndex == 0:  # 吃豆人
        MAX = float("-inf")  # 初始化MAX為負無窮
        pacmanActions = gameState.getLegalActions(agentIndex)  # 獲取吃豆人所有的合法動作
        for nextAction in pacmanActions:
           	successor = gameState.getNextState(agentIndex, each_action)  # 對每一個合法的動作生成對應的狀態
            value = self.minimax(1, successor, Depth + 1)  # 下一層是到幽靈開始行動
            MAX = max(MAX, value)
        return MAX

    else:  # 幽靈即agentIndex >= 1
        values = []	# 由于可能存在多個幽靈，故設立一個values陣列進行存放
        MIN = float("inf")  # 初始化MIN為正無窮
        ghostActions = gameState.getLegalActions(agentIndex)	# 獲取幽靈所有的合法動作
        for nextAction in ghostActions:
           	successor = gameState.getNextState(agentIndex, each_action)
            if agentIndex >= gameState.getNumAgents() - 1:  # 遍歷完幽靈后再進行下一輪的吃豆人
                values.append(self.minimax(0, successor, Depth + 1))
            else:  # 注意：>= 1代表幽靈，因為可能不止一只幽靈
                values.append(self.minimax(agentIndex + 1, successor, Depth))  # 這里得注意代入遞回函式的Depth不加1，因為還有幽靈沒有運動
            value = min(values)
            MIN = min(MIN, value)
        return MIN

測驗結果：

Pacman died! Score: 84
Average Score: 84.0
Scores:        84.0
Win Rate:      0/1 (0.00)
Record:        Loss
*** Finished running MinimaxAgent on smallClassic after 1 seconds.
*** Won 0 out of 1 games. Average score: 84.000000 ***
*** PASS: test_cases\q2\8-pacman-game.test

### Question q2: 5/5 ###

tips:
在更大的棋盤上，比如openClassic和mediumClassic（默認），你會發現吃豆子擅長不死，但在獲勝方面卻很糟糕，他經常在沒有進步的情況下四處奔波，他甚至可能會在一個點旁邊打滾而不吃它，因為他不知道吃了那個點后他會去哪里，如果您看到這種行為，請不要擔心，問題 5 將解決所有這些問題，

question3：Alpha-Beta 剪枝

Minimax演算法往往會生成巨大的分支，尤其是當遇到復雜問題的時候，這時候就需要用到Alpha-Beta剪枝演算法來對Minimax演算法進行優化，

定義極大層的下界為alpha，極小層的上界為beta，alpha-beta剪枝規則描述如下：
（1）alpha剪枝，若任一極小值層結點的beta值不大于它任一前驅極大值層結點的alpha值，即alpha(前驅層) >= beta(后繼層)，則可終止該極小值層中這個MIN結點以下的搜索程序，這個MIN結點最終的倒推值就確定為這個beta值，
（2）beta剪枝，若任一極大值層結點的alpha值不小于它任一前驅極小值層結點的beta值，即alpha(后繼層) >= beta(前驅層)，則可以終止該極大值層中這個MAX結點以下的搜索程序，這個MAX結點最終倒推值就確定為這個alpha值，²

在該問題中，我們要做的是在question2的基礎上添加剪枝操作，話不多說，直接上代碼：

def getAction(self, gameState):
    maxvalue = float('-inf')
    bestaction = []
    # alpha < 結點值 < beta
    alpha = float('-inf')
    beta = float('inf')
    for each_action in gameState.getLegalActions(0):
        successor = gameState.getNextState(0, each_action)
        # 求出后繼狀態的評估值，并和maxvalue比較，求出最大值
        value = self.new_minimax(agentIndex=1, gameState=successor, Depth=1, alpha=alpha, beta=beta)
        # 如果當前的value比maxvalue要大，則更新maxvalue，并記下bestaction
        if maxvalue < value:
            bestaction = []
            maxvalue = value
            bestaction.append(each_action)
        elif maxvalue == value:
            bestaction.append(each_action)
        if maxvalue > alpha:  # 按照alpha-beta剪枝演算法，需要更新alpha值
            alpha = maxvalue

    return random.choice(bestaction)  # 隨機選擇最優的合法動作

def new_minimax(self, agentIndex, gameState, Depth, alpha, beta):
	# 這一部分與前面minimax對應部分一模一樣，無需改動
    if Depth >= self.depth * 2 or gameState.isWin() or gameState.isLose():
        return self.evaluationFunction(gameState)  # minimax() 函式回傳的是評估值

    if agentIndex == 0:  # 吃豆人
        MAX = float("-inf")  # 初始化MAX為負無窮
        pacmanActions = gameState.getLegalActions(agentIndex)  # 獲取吃豆人合法的動作
        for nextAction in pacmanActions:
            successor = gameState.getNextState(agentIndex, nextAction)  # 對每一個合法的動作生成對應的狀態
            value = self.new_minimax(1, successor, Depth + 1,alpha,beta)  # 下一輪是到幽靈開始行動
            if value is not None:
                MAX = max(MAX, value)
            if MAX > beta:  # alpha-beta剪枝演算法
                return MAX
            if MAX > alpha:  # 更新alpha值
                alpha = MAX
        return MAX

    else:  # 幽靈
        values = []
        MIN = float("inf")  # 初始化MIN為正無窮
        ghostActions = gameState.getLegalActions(agentIndex)
        for nextAction in ghostActions:
            successor = gameState.getNextState(agentIndex, each_action)
            if agentIndex >= gameState.getNumAgents() - 1:
                values.append(self.new_minimax((agentIndex+1) % gameState.getNumAgents(),successor, Depth + 1, alpha,beta))
            else:
                values.append(self.new_minimax((agentIndex+1) % gameState.getNumAgents(),successor, Depth, alpha,beta))

            if values is not None:
                value = min(values)
                MIN = min(MIN, value)
            if MIN < alpha:
                return MIN
            # 按照alpha-beta剪枝演算法，這里需要更新beta的值
            if MIN < beta:
                beta = MIN
       	return MIN

測驗結果：

Pacman died! Score: 84
Average Score: 84.0
Scores:        84.0
Win Rate:      0/1 (0.00)
Record:        Loss
*** Finished running AlphaBetaAgent on smallClassic after 0 seconds.
*** Won 0 out of 1 games. Average score: 84.000000 ***
*** PASS: test_cases\q3\8-pacman-game.test

### Question q3: 5/5 ###

question4：Expectimax

對于Minimax演算法來說，它所考慮的對手都是選擇最利他（對方盡可能得分）的動作，但是在現實情況中，并非如此，
在本問題中，我并沒有基于前兩個問題進行優化和改進，而是選取了新的方法：對于吃豆人和幽靈采用不同的函式，然后進行交替調取，并且深度的判斷方式轉為了剩余深度與0的比較，

def getAction(self, gameState):
    val = maxiExp(gameState, self.depth, gameState.getNumAgents() - 1, self.evaluationFunction)
    # print(val)
    return val[1]

由于后面的maxiExp和miniExp函式都使用了雙引數的回傳值，一個是得分，一個動作，故要回傳動作引數，

def maxiExp(state, depth, numGhosts, func):
	# 如果超過了限制的深度，或者已經輸了或者贏了，就可以直接回傳評估值
    if depth == 0 or state.isLose() or state.isWin():
        score = func(state)
        return (score, Directions.STOP)
    else:
        v = float('-inf')
        # 獲取吃豆人所有合法動作
        actions = state.getLegalActions(0)
        bestAction = Directions.STOP
        for action in actions:
            successor = state.getNextState(0, action)
            m = miniExp(successor, depth, 1, successor.getNumAgents() - 1, func)
            # 得分值中取大
            if m > v:
                v = m
                bestAction = action
        return (v, bestAction)

def miniExp(state, depth, ghost, numGhosts, func):
    if depth == 0 or state.isLose() or state.isWin():
        score = func(state)
        return score
    v = 0
    actions = state.getLegalActions(ghost)
    for action in actions:
        successor = state.getNextState(ghost, action)
        m = 0
        # 若幽靈還沒遍歷完則繼續遍歷幽靈
        if ghost < numGhosts:
            m = miniExp(successor, depth, ghost + 1, numGhosts, func)
        # 遍歷完幽靈后進行吃豆人的回合
        else:
            m = maxiExp(successor, depth - 1, numGhosts, func)[0]
        v += m / len(actions)
    return v

測驗結果：

Pacman died! Score: 84
Average Score: 84.0
Scores:        84.0
Win Rate:      0/1 (0.00)
Record:        Loss
*** Finished running ExpectimaxAgent on smallClassic after 1 seconds.
*** Won 0 out of 1 games. Average score: 84.000000 ***
*** PASS: test_cases\q4\7-pacman-game.test

### Question q4: 5/5 ###

question5：優化評估函式

在question5中，我們將解決前面遺留下來的問題：吃豆人總是無法獲勝，
我們需要對評估函式進行一定的優化，我的主要思路就是在所剩的食物中挑選最近的食物進行食用，
ps：我在本問題中沒有特別考慮幽靈對于吃豆人的啟發值，后續可以再次進行優化，

def betterEvaluationFunction(currentGameState):
	# 獲取吃豆人的位置
	Position = currentGameState.getPacmanPosition()
	# 獲取當前所剩食物的位置
    Food = currentGameState.getFood().asList()
    # 引數初始化
    FoodCheck = -float("inf")
    GhostCheck = float("inf")

	# 對所剩的所有食物進行判斷
    for food in Food:
    	# 計算吃豆人和食物的曼哈頓距離
        MinFood = manhattanDistance(Position, food) * (-1)  
        # 如果我們在最好的情況下:食物就在我們旁邊!
        if MinFood > FoodCheck:
            FoodCheck = MinFood

    if FoodCheck == -float("inf"):
        FoodCheck = 0

    return currentGameState.getScore() + FoodCheck

測驗結果：

Pacman emerges victorious! Score: 1083
Pacman emerges victorious! Score: 1145
Pacman emerges victorious! Score: 1009
Pacman emerges victorious! Score: 1081
Pacman emerges victorious! Score: 994
Pacman emerges victorious! Score: 1097
Pacman emerges victorious! Score: 1088
Pacman emerges victorious! Score: 1007
Pacman emerges victorious! Score: 1112
Pacman emerges victorious! Score: 1100
Average Score: 1071.6
Scores:        1083.0, 1145.0, 1009.0, 1081.0, 994.0, 1097.0, 1088.0, 1007.0, 1112.0, 1100.0
Win Rate:      10/10 (1.00)
Record:        Win, Win, Win, Win, Win, Win, Win, Win, Win, Win
*** PASS: test_cases\q5\grade-agent.test (6 of 6 points)
***     1071.6 average score (2 of 2 points)
***         Grading scheme:
***          < 500:  0 points
***         >= 500:  1 points
***         >= 1000:  2 points
***     10 games not timed out (1 of 1 points)
***         Grading scheme:
***          < 0:  fail
***         >= 0:  0 points
***         >= 10:  1 points
***     10 wins (3 of 3 points)
***         Grading scheme:
***          < 1:  fail
***         >= 1:  1 points
***         >= 5:  2 points
***         >= 10:  3 points

### Question q5: 6/6 ###

完成question5后我們發現，我們獲得的分數也僅僅在1000分左右徘徊，如果想要獲得更高的分數，除了完善幽靈的啟發值，其次也要考慮特效豆子的特殊效果（吃特效豆子可以讓幽靈進入恐懼狀態，從而吃掉幽靈后可以獲得更高的分數），為了能夠高效利用特效豆子的效果，拉高特效豆子的權重，如果特效豆子的啟發值和普通豆子一樣，那么當幽靈來的時候，吃豆人只會去躲避幽靈，不會想到去吃特效豆子讓幽靈變成恐懼狀態，把特效豆子權重拉高一些，就可以抵消幽靈對于吃豆人的消極影響，
但是要注意，特效豆子是有有效時長的，吃了特效豆子一定時間后，幽靈就會恢復正常，這時候我們就要考慮幽靈距離吃豆人的距離以及吃豆人距離特效豆子的距離，可以考慮在一般時候的特效豆子分數和普通豆子相等或者略低，等幽靈靠近時，拉高特效豆子的啟發值，

總結

minimax演算法可以在對抗博弈搜索中取得最大分數，但是是在理想情況下（即對手都會選擇最有利于它的行為），但在現實中并不是這樣，所以要對minimax演算法中mini層進行優化，
其次單純的minimax樹會隨著游戲的復雜度而變得非常龐大，此時就需要使用alpha-beta剪枝來對minimax演算法進行剪枝優化，如此一來不僅能夠提高演算法效率還能夠減少空間復雜度，
所以按照上面的分析結合本實驗來講，這三個問題（minimax演算法，alpha-beta剪枝及Expectimax）雖然能達到不同的目的，但是對于分數的提升很小甚至沒有，而想要獲取更高的分數則需要通過優化評估函式來實作，具體優化方式要視游戲規則而定，
總的來說，可以通過這個實驗專案來加深自己對minimax，alpha-beta剪枝以及評估函式的理解，對于光理論學習來說提升太多，