ゲームの説明
今回はパズルではありませんが、簡単な思考ゲームを作ってみましょう。8 行 8 列の盤面に配置された数字を取り合って、合計点が多い方が勝ちというゲームです。名前はたしか MiniMax だったと思いますが、ちょっと記憶があやふやです。
ルールは簡単です。盤面には 1 から 9 までの数字と + と - の符号がランダムに配置されています。最初、先手は 0 行目の中から数字を選びます。次の図を見てください。
盤面の行と列は、プログラムに合わせて 0 から数えることにします。先手は 0 行 3 列目 (0, 3) の 6 を選びました。後手が数字を選ぶ場合、相手が選んだ数字と同じ列の中から選ばなければいけません。この場合は 3 列目から選ぶことになります。つまり、先手は相手が選んだ数字と同じ行から、後手は同じ列から数字を選ぶのです。あとはこれを交互に繰り返します。
そして、行または列の数字が無くなったらゲーム終了です。次の図を見てください。
先手が 7 : 2 で勝っている状況です。ここで、5 行目から数字を選びますが、1 列目の 4 を選ぶと、その列には数字が 3 のひとつしか残りませんね。したがって、後手は 3 を選ぶしかなく、ここでゲームが終了します。11 : 5 で先手の勝ちとなります。
このゲームは単純なので、思考ルーチンも簡単に作ることができます。思考ルーチンの基本アルゴリズム「ミニマックス法」を使って数手先読みするだけで、ほとんどの人は勝てなくなるでしょう。ミニマックス法については拙作のページ Algorithms with Python (ver 3.0) ミニマックス法 をお読みください。
なお、MiniMax の Tcl/Tk バージョン も用意しています。Tcl/Tk に興味のある方は遊んでみてください。
●プログラムの作成
それではプログラムを作りましょう。とりあえず、同じ思考ルーチン同士で対戦させて、探索レベルによって局面を評価する回数がどのくらい増えるのか確かめてみます。使用するプログラミング言語は Python3 (PyPy3) です。
最初に盤面を表すデータ構造を定義します。リバーシなどのボードゲームの場合、一次元配列を使って盤面を表した方が便利なのですが、今回は簡単に二次元配列を使います。思考ルーチンで先読みするとき盤面を直接書き換え、バックトラックしたときは前の盤面に戻すことにします。このほかに、先読みするとき盤面をコピーする方法もあります。
盤面を初期化する関数 init_board() は次のようになります。
リスト : 盤面の初期化
def init_board():
def select_number():
n = random.randint(-9, 9)
if n == 0:
n = random.randint(1, 9)
return n
return [[select_number() for _ in range(SIZE)] for _ in range(SIZE)]
局所関数 select_number() で 0 を除く -9 から 9 までの数値を選びます。randint(s, e) は s 以上 e 以下の乱数 (整数) を発生します。0 の場合は 1 から 9 までの数値を選び直します。
次はゲームの終了を判定する関数 gameover() を作ります。
リスト : 終了判定
def gameover(board, x, y):
c1, c2 = True, True
for i in range(SIZE):
if board[x][i] != NON_VAL: c1 = False
if board[i][y] != NON_VAL: c2 = False
return c1 or c2
ゲーム終了の判定は簡単です。取った数字の位置の行と列をチェックするだけです。NON_VAL (999) は数字が無いことを表す値です。行と列のどちらかがすべて NON_VAL であればゲーム終了です。
次は盤面を評価する関数 value_func() を作ります。
リスト : 評価関数
def value_func(fval, sval, final = False):
global count
count += 1
if final:
if fval > sval:
m = WIN_FST
elif fval < sval:
m = WIN_SND
else:
m = 0
else:
m = fval - sval
return m
引数 fval は先手の点数、sval は後手の点数、final が True のときはゲーム終了時の評価値を返します。通常は fval - sval が評価値になります。とても単純な評価関数ですが、これでもミニマックス法は十分に機能します。大域変数 count は評価回数をカウントするために使います。
ゲーム終了の場合、先手が勝ちの場合は WIN_FST を返し、後手が勝ちの場合は WIN_SND を返します。WIN_FST は MAX_VAL (999) より小さな値、WIN_SND は MIN_VAL (-999) より大きな値に設定します。今回は 500 と -500 にしました。
通常の評価値 fval - sval を返してもミニマックス法は機能しますが、そうすると勝負がついていない局面の評価値の方を選択する場合があり、ズルズルとゲームが続いてしまうのです。特別な値を返すことにより、ミニマックス法の中で勝敗がつく指し手を選ぶことができます。
●ゲーム木の探索
次は、指し手を選ぶ処理を作りましょう。先手の指し手を選ぶ関数を move_first() とし、後手の指し手を選ぶ関数を move_second() とします。これらの関数はゲームの木を深さ優先で探索して、ミニマックス法で指し手を選びます。move_first() は次のようになります。
リスト : 先手の指し手を選択
def move_first(depth, board, prev, fval, sval):
if depth == 0:
return value_func(fval, sval), -1
value = MIN_VAL
m = -1
for x in range(SIZE):
if board[prev][x] == NON_VAL: continue
num = board[prev][x]
board[prev][x] = NON_VAL
if gameover(board, prev, x):
v = value_func(fval, sval, True)
else:
v, _ = move_second(depth - 1, board, x, fval + num, sval)
board[prev][x] = num
# ミニマックス法
if v > value:
value = v
m = x
return value, m
引数 depth はゲーム木の探索レベル、board が盤面、prev は 1 手前に選んだ数字の行、fval が先手の点数、sval が後手の点数を表します。depth が 0 になったら先読みは終了です。value_func() を呼び出して局面を評価します。move_first() は評価値と指し手を返します。
そうでなければ、盤面から数字を選びます。数字を取り除いた場所には NON_VAL が格納されているので、それ以外の場所から数字を取り出します。このとき、盤面を元に戻すため、取り出した数字を変数 num に保存しておきます。
盤面の値を NON_VAL に書き換えたら、gameover() を呼び出してゲームの終了を判定します。ゲーム終了であれば value_func() を呼び出して、終了時の評価値を求めます。そうでなければ、move_second() を呼び出して手番を後手に移します。どちらの場合も評価値は変数 v にセットします。
次の処理がミニマックス法の心臓部です。先手は評価値の大きい方が有利なわけですから、いちばん大きな評価値 (マックス) の指し手を選びます。選んだ指し手は変数 m に格納し、その評価値は value に格納しておきます。評価値 v が value よりも大きい値であれば、その指し手を選べばいいわけです。まだ指し手を選んでいない場合、value は一番小さな評価値 MIN_VAL (-999) に初期化されているので、最初に調べた指し手が必ず選択されます。
あとは、すべての指し手を調べるだけです。それから、次の指し手を調べる前に、盤面の状態を元に戻すことをお忘れなく。後手側の選択処理ならば、逆にいちばん小さな評価値 (ミニマム) の指し手を選択すればいいのです。ミニマックス法の処理はたったこれだけです。とても簡単ですね。
●ゲームの進行
あとはゲームを進める処理を作るだけです。プログラムは次のようになります。
リスト : ゲームの進行
def play(first_depth, second_depth, verbos = True):
global count
count = 0
b = init_board()
fval, sval = 0, 0
if verbos: print_board(b, fval, sval)
prev = 0
move = 1
while True:
if move % 2 != 0:
# 先手
_, m = move_first(first_depth, b, prev, fval, sval)
num = b[prev][m]
fval += num
b[prev][m] = NON_VAL
if verbos: print(f'\n{move}: 先手 ({prev}, {m}) の {num} をゲット\n')
if gameover(b, prev, m): break
else:
# 後手
_, m = move_second(second_depth, b, prev, fval, sval)
num = b[m][prev]
sval += num
b[m][prev] = NON_VAL
if verbos: print(f'\n{move}: 後手 ({m}, {prev}) の {num} をゲット\n')
if gameover(b, m, prev): break
if verbos: print_board(b, fval, sval)
prev = m
move += 1
#
if verbos:
print('Game Over')
print_board(b, fval, sval)
print(count)
if fval > sval:
print('先手の勝ちです')
elif fval < sval:
print('後手の勝ちです')
else:
print('引き分けです')
return fval - sval, count
引数 first_depth が先手の探索レベル、second_depth が後手の探索レベル、verbos が真のときはゲームの実況を表示します。init_board() で盤面を生成して、変数 b にセットします。変数 fval と sval は先手と後手の点数です。変数 prev は 1 手前に選んだ数字の行 (または列) です。0 に初期化するので、先手は 0 行目から選ぶことになります。move は手数を表します。move が奇数のときは先手番、偶数のときは後手番になります。
先手番であれば move_first() を呼び出して、指し手を変数 m にセットします。選ぶ数字の位置は (prev, m) になります。数字を取得したら、gameover() を呼び出してゲームの終了を判定します。ゲーム終了ならば break で while ループを脱出します。そうでなければ、prev を m に書き換えて、move を +1 します。これで手番を変えることができます。最後にゲームの結果を表示します。
あとのプログラムは簡単なので説明は割愛させていただきます。詳細は プログラムリスト をお読みくださいませ。
●実行結果
それでは実際に試してみましょう。ゲーム実況の一部を示します。
>>>> play(2, 2)
先手 0 点, 後手 0 点
-5 +4 +4 -3 -2 +9 -5 +8
-4 -8 -5 +7 +6 +1 -5 -9
+9 -3 +9 +8 -8 -5 -1 +9
-1 +6 +5 -7 +4 -7 -7 +7
-8 +7 -1 -9 +2 +7 +9 -5
+1 +5 -8 +8 +2 -7 +7 -9
-6 -7 +6 +9 +3 +6 -8 -1
-3 -8 -7 -9 +6 -7 -5 +9
1: 先手 (0, 5) の 9 をゲット
先手 9 点, 後手 0 点
-5 +4 +4 -3 -2 ** -5 +8
-4 -8 -5 +7 +6 +1 -5 -9
+9 -3 +9 +8 -8 -5 -1 +9
-1 +6 +5 -7 +4 -7 -7 +7
-8 +7 -1 -9 +2 +7 +9 -5
+1 +5 -8 +8 +2 -7 +7 -9
-6 -7 +6 +9 +3 +6 -8 -1
-3 -8 -7 -9 +6 -7 -5 +9
2: 後手 (4, 5) の 7 をゲット
先手 9 点, 後手 7 点
-5 +4 +4 -3 -2 ** -5 +8
-4 -8 -5 +7 +6 +1 -5 -9
+9 -3 +9 +8 -8 -5 -1 +9
-1 +6 +5 -7 +4 -7 -7 +7
-8 +7 -1 -9 +2 ** +9 -5
+1 +5 -8 +8 +2 -7 +7 -9
-6 -7 +6 +9 +3 +6 -8 -1
-3 -8 -7 -9 +6 -7 -5 +9
・・・省略・・・
先手 69 点, 後手 57 点
-5 ** ** -3 ** ** -5 **
-4 -8 -5 +7 ** ** -5 -9
+9 -3 +9 +8 -8 -5 -1 +9
-1 ** +5 -7 ** -7 -7 +7
-8 ** -1 -9 ** ** ** -5
+1 ** -8 ** ** -7 ** -9
-6 -7 ** ** ** ** -8 -1
-3 -8 -7 -9 ** -7 -5 **
24: 後手 (2, 4) の -8 をゲット
Game Over
先手 69 点, 後手 49 点
-5 ** ** -3 ** ** -5 **
-4 -8 -5 +7 ** ** -5 -9
+9 -3 +9 +8 ** -5 -1 +9
-1 ** +5 -7 ** -7 -7 +7
-8 ** -1 -9 ** ** ** -5
+1 ** -8 ** ** -7 ** -9
-6 -7 ** ** ** ** -8 -1
-3 -8 -7 -9 ** -7 -5 **
857
先手の勝ちです
(20, 857)
どちらもレベル 2 で対戦したところ、24 手で先手の勝ちになりました。乱数で盤面を生成しているので、実行するたびに勝敗は変わると思います。そこで、レベル 2 から 5 の組み合わせで、100 回ずつ対戦させてみました。
リスト : 簡単なテスト
def test(n, fd, sd):
fwin = swin = draw = 0
cnt = 0
for _ in range(n):
v, c = play(fd, sd, False)
if v > 0: fwin += 1
elif v < 0: swin += 1
else: draw += 1
cnt += c
print(f'先手 {fwin} 勝, 後手 {swin} 勝, {draw} 分け')
print(f'平均評価回数 {cnt // n}')
def test1(s, e):
random.seed(0)
for x in range(s, e):
for y in range(s, e):
print('----', x, y, '----')
test(100, x, y)
test1() を実行するとき、乱数のシードを 0 に設定するので、同じ乱数列が生成されます。test1() を実行したときの結果は同じになることに注意してください。結果は次のようになりました。
表 : 勝敗と評価回数
先 手
: 2 : 3 : 4 : 5
------+-----------+-----------+-----------+-----------
2 : 63, 33, 2 : 84, 16, 0 : 91, 8, 1 : 90, 10, 0
: 1009 : 3420 : 17829 : 101983
:
後 3 : 45, 55, 0 : 73, 25, 2 : 78, 21, 1 : 77, 22, 1
: 3512 : 6201 : 21278 : 109437
:
4 : 33, 67, 0 : 49, 49, 2 : 70, 29, 1 : 79, 20, 1
手 : 17373 : 20281 : 34851 : 122856
:
5 : 31, 68, 1 : 56, 43, 1 : 61, 37, 2 : 66, 32, 2
: 96798 : 99393 : 114155 : 201120
上段 : 先手勝, 後手勝, 引き分け
下段 : 平均評価回数
探索レベルを上げると平均評価回数が増えることがわかります。単純なミニマックス法なので、これ以上レベルを上げると時間がかかるようになります。アルファベータ法を使って枝刈りを行うと、もう少しレベルを上げることができると思います。これは次回に試してみましょう。
同じレベル同士の対戦は先手が勝ち越しているので、このゲームは先手が有利なのかもしれませんね。後手が勝ち越したのは (2, 3), (2, 4), (2, 5) の 3 つ、引き分けが (3, 4) の 1 つだけなので、レベルの差が 2 つくらいありそうです。それでも、後手のレベルを上げると勝ち数は増えるので、ミニマックス法は機能しているようです。興味のある方はいろいろ試してみてください。
●プログラムリスト
#
# minimax.py : 数字を取り合うゲーム
#
# Copyright (C) 2022 Makoto Hiroi
#
import random
# 定数
SIZE = 8
NON_VAL = 999
MAX_VAL = 999
MIN_VAL = -999
WIN_FST = 500
WIN_SND = -500
# 盤面の初期化
def init_board():
def select_number():
n = random.randint(-9, 9)
if n == 0:
n = random.randint(1, 9)
return n
return [[select_number() for _ in range(SIZE)] for _ in range(SIZE)]
# 盤面の表示
def print_board(b, fval, sval):
print(f'先手 {fval} 点, 後手 {sval} 点')
for xs in b:
for x in xs:
if x == NON_VAL:
print('**', end=' ')
else:
print('{:+d}'.format(x), end=' ')
print()
# 終了判定
def gameover(board, x, y):
c1, c2 = True, True
for i in range(SIZE):
if board[x][i] != NON_VAL: c1 = False
if board[i][y] != NON_VAL: c2 = False
return c1 or c2
# 評価関数
def value_func(fval, sval, final = False):
global count
count += 1
if final:
if fval > sval:
m = WIN_FST
elif fval < sval:
m = WIN_SND
else:
m = 0
else:
m = fval - sval
return m
# 先手の指し手
def move_first(depth, board, prev, fval, sval):
if depth == 0:
return value_func(fval, sval), -1
value = MIN_VAL
m = -1
for x in range(SIZE):
if board[prev][x] == NON_VAL: continue
num = board[prev][x]
board[prev][x] = NON_VAL
if gameover(board, prev, x):
v = value_func(fval, sval, True)
else:
v, _ = move_second(depth - 1, board, x, fval + num, sval)
board[prev][x] = num
# ミニマックス法
if v > value:
value = v
m = x
return value, m
# 後手の指し手
def move_second(depth, board, prev, fval, sval):
if depth == 0:
return value_func(fval, sval), -1
value = MAX_VAL
m = -1
for x in range(SIZE):
if board[x][prev] == NON_VAL: continue
num = board[x][prev]
board[x][prev] = NON_VAL
if gameover(board, x, prev):
v = value_func(fval, sval, True)
else:
v, _ = move_first(depth - 1, board, x, fval, sval + num)
board[x][prev] = num
# ミニマックス法
if v < value:
value = v
m = x
return value, m
# ゲームの実行
def play(first_depth, second_depth, verbos = True):
global count
count = 0
b = init_board()
fval, sval = 0, 0
if verbos: print_board(b, fval, sval)
prev = 0
move = 1
while True:
if move % 2 != 0:
# 先手
_, m = move_first(first_depth, b, prev, fval, sval)
num = b[prev][m]
fval += num
b[prev][m] = NON_VAL
if verbos: print(f'\n{move}: 先手 ({prev}, {m}) の {num} をゲット\n')
if gameover(b, prev, m): break
else:
# 後手
_, m = move_second(second_depth, b, prev, fval, sval)
num = b[m][prev]
sval += num
b[m][prev] = NON_VAL
if verbos: print(f'\n{move}: 後手 ({m}, {prev}) の {num} をゲット\n')
if gameover(b, m, prev): break
if verbos: print_board(b, fval, sval)
prev = m
move += 1
#
if verbos:
print('Game Over')
print_board(b, fval, sval)
print(count)
if fval > sval:
print('先手の勝ちです')
elif fval < sval:
print('後手の勝ちです')
else:
print('引き分けです')
return fval - sval, count
# テスト
def test(n, fd, sd):
fwin = swin = draw = 0
cnt = 0
for _ in range(n):
v, c = play(fd, sd, False)
if v > 0: fwin += 1
elif v < 0: swin += 1
else: draw += 1
cnt += c
print(f'先手 {fwin} 勝, 後手 {swin} 勝, {draw} 分け')
print(f'平均評価回数 {cnt // n}')
def test1(s, e):
random.seed(0)
for x in range(s, e):
for y in range(s, e):
print('----', x, y, '----')
test(100, x, y)
改訂 2022 年 11 月 27 日