Puzzle DE Programming

問題の説明

三目並べは、皆さんお馴染みの二人で対戦するゲームです。ひとりが○側でもうひとりが×側を受け持ち、3 行 3 列のマス目に○×を書いて、3 つ並べた方が勝ちというゲームです。

 ┌─┬─┬─┐ 
 │×│○│○│ 
 ├─┼─┼─┤ 
 │○│○│×│ 
 ├─┼─┼─┤ 
 │×│×│○│ 
 └─┴─┴─┘ 

 図 : 三目並べ

上図は○側が先手で引き分けになった例です。三目並べは、両者が最善を尽くすと引き分けになることが知られています。本当に引き分けになるのか、プログラムを作って確かめてみましょう。

三目並べは簡単なゲームなので、ゲーム終了まで読み切ることができます。局面の状態は○側の勝ち、×側の勝ち、引き分けの 3 通りしかありません。あとはミニマックス法により最善手を選択させ、その結果を求めればいいわけです。ミニマックス法は拙作のページ Alogorithms with Python: 「ミニマックス法」で説明しています。よろしければお読みくださいませ。

とりあえず、プログラムでは指し手を保存しないで、評価値の結果だけを出力することにします。初手をどこに選んでも、引き分けの評価値が出力されるはずです。

●プログラムの作成

それではプログラムを作りましょう。使用するプログラミング言語は Python3 (ver 3.8.10) です。最初に大域変数を定義します。

 ┌─┬─┬─┐ 
 │０│１│２│ 
 ├─┼─┼─┤ 
 │３│４│５│ 
 ├─┼─┼─┤ 
 │６│７│８│ 
 └─┴─┴─┘ 

 図 : 盤面の番号

リスト : 大域変数の定義

S = 0  # 空き場所
M = 1  # マル
B = 2  # バツ

SIZE = 9
DRAW = 0
M_WIN = 1
B_WIN = -1
MAX_V = 2
MIN_V = -2

# 直線
lines = (
    (0, 1, 2), (3, 4, 5), (6, 7, 8),
    (0, 3, 6), (1, 4, 7), (2, 5, 8),
    (0, 4, 8), (2, 4, 6)
)

盤面は一次元配列 (Python のリスト) で表します。盤面の位置と配列の添字の対応は、上図のように定義します。すると、駒が 3 つ並ぶ直線はタプル lines で表すことができます。勝敗を判定するプログラムは、lines を使えば簡単にプログラムできます。

リスト : 勝敗の判定

def game_over(b):
    for i, j, k in lines:
        if b[i] != S and b[i] == b[j] == b[k]:
            return M_WIN if b[i] == M else B_WIN
    return DRAW

関数 game_over() は 8 本の直線を調べ、同じ駒が 3 つ並んでいないか調べます。直線の最初の位置に M か B があり、残り 2 つの場所に同じ駒があれば 3 つ並んでいることがわかります。M が 3 つ並んでいれば評価値 M_WIN (1) を、B であれば B_WIN (-1) を返します。M も B も 3 つ並んでいなければ、DRAW (0) を返します。

ミニマックス法を使う場合、局面の評価値が必要になります。局面から評価値を計算する関数を「評価関数」といいます。評価関数は、先手が有利 (後手が不利) な局面ほど大きな値 (正の値)、逆に後手が有利 (先手が不利) なほど小さな値 (負の値)、互角の場合は 0 になるように作るのが一般的です。三目並べの場合、ゲーム終了まで読み切ることができるので、評価値は、勝ち、負け、引き分けの 3 つでいいわけです。

次は、先手 (○) の指し手を決める think_maru を作ります。プログラムは次のようになります。

リスト : 先手の指し手

def think_maru(b, n):
    if n >= SIZE: return DRAW
    value = MIN_V
    for i in range(SIZE):
        if b[i] != S: continue
        b[i] = M
        v = game_over(b)
        if v == DRAW:
            v = think_batu(b, n + 1)
        if v > value: value = v
        b[i] = S
    return value

関数 think_maru() は先手が有利になる指し手、つまり、評価値が大きい手を選べばいいわけです。引数 b は盤面、n は手数を表します。n が SIZE (9) 以上の場合、駒を置く場所がなくなったので DRAW を返します。選んだ指し手の評価値は変数 value にセットします。value は MIN_V で初期化します。MIN_V は B_WIN よりも小さな値にします。この値はまだ指し手を選んでいないことを表します。

次に、盤面 b を調べて空き場所に M を書き込みます。そして、game_over() を呼び出して勝敗の判定を行います。評価値 v が DRAW の場合、ゲームは終了していません。関数 think_batu() を呼び出して手番を相手に移します。

ミニマックス法による指し手の決定は簡単です。先手は評価値が大きい手を選べばいいのですから、v が value よりも大きな値であれば、それを指し手として選びます。value は MIN_V に初期化されているので、最初に調べた指し手は必ず選ばれることになります。そして、盤面 b を元の値に戻して、次の指し手を調べます。最後に、選んだ指し手の評価値 value を返します。

次は、後手 (×) の指し手を決める関数 think_batu() を作ります。プログラムは次のようになります。

リスト : 後手の指し手

def think_batu(b, n):
    if n >= SIZE: return DRAW
    value = MAX_V
    for i in range(SIZE):
        if b[i] != S: continue
        b[i] = B
        v = game_over(b)
        if v == DRAW:
            v = think_maru(b, n + 1)
        if v < value: value = v
        b[i] = S
    return value

think_batu() は think_maru() とは逆に後手が有利になる指し手 (評価値が小さな手) を選びます。変数 value は M_WIN よりも大きな値 MAX_V に初期化しておきます。ミニマックス法では、v が value よりも小さければ、その指し手を選べばいいわけです。ミニマックス法のプログラムはこれだけです。

最後にメインルーチンを作ります。

リスト : メインルーチン

def solver():
    b = [S] * SIZE
    for i in range(SIZE):
        b[i] = M
        v = think_batu(b, 1)
        print(f'初手 {i}: 評価値 {v}')
        b[i] = S

最初に盤面 b を S (0) に初期化します。そして、初手を指してから、think_batu() を呼び出して手番を相手に移します。この返り値が勝敗の結果を表しているので、それを出力するだけです。

●実行結果

それでは実行結果を示しましょう。

初手 0: 評価値 0
初手 1: 評価値 0
初手 2: 評価値 0
初手 3: 評価値 0
初手 4: 評価値 0
初手 5: 評価値 0
初手 6: 評価値 0
初手 7: 評価値 0
初手 8: 評価値 0

初手がどこでも、結果は引き分けとなりました。これで、両者が最善を尽くすと引き分けになることが確かめられました。

それでは、ルールを「3 つ並べた方が負け」に変更すると、結果はどうなるでしょうか。プログラムは簡単に改造できます。game_over() では、M が 3 つ並んでいたら M_WIN を出力していましたが、これを B_WIN に変更します。逆に、B が 3 つ並んでいたら M_WIN を出力します。ようするに、勝敗の判定を逆にするだけです。

このルールでは先手が不利なように思いますが、それでも引き分けになるのでしょうか。さっそく実行してみましょう。

初手 0: 評価値 -1
初手 1: 評価値 -1
初手 2: 評価値 -1
初手 3: 評価値 -1
初手 4: 評価値 0
初手 5: 評価値 -1
初手 6: 評価値 -1
初手 7: 評価値 -1
初手 8: 評価値 -1

初手が中央の場合のみ引き分けで、あとは後手の勝ちとなりました。後手必勝にはなりませんでしたね。興味のある方は、実際にプレイして確かめてみてください。また、今回のプログラムは評価値を出力するだけでしたが、指し手を表示するように改造してみるのも面白いと思います。

●プログラムリスト

#
# tictactoe.py : 三目並べ
#
#                Copyright (C) 2022 Makoto Hiroi
#

# 定数
S = 0  # 空き場所
M = 1  # マル
B = 2  # バツ

SIZE = 9
DRAW = 0
M_WIN = 1
B_WIN = -1
MAX_V = 2
MIN_V = -2

# 盤面
# 0 1 2
# 3 4 5
# 6 7 8

# 直線
lines = (
    (0, 1, 2), (3, 4, 5), (6, 7, 8),
    (0, 3, 6), (1, 4, 7), (2, 5, 8),
    (0, 4, 8), (2, 4, 6)
)

# 勝敗の判定
def game_over(b):
    for i, j, k in lines:
        if b[i] != S and b[i] == b[j] == b[k]:
            return M_WIN if b[i] == M else B_WIN
            # return B_WIN if b[i] == M else M_WIN
    return DRAW

# 先手
def think_maru(b, n):
    if n >= SIZE: return DRAW
    value = MIN_V
    for i in range(SIZE):
        if b[i] != S: continue
        b[i] = M
        v = game_over(b)
        if v == DRAW:
            v = think_batu(b, n + 1)
        if v > value: value = v
        b[i] = S
    return value

# 後手
def think_batu(b, n):
    if n >= SIZE: return DRAW
    value = MAX_V
    for i in range(SIZE):
        if b[i] != S: continue
        b[i] = B
        v = game_over(b)
        if v == DRAW:
            v = think_maru(b, n + 1)
        if v < value: value = v
        b[i] = S
    return value

# メインルーチン
def solver():
    b = [S] * SIZE
    for i in range(SIZE):
        b[i] = M
        v = think_batu(b, 1)
        print(f'初手 {i}: 評価値 {v}')
        b[i] = S