Pythonでマルバツゲームをつくろう #6 枝刈り編

前回：

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

• 今回は、前回のボットをさらに効率的にしましょう。

マルバツゲームを枝刈りで効率的にしよう

• 前回のマルバツゲームのminimaxボットは、その盤面から派生しうる全ての盤面を探索していました。
• 例えば、以下の盤面A(○の番)の値を知りたい場合は、全ての子局面の値を調べ、そのうち最も高い値を盤面Aの値としていました。

• でも考えてみれば、+1の子局面(×の番なら-1の子局面)が一つでも見つかれば、別に全部の子局面を調べなくても良いと思いませんか？

• このように、不要な探索を打ち切ることを枝刈りと言います。
• それでは、枝刈りをしたボットをコーディングしていきましょう。

minimax関数の変更

• minimax関数は
  (1)終局盤面を受け取った場合の処理と、
  (2)進行中盤面を受け取った場合の処理と
  に分かれていました。今回変更点があるのは後者の処理のみです。
• 元々はこのようになっていました。○の番の進行中盤面を受け取った時の処理部分です。

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

• これを、下のように変えます。

if player == O:
    max_val = -1
    moves = legal_moves(board)  # ⭐️
    random.shuffle(moves)       # ⭐️
    for index in moves:         # ⭐️
        boardcopy = board.copy()
        boardcopy[index] = O
        val = minimax(boardcopy, X)
        if val > max_val:
            max_val = val
            if max_val == 1:    # 🌙
                return max_val  # 🌙
    return max_val

• # ⭐️、# 🌙 となっている部分が変更・追加された部分です。
• まず、最初の⭐️の部分では、次打てる手のリストをシャッフルしています。一番上の図で言うと、5つの子局面のうち、左から順番に調べていくのではなく、ランダムな順番で調べるということです。そうしないと、毎回一番左の手が選ばれてしまうようになります。
• 二つ目の🌙では、+1の子局面が見つかり次第探索を打ち切り、それを値として返しています。
• ×の進行中盤面を受け取った場合の処理も同じように変更します。

else:
    min_val = 1
    moves = legal_moves(board)  # ⭐️
    random.shuffle(moves)       # ⭐️
    for index in moves:         # ⭐️
        boardcopy = board.copy()
        boardcopy[index] = X
        val = minimax(boardcopy, O)
        if val > min_val:
            min_val = val
            if min_val == -1:   # 🌙
                return min_val  # 🌙
    return min_val

ボットが手を選ぶ部分の変更

• ボットがminimax関数を使って手を選ぶ部分も変更します。元はこのようになっていました。

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}")

• これを以下のように変えます。

else:
    print("ボット考え中...")
    clear_output(wait=True)
    time.sleep(2)
    win_moves = []
    draw_moves = []
    lose_moves = []
    moves = legal_moves(board)  # ⭐️
    random.shuffle(moves)       # ⭐️
    for idx in moves:           # ⭐️
        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)
            break               # 🌙
        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}")

• ⭐️では、上と同様、インデックス順に探索するのではなくランダムに盤面を探索するようにしています。
• 🌙でもやはり上と同様に、勝てる盤面(○なら+1、×なら-1)が見つかり次第すぐに探索を打ち切っています。

完成！

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:
            return "○ win"
        else:
            return "× win"
    elif not legal_moves(board):
        return "draw"

# 盤面とプレイヤを受け取ると、その盤面からプレイヤが受け取れる最も良い値を返す関数。○勝ち：１、引き分け：０、×勝ち：−１とする
# 具体的には：①もし終局盤面なら、その結果を返す
#           ②そうではなくもしゲーム進行中の盤面なら、子局面達のうち最も良い結果を返す
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
        moves = legal_moves(board)
        random.shuffle(moves)
        for index in moves:
            boardcopy = board.copy()
            boardcopy[index] = O
            val = minimax(boardcopy, X)
            if val > max_val:
                max_val = val
                if max_val == 1:
                    return max_val
        return max_val
    else:
        min_val = 1
        moves = legal_moves(board)
        random.shuffle(moves)
        for index in moves:
            boardcopy = board.copy()
            boardcopy[index] = X
            val = minimax(boardcopy, O)
            if val < min_val:
                min_val = val
                if min_val == -1:
                    return min_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 = []
        moves = legal_moves(board)
        random.shuffle(moves)
        for idx in moves:
            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)
                break
            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("引き分け")