ここのつめ

三目並べAIのアルゴリズム(minimax探索)

『囲碁ディープラーニングプログラミング』を引き続き読んでいる。

肝心のディープラーニングの内容についての部分まで、なかなか到達しそうにない(^_^;

今回は、「三目並べ」である。

囲碁AIが次の一手を決めるとき、妥当な次の一手のリストを作成し、そのリストのそれぞれについて、相手がどう打つか、それに対して自分がどうするか、先まで読んで、その一手についての結論を出す。

その検討を次の一手のリスト全てについておこなう。その結果で次の一手を決定する。そのアルゴリズムがこれである。

ただ、これはこのゲームだからできるので、このアルゴリズムは時間がかかりすぎる。

さて、このアルゴリズム minimax探索の根幹はこのbest_result 関数である。
この関数では再帰処理を使っている。

<A>の部分が終了条件である。
game_stateが is_over() であるとき、
winner() が next_player すなわち 自分であるとき、GameResult.win が返る。
winner() が None すなわち 勝者がいないときは、GameResult.draw が返る。
その他は、GameResult.loss が返る。
def best_result(game_state):
    # <A> 終了条件
    if game_state.is_over():                                  
        if game_state.winner() == game_state.next_player:
            return GameResult.win
        elif game_state.winner() is None:
            return GameResult.draw
        else:
            return GameResult.loss

    # <B> 次の手を求める処理
    best_result_so_far = GameResult.loss                         # <1>
    opponent = game_state.next_player.other                      # <2>
    for candidate_move in game_state.legal_moves():              # <3>
        next_state = game_state.apply_move(candidate_move)       # <4>
        opponent_best_result = best_result(next_state)           # <5>
        our_result = reverse_game_result(opponent_best_result)   # <6>
        if our_result.value > best_result_so_far.value:          # <7>
            best_result_so_far = our_result                      # <8>
    return best_result_so_far                                    # <9>
# best_result_so_far -- これまでの最高の結果
<B>が次の手を求める処理で、再帰処理をしながら最終的に <A> の終了条件に
いきつく。
<1> -- best_result_so_far に GameResult.loss をセットしておく。
<2> -- opponent を相手とする。
<3> -- game_state.legal_move() -- 妥当と思われる次の手のリストを返す。
       candidate_move -- そのリストを1つひとつ candidate_move として
       検討する。
<4> -- next_state -- candidate_move すなわち、検討すべき次の手を適用し
       た局面。
<5> -- その next_state を引数として、この best_result を実行する。
例えば以下のような局面があったとする。

  A B C
1|o| |
2|x|x|
3| | |

今、黒は B2 と打ったところである。

(1) B1(o)-(row=1,col=2)と打つ手から検討する。
  
    A B C
  1|o|o|
  2|x|x|
  3| | |

  それに対して黒(x)は、C1、C2、A3、B3、C3 という手が考えられる。

  (1-1) 黒(x)が C1(row=1,col=3) と打った場合
              next_state.next_player == Player.black
      A B C
    1|o|o|x
    2|x|x|
    3| | |

    (1-1-1) それに対して白(o)が C2(row=2,col=3) と打った場合
                 next_state.next_player == Player.white
        A B C
      1|o|o|x
      2|x|x|o
      3| | |

      (1-1-1-1) それに対して黒(x)が A3(row=3,col=1) と打った場合
                   next_state.next_player === Player.black
                   opponent_best_result              our_result
                   GameResult.win    --> reverse --> GameResult.loss
          A B C
        1|o|o|x
        2|x|x|o
        3|x| |

      (1-1-1-2) 次は黒(x)が B3(row=3,col=2) と打った場合
                   next_state.next_player === Player.black
          A B C
        1|o|o|x
        2|x|x|o
        3| |x|

        (1-1-1-2-1) それに対して白(o)が A3(row=1,col=2) と打った場合
                     next_state.next_player === Player.white
                     opponent_best_result              our_result
                     GameResult.draw   --> reverse --> GameResult.draw
            A B C
          1|o|o|x
          2|x|x|o
          3|o|x|

他にもいろいろな結果が考えられるが、
(1-1)のように、黒(x)が C1(row=1,col=3) と打った場合には、
GameResult.loss と GameResult.draw の2種類の結果が得られる。

黒(x)も best_result関数を使って GameResult.win の手を探し出す。
(1)の白(o)B1 という手については、黒が C3 (GameResult.win) という手を見つけだす。だから、白(o)B1 という手は、GameResult.loss という値を返すことになる。

白(o)は、B1, C1, C2, A3, B3, C3 と、順に best_result関数を使って最善手を探す。B1 は GameResult.loss であったが、C1, A3, B3, C3 については、黒(x)が C2 と打てば GameResult.loss という値が返ってくるので、白(o)の C2 という手のみが GameResult.draw もしくは GameResult.winという値を返すことになる。

『囲碁ディープラーニングプログラミング』

Max Pumperia、Kevin Ferguson 著
山岡忠夫 訳
マイナビ出版
2019年4月22日 初版第1刷