Pythonでリバーシ(オセロ)をつくろう

  • 2021年11月28日
  • 2022年2月9日
  • Python
  • 1367view

Pythonでリバーシ(オセロ)を制作します。この本では警をクリックして石を打ち、相手の石を挟んでひくり返す処理を組み込み、ゲームとし一通り遊べるようにします。

コンピュータを強くする思考ルーチンを実装し、本格的なゲームとアルゴリズムの開発方法を学びます。

1、キャンバスに盤を描く

リバーシのルールを説明し、石を打つ盤を表示するところからプログラミングを始めていきます。

リバーシは、二人のプレイヤーが、盤に黒い石と白い石を交互に打ち、相手の石を挟んでひっくり返すボードゲームです。石の片面は黒、片面は白で、ひっくり返すと色が変わります。相手の石をひっくり返すと自分の石になります。

市販されているリバーシは、次のような盤を用いてプレイします。

ボードゲームのリバーシ

マスは88列のものが一般的です。本書でも8×8マスの盤でプレイするリバーシを制作します。

先手が黒い石、後手が白い石を打ちます。二人とも打てるマスがなくなったら終局(ゲーム終了)です。全てのマスが埋まらない状態で終局することもあります。

終局したら盤にある黒い石と白い石を数え、より多く置いた方の勝ちです。黒と白が同数

で引き分けになることもあります。

このゲームは一般的な呼び名としてリバーシと呼ばれますが、

オセロという名称で販売されているボードゲームが有名です。

オセロはその商品の発売元の登録商標です。

盤面を表示する

本書で制作するリバーシは、図形の描画命令で画面を構成して、画像ファイルは用いません。 ウィンドウにキャンバスを配置し、盤面を表示するところからプログラミングを始めます。ウィンドウを表示するのでtkinter を用います。

次のプログラムを入力して実行し、動作を確認しましょう。

list1.py

import tkinter
def banmen():
    for y in range(8):
        for x in range(8):
            X = x*80
            Y = y*80
            cvs.create_rectangle(X, Y, X+80, Y+80, outline="black")
root = tkinter.Tk()
root.title("リバーシ")
root.resizable(False, False)
cvs = tkinter.Canvas(width=640, height=700, bg="green")
cvs.pack()
banmen()
root.mainloop() 
Python

コードの意味

tkinterモジュールをインポート
盤面を表示する関数
繰り返し yは0から7まで1ずつ増える
繰り返し xは0から7まで1ずつ増える
マス目のX座標
マス目のY座標
(X, Y)を左上角とした正方形を描く
ウィンドウのオブジェクトを準備
ウィンドウのタイトルを指定
ウィンドウサイズを変更できなくする
キャンバスの部品を用意
キャンバスをウィンドウに配置
banmen()関数を呼び出す
ウィンドウの処理を開始

解説

関数名は盤面のbanmen() としました。この関数で変数yxを用いた二重ループの繰り返しにより、ゲーム画面を描く関数を定義しています。関数名は盤面のローマ字でのように左上から右下に向かって8×8のマスを表示します。

マス目は矩形を描く create_rectangle()命令で表示しています。

0~16行目でウィンドウを作り、キャンバスを配置し、ウィンドウの処理を開始していす。

 6×6のリバーシは、全ての局面がコンピュータで解析されているそうです。8×8のリバーシの完全解析はまだ行われていないと聞いています。

2、リストで石を管理する

どこに何色の石があるかを二次元リストで管理します。ここではクリックしたマスに石を打つプログラムで、二次元リストによるデータ管理を確認します。

盤面の状態を二次元リストで管理

次のプログラムの動作を確認しましょう。何もないマスをクリックすると黒い石が置かれます。黒い石をクリックすると白い石になり、白い石をクリックすると何もないマスに戻ります。

list.2py

import tkinter
BLACK = 1
WHITE = 2
board = [
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 2, 1, 0, 0, 0],
 [0, 0, 0, 1, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]
]

def click(e):
    mx = int(e.x/80)
    my = int(e.y/80)
    if mx>7: mx = 7
    if my>7: my = 7
    if board[my][mx]==0:
        board[my][mx] = BLACK
    elif board[my][mx]==BLACK:
        board[my][mx] = WHITE
    elif board[my][mx]==WHITE:
        board[my][mx] = 0
    banmen()
def banmen():
    cvs.delete("all")
    for y in range(8):
        for x in range(8):
            X = x*80
            Y = y*80
            cvs.create_rectangle(X, Y, X+80, Y+80, outline="black")
            if board[y][x]==BLACK:
                cvs.create_oval(X+10, Y+10, X+70, Y+70, fill="black", width=0
            if board[y][x]==WHITE:
                cvs.create_oval(X+10, Y+10, X+70, Y+70, fill="white", width=0)

root = tkinter.Tk()

root.title("リバーシ")
root.resizable(False, False)
root.bind("<Button>", click)
cvs = tkinter.Canvas(width=640, height=700, bg="green")
cvs.pack()
banmen()
root.mainloop()

実行結果 

Python

コードの意味

tkinterモジュールをインポート
黒い石を管理するための定数
白い石を管理するための定数
一盤を管理するリスト
盤をクリックしたときに働く関数
ポインタのX座標を80で割りmxに代入
ポインタのY座標を80で割りmyに代入
mxが7を超えたら7にする
myが7を超えたら7にする
クリックしたマスに何もなければ
board[ my limx]をBLACKにして黒を置く
クリックしたマスが黒い石なら
board[my][mx]をWHITEにして白を置く
クリックしたマスが白い石なら
board[my][mx]を0にして石を消す
盤面を描く関数を呼び出す
盤面を表示する関数の定義
キャンバスに描いたものを全て削除
繰り返し yは0から7まで1ずつ増える
繰り返し xは0から7まで1ずつ増える
マス目のX座標
マス目のY座標
(X, Y)を左上角とした正方形を描く
board[y][x]の値がBLACKなら
黒い円を表示
board[y][x]の値がWHITEなら
白い円を表示
ウィンドウのオブジェクトを準備
ウィンドウのタイトルを指定
ウィンドウサイズを変更できなくする
クリック時に実行する関数を指定
キャンバスの部品を用意
キャンバスをウィンドウに配置
banmen()関数を呼び出す
ウィンドウの処理を開始

解説

黒い石と白い石を管理するための定数を、BLACK-1WHITE-2 と定めています。

盤面を管理する二次元リスト bord[][] を宣言しています。bord[][] の初期値として、盤の中央に黒い石と白い石を2つずつ置いています。

banmen()関数ので、board[][] の値がBLACK(1)ならそのマスに黒い石を描き、値がWHITE(2) なら白い石を描いています。石は円を描く create_oval()命令で表示しています。

ウィンドウ(盤面)をクリックしたときに働く click()関数を記述しています。

root.bind(“<Button>”, click) とし、マウスボタンを押したときに、この関数が呼び出されるようにしています。

click(e) の引数e に、 .x .yを付けたe.x e.y がマウスポインタの座標です。それらの値をマス目の大きさ(幅と高さのドット数)80で割った整数値を、変数mx my に代入しています。マス目は8×8なので、mx myの値が7より大きくならないようにif文を記述しています。

そして board[my][mx] 0なら、board[my][mx] BLACK の値を代入し、黒い石を置いています。board[my][mx] BLACKならばWHITE を代入して白い石にし、board[my][mx] WHITEならば0を代入して何もないマスに戻しています。

二次元リストの宣言について

このプログラムでは、二次元リストを次のように宣言しています。

board=[
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 2, 1, 0, 0, 0],
[0, 0, 0, 1, 2, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]
]

この書き方は二次元リストの構造が一目瞭然で、プログラミング初心者にお勧めできる記述の仕方です。

二次元リストはこの他に、空のリストを宣言し、for append() 命令で準備する方法があります。for append() で二次元リストを用意する方法も後に用います。

3、どのようなアルゴリズムでひっくり返すか

相手の石を挟んでひっくり返すアルゴリズム(黒い石を白に、白い石を黒にする処理)を組み込みます。

リバーシは相手の石を、縦、横、斜めに挟んだら、それらの石を全て裏返して自分の色にします。石をひっくり返すルールを、次の図の黄色のマスに黒い石を打つとして説明します。

ここから先は石を裏返し、黒い石を白に、白い石を黒にすることを返すと言うことにします。

全ての向きを調べる

左上と右上、左下、そして下方向を合わせ、全部で8つの向きがあります。プログラムで石を返すには、全方向に対して、相手の石があり、その先に自分の石があるかを調べます。そして相手の石が途切れることなく並んだ先に、自分の色の石がある場合、相手の石を返すようにプログラミングします。

動作の確認

この処理を組み込み、石を返すようにしたプログラムを確認します。次のプログラムは、左上角のマスと、中央右下のマスに黒い石を打つと、白い石が返されます。

list3.py

import tkinter
BLACK = 1
WHITE = 2
board = [
 [0, 2, 2, 2, 2, 2, 2, 1],
 [2, 2, 0, 0, 0, 0, 0, 0],
 [2, 0, 2, 0, 0, 1, 0, 0],
 [2, 0, 0, 1, 0, 2, 0, 0],
 [2, 0, 0, 0, 0, 2, 0, 0],
 [2, 0, 0, 1, 2, 0, 2, 1],
 [2, 0, 0, 0, 0, 2, 0, 0],
 [1, 0, 0, 0, 0, 1, 0, 0]
]

def click(e):
    mx = int(e.x/80)
    my = int(e.y/80)
    if mx>7: mx = 7
    if my>7: my = 7
    if board[my][mx]==0:
        ishi_utsu(mx, my, BLACK)
    banmen()
def banmen():
    cvs.delete("all")
    for y in range(8):
        for x in range(8):
            X = x*80
            Y = y*80
            cvs.create_rectangle(X, Y, X+80, Y+80, outline="black")
            if board[y][x]==BLACK:
                cvs.create_oval(X+10, Y+10, X+70, Y+70, fill="black", width=0)
            if board[y][x]==WHITE:
                cvs.create_oval(X+10, Y+10, X+70, Y+70, fill="white", width=0)
    cvs.update()

# 石を打ち、相手の石をひっくり返す
def ishi_utsu(x, y, iro):
    board[y][x] = iro
    for dy in range(-1, 2):
        for dx in range(-1, 2):
            k = 0
            sx = x
            sy = y
            while True:
                sx += dx
                sy += dy
                if sx<0 or sx>7 or sy<0 or sy>7:
                    break
                if board[sy][sx]==0:
                    break
                if board[sy][sx]==3-iro:
                    k += 1
                if board[sy][sx]==iro:
                    for i in range(k):
                        sx -= dx
                        sy -= dy
                        board[sy][sx] = iro
                    break
root = tkinter.Tk()
root.title("リバーシ")
root.resizable(False, False)
root.bind("<Button>", click)
cvs = tkinter.Canvas(width=640, height=700, bg="green")
cvs.pack()
banmen()
root.mainloop()

実行結果 

Python

コードの意味

tkinterモジュールをインポート
黒い石を管理するための定数
白い石を管理するための定数
盤を管理するリスト
盤をクリップしたときに働く関数
ポインタの製を80で割りmxに代入
ポインタのY座標を80で割りmyに代入
mxが7を超えたら7にする
myが7を超えたら7にする
クリックしたマスに何もなければ
石を打ち、相手の石を返す関数を実行
盤面を描く
盤面を表示する関数の定義
キャンバスに描いたものを全て削除
繰り返し yは0から7まで1ずつ増える
繰り返し xは0から7まで1ずつ増える
マス目のX座標
マス目のY座標
(X, Y)を左上角とした正方形を描く
board[y][x]の値がBLACKなら
黒い円を表示
board[y][x]の値がWHITEなら
白い円を表示
キャンバスを更新し、即座に描画する
石を打ち、相手の石をひっくり返す関数
(x, y)のマスに引数の色の石を打っ
繰り返し dyは-1→0→1と変化
繰り返し dxは-1→0→1と変化
変数kに0を代入
sxに引数xの値を代入
syに引数yの値を代入
無限ループで繰り返す
sxとsyの値を変化させる
盤から出てしまうなら
whileの繰り返しを抜ける
何も置かれていないマスなら
whileの繰り返しを抜ける
相手の石があれば
kの値を1増やす
自分の色の石があれば
はさんだ相手の石をひっくり返す
whileの繰り返しを抜ける
ウィンドウのオブジェクトを準備
ウィンドウのタイトルを指定
ウィンドウサイズを変更できなくする
クリック時に実行する関数を指定
キャンバスの部品を用意
キャンバスをウィンドウに配置
banmen()関数を呼び出す

解説

自分の石(引数で指定した色の石)を打ち、相手の石を挟んだら自分の色にする関数を定義しています。

関数名は ishi_utsu(x, y, iro) とし、board[y][x]のマスに iro で指定する色の石を打ちます。

この関数は、まず board[y][x] = iro で、引数で指定したマスに iroの石を打ちます。今回は click()関数内の ishi_utsu(mx, my, BLACK) と記述し、クリックしたマスに黒い石を打ちます。

太字で示した変数dy dx を用いた二重ループがポイントです。dydx ともに -1→0→1と値が変化します。

その値を使って、(x, y)のマスから8方向に盤面の状態を調べていきます。

(x, y)のマスから各方向を調べ始める際、変数 sx xの値、syyの値を代入しています。

そして while True の無限ループで、sx syの値を変化させながら、(sx, sy)のマスがどのような状態かを調べています。変数 dydxの値は、dy=-1dx=-1から始まるので、左上方向から調べ始めます。

次のアルゴリズムでマスの状態を調べています。

if sx<0 or sx>7 or sy<0 or sy>7 → 調べる位置が盤の外に出たか?

出たなら、breakwhileのループを抜けます。

if board[sy][sx]==0 → 調べるマスに何もないか?

何もなければ挟んで返すことはできないので、これもbreakでループを抜けます。

if board[sy][sx]=3-iro → 相手の石があるか?

相手の石があるなら、変数kの値を1増やして、いくつ並んでいるかを数えます。

board[sy][sx]==iro → 自分の石があるか?

自分の石があるなら、相手の石を返すことができます。その場合、for i in range(k) という for文で、sx から dx の値を引き、sy から dy の値を引いて、board[sy][sx] iro の値を代入します。はじめに石を打ったマスのすぐ隣が自分の石だったとしても、そのときは値が0なので、この forは実行されません。

dxdy とも0のときは?

8つの方向を効率良く調べるために、二重ループの for を用いました。その for文で dy=0dx=0 になるときがあります。その場合、「sxsy の値は変化しないので、判定が行われないのでは?

と疑問に思う方がおられるかもしれないので、解説しておきます。

dydx とも0のとき、sx sy は、引数xyの値のままです。board[y][x] には iro の値を代入しています。そのため

 if board[sy][sx] == iroの条件式が成り立ち、for i in range(k)で石を返しますが、kの値は0のままで、どの石も返りません。このように不具合が起きることはなく、全方向を調べ、石を返すことができます。

二重ループの繰り返しで、8つの向きを調べているのがポイントです。

二重ループ以外にも、例えば各方向を調べるときの座標の変化値を

XP=[-1,0,1,-1,1,-1,0,1]YP=[-1,-1,-1,0,0,1,1,1] とリストで定義して、マスを調べる方法もあります。

そうするなら、XP[0]YP[0] に左上の向き、XP[7]YP[7] に右下の向きに座標を増減する値が入ります。

同じことを行うアルゴリズムでも、プログラムには色々な書き方があります。

4、打てるマスを調べる

リバーシで石が打てるのは、そこに打つと相手の石をひっくり返せるときだけです。プレイヤー、コンピュータとも、石を打つとき、そのマスに打てるかを調べる必要があります。

ここでは board[y][x] のマスに指定の色の石を打つことができるかを判断する関数を用意します。

挟んで返すアルゴリズムと同じ

あるマスに石を打つことができるかを調べる方法は、前の節で組み込んだ、相手の石を投んで返す仕組みと一緒です。 board[y][x] に石を打つ前に、そのマスを起点として、全ての方向について返せる石を数えて加算します。その値が1以上なら(x,y)のマスに石を打てます。

動作の確認

返せる石を数え、黒い石を打てるマスに水色の丸印を付けるプログラムを確認します。この印は開発過程の確認用です。

list4.py

import tkinter
BLACK = 1
WHITE = 2
board = [
 [0, 2, 2, 0, 2, 2, 2, 1],
 [2, 0, 0, 0, 0, 0, 0, 0],
 [2, 0, 2, 0, 0, 1, 2, 0],
 [1, 0, 0, 1, 0, 2, 2, 0],
 [0, 0, 0, 0, 0, 2, 2, 0],
 [0, 0, 0, 1, 2, 0, 2, 1],
 [2, 0, 0, 2, 0, 2, 0, 0],
 [1, 0, 0, 0, 0, 1, 0, 0]
]

def click(e):
    mx = int(e.x/80)
    my = int(e.y/80)
    if mx>7: mx = 7
    if my>7: my = 7
    if board[my][mx]==0:
        ishi_utsu(mx, my, BLACK)
    banmen()
def banmen():
    cvs.delete("all")
    for y in range(8):
        for x in range(8):
            X = x*80
            Y = y*80
            cvs.create_rectangle(X, Y, X+80, Y+80, outline="black")
            if board[y][x]==BLACK:
                cvs.create_oval(X+10, Y+10, X+70, Y+70, fill="black", width=0)
            if board[y][x]==WHITE:
                cvs.create_oval(X+10, Y+10, X+70, Y+70, fill="white", width=0)
            if kaeseru(x, y, BLACK)>0:
                cvs.create_oval(X+5, Y+5, X+75, Y+75, outline="cyan", width=2)
    cvs.update()

# 石を打ち、相手の石をひっくり返す

def ishi_utsu(x, y, iro):
    board[y][x] = iro
    for dy in range(-1, 2):
        for dx in range(-1, 2):
            k = 0
            sx = x
            sy = y
            while True:
                sx += dx
                sy += dy
                if sx<0 or sx>7 or sy<0 or sy>7:
                    break
                if board[sy][sx]==0:
                    break
                if board[sy][sx]==3-iro:
                    k += 1
                if board[sy][sx]==iro:
                    for i in range(k):
                        sx -= dx
                        sy -= dy
                        board[sy][sx] = iro
                    break

# そこに打つといくつ返せるか数える

def kaeseru(x, y, iro):
    if board[y][x]>0:
        return -1 # 置けないマス
    total = 0
    for dy in range(-1, 2):
        for dx in range(-1, 2):
            k = 0
            sx = x
            sy = y
            while True:
                sx += dx
                sy += dy
                if sx<0 or sx>7 or sy<0 or sy>7:
                    break
                if board[sy][sx]==0:
                    break
                if board[sy][sx]==3-iro:
                    k += 1
                if board[sy][sx]==iro:
                    total += k
                    break
    return total
root = tkinter.Tk()
root.title("リバーシ")
root.resizable(False, False)
root.bind("<Button>", click)
cvs = tkinter.Canvas(width=640, height=700, bg="green")
cvs.pack()
banmen()
root.mainloop()

実行結果 

Python

コードの解説

tkinterモジュールをインポート
黒い石を管理するための定数
白い石を管理するための定数
一盤を管理するリスト
盤をクリックしたときに働く関数
ポインタのX座標を80で割りmxに代入
ポインタのY座標を80で割りmyに代入
mxが7を超えたら7にする
myが7を超えたら7にする
クリックしたマスに何もなければ
石を打ち、相手の石を返す関数を実行
盤面を描く
盤面を表示する関数の定義
キャンバスに描いたものを全て削除
繰り返し、yは0から7まで1ずつ増える
繰り返し xは0から7まで1ずつ増える
マス目のx座標
マス目のY座標
(X, Y)を左上角とした正方形を描く
board[y][x]の値がBLACKなら
黒い円を表示
board[y][x]の値がWHITEなら
白い円を表示
黒い石を打てるマスなら
水色の丸を表示
キャンバスを更新し、即座に描画する
石を打ち、相手の石をひっくり返す関数
(x,y)のマスに引数の色の石を打つ
繰り返し dyは-1→0→1と変化
繰り返し dxは-1→0→1と変化
変数kに0を代入
sxに引数xの値を代入
syに引数yの値を代入
無限ループで繰り返す
sxsyの値を変化させる
盤から出てしまうなら
whileの繰り返しを抜ける
何も置かれていないマスなら
whileの繰り返しを抜ける
相手の石があれば
kの値を1増やす
自分の色の石があれば
はさんだ相手の石をひっくり返す
whileの繰り返しを抜ける
そこに打つといくつ返せるか数える関数
(x, y)のマスに石があるなら
-1を返して関数から戻る
変数totalに0を代入
繰り返し dyは-1→0→1と変化
繰り返し dxは-1→0→1と変化
変数kに0を代入
sxに引数xの値を代入
syに引数yの値を代入
無限ループで繰り返す
sxとsyの値を変化させる
盤から出てしまうなら
whileの繰り返しを抜ける
何も置かれていないマスなら
whileの繰り返しを抜ける
相手の石があれば
kの値を1増やす
自分の色の石があれば
totalにkの値を加える
whileの繰り返しを抜ける
totalの値を戻り値として返す
ウィンドウのオブジェクトを準備
ウィンドウのタイトルを指定
ウィンドウサイズを変更できなくする
クリック時に実行する関数を指定
キャンバスの部品を用意
キャンバスをウィンドウに配置
banmen()関数を呼び出す
ウィンドウの処理を開始

解説

指定のマスに打つといくつ返せるかを数える kaeseru()関数を定義しています。この関数は、石を打つマスを引数xyで、打つ石の色を引数iro で受け取り、相手の石をいくつ返せるかを計算し、それを戻り値として返します。

kaeseru()関数を確認します。ishi_utsu()関数は挟んだ相手の石を返しますが、このkaeseru()関数はそれを行わず、代わりに返せる石を数えています。

この関数では、はじめに if board[y][x]>0 という if文で、引数(x, y) のマスに石が打たれているかを調べています。石があるならそこには打てないので、-1 を返して関数の処理を終えます。0を返してもよいですが、-1 を返しておけば、プレイヤーが石のあるマスに打とうとしたとき(-1 が返ったとき)、「そこには石があります」というメッセージを出す改良などがしやすくなります。

それ以降の処理は前の節で学んだ通りです。もう一度、概要を説明すると、二重ループのfor文で8つの方向を1つずつ調べていきます。そして返せる相手の石を変数kで数えて、変数 total kの値を加えています。

kaeseru()関数は、最後に total の値を戻り値として返しています。

ishi_utsu()関数やkaeseru()関数で行っている盤面の状態を調べる仕組みは、リバーシを完成させるために必須となるアルゴリズムです。

現在の局面に打てるマスがあるかを知る

盤面全体のマスに対して kaeseru()関数を実行し、1以上が返るマスがあるかを調べれば、現在の局面に石を打てるマスがあるかを知ることができます。次の節で、プレイヤーとコンピュータが交互に石を打つようにしますが、そこで現在の局面に石を打てるマスがあるかを、kaeseru() を呼び出して調べる関数を追加します。

リバーシを完成させるのに必要な関数を、ここで用意したわけです。

5、コンピュータが石を打つ

プレイヤーとコンピュータが交互に石を打つようにします。ここではプレイヤーが黒い石、コンピュータが白い石を打ちます。次の節で先手、後手を選べるようにし、後手を選ぶと、プレイヤーが打つのは白い石(コンピュータは黒い石)になります。

変数でゲーム進行を管理する

プレイヤーとコンピュータが交互に石を打ち、ひっくり返せる相手の石があるなら返すという一連の処理を、proc という変数を用意し、その値によって順に行うようにします。

proc0から5の値をとるものとし、それぞれの値で処理を次のように分岐させます。これらを行うために main() という関数を用意し、その関数の中で処理を分岐させます。

procと処理の内容

0 タイトル画面

1 どちら番かを表示する

2 石を打つマスを決める

3 打つ番を交代する

4 プレイヤーとコンピュータの打てるマスがあるかを調べる

5 勝敗判定

プレイヤーとコンピュータの処理を共通化

procの値が2のときにプレイヤー、コンピュータそれぞれが石を打つマスを決め、procの値が4のときに対局を続けるか調べるというように、処理を共通化します。それを行うために、どちらが打つ番かを管理する変数を用意し、その変数名をturn とします。

動作の確認

以上の処理を組み込んだプログラムを確認します。プレイヤーが黒い石を打ったら、コンピュータが白い石を打ちます。コンピュータが打つマスはランダムに決めています。

相手の石を返せないマスには、プレイヤーもコンピュータも打つことはできません。石を打てないときは、相手の番になります。どちらとも打てない状態になったら終了です。

list5.py

import tkinter
import random
BLACK = 1
WHITE = 2
mx = 0
my = 0
mc = 0
proc = 0
turn = 0
msg = ""

board = [
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 2, 1, 0, 0, 0],
 [0, 0, 0, 1, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]
]

def click(e):
    global mx, my, mc
    mc = 1
    mx = int(e.x/80)
    my = int(e.y/80)
    if mx>7: mx = 7
    if my>7: my = 7
def banmen():
    cvs.delete("all")
    cvs.create_text(320, 670, text=msg, fill="silver")
    for y in range(8):
        for x in range(8):
            X = x*80
            Y = y*80
            cvs.create_rectangle(X, Y, X+80, Y+80, outline="black")
            if board[y][x]==BLACK:
                cvs.create_oval(X+10, Y+10, X+70, Y+70, fill="black", width=0)
            if board[y][x]==WHITE:
                cvs.create_oval(X+10, Y+10, X+70, Y+70, fill="white", width=0)
    cvs.update()
# 石を打ち、相手の石をひっくり返す
def ishi_utsu(x, y, iro):
    board[y][x] = iro
    for dy in range(-1, 2):
        for dx in range(-1, 2):
            k = 0
            sx = x
            sy = y
            while True:
                sx += dx
                sy += dy
                if sx<0 or sx>7 or sy<0 or sy>7:
                    break
                if board[sy][sx]==0:
                    break
                if board[sy][sx]==3-iro:
                    k += 1
                if board[sy][sx]==iro:
                    for i in range(k):
                        sx -= dx
                        sy -= dy
                        board[sy][sx] = iro
                    break

# そこに打つといくつ返せるか数える

def kaeseru(x, y, iro):
    if board[y][x]>0:
        return -1 # 置けないマス
    total = 0
    for dy in range(-1, 2):
        for dx in range(-1, 2):
            k = 0
            sx = x
            sy = y
            while True:
                sx += dx
                sy += dy
                if sx<0 or sx>7 or sy<0 or sy>7:
                    break

                if board[sy][sx]==0:
                    break

                if board[sy][sx]==3-iro:
                    k += 1
                if board[sy][sx]==iro:
                    total += k
                    break

    return total

# 打てるマスがあるか調べる

def uteru_masu(iro):
    for y in range(8):
        for x in range(8):
            if kaeseru(x, y, iro)>0:
                return True
    return False
#コンピュータの思考ルーチン
def computer_0(iro): # ランダムに打つ
    while True:
        rx = random.randint(0, 7)
        ry = random.randint(0, 7)
        if kaeseru(rx, ry, iro)>0:
            return rx, ry

def main():
    global mc, proc, turn, msg
    banmen()
    if proc==0: # スタート待ち
        msg = "クリックして開始します"
        if mc==1: # ウィンドウをクリック
            mc = 0
            turn = 0
            proc = 1

    elif proc==1: # どちらの番か表示
        msg = "あなたの番です"
        if turn==1:
            msg = "コンピュータ 考え中."

        proc = 2
    elif proc==2: # 石を打つマスを決める
        if turn==0: # プレイヤー
            if mc==1:
                mc = 0
                if kaeseru(mx, my, BLACK)>0:
                    ishi_utsu(mx, my, BLACK)
                    proc = 3
        else: # コンピュータ
            cx, cy = computer_0(WHITE)
            ishi_utsu(cx, cy, WHITE)
            proc = 3
    elif proc==3: # 打つ番を交代
        turn = 1-turn
        proc = 4
    elif proc==4: # 打てるマスがあるか
        if uteru_masu(BLACK)==False and uteru_masu(WHITE)==False:
            msg = "どちらも打てないので終了です"
        elif turn==0 and uteru_masu(BLACK)==False:
            msg = "あなたは打てないのでパス"
            proc = 3
        elif turn==1 and uteru_masu(WHITE)==False:
            msg = "コンピュータは打てないのでパス"
            proc = 3
        else:
            proc = 1
    root.after(100, main)
root = tkinter.Tk()
root.title("リバーシ")
root.resizable(False, False)
root.bind("<Button>", click)
cvs = tkinter.Canvas(width=640, height=700, bg="green")
cvs.pack()
root.after(100, main)
root.mainloop()

実行結果 

Python

コードの意味

tkinterモジュールをインポート
randomモジュールをインポート
黒い石を管理するための定数
白い石を管理するための定数
クリックしたマスの列の値
クリックしたマスの行の値
クリックしたときに1を代入する変数
ゲーム進行を管理する変数
どちらの番かを管理する変数
メッセージ表示用の変数(文字列を代入)
一盤を管理するリスト
盤をクリックしたときに働く関数
これらをグローバル変数として扱う
mcに1を代入
ポインタのX座標を80で割りmxに代入
ポインタのY座標を80で割りmyに代入
mxが7を超えたら7にする
myが7を超えたら7にする
盤面を表示する関数
キャンバスに描いたものを全て削除
メッセージの文字列を表示
繰り返し yは0から7まで1ずつ増える
繰り返し xは0から7まで1ずつ増える
マス目のX座標
マス目のY座標
(X,Y)を左上角とした正方形を描く
board[y][x]の値がBLACKなら
黒い円を表示
board[y][x]の値がWHITEなら
白い円を表示
キャンバスを更新し、即座に描画する
石を打ち、相手の石をひっくり返す関数
(x,y)のマスに引数の色の石を打っ
繰り返し dyは-1→0→1と変化
繰り返し dxは-1→0→1と変化
変数に0を代入
Sxに引数xの値を代入
syに引数yの値を代入
無限ループで繰り返す
sxとsyの値を変化させる
盤から出てしまうなら
whileの繰り返しを抜ける
何も置かれていないマスなら
whileの繰り返しを抜ける
相手の石があれば
kの値を1増やす
自分の色の石があれば
はさんだ相手の石をひっくり返す
whileの繰り返しを抜ける
そこに打つといくつ返せるか数える関数
(x,y)のマスに石があるなら
-1を返して関数から戻る
変数totalに0を代入
繰り返し dyは-1→0→1と変化
繰り返し dxは-1→0→1と変化
変数kに0を代入
sxに引数xの値を代入
syに引数yの値を代入
無限ループで繰り返す
xとsyの値を変化させる
盤から出てしまうなら
whileの繰り返しを抜ける
何も置かれていないマスなら
whileの繰り返しを抜ける
相手の石があれば
kの値を1増やす
自分の色の石があれば
totalにkの値を加える
whileの繰り返しを抜ける
totalの値を戻り値として返す
打てるマスがあるか調べる関数
繰り返し yは0から7まで1ずつ増える
繰り返し xは0から7まで1ずつ増える
kaeseru()の戻り値が0より大きいなら
Trueを返す
Falseを返す

コンピュータの思考ルーチン

コンピュータが石を打つ computer_0()関数を定義しています。この関数はランダムにマスを調べ、打てるマスが見つかった時点で、そのマスの列と行の値を返します。コンピュータがちゃんと考えて石を打つように改良します。ランダムに石を打つ処理もコンピュータの思考ルーチンと呼んでおきます。

computer_0()関数を抜き出して説明します。

while Trueの無限ループで、変数 rx ry にランダムなマスの位置を代入し、そこに打つとプレイヤーの石を返せるかを kaeseru()関数で調べています。打てるなら return rx ry の値を返します。

Python は関数の戻り値に複数の変数を記述できます。

例えば return a, b, c 3つの戻り値を定めた関数を実行するときは、x, y, z = my_function()として、戻り値を代入する変数も3つ記述します。

関数に戻り値を1つしか定められないプログラミング言語もあります。

Python は複数の戻り値を記述でき、その使い方に慣れると、戻り値を複数使えるのは、とても便利なことが判ります。

リアルタイム処理を追加

リアルタイム処理を行う main()関数を記述しています。この関数を呼び出しています。呼び出された main()関数は、after()命令で自分を一定間隔で実行し続けます。

単に main() とすると、ウィンドウの×ボタンでプログラムを終了したとき、実行中の処理の内容によっては、エラーメッセージが表示されることがあります。特に問題のないエラーですが、root.after(100, main) で処理を開始すると、エラーが出る頻度が下がるので、このプログラムでは main() をはじめて呼び出すときに after()命令を用いています。

main()関数の処理の内容

変数procの値が0のとき変数 msg に「クリックして開始します」という文字列を代入し、banmen() 関数でそれを画面に表示しています。ウィンドウがクリックされたら mcの値を0にし、turn 0proc 1を代入して、石を打つ処理に移ります。turnの値は0がプレイヤーの番、1がコンピュータの番としています。

mc0にするのは、再びウィンドウをクリックしたことが判るようにするためです。

procの値が1のとき

どちらの番かをmsg に代入し、proc2にしています。

procの値が2のとき

プレイヤー、もしくはコンピュータが石を打つマスを決めます。どちらの番かをturn という変数で管理しています。turn 0のとき(プレイヤーの番)、変数 mc1なら盤面がクリックされたので、変数mxmyのマスに黒い石を打てるかを kaeseru()関数で確認します。

打てるならishi_utsu()関数で石を打ち、コンピュータの石をひっくり返し、proc3にします。

turn1のとき(コンピュータの番)cx, cy = computer_0(WHITE) という記述で、コンピュータが打つマスを cxcyに代入します。ishi_utsu()関数でそこに白い石を打ち、プレイヤーの石をひっくり返し、proc3にします。

procの値が3のとき

turn = 1-turnという式で、turnの値が0なら1に、1なら0にして、プレイヤーとコンピュータの番を交代します。そしてproc4にします。

procの値が4のとき

プレイヤーとコンピュータが石を打てるかを uteru_masu()関数で調べています。どちらも打てないときは「どちらも打てないので終了です」というメッセージを表示します。

elif turn==0 and uteru_masu(BLACK)==False という条件式で、プレイヤーの番のときに黒い石を打てないかを調べています。打てなければ「あなたは打てないのでパス」と表示し、proc3にしてコンピュータの番にします。

elif turn==1 and uteru_masu(WHITE)==False という条件式で、コンピュータの番のときに白い石が打てないかを調べ、打てなければ「コンピュータは打てないのでパス」と表示し、proc3にしてプレイヤーの番にします。

6、ゲームとして遊べるようにする

プレイヤーが先手か後手かを選択できるようにします。終局すると勝敗結果を表示し、ゲームとして一通り遊べるようにします。

リバーシは先手が黒い石を、後手が白い石を打ちます。プレイヤーとコンピュータのそれぞれが打つ石の色を color[] というリストを用意して管理します。

メッセージボックス勝敗を表示

プレイヤーとコンピュータ、共に石を打つマスがなくなったらゲーム終了とし、黒い石と白い石を数えて、どちらが勝ったかを表示します。その表示をメッセージボックスで行います。

メッセージボックスとはパソコン画面に表示される小さなウィンドウのことです。そこにメッセージとなる文字列を表示し、ユーザーに情報を伝えることができます。メッセージボックスを表示するには tkinter.messagebox モジュールを用います。

動作の確認

次のプログラムの動作を確認しましょう。「先手()」か「後手()」の文字をクリックして対局を開始します。最後までプレイすると勝敗が表示されます。黒と白の数が同じときは、引き分けになります。

list6.py

import tkinter
import tkinter.messagebox
import random
FS = ("Times New Roman", 30)
FL = ("Times New Roman", 80)
BLACK = 1
WHITE = 2
mx = 0
my = 0
mc = 0
proc = 0
turn = 0
msg = ""
space = 0
color = [0]*2
who = ["あなた", "コンピュータ"]
board = []
for y in range(8):
    board.append([0,0,0,0,0,0,0,0])
def click(e):
    global mx, my, mc
    mc = 1
    mx = int(e.x/80)
    my = int(e.y/80)
    if mx>7: mx = 7
    if my>7: my = 7
def banmen():
    cvs.delete("all")
    cvs.create_text(320, 670, text=msg, fill="silver", font=FS)
    for y in range(8):
        for x in range(8):
            X = x*80
            Y = y*80
            cvs.create_rectangle(X, Y, X+80, Y+80, outline="black")
            if board[y][x]==BLACK:
                cvs.create_oval(X+10, Y+10, X+70, Y+70, fill="black", width=0)
            if board[y][x]==WHITE:
                cvs.create_oval(X+10, Y+10, X+70, Y+70, fill="white", width=0)
    cvs.update()
def ban_syokika():
    global space
    space = 60
    for y in range(8):
        for x in range(8):
            board[y][x] = 0
    board[3][4] = BLACK
    board[4][3] = BLACK
    board[3][3] = WHITE
    board[4][4] = WHITE
# 石を打ち、相手の石をひっくり返す
def ishi_utsu(x, y, iro):
    board[y][x] = iro
    for dy in range(-1, 2):
        for dx in range(-1, 2):
            k = 0
            sx = x
            sy = y
            while True:
                sx += dx
                sy += dy
                if sx<0 or sx>7 or sy<0 or sy>7:
                    break
                if board[sy][sx]==0:
                    break
                if board[sy][sx]==3-iro:
                    k += 1
                if board[sy][sx]==iro:
                    for i in range(k):
                        sx -= dx
                        sy -= dy
                        board[sy][sx] = iro
                    break
# そこに打つといくつ返せるか数える
def kaeseru(x, y, iro):
    if board[y][x]>0:
        return -1 # 置けないマス
    total = 0
    for dy in range(-1, 2):
        for dx in range(-1, 2):
            k = 0
            sx = x
            sy = y
            while True:
                sx += dx
                sy += dy
                if sx<0 or sx>7 or sy<0 or sy>7:
                    break
                if board[sy][sx]==0:
                    break
                if board[sy][sx]==3-iro:
                    k += 1
                if board[sy][sx]==iro:
                    total += k
                    break
    return total
# 打てるマスがあるか調べる
def uteru_masu(iro):
    for y in range(8):
        for x in range(8):
            if kaeseru(x, y, iro)>0:
                return True
    return False
# 黒い石、白い石、いくつかあるか数える
def ishino_kazu():
    b = 0
    w = 0
    for y in range(8):
        for x in range(8):
            if board[y][x]==BLACK: b += 1
            if board[y][x]==WHITE: w += 1
    return b, w
#コンピュータの思考ルーチン
def computer_0(iro): # ランダムに打つ
    while True:
        rx = random.randint(0, 7)
        ry = random.randint(0, 7)
        if kaeseru(rx, ry, iro)>0:
            return rx, ry
def main():
    global mc, proc, turn, msg, space
    banmen()
    if proc==0: # タイトル画面
        msg = "先手、後手を選んでください"
        cvs.create_text(320, 200, text="Reversi", fill="gold", font=FL)
        cvs.create_text(160, 440, text="先手(黒)", fill="lime", font=FS)
        cvs.create_text(480, 440, text="後手(白)", fill="lime", font=FS)
        if mc==1: # ウィンドウをクリック
            mc = 0
            if (mx==1 or mx==2) and my==5:
                ban_syokika()
                color[0] = BLACK
                color[1] = WHITE
                turn = 0
                proc = 1
            if (mx==5 or mx==6) and my==5:
                ban_syokika()
                color[0] = WHITE
                color[1] = BLACK
                turn = 1
                proc = 1
    elif proc==1: # どちらの番か表示
        msg = "あなたの番です"
        if turn==1:
            msg = "コンピュータ 考え中."
        proc = 2
    elif proc==2: # 石を打つマスを決める
        if turn==0: # プレイヤー
            if mc==1:
                mc = 0
                if kaeseru(mx, my, color[turn])>0:
                    ishi_utsu(mx, my, color[turn])
                    space -= 1
                    proc = 3
        else:  cx, cy = computer_0(color[turn])
            ishi_utsu(cx, cy, color[turn])
            space -= 1
            proc = 3
    elif proc==3: # 打つ番を交代
        msg = ""
        turn = 1-turn
        proc = 4
    elif proc==4: # 打てるマスがあるか
        if space==0:
            proc = 5
        elif uteru_masu(BLACK)==False and uteru_masu(WHITE)==False:
            tkinter.messagebox.showinfo("", "どちらも打てないので終了です")
            proc = 5
        elif uteru_masu(color[turn])==False:
            tkinter.messagebox.showinfo("", who[turn]+"は打てないのでパスです")
            proc = 3
        else:
            proc = 1
    elif proc==5: # 勝敗判定
        b, w = ishino_kazu()
        tkinter.messagebox.showinfo("終了", "黒={}、白={}".format(b, w))
        if (color[0]==BLACK and b>w) or (color[0]==WHITE and w>b):
            tkinter.messagebox.showinfo("", "あなたの勝ち!")
        elif (color[1]==BLACK and b>w) or (color[1]==WHITE and w>b):
            tkinter.messagebox.showinfo("", "コンピュータの勝ち!")
        else:
            tkinter.messagebox.showinfo("", "引き分け")
        proc = 0
    root.after(100, main)
root = tkinter.Tk()
root.title("リバーシ")
root.resizable(False, False)
root.bind("<Button>", click)
cvs = tkinter.Canvas(width=640, height=700, bg="green")
cvs.pack()
root.after(100, main)
root.mainloop()

実行結果 

Python

Macでのタイトル画面の文字のちらつき

Windowsパソコンでは起きませんが、Macではタイトル画面の文字がちらつきます。気になる方は、banmen()関数の42行目を if proc1=0: cvs.update) と書き換えれば、ちらつきがなくなります。

append()で二次元リストを準備

前のプログラムまでは、盤を管理する二次元リストを

board = [

[0, 0, 0, 0, 0, 0, 0, 0],

:

[0, 0, 0, 0, 0, 0, 0, 0]

]

と記述して宣言していました。このプログラムでは次の記述で、二次元リストを用意しています。

board = []

for y in range (8):

board.append([0,0,0,0,0,0,0,0])

board = [] として空のリストを用意し、そこに for append()命令で [0, 0, 0, 0, 0, 0, 0, 0]8つ追加しています。この記述はさらに簡潔にでき、次のようにします。

board = []

for y in range(8):

board.append( [0]*8)

盤面を初期化する

ban_syokika()関数で、次のように board[] にゲーム開始時の値

を代入しています。

def ban_syokika():

global space

space = 60

for y in range(8) :

for x in range(8):

board[y][x]

board[3][4] = BLACK

board[4][3] = BLACK

board[3][3] = WHITE

board[4][4] = WHITE

黒い石と白い石を数える関数

石を数える ishino_kazu() という関数を定義しています。この関数でゲーム終了時に盤上の石を数え、勝敗を決めます。

main()関数に追加した処理

main()関数で変数 proc の値に応じて処理を分岐させ、ゲームの進行を管理しています。

変数 procの値が0のときがタイトル画面の処理です。

「先手」「後手」の文字列を表示し、それらの文字列が載るマスをクリックすると、次のリストと変数に値を代入し、proc1にしてゲームを開始します。

プレイヤー後手の値

コンピュータの石の色をcolor[] というリストで管理するようにしたので、kaeseru(mx, my,procの値が1234の処理は前の節と同じ内容です。ただしプレイヤーとコンcolor[turn]) ishi_utsu(cx, cy, color[turn]) のように、石の色を color[ ]で指定しています。

勝敗判定について

main()関数の proc の値が5のとき、勝敗を判定しています。

盤上の石を数える ishino_kazu()関数で黒と白の石を数え、それらの大小を比べて、プレイヤーの勝ち、コンピュータの勝ち、あるいは引き分けだったことをメッセージボックスで表示しています。

messageboxの使い方

このプログラムでは、プレイヤーとコンピュータどちらも打てないときのメッセージの表示と、終局したときの勝敗結果の表示を、メッセージボックスで行っています。メッセージボックスを用いるには tkinter.messagebox モジュールをインポートします。

そして、tkinter.messagebox.showinfo() 命令でバーに表示するタイトルとメッセージの文字列を引数で指定し、メッセージボックスを表示します。

メッセージボックスには、主に次の種類があります。

メッセージボックスの種類

showinfo()  情報を表示するメッセージボックス

showwarning()警告を表示するメッセージボックス

showerror()エラーを表示するメッセージボックス

askyesno()「はい」「いいえ」のボタンがあるメッセージボックス

askokcancel()OK」「キャンセル」のボタンがあるメッセージボックス

はい、いいえのボタンがあるものと、OK、キャンセルのボタンがあるメッセージボックスは、

変数 = tkinter.messagebox.askyesno(引数)

変数 = tkinter.messagebox.askokcancell(引数)

とし、「はい」や「OK」を選ぶと変数に Trueが代入されます。変数の値を調べることで、どのボタンが押されたか判ります。

メッセージボックスはソフトウェア開発で便利に使えるものです。

使い方を覚えておき、活用しましょう。

コンピュータが弱い

このプログラムでコンピュータはランダムなマスに石を打ちます。人間に例えれば何も考

えずに打つのと一緒ですから、コンピュータは弱く、プレイヤーが負けることは、まずないでしょう。

次の2つのアルゴリズム(思考ルーチン)を組み込み、コンピュータを強くします。

・思考ルーチン1

優先的に石を打つべきマスを定義し、そこに打てるなら石を打つ

思考ルーチン2

乱数を用いてシミュレーションを行うモンテカルロ法で、勝てる確率の高いマスを選び、そこに石を打つ

8、モンテカルロ法について

リバーシの思考ルーチンに採用されるアルゴリズムについて説明します。

思考ルーチンには種類がある

リバーシの思考ルーチンは、古くから複数の手法が考案されてきました。それらの中で、ミニ・マックス法(min-max)や、それを効率化したアルファ・ベータ法(a – B)と呼ばれる手法が有名です。ミニ・マックス法やアルファ・ベータ法では、数手先までの局面

を計算し、各色の石の増減を調べ、プレイヤーは自分が有利になる手(コンピュータにとっては不利になる手)を選ぶという考えを元に、コンピュータが打つべきマスを決めます。

またリバーシには勝つためのテクニック(定石)があり、それらを組み合わせてコンピュータを強くする方法があります。著者の経営するゲーム開発会社でも、定石+アルファ・ベータ法による実装でリバーシを開発したことがあります。

以上のような手法は 1980年代に確立され、長年に渡ってリバーシの思考ルーチンに採用されてきました。現在ではそれらのアルゴリズムの他に、モンテカルロ法と呼ばれる手法で最終局面まで調べ、コンピュータが勝てる確率の高いマスに石を打つ思考ルーチンが用いられるようになりました。

思考ルーチンの新旗手のひとつであるモンテカルロ法による実装を行います。

古典的な手法での先読みについて

ここからは「先の局面を調べ、次の一手を選ぶこと」を「先読み」と表現して説明します。

ミニ・マックス法やアルファ・ベータ法で先読みする仕組みを簡単に説明します。モンテカルロ法はミニ・マックス法やアルファ・ベータ法と異なるアルゴリズムですが、モンテカルロ法の実装でも先の局面を予測する意味を知っておく必要があります。

ミニ・マックス法やアルファ・ベータ法では、次の図のように変化していく局面を計算し、黒と白の石の数の増減を調べ、打つべきマスを選ぶアルゴリズムを実装します。

プレイヤーが黒い石を打ったときの局面で、次はコンピュータが白い石を打てるマスが3つあることを示しています。それらのマスに石を打つと、再びプレイヤーが打てるマスが複数あるという形で、局面は先にいくほど枝分かれして増えていきます。

リバーシは多くの局面で、この図よりたくさんのマスに石を打てる状態になります。そして先へいくほど局面の数は爆発的に増えていきます。

変化していく局面を先読みすることを、考えてみましょう。

探索アルゴリズムについて

複数のデータの中から目的のものを探すアルゴリズムを探索アルゴリズムといいます。探索アルゴリズムは、ばらばらな値が並んでいるデータから目的の値を探す線形探索と呼ばれる手法や、大きな順あるいは小さな順に並んだデータから効率良く値を探す二分探索などの手法が有名です。

リバーシの局面のように枝分かれしていくデータ内から、ミニマックス法などで目的の値を探すことも、広い意味での探索アルゴリズムと考えられます。

線形探索や二分探索は最も単純なアルゴリズムで、莫大なデータであっても、今のコンピュータはそれらの中から瞬時に目的の値を探し出します。一方、リバーシのように先の局面を計算しながら目的のもの(打つべきマス)を見つけるには、ミニ・マックス法やアルファ・ベータ法では何手先まで読むか、モンテカルロ法では何回の試行を行うかによりますが、処理にある程度の時間を要します。

思考時間が重要

探索アルゴリズムは目的のものをできるだけ短時間で探すことが重要です。それはコンピュータゲームの思考ルーチンにも当てはまります。ゲームでコンピュータの思考時間が長いと、プレイヤーは待たされるストレスを感じます。多くの人は、そのようなゲームを途中でプレイするのが嫌になるでしょう。

コンピュータゲームの思考ルーチンは短時間で計算を終えなくてはなりません。リバーシは先の手になるほど局面が爆発的に増えるので、全てを調べようとすると計算に多くの時間を費やします。そのため先読みは、ある時点で打ち切らなくてはなりません。コンピュータゲームの思考時間と強さは、通常、トレードオフの関係にあります。

同じ程度の強さの思考ルーチンでも、優れたプログラマーが作ったアルゴリズムは、より高速な計算方法を採用するなどして、短時間で思考を完了するものがあることを補足しておきます。

思考ルーチンの新旗手、モンテカルロ法

モンテカルロ法は乱数を用いて数値計算やシミュレーションを行う手法です。その手法自体は古くからあるものですが、近年コンピュータゲームの思考ルーチンに採用されるようになりました。

今回は円周率をモンテカルロ法で求める方法を学び、モンテカルロ法の基本を理解します。

モンテカルロ法の学習の前に、思考ルーチンを組み込む練習として、簡単な仕組みでコンピュータをある程度強くするアルゴリズムを制作します。

ミニ・マックス法やアルファ・ベータ法は、多くのコンピュータ雑誌や書物で、昔からリバーシの思考ルーチンとして紹介、解説されてきました。現在ではそれらの実装法をインターネットで紹介するサイトが多く存在します。

ミニ・マックス法やアルファ・ベータ法に興味を持たれた方はネットで検索してみましょう。

思考ルーチンの種類とコンピュータの強さ

リバーシがどれくらい上手か(強いか)は人によって差があり、コンピュータ相手にプレイしたとき、コンピュータの強さをどう感じるかにも個人差があります。とはいえ、ひとつの目安として、思考ルーチン、実装の難易度、処理に掛かる時間、コンピュータの強さ

をお伝えしておくと、この先で学ぶ内容のイメージが掴みやすくなるので、時々、リバーシを遊ぶ程度で普通の人くらいの強にします。

簡易的な思考ルーチンを実装する

思考ルーチンのアルゴリズムを制作する練習として、モンテカルロ法による実装の前に、コンピュータを簡単に、ある程度強くできる、優先的に打つべきマスを定義する方法を学びます。

角を取ると有利になる

リバーシは四隅の角を取ると、相手の石をひっくり返せる可能性が高くなり、その後の展開が有利になります。また四隅の角に隣接するマス(次の図のピンク色のマス)に不用意に石を打つと、相手に角を取られる恐れがあります。角を取られると、その後の展開が不利になることが多いものです。

このことは、ある程度リバーシを遊んだことのある方は経験的にご存知でしょう。コンピュータにもできるだけ角を取らせ、角に隣接するマスにはなるべく打たせないようにすると、ランダムに打つよりも強くなります。

優先すべきマスをデータとして定義

ピンク色のマス以外の周囲のマスに自分の石があると、何かと有利なことがあります。例えば紫色のマスは、そこに自分の石があると角を取れる可能性があると考えられます。そこで、青色のマス紫色のマスオレンジ色のマス白いマスピンク色のマスの順に、コンピュータに石を打たせるようにします。

例えば、角のマスと白いマスに打てるなら、角に優先的に石を打ちます。また、リバーシには、石を打てるときにパスをするルールはありません。

ピンク色のマスにしか打てないなら、もちろん、そこに

打つようにします。

どのマスに優先的に打つかを、次のような二次元リストで数値のデータとして定義します。

point [

[6,2,5,4,4,5,2,6),

[2,1,3,3,3,3,1,2],

[5,3,3,3,3,3,3,5),

[4,3,3,0,0,3,3,4],

[4,3,3,0,0,3,3,4],

[5,3,3,3,3,3,3,5],

[2,1,3,3,3,3,1,2],

[6,2,5,4,4,5,2,6]

]

値が大きいほど優先度が高いマスになります。例えば現在の局面でコンピュータがABのマスに打てるとし、Aの値が5Bの値が3なら、値の大きいAのマスに石を打つようにします。

プログラムの確認

優先的に打つべきマスをコンピュータに選ばせる処理を組み込んだプログラムを確認します。ランダムに石を打つ computer_0() という関数を組み込みましたが、computer_0() は削除しています。そして新たに computer_1() という名の関数を思考ルーチンとして組み込んでいます。

list2.py プログラムからの追加、変更箇所のみ掲載します

import tkinter
import tkinter.messagebox
import random
FS = ("Times New Roman", 30)
FL = ("Times New Roman", 80)
BLACK = 1
WHITE = 2
mx = 0
my = 0
mc = 0
proc = 0
turn = 0
msg = ""
space = 0
color = [0]*2
who = ["あなた", "コンピュータ"]
board = []
for y in range(8):
    board.append([0]*8)

def click(e):
    global mx, my, mc
    mc = 1
    mx = int(e.x/80)
    my = int(e.y/80)
    if mx>7: mx = 7
    if my>7: my = 7
def banmen():
    cvs.delete("all")
    cvs.create_text(320, 670, text=msg, fill="silver", font=FS)
    for y in range(8):
        for x in range(8):
            X = x*80
            Y = y*80
            cvs.create_rectangle(X, Y, X+80, Y+80, outline="black")
            if board[y][x]==BLACK:
                cvs.create_oval(X+10, Y+10, X+70, Y+70, fill="black", width=0)
            if board[y][x]==WHITE:
                cvs.create_oval(X+10, Y+10, X+70, Y+70, fill="white", width=0)
    cvs.update()

def ban_syokika():
    global space
    space = 60
    for y in range(8):
        for x in range(8):
            board[y][x] = 0
    board[3][4] = BLACK
    board[4][3] = BLACK
    board[3][3] = WHITE
    board[4][4] = WHITE

# 石を打ち、相手の石をひっくり返す
def ishi_utsu(x, y, iro):
    board[y][x] = iro
    for dy in range(-1, 2):
        for dx in range(-1, 2):
            k = 0
            sx = x
            sy = y
            while True:
                sx += dx
                sy += dy
                if sx<0 or sx>7 or sy<0 or sy>7:
                    break
                if board[sy][sx]==0:
                    break
                if board[sy][sx]==3-iro:
                    k += 1
                if board[sy][sx]==iro:
                    for i in range(k):
                        sx -= dx
                        sy -= dy
                        board[sy][sx] = iro
                    break

# そこに打つといくつ返せるか数える

def kaeseru(x, y, iro):
    if board[y][x]>0:
        return -1 # 置けないマス
    total = 0
    for dy in range(-1, 2):
        for dx in range(-1, 2):
            k = 0
            sx = x
            sy = y
            while True:
                sx += dx
                sy += dy
                if sx<0 or sx>7 or sy<0 or sy>7:
                    break

                if board[sy][sx]==0:
                    break

                if board[sy][sx]==3-iro:
                    k += 1

                if board[sy][sx]==iro:
                    total += k
                    break

    return total

# 打てるマスがあるか調べる
def uteru_masu(iro):
    for y in range(8):
        for x in range(8):
            if kaeseru(x, y, iro)>0:
                return True
    return False

# 黒い石、白い石、いくつかあるか数える
def ishino_kazu():
    b = 0
    w = 0
    for y in range(8):
        for x in range(8):
            if board[y][x]==BLACK: b += 1
            if board[y][x]==WHITE: w += 1
    return b, w

point = [
    [6,2,5,4,4,5,2,6],
    [2,1,3,3,3,3,1,2],
    [5,3,3,3,3,3,3,5],
    [4,3,3,0,0,3,3,4],
    [4,3,3,0,0,3,3,4],
    [5,3,3,3,3,3,3,5],
    [2,1,3,3,3,3,1,2],
    [6,2,5,4,4,5,2,6]
]

# 優先的に打つべきマスを選ぶ
def computer_1(iro): 
    sx = 0
    sy = 0
    p = 0
    for y in range(8):
        for x in range(8):
            if kaeseru(x, y, iro)>0 and point[y][x]>p:
                    p = point[y][x]
                    sx = x
                    sy = y
    return sx, sy

def main():
    global mc, proc, turn, msg, space
    banmen()

    if proc==0: # タイトル画面
        msg = "先手、後手を選んでください"
        cvs.create_text(320, 200, text="Reversi", fill="gold", font=FL)
        cvs.create_text(160, 440, text="先手(黒)", fill="lime", font=FS)
        cvs.create_text(480, 440, text="後手(白)", fill="lime", font=FS)
        if mc==1: # ウィンドウをクリック
            mc = 0
            if (mx==1 or mx==2) and my==5:
                ban_syokika()
                color[0] = BLACK
                color[1] = WHITE
                turn = 0
                proc = 1
            if (mx==5 or mx==6) and my==5:
                ban_syokika()
                color[0] = WHITE
                color[1] = BLACK
                turn = 1
                proc = 1

 # どちらの番か表示
    elif proc==1:
        msg = "あなたの番です"
        if turn==1:
            msg = "コンピュータ 考え中."
        proc = 2

# 石を打つマスを決める
    elif proc==2: 
        if turn==0: # プレイヤー
            if mc==1:
                mc = 0
                if kaeseru(mx, my, color[turn])>0:
                    ishi_utsu(mx, my, color[turn])
                    space -= 1
                    proc = 3

 # コンピュータ
        else:
            cx, cy = computer_1(color[turn])
            ishi_utsu(cx, cy, color[turn])
            space -= 1
            proc = 3
    elif proc==3:     # 打つ番を交代
        msg = ""
        turn = 1-turn
        proc = 4

    elif proc==4:     # 打てるマスがあるか
        if space==0:
            proc = 5
        elif uteru_masu(BLACK)==False and uteru_masu(WHITE)==False:
            tkinter.messagebox.showinfo("", "どちらも打てないので終了です")
            proc = 5
        elif uteru_masu(color[turn])==False:
            tkinter.messagebox.showinfo("", who[turn]+"は打てないのでパスです")
            proc = 3
        else:
            proc = 1
    elif proc==5: # 勝敗判定
        b, w = ishino_kazu()
        tkinter.messagebox.showinfo("終了", "黒={}、白={}".format(b, w))
        if (color[0]==BLACK and b>w) or (color[0]==WHITE and w>b):
            tkinter.messagebox.showinfo("", "あなたの勝ち!")
        elif (color[1]==BLACK and b>w) or (color[1]==WHITE and w>b):
            tkinter.messagebox.showinfo("", "コンピュータの勝ち!")
        else:
            tkinter.messagebox.showinfo("", "引き分け")
        proc = 0
    root.after(100, main)
root = tkinter.Tk()
root.title("リバーシ")
root.resizable(False, False)
root.bind("<Button>", click)
cvs = tkinter.Canvas(width=640, height=700, bg="green")
cvs.pack()
root.after(100, main)
root.mainloop()

computer_1()関数で打つマスを決める

新たに組み込んだプログラムで、優先的に打つべきマスを二次元リストで定義し、現在の局面で打てるマスの中から、優先度の高いマスを選んでいます。

実行画面は省略します。実際にプレイしてコンピュータがランダムに打つより強くなったことを確認してください。ただし格段に強くなるわけではないので、リバーシが上手い方は、ランダムに打つのと大きくは変わらないと感じるかもしれません。

computer_1()関数の内容

computer_1()関数で行っている処理を説明します。打つべきマスの位置を代入する変数sxsyを宣言しています。またはじめに変数p0を代入しておきます。

変数yxを用いた二重ループで盤面全体を調べます。kaeseru(x,

y, iro)>0 という条件式で board[y][x] iro の石を打てるかを調べ、そこが打てるマスで、かつ、point[y][x] pより大きいなら、p point[y][x] の値を代入し、sx syにそのマスの位置を代入しています。

こうすることで二重ループの処理が終わったとき、打てるマスの中で最も point[] [] の値が大きいマスの位置がSXsy に保持されています。そして関数の最後で sx syの値を戻り値として返しています。

この computer_1()関数を 179行目で呼び出し、変数 cx cy に打つべきマスの位置を代入しています。

変更点は他に、前のプログラムをboard.append([0,0,0,0,0,0,0,0) としていたのを、このプログラムから board.append([0]*8) としています。これは二次元リストを準備する記述を簡略化したもので、

思考ルーチンとは無関係です。

モンテカルロ法を理解する

モンテカルロ法を用いた思考ルーチンを実装するには、モンテカルロ法によるシミュレーションの基本的な仕組みを知る必要があります。モンテカルロ法の具体例を学び、その手法を理解しましょう。

モンテカルロ法の具体例を学ぶ

モンテカルロ法は乱数を用いて数値計算やシミュレーションを行う手法です。プログラミングを学習する題材の1つとして、モンテカルロ法で円周率を求める方法が古くから学ばれ

てきました。この節ではモンテカルロ法で円周率を計算するプログラムを確認し、その手法を学びます。

円周率を求める

モンテカルロ法で円周率をどのように計算するかを説明します。一辺の長さがnの正方形内に、無数の点をランダムに打つとします。

この正方形の内部に、各辺に接する正円が描かれています。

正方形の面積はn×nで、円の面積は

n/2×n/2×pai=n×n×pai/4なので、正方形と円の面積の比率は1:pai/4になります。

正方形内に点を打つとき、打った回数を数え、その点が円の中にあればその回数を数えます。点を打った回数を rp、その点が円のだったときの回数を cp とすると、正方形と円の面積比から

1:pai/4rp:cp

という式が成り立ちます。ここから pai= 4*cp/rp という式を導くことができます。

ただし、この式が成り立つのは、rpcp とも十分大きな値のとき(無数の点を打ったとき)になります。

プログラムの確認

正方形内にランダムに点を打ちながら、円周率を計算する様子をプログラムで確認します。次のプログラムはリアルタイムに、乱数で座標を決めた点をキャンバスに打ちながら、打った回数とそれが円の内部にあるときを数え、n = 4*cp/rpの式で円周率を求めていきま

す。

1万回の描画と計算を行うので、パソコンのスペックによっては終了するまでに時間が掛かることがあります。

スペックにもよりますが、WindowsパソコンよりMacのほうが、時間が掛かります。Macをお使いの方は気長に画面を眺めてみてください。

このプログラムは、リバーシのプログラムとは直接関係はありません。モンテカルロ法を理解するために用いています。

monte.py

import tkinter

import random

pi = 0

rp = 0

cp = 0

def main():

    global pi, rp, cp

    x = random.randint(0, 400)

    y = random.randint(0, 400)

    rp += 1

    col = “red”

    if (x-200)*(x-200)+(y-200)*(y-200) <= 200*200:

        cp += 1

        col = “blue”

    ca.create_rectangle(x, y, x+1, y+1, fill=col, width=0)

    ca.update()

    pi = 4*cp/rp

    root.title(“円周率 “+str(pi))

    if rp < 10000:

        root.after(1, main)

root = tkinter.Tk()

ca = tkinter.Canvas(width=400, height=400, bg=”black”)

ca.pack()

main()

root.mainloop()

実行結果

3.128

このプログラムはif after()main()関数を呼び出し、ウィンドウ内に点を打つ様子を表示しながら、円周率を計算しています。点を打つ正方形の一辺の長さを400main()関数の処理を確認しましょう。9~10行目で変数xyに乱数を代入し、(x, y)の座

標に点を打ちます。乱数の範囲は最小値を0、最大値を400としています。点を打った回数を変数 rpで数え、その点が円内にあれば変数 cp で数えています。

点が円の中にあるかは、13行目の if (x-200)*(x-200)+(y-200)*(y-200) <%3D200~200で判定しています。この条件式は、数学で学ぶ2点間の距離を求める式と同じものです。円の中心座標を(200, 200) とし、点を打った(x,y) と中心との距離が円の半径である200以下なら、その点は円内にあるという if文になっています。

この条件式を詳しく説明します。

(x, y) (xo,yo)との距離は 

√(x – x) (x – x) + √(y – y) (y – y) です。

円の中心を(x,y)とすると、

√(x – x) (x – x) + √(y – y) (y – y) <= 半径

なら、座標(x, y) は円の中にあります。

この式の両辺を二乗すれば、ルートを用いずに

(x – x) (x – x) + (y – y) (y – y) <= 半径の二乗

と記述できます。この式をif文の条件式としています。

円周率の計算は18行目の pa

ゲーム開発に用いるモンテカルロ法

モンテカルロ法によるシミュレーションや、モンテカルロ法を用いた思考ルーチンを利用する企業やプログラマーがゲーム業界で増えたと感じています。その理由として、・コンピュータの処理速度が高速になり、短時間で多くの計算が可能となった・大量のデータを扱うゲームが増え、バランス調整などをモンテカルロ法で行うと便利であるなどが挙げられます。

もう1つの大きな理由として、モンテカルロ法は他のアルゴリズムに比べ、一般的に実装が容易であることが挙げられます。リバーシの思考ルーチンを一からプログラミングする場合、長年用いられてきたミニ・マックス法やアルファ・ベータ法よりも、モンテカル

ロ法のほうが簡単に実装できます。

モンテカルロ法を用いた思考ルーチンをどのように実装する?

モンテカルロ法による思考ルーチンを実装するには、現在の局面で打てるマスに石を打っ

たら、その先はコンピュータが黒い石と白い石をランダムに打ち合い、終局まで戦う処理を

用意します。そして勝ち負けを判定し、勝ったらその回数を記録します。

そのようなシミュレーションをなるべく多く行い、勝つ回数が最も多い次の一手(どのマスに打つか)を決めます。

終局までコンピュータが自動的に戦う処理を用意して、コンピュータに戦わせた結果を見て判断するというわけです。

実装に必要な関数

この思考ルーチンを組み込むために、次の4つの機能を持つ関数を用意します。

1、現在の局面を保存する

2、保存した局面の状態に復元する

3、黒と白の石を、勝敗が決まるまでランダムに打っ

4、現在の局面で打てるマスを調べ、そこに石を打った後、3を行い、勝ったらその回数を数える。元の局面に戻し、3と勝敗判定を何度も行う。打てる全てのマスに対してこれを行い、次の一手を打つと最も多く勝つマスを選ぶ

これらの関数を使って、何度も対戦した結果を確認し、より正解

に近い答え(次の一手を打つと勝つ確率の高いマス)を探します。

モンテカルロ法による思考ルーチンを組み込み、リバーシを完成させます。

9、本格的な思考ルーチンを実装する

モンテカルロ法を用いた思考ルーチンを実装します。これでリバーシが完成します。

思考ルーチンの確認

モンテカルロ法による思考ルーチンを組み込んだプログラムを確認します。リバーシの完成版ということというファイル名にしています。

2、で組み込んだ、打つべきマスを定義して簡易的に強くする処理は削除し、モンテカルロ法による思考ルーチンを computer_2() という関数に記述しています。

reverse.py

import tkinter

import tkinter.messagebox

import random

FS = ("Times New Roman", 30)

FL = ("Times New Roman", 80)

BLACK = 1

WHITE = 2

mx = 0

my = 0

mc = 0

proc = 0

turn = 0

msg = ""

space = 0

color = [0]*2

who = ["あなた", "コンピュータ"]

board = []

back = []

for y in range(8):

    board.append([0]*8)

    back.append([0]*8)

def click(e):

    global mx, my, mc

    mc = 1

    mx = int(e.x/80)

    my = int(e.y/80)

    if mx>7: mx = 7

    if my>7: my = 7

def banmen():

    cvs.delete("all")

    cvs.create_text(320, 670, text=msg, fill="silver", font=FS)

    for y in range(8):

        for x in range(8):

            X = x*80

            Y = y*80

            cvs.create_rectangle(X, Y, X+80, Y+80, outline="black")

            if board[y][x]==BLACK:

                cvs.create_oval(X+10, Y+10, X+70, Y+70, fill="black", width=0)

            if board[y][x]==WHITE:

                cvs.create_oval(X+10, Y+10, X+70, Y+70, fill="white", width=0)

    cvs.update()

def ban_syokika():

    global space

    space = 60

    for y in range(8):

        for x in range(8):

            board[y][x] = 0

    board[3][4] = BLACK

    board[4][3] = BLACK

    board[3][3] = WHITE

    board[4][4] = WHITE

# 石を打ち、相手の石をひっくり返す

def ishi_utsu(x, y, iro):

    board[y][x] = iro

    for dy in range(-1, 2):

        for dx in range(-1, 2):

            k = 0

            sx = x

            sy = y

            while True:

                sx += dx

                sy += dy

                if sx<0 or sx>7 or sy<0 or sy>7:

                    break

                if board[sy][sx]==0:

                    break

                if board[sy][sx]==3-iro:

                    k += 1

                if board[sy][sx]==iro:

                    for i in range(k):

                        sx -= dx

                        sy -= dy

                        board[sy][sx] = iro

                    break

# そこに打つといくつ返せるか数える

def kaeseru(x, y, iro):

    if board[y][x]>0:

        return -1 # 置けないマス

    total = 0

    for dy in range(-1, 2):

        for dx in range(-1, 2):

            k = 0

            sx = x

            sy = y

            while True:

                sx += dx

                sy += dy

                if sx<0 or sx>7 or sy<0 or sy>7:

                    break

                if board[sy][sx]==0:

                    break

                if board[sy][sx]==3-iro:

                    k += 1

                if board[sy][sx]==iro:

                    total += k

                    break

    return total

# 打てるマスがあるか調べる

def uteru_masu(iro):

    for y in range(8):

        for x in range(8):

            if kaeseru(x, y, iro)>0:

                return True

    return False

# 黒い石、白い石、いくつかあるか数える

def ishino_kazu():

    b = 0

    w = 0

    for y in range(8):

        for x in range(8):

            if board[y][x]==BLACK: b += 1

            if board[y][x]==WHITE: w += 1

    return b, w

# モンテカルロ法による思考ルーチン

def save():

    for y in range(8):

        for x in range(8):

            back[y][x] = board[y][x]

def load():

    for y in range(8):

        for x in range(8):

            board[y][x] = back[y][x]

def uchiau(iro):

    while True:

        if uteru_masu(BLACK)==False and uteru_masu(WHITE)==False:

            break

        iro = 3-iro

        if uteru_masu(iro)==True:

            while True:

                x = random.randint(0, 7)

                y = random.randint(0, 7)

                if kaeseru(x, y, iro)>0:

                    ishi_utsu(x, y, iro)

                    break

def computer_2(iro, loops):

    global msg

    win = [0]*64

    save()

    for y in range(8):

        for x in range(8):

            if kaeseru(x, y, iro)>0:

                msg += "."

                banmen()

                win[x+y*8] = 1

                for i in range(loops):

                    ishi_utsu(x, y, iro)

                    uchiau(iro)

                    b, w = ishino_kazu()

                    if iro==BLACK and b>w:

                        win[x+y*8] += 1

                    if iro==WHITE and w>b:

                        win[x+y*8] += 1

                    load()

    m = 0

    n = 0

    for i in range(64):

        if win[i]>m:

            m = win[i]

            n = i

    x = n%8

    y = int(n/8)

    return x, y

def main():

    global mc, proc, turn, msg, space

    banmen()

    if proc==0: # タイトル画面

        msg = "先手、後手を選んでください"

        cvs.create_text(320, 200, text="Reversi", fill="gold", font=FL)

        cvs.create_text(160, 440, text="先手(黒)", fill="lime", font=FS)

        cvs.create_text(480, 440, text="後手(白)", fill="lime", font=FS)

        if mc==1: # ウィンドウをクリック

            mc = 0

            if (mx==1 or mx==2) and my==5:

                ban_syokika()

                color[0] = BLACK

                color[1] = WHITE

                turn = 0

                proc = 1

            if (mx==5 or mx==6) and my==5:

                ban_syokika()

                color[0] = WHITE

                color[1] = BLACK

                turn = 1

                proc = 1

    elif proc==1: # どちらの番か表示

        msg = "あなたの番です"

        if turn==1:

            msg = "コンピュータ 考え中."

        proc = 2

    elif proc==2: # 石を打つマスを決める

        if turn==0: # プレイヤー

            if mc==1:

                mc = 0

                if kaeseru(mx, my, color[turn])>0:

                    ishi_utsu(mx, my, color[turn])

                    space -= 1

                    proc = 3

        else: # コンピュータ

            MONTE = [300, 300, 240, 180, 120, 60, 1]

            cx, cy = computer_2(color[turn], MONTE[int(space/10)])

            ishi_utsu(cx, cy, color[turn])

            space -= 1

            proc = 3

    elif proc==3: # 打つ番を交代

        msg = ""

        turn = 1-turn

        proc = 4

    elif proc==4: # 打てるマスがあるか

        if space==0:

            proc = 5

        elif uteru_masu(BLACK)==False and uteru_masu(WHITE)==False:

            tkinter.messagebox.showinfo("", "どちらも打てないので終了です")

            proc = 5

        elif uteru_masu(color[turn])==False:

            tkinter.messagebox.showinfo("", who[turn]+"は打てないのでパスです")

            proc = 3

        else:

            proc = 1

    elif proc==5: # 勝敗判定

        b, w = ishino_kazu()

        tkinter.messagebox.showinfo("終了", "黒={}、白={}".format(b, w))

        if (color[0]==BLACK and b>w) or (color[0]==WHITE and w>b):

            tkinter.messagebox.showinfo("", "あなたの勝ち!")

        elif (color[1]==BLACK and b>w) or (color[1]==WHITE and w>b):

            tkinter.messagebox.showinfo("", "コンピュータの勝ち!")

        else:

            tkinter.messagebox.showinfo("", "引き分け")

        proc = 0

    root.after(100, main)

root = tkinter.Tk()

root.title("リバーシ")

root.resizable(False, False)

root.bind("<Button>", click)

cvs = tkinter.Canvas(width=640, height=700, bg="green")

cvs.pack()

root.after(100, main)

root.mainloop()

実行結果 

Python

モンテカルロ法による思考ルーチンを組み込むために用意した4つの関数を説明します。

save().load() 

局面の状態を保存する save() という関数を記述しています。この関数は保存用の二次元リスト back[][] board[l]の値を代入します。

局面の状態を復元する load() という関数を記述しています。この関数は board[][] back[][] の値を代入します。

uchiau()関数

黒と白の石をランダムに打ち合う uchiau() という関数を記述しています。この関数で黒白ともに打てなくなるまで石を打ち続けます。computer_2()関数の中で、打てるマスに石を配置してから、この関数を実行しています。

この関数は、whileの中にもう1つのwhile が入る構造になっています。外側のwhileでは、石が打てるマスがある限り、iro = 3-iro という式で黒い石と白い石の番を交代し、内側のwhile を実行しています。内側の while は、ランダムなマスに石を打つ処理です。

if uteru_masu(iro)==True という if文で、石を打てるマスがあるなら、内側の whileを実行します。

この関数の引数 iro には BLACK(1)WHITE(2) が入ります。

iro 1(BLACK) なら 3-iro 2(WHITE) に、iro 2(WHITE) なら

3-iro 1(BLACK) になります。

computer_2()関数

computer_2() が、モンテカルロ法による思考ルーチンの中心的な役割を担う関数です。

computer_2() 関数には、何色の石を打つかを指定する引数iro と、ランダムに打ち合い勝敗を調べることを何度行うかを指定する引数 loops を設けています。打ち合うことを繰り返すので、はじめに現在の局面を save()関数で保持しておきます。

この関数の構造は、変数yxを用いた二重の for文の中に、変数iを用いた for文があり、つまり三重のループ(多重ループ)になっています。

yxの二重ループで盤面全体を確認し、(x, y) のマスに iro の石を打てるなら、uchiau() 関数で決着がつくまでランダムに打ち合うことを、変数i for文で loops回行い、勝った回数を数えています。繰り返し試行するので、打ち合った後、load()関数で局面の状態を元に戻していることか確認してください。

勝った回数は、関数内で宣言した win[] というリストに代入しています。例えば左上角にコンピュータが石を打った後、ランダムに打ち合って勝ったらwin[0] 1増やします。

if kaeseru(x, y, iro)>0で打てるマスを見つけたら、石を打ち合う前に win[x+y*8] = 1としてwin[]1を代入しています。これは、勝つ回数が最も多いマスはどれかを調べるときに、それを行う記述を簡潔にするためです。勝つ回数が最も多いマスを選ぶ処理を説明します。

勝つ回数が最も多いマスを選ぶ

computer_2()関数で、勝つ回数が最も多いマスを選ぶのは、m=0n=0 と、それに続くfori in range(64)の部分です。win[] の値が最も大きなマスをどのように選んでいるかを説明します。

変数mnを用意し、for文で8×864マス全てを調べていきます。if win[i]>mという条件式が成り立てば、m win[i] の値を代入し、nにはマスの番号(i の値)を代入しています。こうして繰り返しが終わると、mwin[]の中で最も大きな値が、nにそのマスの番号が

代入されています。

nの値からx = n%8y = int(n/8) という式で、マスの位(board[y][x] yxの値)を求めています。マスの番号と位置を図示します。プログラムと次の図を合わせて確認してください。

例えばn20のとき、x20%84y int(20/8)2になります。n20のマスはboard[2][4]であることを図で確認しましょう。

求めたxyの値は、関数の最後で戻り値として returnしています。以上の仕組みで、この関数を呼び出すと、その局面で、打つと勝つ可能性が最も高いマスが見つかるようになっています。

ランダムに打ち合って勝てなかったときも、そのマスに打たなくてはならないことがあります。負けが確定して何度シミュレーションしても負けるときなどです。その場合 win[] は加算されませんが、打てるマスの win] 1を入れておけば、for i in range(64)のブロックにある if win[i]>mという記述だけで、打つマスを決めることができます。そのためにwin[x+y*8] = 1 としているのです。

思考中ということが判るようにする

コンピュータの思考にある程度の時間を費やすので、その間、ゲーム画面が止まると、プレイヤーはストレスを感じたり、あるいは不具合が起きてソフトウェアが止まったのではないかと心配になります。そこでコンピュータの思考中、「コンピュータ 考え中.」という文字列のピリオドを増やし、処理が進んでいることが判るようにしています。computer_2() 関数の msg += “.” banmen()でそれを行っています。

コンピュータの思考時間を短くする

computer_2() iro loops2つの引数があり、loopsでランダムに打ち合い勝敗を調べる回数を指定します。loops をいくつにするかを、main()関数のMONTE = [300, 300, 240, 180, 120,60, 1] と定義しています。続く213行目でcx, cy =

computer_2(color[turn), MONTE[int(space/10)]) し、盤上の空きマスの数に応じてloops の値を変え、computer_2() を呼び出しています。

space の値は、まだ石を打っていないマスの数で、はじめに 60 を代入し、石を打つごとに1減らしています。その数と、ランダムに打ち合い勝敗を調べる回数(試行回数)を表で示します。

対戦を始めてしばらくは試行回数を少なくし、コンピュータが短時間で石を打つようにしています。そして後半ほど試行回数を多くしています。

リバーシ、将棋、囲碁のような二人で対戦するゲームで、はじめから相手が長考すると、多くの人は早く打って欲しいという気持ちになりがちです。一方、局面が進むと自分も考える必要があるので、ゲームの中盤や終盤で相手が長く考えても、序盤ほどは待たされるストレスを感じないことが多いでしょう。

そのような人の心理を想像し、後半ほどモンテカルロ法の試行回数を増やすようにしています。また、ゲームの序盤は試行回数が少なくても、勝敗にはさほど大きな影響はないと考えられます。これがコンピュータの思考時間を調整し、プレイヤーにストレスを与えないエ夫になります。

 computer_1() よりも強くなっています

もっと強くするには

この完成版のリバーシで何度も遊んでみると、序盤から中盤でプレイヤーが角を取りやすくなるマスに石を打つなど、コンピュータが定石を無視した打ち方をすることがあるのに気付きます。モンテカルロ法の計算上、そこに打つことが決まったわけですが、リバー

シは定石から外れた打ち方をすると、負ける確率がぐんと上がってしまいます。リバーシをある程度プレイしたことのある方は、一手をミスったと後悔したときから急に不利になる経験、あるいは逆に相手がミスを犯し、そこから急に有利になる経験をされたことがあ

ると思います。序盤から中盤にかけて定石も成り立つようにプログラムを改良すれば、コンピュータをより強くすることができるでしょう。

新しい処理を追加せず簡易的に強くするなら、モンテカルロ法の試行回数を増やせばよいです。ただし試行回数を増やす際には、プレイヤーにストレスを与えるほどの長考になってはいけません。また著者が実験した結果では、このプログラムでは100回の試行より200回の試行のほうが強くなりますが、200300では300回のほうが気持ち強くなる程度で、それ以上試行回数を増やしても格段に強くなることはありませんでした。モンテカルロ法は一般的に試行回数を増やすほど正しい解に近付くものですが、リバーシは打ち方によって局面が刻一刻と変化し、1つの定まった答えがあるものではなく、また局面は爆発的に増えていくので、数百回程度まで試行回数を増やすだけでは完璧な答えが出ないと想像できます。

それから今回組み込んだモンテカルロ法は、現在の局面で打てる全てのマスに対し、同じ回数だけ調べる簡単な仕組みになっています。負ける可能性の高いマスは探索を打ち切り、勝てる可能性のあるマスをもっと調べるようにするなどの工夫で、さらに強くできる

のです。

終わりに~今後ますます必要になるコンピュータ関連の知識~

21世紀は世界に存在するあらゆる機器や機械に電子回路が組み込まれ、それらがプログラムにより制御される時代になりました。冷蔵庫やエアコンなどの家電、自動車や電車などの乗り物、信号機や道路わきに置かれている自動販売機など、プログラムにより動いて

いるものを数え上げればキリがありません。我々の生活はもはや電子回路とプログラム無しには成り立たず、コンピュータに関するしっかりとした知識を持つことが、誰にとってもますます必要になることでしょう。

さて、そのような流れの中で政府がプログラミングを義務教育化したことは意義のあることです。欧米諸国は日本より先行してプログラミング教育に力を入れてきたと言われています。経済大国日本の地位を没落させないためにも義務教育でプログラミングを学ばせることは必要不可欠でしょうが、私は何より子供たちが平等にコピュータの仕組みやプログラミングを学べる機会を得られることが素晴らしいと思います。

ただ1つ懸念していることがあります。私にとっては学校教育で学んだことの多くは、面白くなかった思い出があり、同様の思いを持つ方も多いのではないでしょうか。

義務教育化されたプログラミングが、小難しくつまらない授業にならないことを願います。

最新情報をチェックしよう!
>プログラミング 独学

プログラミング 独学

本当にプログラミングを学びたい人のためになるブログにしたいと思っていますので、些細なことでも気が付いたのであればご報告いただけると幸いです。

CTR IMG