３目並べ（ミニマックス法）

３目並べ（ミニマックス法）

前回は３目並べをランダムでプレイするコードを実装しました。

今回はミニマックス法を使って３目並べをプレイしてみます。

ミニマックス法は相手が自分にとって最も不利になる手を指すと仮定して、最善の手を探す方法です。

解き方・ソースコード

相手が手番の場合は選択できる手の中から最も評価値の高い手を選び、自分が手番の場合は選択できる手の中から最も評価値の低い手を選びます。

ゲームの評価値としては、勝てば $ 1 $ ポイント、負ければ $ -1 $ ポイント、引き分けであれば $ 0 $ ポイントとします。（minmax関数）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
goal = [0b111000000, 0b000111000, 0b000000111,  # 横に３つ並んだケース
        0b100100100, 0b010010010, 0b001001001,  # 縦に３つ並んだケース
        0b100010001, 0b001010100]               # 斜めに３つ並んでケース

# ３つが並んだか判定
def check(player):
    for mask in goal:
        if player & mask == mask:
            return True
    return False

# ミニマックス法
def minmax(p1, p2, turn):
    if check(p2):
        if turn:        # 自分の手番のときは勝ち
            return 1
        else:
            return -1   # 相手の手番のときは負け
    
    board = p1 | p2
    if board == 0b111111111:    # すべて置いたら引き分けで終了
        return 0
    
    w = [i for i in range(9) if (board & (1 << i)) == 0]

    if turn:    # 自分の手番の時は最小値を選ぶ
        return min([minmax(p2, p1 | (1 << i), not turn) for i in w])
    else:       # 相手の手番の時は最大値を選ぶ
        return max([minmax(p2, p1 | (1 << i), not turn) for i in w])

# 交互に置く
def play(p1, p2, turn):
    if check(p2):   # ３つ並んでいたら出力して終了
        print('勝負あり')
        print([bin(p1), bin(p2)])
        return

    board = p1 | p2
    if board == 0b111111111:    # すべて置いたら引き分けで終了
        print('引き分け')
        print([bin(p1), bin(p2)])
        return
    
    # 置ける場所を探す
    w = [i for i in range(9) if (board & (1 << i)) == 0]
    # 各場所に置いたときの評価値を調べる
    r = [minmax(p2, p1 | (1 << i), True) for i in w]
    print('選択可能なマス目', w)
    print('マス目の評価値', r)

    # 評価値が一番高いマス目を取得する
    j = w[r.index(max(r))]
    print('選択するマス目', j)
    print('----------------------------')
    play(p2, p1 | (1 << j), not turn) # 手番を入れ替えて次を探す

play(0, 0, True)      # プレイ開始

[実行結果]

選択可能なマス目 [0, 1, 2, 3, 4, 5, 6, 7, 8]
マス目の評価値 [0, 0, 0, 0, 0, 0, 0, 0, 0]
選択するマス目 0
----------------------------
選択可能なマス目 [1, 2, 3, 4, 5, 6, 7, 8]
マス目の評価値 [-1, -1, -1, 0, -1, -1, -1, -1]
選択するマス目 4
----------------------------
選択可能なマス目 [1, 2, 3, 5, 6, 7, 8]
マス目の評価値 [0, 0, 0, 0, 0, 0, 0]
選択するマス目 1
----------------------------
選択可能なマス目 [2, 3, 5, 6, 7, 8]
マス目の評価値 [0, -1, -1, -1, -1, -1]
選択するマス目 2
----------------------------
選択可能なマス目 [3, 5, 6, 7, 8]
マス目の評価値 [-1, -1, 0, -1, -1]
選択するマス目 6
----------------------------
選択可能なマス目 [3, 5, 7, 8]
マス目の評価値 [0, -1, -1, -1]
選択するマス目 3
----------------------------
選択可能なマス目 [5, 7, 8]
マス目の評価値 [0, -1, -1]
選択するマス目 5
----------------------------
選択可能なマス目 [7, 8]
マス目の評価値 [0, 0]
選択するマス目 7
----------------------------
選択可能なマス目 [8]
マス目の評価値 [0]
選択するマス目 8
----------------------------
引き分け
['0b10011100', '0b101100011']

結果は引き分けとなりました。

３目並べでは両者が最善の手を選べば、確実に引き分けになります。