Pythonでマルバツゲームをつくろう #5 最強ボット編

今回は最強のマルバツゲームボット🤖を作ります。

前回：Pythonでマルバツゲームをつくろう #4 ランダムボット編

from IPython.display import clear_output

O = "○"
X = "×"
USER = O if random.choice([True, False]) else X

current_player = O                             # 現在のプレイヤー
turn = 0                                          # 今何ターン目か
board = [                                         # 盤面(リスト)
    "𝟶", "𝟷", "𝟸",
    "𝟹", "𝟺", "𝟻",
    "𝟼", "𝟽", "𝟾"
]

print(f"あなたは {USER} です")
print(f" {board[0]} │ {board[1]} │ {board[2]} ")  # 最初の盤面を表示
print("───┼───┼───")
print(f" {board[3]} │ {board[4]} │ {board[5]} ")
print("───┼───┼───")
print(f" {board[6]} │ {board[7]} │ {board[8]} ")

while turn < 9:
    turn += 1                                # ターンを進める
    print(f"次は {current_player} の番です")
    if current_player == USER:               # もしcurrent_playerがOなら
        clear_output(wait=True)              # ⭐️
        while True:                          # ユーザの入力を受け取る
            try:
                index = int(input(f"{current_player} の手 : "))
                if board[index] != O and board[index] != X:
                    break
                else:
                    print("𝟶 ~ 𝟾 の空いているマスを選んでください")
            except ValueError:
                print("整数を入力してください")
            print(f" {board[0]} │ {board[1]} │ {board[2]} ")
            print("───┼───┼───")
            print(f" {board[3]} │ {board[4]} │ {board[5]} ")
            print("───┼───┼───")
            print(f" {board[6]} │ {board[7]} │ {board[8]} ")
            clear_output(wait=True)          # ⭐️
    else:                                    # もしcurrent_playerがXなら
        print("ボット考え中...")
        clear_output(wait=True)              # ⭐️
        time.sleep(2)
        index = random.choice([index for index, value in enumerate(board) if value not in (O, X)])
        print(f"ボットの手: {index}")
    board[index] = current_player                       # 入力手を盤面に適用
    print(f" {board[0]} │ {board[1]} │ {board[2]} ")    # 現在の盤面を表示
    print("───┼───┼───")
    print(f" {board[3]} │ {board[4]} │ {board[5]} ")
    print("───┼───┼───")
    print(f" {board[6]} │ {board[7]} │ {board[8]} ")
                                                         # 勝利判定
    if  (board[0] == board[1] == board[2] == current_player) or \
        (board[3] == board[4] == board[5] == current_player) or \
        (board[6] == board[7] == board[8] == current_player) or \
        (board[0] == board[3] == board[6] == current_player) or \
        (board[1] == board[4] == board[7] == current_player) or \
        (board[2] == board[5] == board[8] == current_player) or \
        (board[0] == board[4] == board[8] == current_player) or \
        (board[2] == board[4] == board[6] == current_player):
        print(f"勝者: {current_player}")
        break
    current_player = O if current_player == X else X  # 手番交代
else:
    print("引き分け")                                           # 引き分け

1. ミニマックス法の説明

最強のボットとは

• 最強のボットとは何かというと、最強の手を打てるボットのことです。
• 最強の手を見つけるために今回はミニマックス法というアルゴリズム(手順)を使います。

ミニマックス法とは

• この方法は、「自分は自分の得点を最大化(Maximize)しようとし、一方で相手は最小化(minimize)しようと邪魔してくるだろう」という想定で未来の局面を先読みしていくことで、現在の盤面における最善手を見つけるものです。
• マルバツゲームにおいては、○勝ちを+1、引き分けを0、×勝ちを-1としたとき、○はなるべく点数が高くなるような手を選ぼうとするだろうし、逆に×はなるべく点数が低くなるような手を選ぼうとするだろうと考えるわけです。

具体例：×が右上隅に打った場合

• 例えばこのような盤面Aがあったとします。一手前に○が左上隅に打ちました。×は次にどこに打つべきでしょうか？

• わからないので、とりあえずインデックス順に、試しに右上隅に打ってみることにします。

• まだ終局ではないのでまだこの手が良かったのかはわかりません。○が次の手(左端真ん中)を打ちました。

• すると、左の縦が揃いました！○の勝ち(+1)で終局です。そこで、終局した盤面Cを+1の盤面ということにします。
• ということは、その盤面に導いた一つ前の盤面B（○の番）も、この盤面にさえ持っていければ必ず○勝ちになるということなので、盤面Bも+1の盤面ということにしましょう。

• さて、ここまで先読みしていったことで盤面Aで×が右上隅に打つと×は負けることがわかりました。

他の場合：×が左端真ん中に打った場合

• では、最初に×が左端真ん中に打っていた場合はどうだったのでしょう？先ほどと同じように先読みしていくと、最終的に0(引き分け)の盤面に行き着くことがわかります。

どちらを選ぶ？

• ここまでの先読みが済んだ上で、最初の盤面Aで、×はどの手を選ぶでしょうか。わざわざ+1の盤面になる手を選んで○に勝たせるなんて都合の良いことをするはずがありません。×は得点を最小化しようとするはずですから、+1と0なら、必ず値が低い0を選ぶはずです。ということで、盤面Aは0の盤面ということになります。これがミニマックス法の考え方です。

• このように、「○ならなるべく値が高くなる手を選ぶはずだ」「×ならなるべく値が低くなる手を選ぶはずだ」という前提で終局盤面から遡って考えていき、次の手を決定するのです。

• 同じように一手一手戻っていけば、最終的にはどんな盤面でも最善手がわかるはずです。

2. minimax関数

• これをプログラミングするにあたり、上で各盤面は何をしていたのか整理してみましょう。

1. 盤面が終局盤面だった場合

• まず、盤面が終局盤面だった場合、○勝ちなら+1、引き分けなら0、×勝ちなら-1を自分の値としていました。

2. 盤面が進行中の盤面だった場合

• 一方、進行中の盤面においては、一つ後の盤面（これを子局面と呼ぶことにします）の値を比べて、自分が○ならなるべく高い値を、自分が×ならなるべく低い値を自分の盤面の値としていました。

• つまり、終局盤面と進行中盤面の二パターンで処理が異なっていたのです。
• これを表現する関数を作ります。関数というのは何かを受け取ったら何かを返す自動販売機でした。今回ほしい自動販売機は何かというと、盤面とそれがどちらの番かの二つの情報を渡すと、その盤面の値（○勝ちなら+1、引き分けなら0、×勝ちなら-1）を返してくれるものです。

3. minimax関数をつくる

• それではminimax関数をコーディングしていきましょう。

終局盤面を受け取った場合の処理

• まず、終局盤面を受け取った場合は簡単に表現できます。終局盤面が○勝ちなら+1、引き分けなら0、×勝ちなら-1を返すだけです。

def minimax(board, player):
    # もしboardが終局盤面だったら。進行中盤面ならこのif文は3つともスルーされる
    if result(board, player) == "○ win":    # もし○勝ちなら
        return 1
    elif result(board, player) == "draw":   # もし引き分けなら
        return 0
    elif result(board, player) == "× win":  # もし×勝ちなら
        return -1

• そのためにresult関数という、結果判定用の関数を作っておきます。下のような単純な仕組みになっています。

# ○勝ちなら1を、×勝ちなら-1を、引き分けなら0を返す(まだ終局していないならNoneを返す)
def result(board, player):
    # 勝利判定
    if  (board[0] == board[1] == board[2] == player) or \
        (board[3] == board[4] == board[5] == player) or \
        (board[6] == board[7] == board[8] == player) or \
        (board[0] == board[3] == board[6] == player) or \
        (board[1] == board[4] == board[7] == player) or \
        (board[2] == board[5] == board[8] == player) or \
        (board[0] == board[4] == board[8] == player) or \
        (board[2] == board[4] == board[6] == player):
        if player == O:  # もし勝利したのが O なら
            return "○ win"
        else:            # もし勝利したのが X なら
            return "× win"
    # boardに打てる手が存在しない場合、すなわち引き分けなら
    elif not legal_moves(board):
        return "draw"

• 引き分け判定で使われているlegal_moves関数は、ランダムボットが候補手を集めるコードを関数化しただけのものです。

# boardを受け取ると、次に打てるインデックス(つまり空マス)をまとめたリストを返す
def legal_moves(board):
    return [index for index, value in enumerate(board) if value not in (O, X)]

• これでminimax関数は終局盤面を渡された場合は対処できるようになりました。

進行中の盤面を受け取った場合の処理

• 次は進行中盤面を渡された時に対応できるようにしましょう。具体的には、子局面たちの値を調べ、最も良い（○の番ならば高い、×の番ならば低い）値を返すようにします。

プレイヤが○の場合

• まずは○の番の盤面を渡された場合の処理を見ていきます。○の番の盤面は、子盤面のうち、なるべく高い値を自分の値とします。

if player == O:                       # もしプレイヤが○なら
    max_val = -1                      # 「最大値」は最初は-1に設定しておく
    for index in legal_moves(board):  # 合法手を一つ一つ見ていくループ
        boardcopy = board.copy()      # 盤面のコピーを用意する
        boardcopy[index] = O          # 試しに打ってみる
        val = minimax(boardcopy, X)   # 試しに打ってみた盤面(子局面)を手番とともに再びminimax関数に投げる
        if val > max_val:             # もし子局面の返した値が現在の最大値より大きいなら
            max_val = val             # 最大値を更新する
    return max_val                    # 最大値をreturnする

• 最初に設定しているmax_valというのは子盤面たちの最大値のことです。最初は-1に設定しておき、あとでより高い値が見つかればその都度更新します。
• for index in legal_moves(board):で、この盤面で次に打てる場所を一つ一つ見ていきます。
• boardcopy = board.copy()で、boardのコピーを作っています。このようにすることで、minimax関数を呼び出した側が渡したboard本体がいじられることなくミニマックス関数内で実験が行われます。
• boardcopy[index] = Oで、indexの位置に○を試しに打っています。

minimax関数内にminimax関数が登場

• 大事なのはval = minimax(boardcopy, X)というところです。minimax関数内でminimax関数が登場しています。これは一体どういうことでしょうか？
• minimax関数は、終局盤面を受け取った場合はそのまま値を返しますが、進行中の盤面を受け取った場合はその子局面の値の最も「良い」値を返す、と説明しました。ところが、最初の時点ではそもそも子局面の値は分かりません。

• ではどうするかというと、次は子局面をminimax関数に投げるわけです。

• それでもわからないければもう一度投げます。

• このように繰り返すと、終局盤面に辿り着きます。ここで初めて具体的な値のreturnが起こります。

• 一旦コードに戻ります。

if val > max_val:
    max_val = val

• この部分は、帰ってきた子盤面の値が現在のmax_valより高ければそれを新たなmax_valとしています。
• そして最後に

return max_val

としてmax_valueを返しているのです。

• この仕組みによって、終局局面ならばその値がそのまま上へ、進行中局面ならばその子局面たちの一番良い値が上へ伝播されていくのです。

プレイヤが×の場合

• プレイヤが×だった場合も基本的には全く同じです。○が最大値を探したのに対して、こちらは最小値を探すという違いだけです。

if player == X:
    min_val = 1
    for index in legal_moves(board):
        boardcopy = board.copy()
        boardcopy[index] = X
        val = minimax(boardcopy, O)
        if val < min_val:
            min_val = val
    return min_val

minimax関数の完成

• ここまでを全て合わせるとminimax関数の完成です！

# 盤面とプレイヤを受け取ると、その盤面からプレイヤが受け取れる最も「良い」値を返す関数。○勝ち：１、引き分け：０、×勝ち：−１とする
# 具体的には：①もし終局盤面なら、その結果を返す
#           ②そうではなくもしゲーム進行中の盤面なら、子局面たちのうち最も「良い」値を返す
def minimax(board, player):
    if result(board, player) == "○ win":    # もし○勝ちなら
        return 1
    elif result(board, player) == "draw":   # もし引き分けなら
        return 0
    elif result(board, player) == "× win":  # もし×勝ちなら
        return -1

    if player == O:
        max_val = -1
        for index in legal_moves(board):
            boardcopy = board.copy()
            boardcopy[index] = O
            val = minimax(boardcopy, X)
            if val > max_val:
                max_val = val
        return max_val
    else:
        min_val = 1
        for index in legal_moves(board):
            boardcopy = board.copy()
            boardcopy[index] = X
            val = minimax(boardcopy, O)
            if val < min_val:
                min_val = val
        return min_val

4. minimax関数を利用する

• 最後に、ボットがminimax関数を利用して手を選ぶようにしましょう。
• まずは下準備として、もともとあった定数USERに加えて定数BOTも作ります。コード冒頭の定数定義の部分を以下のように書き換えておきます。

USER, BOT = (O, X) if random.choice([True, False]) else (X, O)

• 1/2の確率でUSERにOそしてBOTにXが、また1/2の確率でUSERにXそしてBOTにOが格納されます。
• ボットが手を選ぶ処理は以下のようになります。

else:                                                              # もしボットのターンなら
    print("ボット考え中...")
    clear_output(wait=True)
    time.sleep(2)
    win_moves = []                                                 # ボットが勝つ手
    draw_moves = []                                                # 引き分ける手
    lose_moves = []                                                # 負ける手
    for idx in legal_moves(board):                                 # 合法手を一つ一つ見ていく
        boardcopy = board.copy()                                   # 盤面のコピーを作っておく
        boardcopy[idx] = BOT                                       # この手がいい手かどうか、試しに打ってみる
        val = minimax(boardcopy, USER)                             # ミニマックス関数を適用
        if (BOT == X and val == -1) or (BOT == O and val == 1):    # もし勝つ手なら:
            win_moves.append(idx)
        elif val == 0:                                             # そうではなくもし引き分ける手なら:
            draw_moves.append(idx)
        elif (BOT == X and val == 1) or (BOT == O and val == -1):  # そうではなくもし負ける手なら:
            lose_moves.append(idx)
    if win_moves:                                                  # もしwin_movesリストが空でないなら:
        index = random.choice(win_moves)
    elif draw_moves:                                               # そうではなくもしdraw_movesリストが空でないなら:
        index = random.choice(draw_moves)
    else:                                                          # そうでないなら:
        index = random.choice(lose_moves)
    print(f"ボットの手: {index}")

• time.sleep(2)までの最初の3行はランダムボットと同じです。ランダムボットでは、この後index = random.choice([index for index, value in enumerate(board) if value not in (O, X)])のように、空マスからランダムに手を選んでいました。
• 一方、ミニマックス法による最強ボットは、まず三つのリストを用意します。

win_moves = []
draw_moves = []
lose_moves = []

• これらのリストにはそれぞれボットが勝てる手、引き分けになる手、負ける手が格納されます。最終的に、win_movesに手があればまずはその中から選び、なければdraw_movesから、そこにもなければlose_movesから選ぶことにします。
• boardcopy = board.copy()では盤面のコピーを作っています。そして、boardcopy[idx] = BOTで試しに打っています。
• val = minimax(boardcopy, USER)で、試しに打った盤面の値を確認しています。そしてそれが勝つ値なのか引き分けの値なのか負ける値なのかに応じて、その下のif文で三つのリストに振り分けています。

if (BOT == X and val == -1) or (BOT == O and val == 1):    # もし勝つ手なら:
    win_moves.append(idx)
elif val == 0:                                             # そうではなくもし引き分ける手なら:
    draw_moves.append(idx)
elif (BOT == X and val == 1) or (BOT == O and val == -1):  # そうではなくもし負ける手なら:
    lose_moves.append(idx)

• 振り分けが完了したら、三つのリストの中から今回打つ手を取り出します。

if win_moves:                                                  # もしwin_movesリストが空でないなら:
    index = random.choice(win_moves)
elif draw_moves:                                               # そうではなくもしdraw_movesリストが空でないなら:
    index = random.choice(draw_moves)
else:                                                          # そうでないなら:
    index = random.choice(lose_moves)

• もしwin_movesリストが空ではないならそこからランダムに選び、もしwin_movesが空でdraw_movesが空ではないならそこからランダムに選び、どちらでもなくlose_movesにしか要素がなければそこからランダムに選びます。

完成！

from IPython.display import clear_output
import random, time

O = "○"
X = "×"
USER, BOT = (O, X) if random.choice([True, False]) else (X, O)

current_player = O
turn = 0
board = [
    "𝟶", "𝟷", "𝟸",
    "𝟹", "𝟺", "𝟻",
    "𝟼", "𝟽", "𝟾"
]

# boardを受け取ると、次に打てるインデックスをまとめたリストを返す
def legal_moves(board):
    return [index for index, value in enumerate(board) if value not in (O, X)]

# ○勝ちなら1を、×勝ちなら-1を、引き分けなら0を、そもそもまだ終局していないならNoneを返す
def result(board, player):
    # 勝利判定
    if  (board[0] == board[1] == board[2] == player) or \
        (board[3] == board[4] == board[5] == player) or \
        (board[6] == board[7] == board[8] == player) or \
        (board[0] == board[3] == board[6] == player) or \
        (board[1] == board[4] == board[7] == player) or \
        (board[2] == board[5] == board[8] == player) or \
        (board[0] == board[4] == board[8] == player) or \
        (board[2] == board[4] == board[6] == player):
        if player == O:  # もし勝利したのが O なら
            return "○ win"
        else:            # もし勝利したのが X なら
            return "× win"
    # boardに合法手が存在しない場合、すなわち引き分けなら
    elif not legal_moves(board):
        return "draw"

# 盤面とプレイヤを受け取ると、その盤面からプレイヤが受け取れる最も良い値を返す関数。○勝ち：１、引き分け：０、×勝ち：−１とする
# 具体的には：①もし終局盤面なら、その結果を返す
#           ②そうではなくもしゲーム進行中の盤面なら、子局面達のうち最も良い結果を返す
def minimax(board, player):
    if result(board, player) == 1:     # ○勝ち
        return 1
    elif result(board, player) == 0:   # 引き分け
        return 0
    elif result(board, player) == -1:  # ×勝ち
        return -1

    if player == O:
        max_val = -1
        for index in legal_moves(board):
            boardcopy = board.copy()
            boardcopy[index] = O
            val = minimax(boardcopy, X)
            if val > max_val:
                max_val = val
        return max_val
    else:
        min_val = 1
        for index in legal_moves(board):
            boardcopy = board.copy()
            boardcopy[index] = X
            val = minimax(boardcopy, O)
            if val < min_val:
                min_val = val
        return min_val

print(f"あなたは {USER} です")
print(f" {board[0]} │ {board[1]} │ {board[2]} ")
print("───┼───┼───")
print(f" {board[3]} │ {board[4]} │ {board[5]} ")
print("───┼───┼───")
print(f" {board[6]} │ {board[7]} │ {board[8]} ")

while turn < 9:
    turn += 1
    print(f"次は {current_player} の番です")
    if current_player == USER:
        clear_output(wait=True)
        while True:
            try:
                index = int(input(f" {current_player} の手: "))
                if 0 <= index <= 8 and board[index] != O and board[index] != X:
                    break
                else:
                    print("𝟶 ~ 𝟾 の空いているマスを選んでください")
            except ValueError:
                print("整数を入力してください")

            print(f" {board[0]} │ {board[1]} │ {board[2]} ")
            print("───┼───┼───")
            print(f" {board[3]} │ {board[4]} │ {board[5]} ")
            print("───┼───┼───")
            print(f" {board[6]} │ {board[7]} │ {board[8]} ")
            clear_output(wait=True)
    else:
        print("ボット考え中...")
        clear_output(wait=True)
        time.sleep(2)
        win_moves = []
        draw_moves = []
        lose_moves = []
        for idx in legal_moves(board):
            boardcopy = board.copy()
            boardcopy[idx] = BOT
            val = minimax(boardcopy, USER)
            if (BOT == X and val == -1) or (BOT == O and val == 1):
                win_moves.append(idx)
            elif val == 0:
                draw_moves.append(idx)
            elif (BOT == X and val == 1) or (BOT == O and val == -1):
                lose_moves.append(idx)
        if win_moves:
            index = random.choice(win_moves)
        elif draw_moves:
            index = random.choice(draw_moves)
        else:
            index = random.choice(lose_moves)
        print(f"ボットの手: {index}")

    board[index] = current_player
    print(f" {board[0]} │ {board[1]} │ {board[2]} ")
    print("───┼───┼───")
    print(f" {board[3]} │ {board[4]} │ {board[5]} ")
    print("───┼───┼───")
    print(f" {board[6]} │ {board[7]} │ {board[8]} ")
    if result(board, current_player) in (-1, 1):
        print(f"勝者: {current_player}")
        break
    current_player = O if current_player == X else X
else:
    print("引き分け")