# Python實作課程 ## 第五堂課 : Tic Tac Toe(AI) ## 2022 / 5 / 27 ### Tony --- ## 重點回顧 ---- 我們前兩堂課寫完了基本的TicTacToe，玩家可以是真人也可以是電腦，但此時的電腦並不像真人用腦子玩遊戲，他只是隨便挑一格放符號而已 可不可以讓電腦具備判斷盤面的能力，讓他下的每一步都是對他具有最大效益的? --- ## minimax ---- MiniMax算法常用於棋類等由兩方較量的遊戲和程序。該算法是一個零總和算法，<font color='FFF300'>即一方要在可選的選項中選擇將其優勢最大化的選擇，另一方則選擇令對手優勢最小化的方法。</font>而開始的時候總和為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](https://hackmd.io/@Tony041010/TicTacToe_FullCode) ---- 在TicTacToe補上這個函式(如果沒有) ```python= def num_empty_squares(self): return self.board.count(' ') ``` ---- 我們要做的： 1. 建一個GeniusComputerPlayer Class 2. 寫minimax函式 ---- 1. 建立GeniusComputerPlayer Class 建在`player.py`裡面，構造仿照前兩個寫過的player 並多一個minimax函式，函式最後會回傳一個字典Dictionary ```python= 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 ``` ---- 2. 寫minimax函式 先設點變數 ```python= def minimax(self, state, player): max_player = self.letter # AI自己 other_player = 'O' if player == 'X' else 'X' ``` ---- 接著，我們check目前盤面是否為一個最終盤面，即上一個玩家已經贏了或是平手 我們需要用到一個資料型態叫做**dictionary字典**，他是一個集合，每一個元素由一個鍵(Key)和值(Value)組成 ```python= 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)} ``` ---- 再來，我們就要進入預測盤面的環節，先初始化環境 ```python= if player == max_player:#如股現在玩家是AI就要選最大優勢的 best = {'position':None, 'score':-math.inf} #負無限大，即保證他的score會越來越大 else:#反之則選傷害最小的 best = {'position':None, 'score':math.inf}#正無限大，即保證他的score會越來越小 ``` ---- 預測盤面：針對目前盤面的下一層所有可能結果 1. 先做一次該結果 2. 利用遞迴去找他的子平面的所有狀況，因此可以模擬所有盤面 3. 回復原狀 4. 如果有模擬盤面有更好的字典就更新 ---- ```python= 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 ```