changed 3 years ago  
Linked with GitHub

Python實作課程

第五堂課 : Tic Tac Toe(AI)

2022 / 5 / 27

Tony

重點回顧

我們前兩堂課寫完了基本的TicTacToe，玩家可以是真人也可以是電腦，但此時的電腦並不像真人用腦子玩遊戲，他只是隨便挑一格放符號而已
可不可以讓電腦具備判斷盤面的能力，讓他下的每一步都是對他具有最大效益的?

minimax

MiniMax算法常用於棋類等由兩方較量的遊戲和程序。該算法是一個零總和算法，即一方要在可選的選項中選擇將其優勢最大化的選擇，另一方則選擇令對手優勢最小化的方法。而開始的時候總和為0。

本Code當中的minimax思維：當換到AI的回合時，挑選對他而言優勢最大的選擇；當另一個玩家的回合時，挑選對他而言傷害最小的選擇

我們希望以最短的步數贏下比賽，所以：

  1. 如果最後AI贏，
    則該盤面的value = 1*(現在盤面所剩空格+1)
  2. 如果最後AI輸掉，
    則該盤面的value = -1*(現在盤面所剩空格+1)
  3. 平局的盤面，其value=0
  4. 每個最終盤面的value往回推，如果該回合換AI，則選擇他的子盤面中value最大者，反之則選最小者
  5. 最後根據當前盤面以及玩家做最好的選擇

開始寫Code

請打開上次寫完的TicTacToe
If 檔案丟失：點我拿完整Code

在TicTacToe補上這個函式(如果沒有)



def num_empty_squares(self):
    return self.board.count(' ')

我們要做的：

  1. 建一個GeniusComputerPlayer Class
  2. 寫minimax函式
  1. 建立GeniusComputerPlayer Class
    建在player.py裡面，構造仿照前兩個寫過的player
    並多一個minimax函式，函式最後會回傳一個字典Dictionary
















class GeniusComputerPlayer(Player):
    def __init__(self, letter):
        super().__init__(letter)
    
    def get_move(self, game):
        
        if len(game.available_moves()) == 9:
            square = random.choice(game.available_moves())
        else:
            square = self.minimax(game, self.letter)['score']
        return square
        
    def minimax(self, state, player):
        #state：遊戲本體，但因為我們指的是"當前盤面"
        #所以用state較佳
        pass
  1. 寫minimax函式
    先設點變數




def minimax(self, state, player):
    max_player = self.letter # AI自己
    other_player = 'O' if player == 'X' else 'X'

接著，我們check目前盤面是否為一個最終盤面，即上一個玩家已經贏了或是平手

我們需要用到一個資料型態叫做dictionary字典，他是一個集合，每一個元素由一個鍵(Key)和值(Value)組成










if state.current_winner == other_player:
    
    if other_player == self.letter: #最終盤面是AI贏
        return {'position':None, 'score':1*(state.num_empty_squares()+1)}
    elif not state.empty_squares():
        return {'position':None, 'score':0}
    else: #最終盤面是AI輸
        return {'position':None, 'score':-1*(state.num_empty_squares()+1)}

再來，我們就要進入預測盤面的環節，先初始化環境





if player == max_player:#如股現在玩家是AI就要選最大優勢的
    best = {'position':None, 'score':-math.inf} #負無限大，即保證他的score會越來越大
else:#反之則選傷害最小的
    best = {'position':None, 'score':math.inf}#正無限大，即保證他的score會越來越小

預測盤面：針對目前盤面的下一層所有可能結果

  1. 先做一次該結果
  2. 利用遞迴去找他的子平面的所有狀況，因此可以模擬所有盤面
  3. 回復原狀
  4. 如果有模擬盤面有更好的字典就更新



















for possible_move in state.available_moves():
    # step 1:make a move, try that spot
    state.make_move(possible_move, player)
    # step 2:recurse using minimax to simulate a game after making that move
    sim_score = self.minimax(state, other_player) #now, we alternate player
            
    # step 3:undo the move
    state.board[possible_move] = ' '
    state.current_winner = None
    sim_score['position'] = possible_move

    # step 4: update the dictionaries if necessary
    if player == max_player: # to maximize the max_player
        if sim_score['score'] > best['score']:
            best = sim_score # replace that
    else: # to minimize the other_player
        if sim_score['score'] < best['score']:
            best = sim_score # replace that
return best
Select a repo