ミニマックス法を学ぶっ!
現在、こちらの書籍で学習しております。
私はChap5-1のミニマックス法でつまづいてしまいました。
ここでは、つまづいた内容である3目並べをミニマックス法で解くAIプレイヤーの作成を目標にして、学習しながら更新していこうと思います。
ミニマックス法とは何ぞや?
人は、3目並べをするときは、何手か先を考えてから石を置くと思います。 コンピューターの場合も、どこに石を置くか考える、 「思考ルーチン」が必要になります。 この1つが、今回の「ミニマックス法」です。 また、ミニマックス法を効率化した「アルファベータ法」というのもあります。
ミニマックス法ってどんなアルゴリズム?
自分が行えるすべての行動に対して「もしここに石を置いたら、相手はこうして...」という先読みを行い、その行動を評価します。 自分は自分にとって最善手を選び、 相手は自分にとって最悪手を選ぶという仮定のもと、最善手を探すアルゴリズムです。
今回は3目並べなので、すべての行動に対して、ゲーム終了まで先読みをして評価します。将棋などの行動に対しての選択肢が多いものについては、手先まで読むなどして、現実的な計算時間で行います。
phtyonで作ろう!
作るもの
- 3目並べ(ゲームシステム)
- プレイAI(ミニマックス)
- 実行コード
実行コード(仮)
先に、実行コードから考えていきます。
疑似コードになります。
# 3目並べをAI同士に対戦させる 1. 3目並べを用意する。 2. ゲーム終了まで、AI同士で戦う 2-1. 先手または後手のAIが石を置く。(ループごとに交代) 2-2. ゲーム終了か確かめる。 2-3. 表示する。
この疑似コードを、それっぽく書いてみる。
# 3目並べの状態を保持するクラス"State"を初期化する。 state = State() # ファーストプレイヤーの決定 player_a = random.randint(0,1) player_b = !player_a # ゲーム終了までループ。(Stateクラスのis_doneで確認) while ( state.is_done() ) : if player_a: # AIの選択した行動を取得する。(現在の状態からミニマックス法で選択) action = mini_max_action( state ) if player_b: # AIの選択した行動を取得する。 action = mini_max_action( state ) # 行動を状態に反映させる。 state = state.update( action ) # 表示 print(state) print("空白") # playerの入れ替え player_a, player_b = player_b, player_a
ここから、今適当に名前を付けたパーツを定義していけばよいことが分かります。
プレイAI (仮)
さて、次はAIについて考えます。 実行コード(仮)から、現在の状態からミニマックス法で選択する、mini_max_action( state )を作成すればよいことが分かりました。 早速疑似コードを作ってみます。 また、すでに石が置いてあるマスは選べません。ここでは、まだ石が置いていないマスを合法手と呼んでいます。Stateクラスで、合法手のリストを作る必要がありそうです。
# 現在の状態からミニマックス法で選択 def mini_max_action( state ): 1. 合法手を取得する 2. すべての合法手に対して、mini_max法で価値を計算する。 3. 最も価値の高い行動を返す。
ここから、もう少し詳しく考えます。 コードっぽく書けるところは、コードにしてしまいます。
# 現在の状態からミニマックス法で選択 def mini_max_action( state ): # 1. 合法手を取得する # 2. すべての合法手に対して、mini_max法で価値を計算する。 for action in state.legal_actions(): # 2-1. mini_max法で価値を取得 score = mini_max( state ) # 2-2. 価値が高いなら更新 if score > best_score: best_action = action best_score = score # 3. 最も価値の高い行動を返す。 return best_action
best_scoreなど、変数の定義などもしていきます。 行動は、マスの数字で返します。0~8の9通りです。 もちろん、合法手も同様にマスの数字を返します。
# 現在の状態からミニマックス法で選択 def mini_max_action( state ): #0. 変数の定義(わかりやすさも含めて、scoreも定義しました。) score = -float( 'inf' ) # 行動の価値。-無限大で初期化。 best_score = -float( 'inf' ) # 最も高い行動の価値。-無限大で初期化。 best_action = 0 # 最も価値の高い行動。マス0で初期化。 # 1&2. 全ての合法手に対して、mini_max法で価値を計算する。 for action in state.legal_actions(): # 2-1. mini_max法で価値を取得 score = mini_max( state.update( action ) ) # 2-2. 価値が高いなら更新 if score > best_score: best_action = action best_score = score # 3. 最も価値の高い行動を返す。 return best_action
整えます。
# 現在の状態からミニマックス法で行動を選択 def mini_max_action( state ): score = -float( 'inf' ) # 行動の価値。 best_score = -float( 'inf' ) # 最も高い行動の価値。 best_action = 0 # 最も価値の高い行動。 # 全ての合法手に対して、mini_max法で価値を計算。 for action in state.legal_actions(): # mini_max法で価値を取得 score = mini_max( state.update( action ) ) # 価値が高いなら更新 if score > best_score: best_action = action best_score = score # 最も価値の高い行動を返す。 return best_action
さて、肝心のmini_max()がまだ定義されていません。 コードが長くなってきたので、mini_max()のみの疑似コードを分けて作っていきます。 ミニマックス法では、再帰的な処理を行います。 今回はゲーム終了まで探索します。勝敗に価値をつけました。
# ミニマックス法である状態の価値を計算する。 def mini_max( state ): #1. もし勝利 なら+10を返す。 #2. もし敗北 なら -10を返す。 #3. もし引き分けなら 0を返す。 #4. もし決着がついてないなら #4-1. 現在の状態からすべての合法手に対してmini_max( state.update( action ) ) を行います。 #4-2.自分の番か相手の番かを確認し、 #4-2-T. もし自分の番なら、価値の最大値を返す。 #4-2-F. もし相手の番なら、価値の最小値を返す。
こんな感じでしょうか。 書籍ではNegaMax法というアルゴリズムを使っています。 今回は理解を深めるために、ひとまずミニマックス法をそのままコードにします。 これを、もっと作りこみます。
# ミニマックス法である状態の価値を計算する。 def mini_max( state ): #1. もし勝利 なら+10を返す。 if state.is_win(): return 10 #2. もし敗北 なら -10を返す。 elif state.is_lose(): return -10 #3. もし引き分けなら 0を返す。 elif state.is_draw(): return 0 #4. もし決着がついてないなら else : #4-1. 現在の状態からすべての合法手に対してmini_max( state.update( action ) ) を行います。 for action in state.legal_actions(): score = mini_max( state.update( action ) ) #4-2.自分の番か相手の番かを確認し、 #4-2-T. もし自分の番なら、価値の最大値を返す。 #4-2-F. もし相手の番なら、価値の最小値を返す。 if state.is_first_player() : if score > best_score: best_or_worst_score = score else: if score < best_score: best_or_worst_score = score return best_or_worst_score
こんな感じでしょうか。
最後に、三目並べ自体を作成します。
三目並べ(ゲームシステム)
盤の状態や、今どちらの手番かや、ゲームの終了判定もここで作成します。
作る機能一覧
- ゲームの石の配置状態の保持( __init__(self) )
- ゲームの終了状態の確認( is_done() )
- ゲームの勝敗状態の確認( is_win( self ), is_lose( self ), is_draw( self ) )
- 行動を入力して盤を更新する機能 (update( self, action ) )
- 合法手一覧の取得( legal_actions( self ) )
- その状態の手番プレイヤーの取得( is_first_player( self ) )
先手後手のルーレット- 表示を整える( __str__(self) )
# 三目並べの作成 # ゲームの状態 class State: # 初期化 def __init__(self, my_pieces=None, enemy_pieces=None): # 石の配置(elseで0で初期化している。) self.my_pieces = my_pieces if my_pieces != None else [0] * 9 self.enemy_pieces = enemy_pieces if enemy_pieces != None else [0] * 9 # 負けたかどうか def is_lose(self): 処理 #勝ったかどうか def is _win(self): 処理 #引分かどうか def is_draw(self): 処理 # ゲーム終了かどうか def is_done(self): 処理 # 次の状態 def update( self, action ): 処理 return State( self.my_pieces, self.enemy_piece ) # 合法手リストの取得 def legal_actions( self ): 処理 return actions # 先手かどうか def is_first_player(self): 処理 return True|False # 文字列表示 def __str__( self ): str = '' 処理 return str
これらをうまく合体させます。 githubに乗せます。