みっつめ

三目並べAI – 深さで刈り込まれたminimax探索

minimax探索だと時間がかかりすぎるので、時間短縮の方法として、探索木の深さを制限する。

今回は DEPTH=3 とした。

たとえば、以下のような局面があるとする。

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

白の手としては、いろいろ考えられる。が、それを深さ 3 までしか考えないとする。

              DEPTH=3       DEPTH=2       DEPTH=1      DEPTH=0
(パターンA)
  A B C         A B C         A B C         A B C      
1|x|o| |      1|x|o| |      1|x|o| |      1|x|o| |     局面評価
2| | | |  ->  2| |x| |  ->  2| |x| |  ->  2|x|x| |  -> 
3| | | |      3| | | |      3| | |o|      3| | |o|

(パターンB)
  A B C         A B C         A B C         A B C      
1|x| | |      1|x|x| |      1|x|x|o|      1|x|x|o|      局面評価
2| |o| |  ->  2| |o| |  ->  2| |o| |  ->  2| |o| |  ->
3| | | |      3| | | |      3| | | |      3|x| | |

さまざまなパターンが考えられるが、DEPTH=0 の時に局面を評価する関数を考えておく。
その関数の性能が良ければ、このAIは賢くなる。

今回はその関数については考えず、単に 0 を返すだけとする。

minimax.py
import enum
import random

from dlgo.agent import Agent

MAX_SCORE = 10
MIN_SCORE = -10
DEPTH = 3

def eval_situation(game_state):
    return 0

# 深さで枝刈りされたミニマックス検索    
def best_result(game_state, max_depth, eval_fn):
    if game_state.is_over():
        if game_state.winner() == game_state.next_player:
            return MAX_SCORE + max_depth
        elif game_state.winner() == game_state.next_player.other:
            return MIN_SCORE - max_depth
        else:
            return 0

    if max_depth == 0:
        return eval_fn(game_state)

    best_so_far = MIN_SCORE
    for candidate_move in game_state.legal_moves():
        next_state = game_state.apply_move(candidate_move)
        opponent_best_result = best_result(next_state, max_depth - 1, eval_fn)
        our_result =  -1 * opponent_best_result
        if our_result > best_so_far:
            best_so_far = our_result
    return best_so_far
# best_so_far -- これまでの最高

def print_best_moves(str, best_moves):
    for move in best_moves:
        print(str, move.point)

class MinimaxAgent(Agent):
    def select_move(self, game_state):
        best_moves = []
        our_best_outcome = None
        for possible_move in game_state.legal_moves():
            print('possible_move %s %s' % (possible_move.point, game_state.next_player))
            next_state = game_state.apply_move(possible_move)        # <1>
            opponent_best_outcome = best_result(next_state, DEPTH, eval_situation)   # <2>
            our_better_outcome = -1 * opponent_best_outcome          # <3>
            if our_best_outcome is None:                             # <4>
                our_best_outcome = our_better_outcome
                best_moves.append(possible_move)
            elif our_best_outcome == our_better_outcome:               # <5>
                best_moves.append(possible_move)
            elif our_best_outcome < our_better_outcome:                # <6>
                our_best_outcome = our_better_outcome
                best_moves.clear()
                best_moves.append(possible_move)
            else:
                print('負ける手なので、考慮の対象外')
            print('our_better_outcome:%d  our_best_outcome:%d' % (our_better_outcome, our_best_outcome))

        if best_moves:
            print_best_moves('best', best_moves)
            return random.choice(best_moves)
        else:
            print('best_movesがないなんて、あり得ない...')
            
    # <1> game_state.apply_move は、next_state を 相手側とする。
    #     つまり、possible_moveを適用した盤状況で、player は相手側であ
    #     る。
    # <2> DEPTH -- 定数とした。
    # <3> 相手が MAX_SCORE なら、こちら側は MIN_SCORE である。
    # <4> our_best_outcome が None ならば、our_better_outcome の値を
    #     our_best_outcome に入れて、best_moves にその着手を入れる。
    # <5> our_best_outcome と our_better_outcome が同じなら
    #     best_moves にその着手を追加する。
    # <6> our_best_outcome よりも our_better_outcome の方が大きければ
    #     best_moves を空にして、その着手をリストに入れる。

実際にやってみる。

$ python3 play_ttt.py

   A   B   C
1    |   |  
2    |   |  
3    |   |  
-- a1
   A   B   C
1  X |   |  
2    |   |  
3    |   |  
possible_move Point(row=1, col=2) Player.o
our_better_outcome:0  our_best_outcome:0
possible_move Point(row=1, col=3) Player.o
our_better_outcome:0  our_best_outcome:0
possible_move Point(row=2, col=1) Player.o
our_better_outcome:0  our_best_outcome:0
possible_move Point(row=2, col=2) Player.o
our_better_outcome:0  our_best_outcome:0
possible_move Point(row=2, col=3) Player.o
our_better_outcome:0  our_best_outcome:0
possible_move Point(row=3, col=1) Player.o
our_better_outcome:0  our_best_outcome:0
possible_move Point(row=3, col=2) Player.o
our_better_outcome:0  our_best_outcome:0
possible_move Point(row=3, col=3) Player.o
our_better_outcome:0  our_best_outcome:0
best Point(row=1, col=2)
best Point(row=1, col=3)
best Point(row=2, col=1)
best Point(row=2, col=2)
best Point(row=2, col=3)
best Point(row=3, col=1)
best Point(row=3, col=2)
best Point(row=3, col=3)
   A   B   C
1  X |   |  
2    |   | O
3    |   |  

A1と黒(人間)が打った。それに対して、白(AI)はすべての着手を検討しているが、深さを3までにしているので、プログラムからは、0が返ってきている。
AIは、ランダムに手を選択して、C2とした。

-- b2
   A   B   C
1  X |   |  
2    | X | O
3    |   |  
possible_move Point(row=1, col=2) Player.o
our_better_outcome:-12  our_best_outcome:-12
possible_move Point(row=1, col=3) Player.o
our_better_outcome:-12  our_best_outcome:-12
possible_move Point(row=2, col=1) Player.o
our_better_outcome:-12  our_best_outcome:-12
possible_move Point(row=3, col=1) Player.o
our_better_outcome:-12  our_best_outcome:-12
possible_move Point(row=3, col=2) Player.o
our_better_outcome:-12  our_best_outcome:-12
possible_move Point(row=3, col=3) Player.o
our_better_outcome:-10  our_best_outcome:-10
best Point(row=3, col=3)
   A   B   C
1  X |   |  
2    | X | O
3    |   | O

黒が B2 と打った。それに対して、白はすべての手を検討し、C3以外は -12 という点で負け。C3 でも負けなのだが、まだ勝負は続くので、max_depthの値が小さくなるので -10 という値になる。それで C3 を選択している。

ここで、黒は C1 と打つと黒の勝ちになるが、AIはどう判断するであろうか?

-- c1
   A   B   C
1  X |   | X
2    | X | O
3    |   | O
possible_move Point(row=1, col=2) Player.o
our_better_outcome:-12  our_best_outcome:-12
possible_move Point(row=2, col=1) Player.o
our_better_outcome:-12  our_best_outcome:-12
possible_move Point(row=3, col=1) Player.o
our_better_outcome:-12  our_best_outcome:-12
possible_move Point(row=3, col=2) Player.o
our_better_outcome:-12  our_best_outcome:-12
best Point(row=1, col=2)
best Point(row=2, col=1)
best Point(row=3, col=1)
best Point(row=3, col=2)
   A   B   C
1  X |   | X
2    | X | O
3  O |   | O

どこに打っても負けと見ている。白はA3を選択したが、これはたまたまである。
B1で黒の勝ちだが、わざとB3と打ってみることにする。

-- b3
   A   B   C
1  X |   | X
2    | X | O
3  O | X | O
possible_move Point(row=1, col=2) Player.o
our_better_outcome:0  our_best_outcome:0
possible_move Point(row=2, col=1) Player.o
負ける手なので、考慮の対象外
our_better_outcome:-12  our_best_outcome:0
best Point(row=1, col=2)
   A   B   C
1  X | O | X
2    | X | O
3  O | X | O

白は、B1 だと引き分け。A2 は負けとしている。
そこで、B1を選択している。

今後のこと

   A   B   C
1  X |   |  
2  O |   |  
3    |   |  

この局面は、黒の勝ちである。黒がB2と打てば、白は負けになる。
ということは、黒がA1と打ったときに、どこに打てば負けないかというと、これはなかなか難しい。B2、C3以外は負けだろうと思われる。

これを初期データとして組み込めばいいんだろうけど、AIに学習させれば面白いと思う。
機械学習って、そういうことなのだろうなと思った。

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

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