Pythonで〇×ゲームのAIを一から作成する　その234　原始モンテカルロ法による〇× ゲームの AI の実装

Posted at 2026-06-28

目次と前回の記事

Python のバージョンとこれまでに作成したモジュール

本記事のプログラムは Python のバージョン 3.13 で実行しています。また、numpy のバージョンは 2.3.5 です。

リンク	説明
marubatsu.py	Marubatsu、Marubatsu_GUI クラスの定義
ai.py	AI に関する関数
mbtest.py	テストに関する関数
util.py	ユーティリティ関数の定義
tree.py	ゲーム木に関する Node、Mbtree クラスなどの定義
gui.py	GUI に関する処理を行う基底クラスとなる GUI クラスの定義

AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

原始モンテカルロ法による〇× ゲームの AI の実装

前回の記事では下記の原始モンテカルロ法のアルゴリズムで必要となるプレイアウトの処理の高速化を行いました。

現在の局面から合法手を着手したすべての局面に対して下記の計算を行う
1. ゲームの決着がつくまで乱数を利用してランダムな着手を行い続け、その結果を記録する。この作業をプレイアウトと呼ぶ
2. あらかじめ決めておいた回数または、あらかじめ決めておいた時間になるまでプレイアウトを繰り返し、その勝率を計算する
最も高い勝率が計算された局面になる合法手を最善手とする

今回の記事では上記のアルゴリズムで最善手を計算する AI の関数を定義します。

なお、「複数回のプレイアウトを行った場合の勝率」という表記は冗長なので、以後は局面の勝率と引き分け率という用語を、その局面から複数回のプレイアウトを行った場合の勝率と引き分け率という意味で用いることにします。また、勝率はその局面の手番のプレイヤーの勝率を表すことにします。

`ai_pmc` の仕様

AI の関数の名前は原始モンテカルロ（pure monte calro）法¹を用いるので ai_pmc と命名することにします。

下記は ai_pmc の仮引数の一覧で、最善手を計算する局面を代入する mb、playout メソッドを呼び出す際に用いるプレイアウトの設定を代入する pnum、timelimit、これまでに作成した AI の関数で実装したデバッグ表示と分析用の結果を返すかどうかを表す仮引数 debug と analyze を定義することにしました。また、mb 以外の仮引数には下記の表のようなデフォルト値を設定することにしました。他にも下記以外の仮引数に対応する実引数が記述された場合にエラーが発生しないようにするために、*args と **kwargs を定義しました。

仮引数	意味	デフォルト値
`mb`	最善手を計算する局面
`pnum`	プレイアウトの回数	10000
`timelimit`	プレイアウトの処理の制限時間。`None` の場合は制限時間なしを表す	`None`
`debug`	`True` の場合にデバッグ表示を行う	`False`
`analyze`	`True` の場合に分析用のデータを返すようにする	`False`

また、analyze が True の場合は分析用のデータとしてて下記の dict を返り値として返すことにします。

キー	キーの値の意味
`candidate`	最善手の候補手の一覧を表す list
`ratio_by_move`	キーを合法手、キーの値をその合法手を着手した局面からプレイアウトを行った対戦結果の割合（ratio）を表す dict
`playout num`	実際にプレイアウトが行われた回数

次に、上記の仕様に従って ai_pmc を定義しますが、その際に先程の原始モンテカルロ法に問題があることに気が付きましたのでその修正を行うことにします。どのような問題があるかについて少し考えてみて下さい。

原始モンテカルロ法のアルゴリズム修正

先程説明した原始モンテカルロ法のアルゴリズムの手順 2 は「最も高い勝率が計算された局面になる合法手を最善手とする」となっています。対戦結果が勝利と敗北だけしかない場合はこれで問題はありませんが、〇× ゲームの場合は引き分けという結果があるため引き分け率についても考慮する必要があります。そこで、最高勝率が等しい場合は引き分け率がより高い局面になる合法手を最善手とすることにします。

想定される具体例としては、どの合法手を着手しても引き分け以上にしかならない局面があります²。その場合はどの合法手を着手した局面の勝率もすべて 0 % になるため、引き分け率が最も高くなる合法手を最善手とします。

また、同率の最善手が複数存在する場合が言及されていないので、そのような場合はその中からランダムに選択することにします。

下記はそのように修正した原始モンテカルロ法の手順 2 です。

最も高い勝率が計算された局面になる合法手を最善手とする。ただし、最高勝率が等しい場合は引き分け率が最も高い合法手を最善手とする
最善手が複数計算された場合は、その中からランダムに選択した合法手を最善手とする

`ai_pmc` の定義

下記は ai_pmc を定義するプログラムです。なお、最善手の一覧を計算するアルゴリズムは以前の記事で説明した、合法手を着手した局面の中で最も高い評価値を計算するアルゴリズムと同様です。ただし、今回は「最高勝率」と「その際の引き分け率」を記録する必要があるので、best_ratio という変数に「最高勝率」と「その際の引き分け率」を要素とする tuple を記録することにしました。

デバッグ表示に関しては以前の記事で定義した、最も評価値が高い合法手を最善手として計算する AI の関数のデコレータとして用いられる ai_by_score の処理を流用しました。

4 行目：上記で説明した仮引数を持つ関数として ai_pmc を定義する
5 行目：playout メソッドで仮引数 pnum と timelimit に代入された回数と制限時間でプレイアウトを行い、その結果を retval に代入する。playout の返り値のデータ構造を忘れた方は以前の記事を復習すること
6 行目：最善手の一覧を記録する best_moves を空の list で初期化する
7 行目：best_ratio を (-1, 0) という tuple で初期化する。勝率の最小値は 0 なので、最高勝率を表す tuple の要素をそれよりも小さい -1 とすることで、必ず best_ratio が最初の合法手を着手した局面の勝率と引き分け率で更新されることになる
8、9 行目：analyze が True の場合に返り値として返す dict の ratio_by_move のキーの値を計算する変数を空の dict で初期化する
10 ~ 29 行目：プレイアウトの集計結果を表す retval["result"] からそれぞれの合法手を着手した局面の勝率と引き分け率を計算し、最高勝率であった場合に best_moves と best_ratio を更新する。繰り返し処理では move には合法手が、count にはその合法手を着手した局面からプレイアウトを行った場合の集計結果を記録した dict が代入される
11 行目：最初に move の着手を行ったプレイアウトの回数を組み込み関数 sum で計算する
12、13 行目：move の着手を行った局面の勝率と引き分け率を計算する。勝率は現在の局面の手番のプレイヤーの勝数を表す count[mb.turn] を用いて計算する
14 ~ 17 行目：move、move を着手した局面の勝率と引き分け率、これまでに計算した最善手の勝率と引き分け率をデバッグ表示する
18 ~ 23 行目：「勝率が最高勝率よりも大きい」または「勝率と最高勝率が等しく、引き分け率が最高勝率の場合の引き分け率よりも大きい」場合に、最善手と最高勝率の更新とデバッグ表示を行う
24 ~ 27 行目：上記の条件を満たさない場合に、「勝率と最高勝率」と「引き分け率と最高勝率の場合の引き分け率」が等しい場合に、最善手の一覧への move の追加とデバッグ表示を行う
28、29 行目：analyze が True の場合に ratio_by_move に move の勝率と引き分け率を記録する
30 ~ 37 行目：analyze の値に応じた返り値を返す

 1  import random
 2  from ai import dprint
 3  
 4  def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
 5      retval = mb.playout(pnum, timelimit)
 6      best_moves = []
 7      best_ratio = (-1, 0)
 8      if analyze:
 9          ratio_by_move = {}
10      for move, count in retval["result"].items():
11          totalcount = sum(count.values())
12          winratio = count[mb.turn] / totalcount
13          drawratio = count[mb.DRAW] / totalcount
14          dprint(debug, "=" * 50)
15          dprint(debug, f"move {move}")
16          dprint(debug, f"ratio      win: {winratio:.3f} draw {drawratio:.3f}")
17          dprint(debug, f"best ratio win: {best_ratio[0]:.3f} draw {best_ratio[1]:.3f}", )
18          if winratio > best_ratio[0] or (winratio == best_ratio[0] and drawratio > best_ratio[1]):
19              best_ratio = (winratio, drawratio)
20              best_moves = [move]
21              dprint(debug, "UPDATE")
22              dprint(debug, f"  best score {best_ratio}")
23              dprint(debug, f"  best moves {best_moves}")
24          elif winratio == best_ratio[0] and drawratio == best_ratio[1]:
25              best_moves.append(move)
26              dprint(debug, "APPEND")
27              dprint(debug, f"  best moves {best_moves}")
28          if analyze:
29              ratio_by_move[move] = (winratio, drawratio)
30      if analyze:
31          return {
32              "candidate": best_moves,
33              "ratio_by_move": ratio_by_move,
34              "playout num": retval["count"]
35          }
36      else:
37          return random.choice(best_moves)

行番号のないプログラム

import random
from ai import dprint

def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
    retval = mb.playout(pnum, timelimit)
    best_moves = []
    best_ratio = (-1, 0)
    if analyze:
        ratio_by_move = {}
    for move, count in retval["result"].items():
        totalcount = sum(count.values())
        winratio = count[mb.turn] / totalcount
        drawratio = count[mb.DRAW] / totalcount
        dprint(debug, "=" * 20)
        dprint(debug, f"move {move}")
        dprint(debug, f"ratio      win: {winratio:.3f} draw {drawratio:.3f}")
        dprint(debug, f"best ratio win: {best_ratio[0]:.3f} draw {best_ratio[1]:.3f}", )
        if winratio > best_ratio[0] or (winratio == best_ratio[0] and drawratio > best_ratio[1]):
            best_ratio = (winratio, drawratio)
            best_moves = [move]
            dprint(debug, "UPDATE")
            dprint(debug, f"  best score {best_ratio}")
            dprint(debug, f"  best moves {best_moves}")
        elif winratio == best_ratio[0] and drawratio == best_ratio[1]:
            best_moves.append(move)
            dprint(debug, "APPEND")
            dprint(debug, f"  best moves {best_moves}")
        if analyze:
            ratio_by_move[move] = (winratio, drawratio)
    if analyze:
        return {
            "candidate": best_moves,
            "ratio_by_move": ratio_by_move,
            "playout num": retval["count"]
        }
    else:
        return random.choice(best_moves)

下記はゲーム開始時の局面に対して上記で定義した ai_mbc で最善手を計算するプログラムです。実行結果から真ん中のマスの (1, 1) が計算されたことが確認できます。

from marubatsu import Marubatsu

mb = Marubatsu()
print(mb.board.move_to_xy(ai_pmc(mb)))

実行結果

(1, 1)

下記は debug=True と analyze=True を実引数に記述した場合のプログラムです。返り値の dict の表示をわかりやすくするために pprint を利用しました。実行結果に表示される合法手の座標が、整数で表される BitBoard3x3 の座標である点がわかりづらいという問題があるので、その修正を行ってから実行結果について考察することにします。

from pprint import pprint

pprint(ai_pmc(mb, debug=True, analyze=True))

実行結果

====================
move 1
ratio      win: 0.610 draw 0.134
best ratio win: -1.000 draw 0.000
UPDATE
  best score (0.6099656357388317, 0.13402061855670103)
  best moves [1]
====================
move 2
ratio      win: 0.555 draw 0.128
best ratio win: 0.610 draw 0.134
====================
move 4
ratio      win: 0.602 draw 0.122
best ratio win: 0.610 draw 0.134
====================
move 8
ratio      win: 0.515 draw 0.124
best ratio win: 0.610 draw 0.134
====================
move 16
ratio      win: 0.684 draw 0.134
best ratio win: 0.610 draw 0.134
UPDATE
  best score (0.6843525179856115, 0.13399280575539568)
  best moves [16]
====================
move 32
ratio      win: 0.546 draw 0.133
best ratio win: 0.684 draw 0.134
====================
move 64
ratio      win: 0.626 draw 0.131
best ratio win: 0.684 draw 0.134
====================
move 128
ratio      win: 0.535 draw 0.128
best ratio win: 0.684 draw 0.134
====================
move 256
ratio      win: 0.601 draw 0.139
best ratio win: 0.684 draw 0.134
{'candidate': [16],
 'playout num': 10000,
 'ratio_by_move': {1: (0.6099656357388317, 0.13402061855670103),
                   2: (0.5545893719806764, 0.12753623188405797),
                   4: (0.6019766397124887, 0.12219227313566937),
                   8: (0.5151253241140882, 0.12359550561797752),
                   16: (0.6843525179856115, 0.13399280575539568),
                   32: (0.545774647887324, 0.1329225352112676),
                   64: (0.6255792400370713, 0.13067655236329936),
                   128: (0.5347159603246168, 0.12804328223624886),
                   256: (0.6009132420091324, 0.13881278538812786)}}

`ai_pmc` の座標の表示の修正

下記は、board_to_xy メソッドを利用して合法手を (x, y) の座標で表示するように ai_pmc を修正したプログラムです。なお、analyze が False の場合に返り値として計算する最善手はゲーム盤の座標として計算する必要があります。そのため best_moves の計算処理は変更せずに、分析用として (x, y) の座標で最善手の一覧を表す best_movesxy を別途計算することにしました。また、best_movesxy に関する処理を追加した分だけ ai_pmc の処理速度は遅くなりますが、プレイアウトの回数がある程度以上多い場合はプレイアウトの処理時間と比較すると無視できるくらいの短い処理なので、その点を気にする必要はないでしょう。

4 行目：(x, y) の座標で最善手の一覧を記録する best_movesxy を空の list で初期化する
12 行目：move を (x, y) の座標に変換し movexy に代入する
20、26 行目：bestmovesxy に (x, y) の座標を記録する処理を追加する
14、23、28、30 行目：デバッグ表示と ratio_by_move に関する move を（x, y) で座標を表す movexy に修正する
33 行目：best_moves を best_movesxy に修正する

 1  def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
 2      retval = mb.playout(pnum, timelimit)
 3      best_moves = []
 4      best_movesxy = []
 5      best_ratio = (-1, 0)
 6      if analyze:
 7          ratio_by_move = {}
 8      for move, count in retval["result"].items():
 9          totalcount = sum(count.values())
10          winratio = count[mb.turn] / totalcount
11          drawratio = count[mb.DRAW] / totalcount
12          movexy = mb.board.move_to_xy(move)
13          dprint(debug, "=" * 50)
14          dprint(debug, f"move {movexy}")
15          dprint(debug, f"ratio      win: {winratio:.3f} draw {drawratio:.3f}")
16          dprint(debug, f"best ratio win: {best_ratio[0]:.3f} draw {best_ratio[1]:.3f}", )
17          if best_ratio is None or winratio > best_ratio[0] or (winratio == best_ratio[0] and drawratio > best_ratio[1]):
18              best_ratio = (winratio, drawratio)
19              best_moves = [move]
20              best_movesxy = [movexy]
21              dprint(debug, "UPDATE")
22              dprint(debug, f"  best score {best_ratio}")
23              dprint(debug, f"  best moves {best_movesxy}")
24          elif winratio == best_ratio[0] and drawratio == best_ratio[1]:
25              best_moves.append(move)
26              best_movesxy.append(movexy)
27              dprint(debug, "APPEND")
28              dprint(debug, f"  best moves {best_movesxy}")
29          if analyze:
30              ratio_by_move[movexy] = (winratio, drawratio)
31      if analyze:
32          return {
33              "candidate": best_movesxy,
34              "ratio_by_move": ratio_by_move,
35              "playout num": retval["count"]
36          }
37      else:
38          return random.choice(best_moves)

行番号のないプログラム

def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
    retval = mb.playout(pnum, timelimit)
    best_moves = []
    best_movesxy = []
    best_ratio = (-1, 0)
    if analyze:
        ratio_by_move = {}
    for move, count in retval["result"].items():
        totalcount = sum(count.values())
        winratio = count[mb.turn] / totalcount
        drawratio = count[mb.DRAW] / totalcount
        movexy = mb.board.move_to_xy(move)
        dprint(debug, "=" * 50)
        dprint(debug, f"move {movexy}")
        dprint(debug, f"ratio      win: {winratio:.3f} draw {drawratio:.3f}")
        dprint(debug, f"best ratio win: {best_ratio[0]:.3f} draw {best_ratio[1]:.3f}", )
        if best_ratio is None or winratio > best_ratio[0] or (winratio == best_ratio[0] and drawratio > best_ratio[1]):
            best_ratio = (winratio, drawratio)
            best_moves = [move]
            best_movesxy = [movexy]
            dprint(debug, "UPDATE")
            dprint(debug, f"  best score {best_ratio}")
            dprint(debug, f"  best moves {best_movesxy}")
        elif winratio == best_ratio[0] and drawratio == best_ratio[1]:
            best_moves.append(move)
            best_movesxy.append(movexy)
            dprint(debug, "APPEND")
            dprint(debug, f"  best moves {best_movesxy}")
        if analyze:
            ratio_by_move[movexy] = (winratio, drawratio)
    if analyze:
        return {
            "candidate": best_movesxy,
            "ratio_by_move": ratio_by_move,
            "playout num": retval["count"]
        }
    else:
        return random.choice(best_moves)

修正箇所

def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
    retval = mb.playout(pnum, timelimit)
    best_moves = []
+   best_movesxy = []
    best_ratio = (-1, 0)
    if analyze:
        ratio_by_move = {}
    for move, count in retval["result"].items():
        totalcount = sum(count.values())
        winratio = count[mb.turn] / totalcount
        drawratio = count[mb.DRAW] / totalcount
+       movexy = mb.board.move_to_xy(move)
        dprint(debug, "=" * 50)
-       dprint(debug, f"move {move}")
+       dprint(debug, f"move {movexy}")
        dprint(debug, f"ratio      win: {winratio:.3f} draw {drawratio:.3f}")
        dprint(debug, f"best ratio win: {best_ratio[0]:.3f} draw {best_ratio[1]:.3f}", )
        if best_ratio is None or winratio > best_ratio[0] or (winratio == best_ratio[0] and drawratio > best_ratio[1]):
            best_ratio = (winratio, drawratio)
            best_moves = [move]
+           best_movesxy = [movexy]
            dprint(debug, "UPDATE")
            dprint(debug, f"  best score {best_ratio}")
-           dprint(debug, f"  best moves {best_moves}")
+           dprint(debug, f"  best moves {best_movesxy}")
        elif winratio == best_ratio[0] and drawratio == best_ratio[1]:
            best_moves.append(move)
+           best_movesxy.append(movexy)
            dprint(debug, "APPEND")
-           dprint(debug, f"  best moves {best_moves}")
+           dprint(debug, f"  best moves {best_movesxy}")
        if analyze:
-           ratio_by_move[move] = (winratio, drawratio)
+           ratio_by_move[movexy] = (winratio, drawratio)
    if analyze:
        return {
-           "candidate": best_moves,
+           "candidate": best_movesxy,
            "ratio_by_move": ratio_by_move,
            "playout num": retval["count"]
        }
    else:
        return random.choice(best_moves)

処理速度がほんの少しだけ遅くなるため本記事では行いませんが、ai.py の ai_by_score や ai_by_mmscore にも同様の性質があるので、その点が気になる方は上記のように (x, y) の座標が表示されるように修正してみて下さい。

`ai_pmc` の動作の確認

いくつかの条件で debug=True、analyze=True として ai_pmc の動作の確認を行うこで、ai_pmc が理論上のプレイアウトの結果に近い値を計算することと、原始モンテカルロ法のアルゴリズム通りの計算を行うことを確認することにします。

〇の手番の局面での確認

最初に〇の手番の局面での確認を行うことにします。下記は先程と同じゲーム開始時の〇の手番の局面に対して ai_pmc で最善手を計算するプログラムです。実行結果から上記の修正によって合法手の座標が (x, y) の座標でに表示されるようになったことが確認できます。また、デバッグ表示から最善手の一覧のデータが原始モンテカルロ法のアルゴリズムに従って正しく更新されていく様子が確認できます。

pprint(ai_pmc(mb, debug=True, analyze=True))

実行結果

==================================================
move (0, 0)
ratio      win: 0.613 draw 0.112
best ratio win: -1.000 draw 0.000
UPDATE
  best score (0.6129597197898424, 0.11208406304728546)
  best moves [(0, 0)]
==================================================
move (0, 1)
ratio      win: 0.547 draw 0.118
best ratio win: 0.613 draw 0.112
==================================================
move (0, 2)
ratio      win: 0.589 draw 0.143
best ratio win: 0.613 draw 0.112
==================================================
move (1, 0)
ratio      win: 0.554 draw 0.123
best ratio win: 0.613 draw 0.112
==================================================
move (1, 1)
ratio      win: 0.678 draw 0.110
best ratio win: 0.613 draw 0.112
UPDATE
  best score (0.6776715899218071, 0.1103388357949609)
  best moves [(1, 1)]
==================================================
move (1, 2)
ratio      win: 0.538 draw 0.118
best ratio win: 0.678 draw 0.110
==================================================
move (2, 0)
ratio      win: 0.595 draw 0.131
best ratio win: 0.678 draw 0.110
==================================================
move (2, 1)
ratio      win: 0.542 draw 0.123
best ratio win: 0.678 draw 0.110
==================================================
move (2, 2)
ratio      win: 0.590 draw 0.151
best ratio win: 0.678 draw 0.110
{'candidate': [(1, 1)],
 'playout num': 10000,
 'ratio_by_move': {(0, 0): (0.6129597197898424, 0.11208406304728546),
                   (0, 1): (0.5465013286093888, 0.11780336581045173),
                   (0, 2): (0.5885964912280702, 0.14298245614035088),
                   (1, 0): (0.5535880708294502, 0.12301957129543337),
                   (1, 1): (0.6776715899218071, 0.1103388357949609),
                   (1, 2): (0.5377777777777778, 0.11822222222222223),
                   (2, 0): (0.594959495949595, 0.13141314131413143),
                   (2, 1): (0.5422740524781341, 0.12342079689018465),
                   (2, 2): (0.59, 0.1509090909090909)}}

下記は以前の記事で計算した、ゲーム開始後に 1 回の着手を行った局面からプレイアウトを行った場合の理論上の確率を表す表です。上記の実行結果と見比べてかなり近い〇の勝率と引き分け率が計算されていることを確認して下さい。また、その中でも最も〇の勝率が高い (1, 1) だけが最善手の候補（candidate）として計算されていることが確認できます。

局面	〇の勝率	× の勝率	引き分け率
`o..`　`..o`　`...`　`...` `...`　`...`　`...`　`...` `...`　`...`　`o..`　`..o`	60.7%	26.4%	12.9 %
`...`　`.o.`　`...`　`...` `o..`　`...`　`..o`　`...` `...`　`...`　`...`　`.o.`	53.6%	33.6%	12.9 %
`...` `.o.` `...`	69.3%	19.3%	11.4 %

× の手番の局面での確認

次に下記のプログラムでゲーム開始後に真ん中の (1, 1) に着手を行った × の手番の局面に対して ai_pmc で最善手を計算することにします。この局面は × の手番の局面なので、勝率は × の勝率を表す点に注意して下さい。

mb = Marubatsu()
mb.cmove(1, 1)
print(mb)
pprint(ai_pmc(mb, debug=True, analyze=True))

実行結果

Turn x
...
.O.
...

==================================================
move (0, 0)
ratio      win: 0.255 draw 0.110
best ratio win: -1.000 draw 0.000
UPDATE
  best score (0.25494853523357086, 0.110055423594616)
  best moves [(0, 0)]
==================================================
move (0, 1)
ratio      win: 0.164 draw 0.104
best ratio win: 0.255 draw 0.110
==================================================
move (0, 2)
ratio      win: 0.216 draw 0.125
best ratio win: 0.255 draw 0.110
==================================================
move (1, 0)
ratio      win: 0.146 draw 0.117
best ratio win: 0.255 draw 0.110
==================================================
move (1, 2)
ratio      win: 0.159 draw 0.099
best ratio win: 0.255 draw 0.110
==================================================
move (2, 0)
ratio      win: 0.216 draw 0.105
best ratio win: 0.255 draw 0.110
==================================================
move (2, 1)
ratio      win: 0.155 draw 0.097
best ratio win: 0.255 draw 0.110
==================================================
move (2, 2)
ratio      win: 0.226 draw 0.109
best ratio win: 0.255 draw 0.110
{'candidate': [(0, 0)],
 'playout num': 10000,
 'ratio_by_move': {(0, 0): (0.25494853523357086, 0.110055423594616),
                   (0, 1): (0.1635777598710717, 0.10394842868654311),
                   (0, 2): (0.21643612693246542, 0.12530512611879577),
                   (1, 0): (0.14557485525227462, 0.11745244003308519),
                   (1, 2): (0.15866558177379983, 0.09926769731489016),
                   (2, 0): (0.21610845295055822, 0.10526315789473684),
                   (2, 1): (0.15467904098994587, 0.09744779582366589),
                   (2, 2): (0.22620904836193448, 0.10920436817472699)}}

実行結果の ratio_by_move から下記の事が確認できます。

同一局面になる 4 隅の合法手の勝率はほぼ等しい
同一局面になる 4 辺の合法手の勝率はほぼ等しい
4 隅の合法手のほうが 4 辺の合法手よりも勝率が高く、4 隅の中で最も勝率高い (0, 0) が最善手として計算された

次に、上記の結果が理論上の確率に近い値になることを確認することにします。

下記は以前の記事で計算してファイルに保存した、各局面でのプレイアウトの結果の理論上の確率を記録した Mbtree のデータをファイルから読み込み、上記のプログラムで合法手を着手したそれぞれの局面でのプレイアウト結果の理論上の確率を表示するプログラムです。

3 行目：Mbtree の load メソッドでファイルに保存した Mbtree のデータを読み込む
4 行目：処理の過程でゲーム盤のクラスの xy_to_move と move_to_xy メソッドを利用する必要があるので、ゲーム盤を表すクラスのインスタンスをゲーム開始時の局面を表すゲーム木のルートノードである mbtree.root から取り出して board に代入する
5 行目：(1, 1) の合法手のゲーム盤の座標を計算する
6 行目：ゲーム開始時の局面を表す mbtree.root に対して (1, 1) を着手した局面を表す子ノードを、「合法手をキー、キーの値をその合法手を着手した局面を表す子ノード」とする dict が代入された children_by_move 属性を利用して計算して node に代入する
7 ~ 11 行目：node の children_by_move 属性に対する繰り返し処理を行うことで、node のそれぞれの子ノードに対する処理を行う
8 行目：node に対して行われた着手を表す move を (x, y) の座標に変換する
9、10 行目：node の局面からのプレイアウトの結果の理論上の確率は playout_prob 属性に代入されているので、そこから × の手番を表すnode.turn の手番の勝率と引き分け率を参照する
11 行目：行われた着手、× の手番の勝率、引き分け率を表示する

 1  from tree import Mbtree
 2  
 3  mbtree = Mbtree.load("../data/playout")
 4  board = mbtree.root.mb.board
 5  centermove = board.xy_to_move(1, 1)
 6  node = mbtree.root.children_by_move[centermove]
 7  for move, childnode in node.children_by_move.items():
 8      movexy = board.move_to_xy(move)
 9      winprob = childnode.playout_prob[node.mb.turn]
10      drawprob = childnode.playout_prob[node.mb.DRAW]
11      print(f"{movexy} x win prob {winprob:.3f} draw prob {drawprob:.3f}")

行番号のないプログラム

from tree import Mbtree

mbtree = Mbtree.load("../data/playout")
board = mbtree.root.mb.board
centermove = board.xy_to_move(1, 1)
node = mbtree.root.children_by_move[centermove]
for move, childnode in node.children_by_move.items():
    movexy = board.move_to_xy(move)
    winprob = childnode.playout_prob[node.mb.turn]
    drawprob = childnode.playout_prob[node.mb.DRAW]
    print(f"{movexy} x win prob {winprob:.3f} draw prob {drawprob:.3f}")

実行結果

(0, 0) x win prob 0.229 draw prob 0.114
(0, 1) x win prob 0.157 draw prob 0.114
(0, 2) x win prob 0.229 draw prob 0.114
(1, 0) x win prob 0.157 draw prob 0.114
(1, 2) x win prob 0.157 draw prob 0.114
(2, 0) x win prob 0.229 draw prob 0.114
(2, 1) x win prob 0.157 draw prob 0.114
(2, 2) x win prob 0.229 draw prob 0.114

下記はそれぞれの合法手に対する先程の ai_pmc の実行結果と上記の理論上の確率をまとめた表です。上段が × の勝率、下段が引き分け率を表します。表から多少のばらつきはありますが、ai_pmc が理論上の確率に近い値を計算していることが確認できました。

合法手	`ai_pmc` の結果	理論上の確率
(0, 0)	0.255 0.110	0.229 0.114
(0, 1)	0.164 0.104	0.157 0.114
(0, 2)	0.216 0.125	0.229 0.114
(1, 0)	0.146 0.117	0.157 0.114
(1, 2)	0.159 0.099	0.157 0.114
(2, 0)	0.216 0.105	0.229 0.114
(2, 1)	0.155 0.097	0.157 0.114
(2, 2)	0.226 0.109	0.229 0.114

〇が勝利できない局面での確認

次に、下記のプログラムで〇が絶対に勝利できない局面に対して ai_pmc が意図通りの計算を行うことを確認します。

mb = Marubatsu()
mb.cmove(0, 0)
mb.cmove(1, 0)
mb.cmove(0, 1)
mb.cmove(1, 1)
mb.cmove(1, 2)
mb.cmove(0, 2)
print(mb)
pprint(ai_pmc(mb, debug=True, analyze=True))

実行結果

Turn o
ox.
ox.
Xo.

==================================================
move (2, 0)
ratio      win: 0.000 draw 1.000
best ratio win: -1.000 draw 0.000
UPDATE
  best score (0.0, 1.0)
  best moves [(2, 0)]
==================================================
move (2, 1)
ratio      win: 0.000 draw 0.491
best ratio win: 0.000 draw 1.000
==================================================
move (2, 2)
ratio      win: 0.000 draw 0.499
best ratio win: 0.000 draw 1.000
{'candidate': [(2, 0)],
 'playout num': 10000,
 'ratio_by_move': {(2, 0): (0.0, 1.0),
                   (2, 1): (0.0, 0.49097366084640426),
                   (2, 2): (0.0, 0.49866190900981266)}}

この局面では〇が (2, 0) に着手した場合は必ず引き分けになり、それ以外に着手をした場合は × が (2, 0) に着手すれば × の勝利、(2, 0) に着手をしなければ引き分けになります。従って、それぞれの合法手を着手した局面の勝率と引き分け率の理論値は下記の表のようになり、実行結果の ratio_by_move から ai_pmc が理論上の確率に非常に近い値を計算していることが確認できました。

合法手	勝率	引き分け率
(2, 0)	0 %	100 %
(2, 1)	0 %	50 %
(2, 2)	0 %	50 %

また、すべての合法手を着手した局目の勝率が 0 % なので、原始モンテカルロ法のアルゴリズムに従って最も引き分け率が高かった合法手である (2, 0) が最善手として正しく計算されたことが確認できます。

プレイアウトの回数を変化させた場合の確認

これまでのプログラムではプレイアウトの回数を ai_pmc の仮引数 pnum のデフォルト値である 10000 回として計算を行ってきましたので、それとは異なる回数のプレイアウトで ai_pmc の計算を行うことにします。

下記はゲーム開始時の局面に対してプレイアウトの回数を 10 から 100 万まで 10 倍ずつ増やしながら ai_pmc の計算を行うプログラムです。計算の過程の確認はもう十分だと思いましたので下記のプログラムでは analyze のみ True としました。

このプログラムを実行すると、実行結果のようなエラーが発生しました³。このエラーの原因について少し考えてみて下さい。

mb = Marubatsu()
for pnum in [10, 100, 1000, 10000, 100000, 1000000]:
    print(f"pnum {pnum}")
    pprint(ai_pmc(mb, pnum=pnum, analyze=True))
    print()

実行結果

pnum 10

---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
Cell In[9], line 4
      2 for pnum in [10, 100, 1000, 10000, 100000, 1000000]:
      3     print(f"pnum {pnum}")
----> 4     pprint(ai_pmc(mb, pnum=pnum, analyze=True))
      5     print()

Cell In[4], line 10
      8 for move, count in retval["result"].items():
      9     totalcount = sum(count.values())
---> 10     winratio = count[mb.turn] / totalcount
     11     drawratio = count[mb.DRAW] / totalcount
     12     movexy = mb.board.move_to_xy(move)

ZeroDivisionError: division by zero

エラーの原因の検証と修正

pnum 10 の表示の後でエラーが発生していることから pnum の値が 10 の場合にエラーが発生していることがわかります。また、エラーメッセージから winratio の計算で 0 で除算（division by zero）するという、計算できない演算が行われたことが原因であることがわかります。また、そのことから totalcount の値が 0 であることがわかります。

totalcount は pnum 回のプレイアウトの中で、最初に move の合法手が着手された回数を表しますが、pnum が 10 のような小さな数値の場合はプレイアウトで一度も最初に move の合法手が着手されない場合が高確率で生じ、その結果 totalcount が 0 になって 0 除算のエラーが発生します。

例えば、プレイアウトの回数が 9 で合法手の数が 9 の場合は、9 回のプレイアウトで最初に着手された合法手がすべて異なる場合を除くと、いずれかの合法手が着手された回数が 0 回になります。その具体的な確率は、9 回のプレイアウトですべての最初の着手が異なる組み合わせが $9!$、9 回のプレイアウトでの最初の着手の組み合わせが $9^9$ であることから $1 - \frac{9!}{9^9} =$ 約 0.999 = 約 99.9% となります。別の例としては、プレイアウトの回数が合法手の数未満の場合は、いずれかの合法手が絶対に最初に着手されないため必ずこのエラーが発生することになります。

一方、プレイアウトの回数を増やすことでこのエラーが発生する確率は 0 に極めて近くなります。例えばプレイアウトの回数が 10000 回で合法手の数が 6 の場合は、サイコロを 10000 回振って 1 度も特定の出目が出ない場合と同じという、極めて小さな確率（約 $10^{-800}$）でこのエラーが発生します。ただし、どれだけプレイアウトの回数を増やしても残念ながらその確率を 0 にすることはできないので、仮にプレイアウトの回数が一定以上大きな場合でしか計算を行わないことがわかっていたとしてもこのエラーが発生しないようにするべきです。

このエラーが発生しないようにするためには、プレイアウトで一度も着手が行われなかった合法手に対してどのような処理を行うかを決める必要があります。本記事ではそのような、勝率や引き分け率を計算することができない合法手を最善手として選択しないようにプログラムを修正することにします。

そのような修正を行う方法の一つに、最大値を計算する組み込み関数 max を利用した totalcount = max(1, sum(count.values())) によって totalcount の最小値を 1 として勝率と引き分け率を計算するという方法があり、その場合は下記のような計算が行われます。

元の totalcount の値が 1 以上の場合は totalcount の値は変化しないので計算結果は変化しない
元の totalbount の値が 0 の場合は totalcount を 1 として計算する。元の totalcount は勝数と引き分け数の合計なので、この場合は勝数と引き分けの数は必ず 0 となり、勝率と引き分け率はどちらも 0 ÷ 1 = 0 が計算される。その結果、その合法手は他のすべての合法手の勝率と引き分け率が 0 でない限り選択されなくなる

他の方法としては if 文を利用して totalcount が 0 の場合は continue 文で処理を飛ばすというものがあります。if 文を記述する必要がない分だけプログラムを簡潔に記述できるという利点があることから、本記事では上記の方法を採用することにします。

下記はそのように ai_pmc を修正したプログラムです。

3 行目：組み込み関数 max を利用して totalcount の最小値が 1 となるように修正した

1  def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
元と同じなので省略
2      for move, count in retval["result"].items():
3          totalcount = max(1, sum(count.values()))
元と同じなので省略

行番号のないプログラム

def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
    retval = mb.playout(pnum, timelimit)
    best_moves = []
    best_movesxy = []
    best_ratio = (-1, 0)
    if analyze:
        ratio_by_move = {}
    for move, count in retval["result"].items():
        totalcount = max(1, sum(count.values()))
        winratio = count[mb.turn] / totalcount
        drawratio = count[mb.DRAW] / totalcount
        movexy = mb.board.move_to_xy(move)
        dprint(debug, "=" * 50)
        dprint(debug, f"move {movexy}")
        dprint(debug, f"ratio      win: {winratio:.3f} draw {drawratio:.3f}")
        dprint(debug, f"best ratio win: {best_ratio[0]:.3f} draw {best_ratio[1]:.3f}", )
        if best_ratio is None or winratio > best_ratio[0] or (winratio == best_ratio[0] and drawratio > best_ratio[1]):
            best_ratio = (winratio, drawratio)
            best_moves = [move]
            best_movesxy = [movexy]
            dprint(debug, "UPDATE")
            dprint(debug, f"  best score {best_ratio}")
            dprint(debug, f"  best moves {best_movesxy}")
        elif winratio == best_ratio[0] and drawratio == best_ratio[1]:
            best_moves.append(move)
            best_movesxy.append(movexy)
            dprint(debug, "APPEND")
            dprint(debug, f"  best moves {best_movesxy}")
        if analyze:
            ratio_by_move[movexy] = (winratio, drawratio)
    if analyze:
        return {
            "candidate": best_movesxy,
            "ratio_by_move": ratio_by_move,
            "playout num": retval["count"]
        }
    else:
        return random.choice(best_moves)

修正箇所

def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
元と同じなので省略
    for move, count in retval["result"].items():
-       totalcount = sum(count.values())
+       totalcount = max(1, sum(count.values()))
元と同じなので省略

このような 0 除算によるバグは非常によくあるバグの一つです。割り算を行う際は 0 除算が行われないようにすることを気を付けて下さい。

恥ずかしながら上記で説明したのと同じ 0 除算によるバグが以前の記事で定義した analyze_playout にもあることに気が付きましたので、該当する箇所を下記のプログラムのように修正しておくことにします。

total = max(1, sum(counts.values()))

上記の修正後に下記のプログラムを実行すると、実行結果のようにエラーが発生しなくなったことが確認できます。

for pnum in [10, 100, 1000, 10000, 100000, 1000000]:
    print(f"pnum {pnum}")
    pprint(ai_pmc(mb, pnum=pnum, analyze=True))
    print()

実行結果

pnum 10
{'candidate': [(0, 0), (0, 2), (1, 0), (1, 2), (2, 0)],
 'playout num': 10,
 'ratio_by_move': {(0, 0): (1.0, 0.0),
                   (0, 1): (0.0, 0.0),
                   (0, 2): (1.0, 0.0),
                   (1, 0): (1.0, 0.0),
                   (1, 1): (0.0, 0.0),
                   (1, 2): (1.0, 0.0),
                   (2, 0): (1.0, 0.0),
                   (2, 1): (0.0, 0.0),
                   (2, 2): (0.0, 0.0)}}

pnum 100
{'candidate': [(2, 0)],
 'playout num': 100,
 'ratio_by_move': {(0, 0): (0.5833333333333334, 0.25),
                   (0, 1): (0.5, 0.125),
                   (0, 2): (0.5333333333333333, 0.06666666666666667),
                   (1, 0): (0.5, 0.25),
                   (1, 1): (0.6666666666666666, 0.0),
                   (1, 2): (0.5714285714285714, 0.0),
                   (2, 0): (0.7619047619047619, 0.047619047619047616),
                   (2, 1): (0.42857142857142855, 0.2857142857142857),
                   (2, 2): (0.5, 0.5)}}

pnum 1000
{'candidate': [(1, 1)],
 'playout num': 1000,
 'ratio_by_move': {(0, 0): (0.6019417475728155, 0.06796116504854369),
                   (0, 1): (0.5175438596491229, 0.16666666666666666),
                   (0, 2): (0.6929824561403509, 0.09649122807017543),
                   (1, 0): (0.5528455284552846, 0.11382113821138211),
                   (1, 1): (0.7019230769230769, 0.14423076923076922),
                   (1, 2): (0.5272727272727272, 0.09090909090909091),
                   (2, 0): (0.5948275862068966, 0.1206896551724138),
                   (2, 1): (0.5575221238938053, 0.12389380530973451),
                   (2, 2): (0.6310679611650486, 0.14563106796116504)}}

pnum 10000
{'candidate': [(1, 1)],
 'playout num': 10000,
 'ratio_by_move': {(0, 0): (0.6309834638816362, 0.11314186248912098),
                   (0, 1): (0.527124773960217, 0.12296564195298372),
                   (0, 2): (0.6067615658362989, 0.11476868327402136),
                   (1, 0): (0.5568075117370892, 0.12018779342723004),
                   (1, 1): (0.6947935368043088, 0.10861759425493717),
                   (1, 2): (0.5505415162454874, 0.1263537906137184),
                   (2, 0): (0.6139240506329114, 0.12025316455696203),
                   (2, 1): (0.5340406719717065, 0.12024756852343059),
                   (2, 2): (0.6207839562443026, 0.11212397447584321)}}

pnum 100000
{'candidate': [(1, 1)],
 'playout num': 100000,
 'ratio_by_move': {(0, 0): (0.6072675199140786, 0.12646558668218025),
                   (0, 1): (0.5354809843400448, 0.1319910514541387),
                   (0, 2): (0.6132596685082873, 0.12571325061135766),
                   (1, 0): (0.5451559934318555, 0.12506841817186645),
                   (1, 1): (0.6978346456692913, 0.11309949892627058),
                   (1, 2): (0.552236103566902, 0.12230671736375158),
                   (2, 0): (0.6209518697441403, 0.11996779388083736),
                   (2, 1): (0.5380263984915148, 0.13253120229864415),
                   (2, 2): (0.6040316774658028, 0.12544996400287978)}}

pnum 1000000
{'candidate': [(1, 1)],
 'playout num': 1000000,
 'ratio_by_move': {(0, 0): (0.609351364978751, 0.12847547360080674),
                   (0, 1): (0.5359647941084018, 0.12743275405271903),
                   (0, 2): (0.6050867135258701, 0.12945379928541215),
                   (1, 0): (0.5374851677393837, 0.12898673186868506),
                   (1, 1): (0.6921368120947216, 0.11388716509726682),
                   (1, 2): (0.5375753757537576, 0.12837728377283772),
                   (2, 0): (0.607842606868818, 0.12878357542806135),
                   (2, 1): (0.5366019931289973, 0.12870123695989524),
                   (2, 2): (0.6076529919942105, 0.12790266407345424)}}

プレイアウトの回数を変化させた場合の検証

上記の実行結果から下記のことが確認できます。

実行結果の playout num のキーの値から指定した回数のプレイアウトが行われている
プレイアウトが 10 回の場合は着手されなかった合法手がいくつか生じるため、それらの合法手を着手した局面の勝率と引き分け率が 0 として計算される

下記は上記の実行結果の中の (0, 0) の合法手が着手された場合の結果と理論値をまとめた表で、結果を小数点以下第 4 桁で四捨五入しました。また、「計算された最善手の一覧」の列には ai_pmc が計算した最善手の一覧とを表記しました。ただし、最善手の行には〇が勝率する理論上の確率が最も高い合法手を表記しました。興味がある方は他の合法手が着手された場合の結果もまとめてみて下さい。

回数	〇の勝率	引き分け率	計算された最善手の一覧
10	1.000	0.000	(0, 0), (0, 2), (1, 0), (1, 2), (2, 0)
100	0.583	0.250	(2, 0)
1000	0.602	0.068	(1, 1)
10000	0.631	0.113	(1, 1)
100000	0.607	0.126	(1, 1)
1000000	0.609	0.128	(1, 1)
理論値	0.607	0.129	(1, 1)

上記の表から下記のことが確認できます。

プレイアウトの回数が 10 回と 100 回の場合はプレイアウトの回数が少ないため、大数の法則から勝率が理論値から大きく離れた値になる確率が高く、上記のように実際に理論上の確率による最善手である (1, 1) ではない合法手が最善手として計算されている
それぞれの勝率と引き分け率は、プレイアウトの回数が大きくなるほど大数の法則からばらつきが減るため理論値に近づいていく
表には示していないが、他の合法手の勝率と引き分け率もプレイアウトの回数が大きくなるほど理論値に近づいていくため、プレイアウトの回数が 1000 回以上の場合は理論上の勝率が最も高くなる (1, 1) だけ最善手として計算されている

制限時間を変化させた場合の確認と検証

次にプレイアウトの時間制限を変化させた場合の処理の確認を行うことにします。下記はゲーム開始時の局面に対してプレイアウトの回数を 1 億回とし、制限時間を 0.001 秒から 100 秒まで 10 倍ずつ増やしながら ai_pmc の計算を行うプログラムです。

for timelimit in [0.001, 0.01, 0.1, 1, 10]:
    print(f"timelimit {timelimit}")
    pprint(ai_pmc(mb, pnum=100000000, timelimit=timelimit, analyze=True))
    print()

実行結果

timelimit 0.001
{'candidate': [(0, 1), (1, 1), (2, 0), (2, 2)],
 'playout num': 23,
 'ratio_by_move': {(0, 0): (0.5, 0.0),
                   (0, 1): (1.0, 0.0),
                   (0, 2): (0.5, 0.0),
                   (1, 0): (0.6666666666666666, 0.0),
                   (1, 1): (1.0, 0.0),
                   (1, 2): (0.5, 0.0),
                   (2, 0): (1.0, 0.0),
                   (2, 1): (0.5, 0.0),
                   (2, 2): (1.0, 0.0)}}

timelimit 0.01
{'candidate': [(2, 2)],
 'playout num': 200,
 'ratio_by_move': {(0, 0): (0.6, 0.16),
                   (0, 1): (0.5, 0.13636363636363635),
                   (0, 2): (0.43478260869565216, 0.21739130434782608),
                   (1, 0): (0.2222222222222222, 0.25925925925925924),
                   (1, 1): (0.631578947368421, 0.10526315789473684),
                   (1, 2): (0.5185185185185185, 0.07407407407407407),
                   (2, 0): (0.6, 0.2),
                   (2, 1): (0.4666666666666667, 0.0),
                   (2, 2): (0.8235294117647058, 0.058823529411764705)}}

timelimit 0.1
{'candidate': [(1, 1)],
 'playout num': 7165,
 'ratio_by_move': {(0, 0): (0.6022443890274314, 0.13466334164588528),
                   (0, 1): (0.5381818181818182, 0.1296969696969697),
                   (0, 2): (0.6214196762141968, 0.11706102117061021),
                   (1, 0): (0.5180572851805728, 0.11083437110834371),
                   (1, 1): (0.6803594351732991, 0.1245186136071887),
                   (1, 2): (0.5428571428571428, 0.14545454545454545),
                   (2, 0): (0.6062111801242236, 0.12919254658385093),
                   (2, 1): (0.5438144329896907, 0.12628865979381443),
                   (2, 2): (0.6022443890274314, 0.13341645885286782)}}

timelimit 1
{'candidate': [(1, 1)],
 'playout num': 90402,
 'ratio_by_move': {(0, 0): (0.6098280098280098, 0.12953316953316954),
                   (0, 1): (0.538943961157192, 0.12937487355856767),
                   (0, 2): (0.6166931953840031, 0.12475129327497016),
                   (1, 0): (0.5411741721207385, 0.1320699423659275),
                   (1, 1): (0.6977392689971118, 0.11622348371676128),
                   (1, 2): (0.5310492505353319, 0.13023165271559276),
                   (2, 0): (0.6120040691759918, 0.1299084435401831),
                   (2, 1): (0.5382622558788361, 0.12136309286568354),
                   (2, 2): (0.6082463782798095, 0.12703880052679567)}}

timelimit 10
{'candidate': [(1, 1)],
 'playout num': 902011,
 'ratio_by_move': {(0, 0): (0.6061254980079681, 0.12840637450199202),
                   (0, 1): (0.5373855569644266, 0.1279964855879152),
                   (0, 2): (0.6086085986372873, 0.12757500896521495),
                   (1, 0): (0.5376069659210329, 0.12760846719711755),
                   (1, 1): (0.690885984749935, 0.113765084956071),
                   (1, 2): (0.5355865486442744, 0.12910863788039242),
                   (2, 0): (0.6055547804596098, 0.13118609610746815),
                   (2, 1): (0.5364871715856337, 0.12743918804735727),
                   (2, 2): (0.6102138194014654, 0.12752300904390185)}}

下記は先ほどと同様に実行結果の中の (0, 0) の合法手が着手された場合の結果と理論値をまとめた表です。

制限時間	回数	〇の勝率	引き分け率	計算された最善手の一覧
0.001	23	0.500	0.000	(0, 1), (1, 1), (2, 0), (2, 2)
0.01	200	0.600	0.160	(2, 2)
0.1	7165	0.602	0.135	(1, 1)
1	90402	0.609	0.130	(1, 1)
10	902011	0.606	0.128	(1, 1)
理論値		0.607	0.129	(1, 1)

上記の表から下記の事がわかります。

多少の誤差はあるが、制限時間を 10 倍にするとプレイアウトの回数もほぼ 10 倍になる
制限時間を増やすとプレイアウトの回数が多くなるため、大数の法則により計算結果が理論上の確率に近くなる
制限時間を 0.1 秒以上にすると計算結果の誤差が十分に小さくなるため、最善手として理論上の勝率が最も高くなる (1, 1) だけが計算される

プレイアウトはゲームの決着がつくまで着手を行い続けるので、ゲームの局面によって処理時間が大きく異なります。〇× ゲームの場合は最大で 9 回の着手を行うと必ずゲームの決着がつくので、着手を多く行った局面のほうがプレイアウトの処理時間が短くなります。

下記はそのことを確認するプログラムで、5 回の着手を行った局面に対して先程と同様の制限時間で ai_pmc を実行しています。

mb.cmove(0, 0)
mb.cmove(0, 1)
mb.cmove(0, 2)
mb.cmove(1, 0)
mb.cmove(1, 1)
for timelimit in [0.001, 0.01, 0.1, 1, 10]:
    print(f"timelimit {timelimit}")
    pprint(ai_pmc(mb, pnum=100000000, timelimit=timelimit, analyze=True))
    print()

実行結果

timelimit 0.001
{'candidate': [(2, 2)],
 'playout num': 59,
 'ratio_by_move': {(1, 2): (0.0, 0.0),
                   (2, 0): (0.0, 0.35294117647058826),
                   (2, 1): (0.0, 0.0),
                   (2, 2): (0.0, 0.3888888888888889)}}

timelimit 0.01
{'candidate': [(2, 0)],
 'playout num': 888,
 'ratio_by_move': {(1, 2): (0.0, 0.0),
                   (2, 0): (0.0, 0.32286995515695066),
                   (2, 1): (0.0, 0.0),
                   (2, 2): (0.0, 0.29357798165137616)}}

timelimit 0.1
{'candidate': [(2, 0)],
 'playout num': 13867,
 'ratio_by_move': {(1, 2): (0.0, 0.0),
                   (2, 0): (0.0, 0.34169371496016526),
                   (2, 1): (0.0, 0.0),
                   (2, 2): (0.0, 0.330848623853211)}}

timelimit 1
{'candidate': [(2, 0)],
 'playout num': 228419,
 'ratio_by_move': {(1, 2): (0.0, 0.0),
                   (2, 0): (0.0, 0.3331477098705276),
                   (2, 1): (0.0, 0.0),
                   (2, 2): (0.0, 0.3325197970256176)}}

timelimit 10
{'candidate': [(2, 0)],
 'playout num': 2347052,
 'ratio_by_move': {(1, 2): (0.0, 0.0),
                   (2, 0): (0.0, 0.33381425597803316),
                   (2, 1): (0.0, 0.0),
                   (2, 2): (0.0, 0.33328782692091097)}}

下記は 2 つの実行結果のプレイアウトの回数まとめた表です。いずれの場合も手数が進んだ局面のほうが同じ制限時間で比較するとプレイアウトの回数が増えることが確認できます。

制限時間	ゲーム開始時の局面	5 手の着手を行った局面
0.001	23	59
0.01	200	888
0.1	7165	13867
1	90402	228419
10	902011	2347052

このことから、原始モンテカルロ法では局面によって十分な精度の計算結果を得るために必要な処理時間が異なることがわかります。

なお、本記事では省略しますが、興味がある方は上記の実行結果から制限時間を長くすることで計算結果が理論値に近づいていくことを確認してみて下さい。

以上で本記事での ai_pmc の検証は終了します。興味がある方は他の条件での検証を行ってみて下さい。

`ai2` と `ai14s` との対戦

原始モンテカルロ法による AI の強さを確認するために、ランダムな着手を行う ai2s と弱解決の AI である ai14s と下記の条件で対戦を行うことにします。

処理に時間がかかるので対戦回数は 1000 回とする
プレイアウトの回数を 5、10、50、100、1000、10000 回として対戦を行う
プレイアウトの回数を 1 億回、制限時間を 0.0001、0.0005、0.001、0.01、0.1 秒として対戦を行う

`ai_pmc` の改良

この記事を書いている途中で ai_pmc の処理速度を少しだけ改善する方法を思いつきましたので先にその改良を行うことにします。

現状の ai_pmc はどの局面に対してもプレイアウトを行っていますが、合法手の数が 1 つしかない場合はその合法手が最善手であることが確定しているのでプレイアウトを行う必要はありません。そこで下記のプログラムのように合法手が 1 つしかない 8 手目の局面ではプレイアウトを行わないように ai_pmc を修正することにします。12 行目以降のプログラムに変更はありません。

2 ~ 11 行目：8 手目の局面の場合は 1 つしかない合法手が最善手となる
3 行目：calc_legal_mnoves では要素が 1 つの list が計算され、その 0 番の要素が最善手となる
4 ~ 9 行目：analyze が True の場合の処理を行う。プレイアウトは行っていないので ratio_by_move のキーの値は空の dict とし、count のキーの値は 0 とした
10、11 行目：analyze が False の場合に最善手を返り値として返す

 1  def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
 2      if mb.move_count == 8:
 3          best_move = mb.calc_legal_moves()[0]
 4          if analyze:
 5              return {
 6                  "candidate": [mb.board.move_to_xy(best_move)],
 7                  "ratio_by_move": {},
 8                  "playout num": 0,
 9              }
10          else:
11              return best_move
元と同じなので省略

行番号のないプログラム

def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
    if mb.move_count == 8:
        best_move = mb.calc_legal_moves()[0]
        if analyze:
            return {
                "candidate": [mb.board.move_to_xy(best_move)],
                "ratio_by_move": {},
                "playout num": 0,
            }
        else:
            return best_move
    retval = mb.playout(pnum, timelimit)
    best_moves = []
    best_movesxy = []
    best_ratio = (-1, 0)
    if analyze:
        ratio_by_move = {}
    for move, count in retval["result"].items():
        totalcount = max(1, sum(count.values()))
        winratio = count[mb.turn] / totalcount
        drawratio = count[mb.DRAW] / totalcount
        movexy = mb.board.move_to_xy(move)
        dprint(debug, "=" * 50)
        dprint(debug, f"move {movexy}")
        dprint(debug, f"ratio      win: {winratio:.3f} draw {drawratio:.3f}")
        dprint(debug, f"best ratio win: {best_ratio[0]:.3f} draw {best_ratio[1]:.3f}", )
        if best_ratio is None or winratio > best_ratio[0] or (winratio == best_ratio[0] and drawratio > best_ratio[1]):
            best_ratio = (winratio, drawratio)
            best_moves = [move]
            best_movesxy = [movexy]
            dprint(debug, "UPDATE")
            dprint(debug, f"  best score {best_ratio}")
            dprint(debug, f"  best moves {best_movesxy}")
        elif winratio == best_ratio[0] and drawratio == best_ratio[1]:
            best_moves.append(move)
            best_movesxy.append(movexy)
            dprint(debug, "APPEND")
            dprint(debug, f"  best moves {best_movesxy}")
        if analyze:
            ratio_by_move[movexy] = (winratio, drawratio)
    if analyze:
        return {
            "candidate": best_movesxy,
            "ratio_by_move": ratio_by_move,
            "playout num": retval["count"]
        }
    else:
        return random.choice(best_moves)

修正箇所

def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
+   if mb.move_count == 8:
+       best_move = mb.calc_legal_moves()[0]
+       if analyze:
+           return {
+               "candidate": [mb.board.move_to_xy(best_move)],
+               "ratio_by_move": {},
+               "playout num": 0,
+           }
+       else:
+           return best_move
元と同じなので省略

上記の修正後に下記のプログラムで 8 回の着手を行った局面に対して ai_pmc を実行すると、実行結果のように正しい処理が行われることが確認できます。

mb = Marubatsu()
mb.cmove(0, 0)
mb.cmove(1, 0)
mb.cmove(2, 0)
mb.cmove(0, 1)
mb.cmove(1, 1)
mb.cmove(2, 1)
mb.cmove(1, 2)
mb.cmove(2, 2)
print(mb)
pprint(ai_pmc(mb, debug=True, analyze=True))

実行結果

Turn o
oxo
xox
.oX

{'candidate': [(0, 2)], 'playout num': 0, 'ratio_by_move': {}}

なお、この修正によってこの後で行う対戦の処理時間がほんの少しだけ向上しましたが、残念ながら筆者が期待していたほどではありませんでした。その原因の一つはこの後の対戦結果からわかるように、引き分けとなる対戦の割合が少ないため 8 手目まで着手が行われる対戦があまり多くないからではないかと思います。また、対戦の中での 8 手目の局面に対する ai_pmc の処理時間が、他の局面の ai_pmc の処理時間と比較して短いため、8 手目の局面の処理時間を短縮しても全体の処理時間に大きな影響を与えないことも原因の一つではないかと思います。興味がある方は実際にそのことを検証してみて下さい。

`ai2s` との対戦

下記は ai2s と対戦を行うプログラムです。

from ai import ai_match, ai2s, ai14s

for pnum in [5, 10, 50, 100, 1000, 10000]:
    print(f"pnum {pnum}")
    ai_match(ai=[ai_pmc, ai2s], params=[{"pnum": pnum}, {}], match_num=1000)
    
for timelimit in [0.0001, 0.0005, 0.001, 0.01, 0.1]:
    print(f"timelimit {timelimit}")
    ai_match(ai=[ai_pmc, ai2s], params=[{"pnum": 100000000, "timelimit": timelimit}, {}],
             match_num=1000)

実行結果

pnum 5
ai_pmc VS ai2s
100%|██████████| 1000/1000 [00:00<00:00, 1349.38it/s]
count     win    lose    draw
o         807     119      74
x         573     300     127
total    1380     419     201

ratio     win    lose    draw
o       80.7%   11.9%    7.4%
x       57.3%   30.0%   12.7%
total   69.0%   20.9%   10.1%

pnum 10
ai_pmc VS ai2s
100%|██████████| 1000/1000 [00:00<00:00, 1002.53it/s]
count     win    lose    draw
o         865      77      58
x         675     258      67
total    1540     335     125

ratio     win    lose    draw
o       86.5%    7.7%    5.8%
x       67.5%   25.8%    6.7%
total   77.0%   16.8%    6.2%

pnum 50
ai_pmc VS ai2s
100%|██████████| 1000/1000 [00:03<00:00, 296.94it/s]
count     win    lose    draw
o         957      21      22
x         807     155      38
total    1764     176      60

ratio     win    lose    draw
o       95.7%    2.1%    2.2%
x       80.7%   15.5%    3.8%
total   88.2%    8.8%    3.0%

pnum 100
ai_pmc VS ai2s
100%|██████████| 1000/1000 [00:06<00:00, 157.87it/s]
count     win    lose    draw
o         978      12      10
x         853     125      22
total    1831     137      32

ratio     win    lose    draw
o       97.8%    1.2%    1.0%
x       85.3%   12.5%    2.2%
total   91.5%    6.9%    1.6%

pnum 1000
ai_pmc VS ai2s
100%|██████████| 1000/1000 [00:55<00:00, 18.11it/s]
count     win    lose    draw
o         990       2       8
x         896      91      13
total    1886      93      21

ratio     win    lose    draw
o       99.0%    0.2%    0.8%
x       89.6%    9.1%    1.3%
total   94.3%    4.7%    1.1%

pnum 10000
ai_pmc VS ai2s
100%|██████████| 1000/1000 [08:12<00:00,  2.03it/s]
count     win    lose    draw
o         990       0      10
x         917      70      13
total    1907      70      23

ratio     win    lose    draw
o       99.0%    0.0%    1.0%
x       91.7%    7.0%    1.3%
total   95.3%    3.5%    1.1%

timelimit 0.0001
ai_pmc VS ai2s
100%|██████████| 1000/1000 [00:01<00:00, 919.23it/s]
count     win    lose    draw
o         904      62      34
x         715     215      70
total    1619     277     104

ratio     win    lose    draw
o       90.4%    6.2%    3.4%
x       71.5%   21.5%    7.0%
total   81.0%   13.9%    5.2%

timelimit 0.0005
ai_pmc VS ai2s
100%|██████████| 1000/1000 [00:03<00:00, 261.21it/s]
count     win    lose    draw
o         957      24      19
x         813     158      29
total    1770     182      48

ratio     win    lose    draw
o       95.7%    2.4%    1.9%
x       81.3%   15.8%    2.9%
total   88.5%    9.1%    2.4%

timelimit 0.001
ai_pmc VS ai2s
100%|██████████| 1000/1000 [00:06<00:00, 143.16it/s]
count     win    lose    draw
o         974      17       9
x         852     131      17
total    1826     148      26

ratio     win    lose    draw
o       97.4%    1.7%    0.9%
x       85.2%   13.1%    1.7%
total   91.3%    7.4%    1.3%

timelimit 0.01
ai_pmc VS ai2s
100%|██████████| 1000/1000 [01:05<00:00, 15.35it/s]
count     win    lose    draw
o         984       2      14
x         915      77       8
total    1899      79      22

ratio     win    lose    draw
o       98.4%    0.2%    1.4%
x       91.5%    7.7%    0.8%
total   95.0%    4.0%    1.1%

timelimit 0.1
ai_pmc VS ai2s
100%|██████████| 1000/1000 [10:42<00:00,  1.56it/s]
count     win    lose    draw
o         989       0      11
x         906      75      19
total    1895      75      30

ratio     win    lose    draw
o       98.9%    0.0%    1.1%
x       90.6%    7.5%    1.9%
total   94.8%    3.8%    1.5%

下記は上記の実行結果をまとめた表です。左から ai_pmc の勝率、敗率、引分率の % を表します。また、他の AI と比較するために以前の記事で計測した ai2s VS ai2s と ai14s VS ai2s の対戦結果を表の最後に加えました。

回数または制限時間	先手の成績	後手の成績	通算成績	時間（分:秒)
5 回	80.7/11.9/ 7.4	57.3/30.0/20.9	69.0/20.9/10.1	0
10 回	86.5/ 7.7/ 5.8	67.5/25.8/ 6.7	77.0/16.8/ 6.2	0
50 回	95.7/ 2.1/ 2.2	80.7/15.5/ 3.8	88.2/ 8.8/ 3.0	3
100 回	97.8/ 1.2/ 1.0	85.3/12.5/ 2.2	91.5/ 6.9/ 1.6	6
1000 回	99.0/ 0.2/ 0.8	89.6/ 9.1/ 1.3	94.3/ 4.7/ 1.1	55
10000 回	99.0/ 0.0/ 1.0	91.7/ 7.0/ 1.3	95.3/ 3.5/ 11.1	8:12
0.0001 秒	90.4/ 6.2/ 3.4	71.5/21.5/ 7.0	81.0/13.9/ 5.2	1
0.0005 秒	95.7/ 2.4/ 1.9	81.3/15.8/ 2.9	88.5/ 9.1/ 2.4	3
0.001 秒	97.4/ 1.7/ 0.9	85.2/13.1/ 1.7	91.3/ 7.4/ 1.3	6
0.01 秒	98.4/ 0.2/ 1.4	91.5/ 7.7/ 0.8	95.0/ 4.0/ 1.1	1:05
0.1 秒	98.9/ 0.0/ 1.1	90.6/ 7.5/ 1.9	94.8/ 3.8/ 1.5	10:42
`ai2s` VS `ai2s`	58.7/28.8/12.6	29.1/58.6/12.3	43.9/43.7/12.5
`ai14s` VS `ai2s`	99.0/ 0.0/ 1.0	88.8/ 0.0/11.2	93.9/ 0.0/ 6.1

上記の表からわかるようにプレイアウトの回数が 10000 の場合や、制限時間が 0.1 秒の場合は対戦回数を 1000 回に減らしても処理時間が約 10 分ほどかかってしまいます。このことから 10000 回の対戦を 1 分以内で行うことができる ai1s ~ ai14s のような静的な評価関数による AI と比較して、原始モンテカルロ法による AI は計算の精度を上げるためにプレイアウトの回数を多くすると処理時間がかなり長くなることがわかります。

対戦成績に関しては、上記の表から下記の事がわかります。

プレイアウトの回数が 5 回のように非常に少ない場合や、制限時間が 0.0001 秒のように非常に短い場合でも ai2s VS ai2s よりも成績が良い
プレイアウトの回数や制限時間が大きくなるにつれて対戦成績が良くなる
プレイアウトの回数が 10000 回、制限時間が 0.1 秒になると、ai_pmc の先手の場合の成績が弱解決の AI である ai14s と同じで敗率が 0 % になる
プレイアウトの回数が 1000 回以上、制限時間が 0.01 秒以上になると、の ai_pmc の後手の場合と通算成績の勝率が弱解決の AI である ai14s よりも高くなるが、ai14s と異なり敗率は 0 % にはならない
〇× ゲームは引き分けのゲームなので、敗北する可能性が存在することから ai_pmc は弱解決の AI ではない

なお、上記の結果ではプレイアウトの回数を多くすると ai_pmc が先手の場合に敗北していないため、先手の場合に限定するとプレイアウトの回数を多くすることで ai_pmc が弱解決の AI になるのではないかと思う人がいるかもしれませんが、乱数で着手を計算しているためどれだけプレイアウトの回数を多くしても最善手を選択しない確率は 0 になりません。そのため、残念ながら ai_pmc は先手の場合でも弱解決な AI にはなりません。

このような結果になる原因は以下の通りです。

ai_pmc はお互いにランダムな着手を行い続けた場合に最も勝率が高くなる着手を選択するため、ai_pmc が理論値通りの計算を行った場合はランダムな着手を行う ai2s に対して最も勝率が高くなる合法手が計算される。一方、弱解決の ai14s は ai2s のような特定の相手に最も勝率が高くなる合法手ではなく、局面の状況を悪化させないという最善手を選択する点が異なる。そのため、プレイアウトの回数を多くすることで大数の法則によって計算結果の精度が高くなると、ai14s よりも ai2s に対する勝率は高くなる
ai_pmc が計算するのは、相手がランダムな着手を行う ai2s の場合に最も勝率が高くなる合法手であるため、計算した合法手の中には局面の状況を悪化させる最善手でないものが含まれる。そのような着手を選択した場合は、相手の ai2s が低い確率であっても最善手を着手し続けた場合は敗北する可能性が生じる

原始モンテカルロ法の利点はランダムな着手を行い続けるという、ゲームの性質を一切理解していなくても行うことができる処理を用いて、上記の実行結果が示すようにそこそこの強さの AI を作成できる点にあります。一方で、残念ながらプレイアウトの回数をどれだけ増やしても弱解決の AI を作成することはできません。

なお、先手であれば原始モンテカルロ法で弱解決の AI を常に作成できるわけではない点に注意して下さい。オセロや将棋など、ほとんどのゲームの場合は先手であっても原始モンテカルロ法ではそれほど強い AI を作成することはできません。

ai_pmc がどのような場合に本当の最善手を選択しないかについては次回の記事で検証することにします。

`ai14s` との対戦

下記は ai14s と対戦を行うプログラムです。

for pnum in [5, 10, 50, 100, 1000, 10000]:
    print(f"pnum {pnum}")
    ai_match(ai=[ai_pmc, ai14s], params=[{"pnum": pnum}, {}], match_num=1000)
    
for timelimit in [0.0001, 0.0005, 0.001, 0.01, 0.1]:
    print(f"timelimit {timelimit}")
    ai_match(ai=[ai_pmc, ai14s], params=[{"pnum": 100000000, "timelimit": timelimit}, {}],
             match_num=1000)

実行結果

pnum 5
ai_pmc VS ai14s
100%|██████████| 1000/1000 [00:00<00:00, 1168.83it/s]
count     win    lose    draw
o           0     722     278
x           0     935      65
total       0    1657     343

ratio     win    lose    draw
o        0.0%   72.2%   27.8%
x        0.0%   93.5%    6.5%
total    0.0%   82.8%   17.2%

pnum 10
ai_pmc VS ai14s
100%|██████████| 1000/1000 [00:01<00:00, 911.10it/s]
count     win    lose    draw
o           0     700     300
x           0     945      55
total       0    1645     355

ratio     win    lose    draw
o        0.0%   70.0%   30.0%
x        0.0%   94.5%    5.5%
total    0.0%   82.2%   17.8%

pnum 50
ai_pmc VS ai14s
100%|██████████| 1000/1000 [00:03<00:00, 300.37it/s]
count     win    lose    draw
o           0     569     431
x           0     997       3
total       0    1566     434

ratio     win    lose    draw
o        0.0%   56.9%   43.1%
x        0.0%   99.7%    0.3%
total    0.0%   78.3%   21.7%

pnum 100
ai_pmc VS ai14s
100%|██████████| 1000/1000 [00:06<00:00, 165.93it/s]
count     win    lose    draw
o           0     497     503
x           0     999       1
total       0    1496     504

ratio     win    lose    draw
o        0.0%   49.7%   50.3%
x        0.0%   99.9%    0.1%
total    0.0%   74.8%   25.2%

pnum 1000
ai_pmc VS ai14s
100%|██████████| 1000/1000 [01:00<00:00, 16.49it/s]
count     win    lose    draw
o           0     196     804
x           0    1000       0
total       0    1196     804

ratio     win    lose    draw
o        0.0%   19.6%   80.4%
x        0.0%  100.0%    0.0%
total    0.0%   59.8%   40.2%

pnum 10000
ai_pmc VS ai14s
100%|██████████| 1000/1000 [08:56<00:00,  1.86it/s]
count     win    lose    draw
o           0       0    1000
x           0    1000       0
total       0    1000    1000

ratio     win    lose    draw
o        0.0%    0.0%  100.0%
x        0.0%  100.0%    0.0%
total    0.0%   50.0%   50.0%

timelimit 0.0001
ai_pmc VS ai14s
100%|██████████| 1000/1000 [00:01<00:00, 826.29it/s]
count     win    lose    draw
o           0     651     349
x           0     957      43
total       0    1608     392

ratio     win    lose    draw
o        0.0%   65.1%   34.9%
x        0.0%   95.7%    4.3%
total    0.0%   80.4%   19.6%

timelimit 0.0005
ai_pmc VS ai14s
100%|██████████| 1000/1000 [00:03<00:00, 264.66it/s]
count     win    lose    draw
o           0     522     478
x           0     997       3
total       0    1519     481

ratio     win    lose    draw
o        0.0%   52.2%   47.8%
x        0.0%   99.7%    0.3%
total    0.0%   75.9%   24.1%

timelimit 0.001
ai_pmc VS ai14s
100%|██████████| 1000/1000 [00:07<00:00, 141.28it/s]
count     win    lose    draw
o           0     475     525
x           0    1000       0
total       0    1475     525

ratio     win    lose    draw
o        0.0%   47.5%   52.5%
x        0.0%  100.0%    0.0%
total    0.0%   73.8%   26.2%

timelimit 0.01
ai_pmc VS ai14s
100%|██████████| 1000/1000 [01:09<00:00, 14.30it/s]
count     win    lose    draw
o           0     244     756
x           0    1000       0
total       0    1244     756

ratio     win    lose    draw
o        0.0%   24.4%   75.6%
x        0.0%  100.0%    0.0%
total    0.0%   62.2%   37.8%

timelimit 0.1
ai_pmc VS ai14s
100%|██████████| 1000/1000 [11:42<00:00,  1.42it/s]
count     win    lose    draw
o           0       2     998
x           0    1000       0
total       0    1002     998

ratio     win    lose    draw
o        0.0%    0.2%   99.8%
x        0.0%  100.0%    0.0%
total    0.0%   50.1%   49.9%

下記は上記の実行結果をまとめた表です。〇× ゲームは引き分けのゲームで、ai14s は弱解決の AI であるため ai_pmc の勝率はすべて 0 % になります。そこで下記の表では勝率を省略して左から ai_pmc の敗率、引分率の % を表記しました。

回数または制限時間	先手の成績	後手の成績	通算成績	時間（分:秒)
5 回	72.2/27.8	93.5/6.5	82.8/17.2	0
10 回	70.0/30.0	94.5/5.5	82.2/17.8	1
50 回	56.9/43.1	99.7/ 0.3	78.3/21.7	3
100 回	49.7/50.3	99.9/0.1	74.8/25.2	6
1000 回	19.6/80.4	100.0/ 0.0	59.8/4.02	1:00
10000 回	0.0/100.0	100.0/0.0	50.0/50.0	8:56
0.0001 秒	65.1/34.9	95.7/ 4.3	80.4/19.6	1
0.0005 秒	52.2/47.8	99.7/ 0.3	75.9/24.1	3
0.001 秒	47.5/52.5	100.0/ 0.0	73.8/26.2	7
0.01 秒	24.4/75.6	100.0/ 0.0	62.2/37.8	1:09
0.1 秒	0.2/ 99.8	100.0/ 0.0	50.1/49.9	11:42

上記の表から下記の事がわかります。処理時間に関しては先ほどと同様なので省略します。

先手の場合はプレイアウトの回数や制限時間が大きくなるにつれて敗率が減り、引き分け率が上がって対戦成績が良くなる。プレイアウトの回数が 10000 回や制限時間が 0.1 秒の場合はほぼ 100 % 引き分けになるので先手の場合はほぼ弱解決の AI であると言える
後手の場合はプレイアウトの回数や制限時間が大きくなるにつれて逆に敗率が高くなり、最終的に敗率が 100 % になることから対戦成績が悪化する

後手の場合にプレイアウトの回数が増えると成績が逆に悪化する理由は以下の通りです。

プレイアウトの回数が少ない場合は計算の精度が低いため ai2s に対する勝率が最も高い合法手ではないが、実際には最善手である合法手が選択される場合が生じるため、低確率であるが引き分けになる場合が生じる
プレイアウトの回数が増えると計算の精度が上がるため、そのような局面で最善手が選択される確率がほぼ 0 になるため敗率が 100 % になる

AI との対戦結果のまとめ

ai2s と ai14s との対戦結果から、原始モンテカルロ法を用いることで〇× ゲームでは先手の場合はプレイアウトの回数を増やした場合に ai2s に対してほぼ 100 % で勝利できる、弱解決に非常に近い強さの AI を作成することができることがわかりました。

一方後手の場合は ai2s 対しては最も勝率の高い AI となりますが、最善手を選択しない局面が生じるため ai14s に対してはほぼ 100 % 敗北する結果になることがわかりました。

プレイアウトの回数を一定以上増やした場合の ai_pmc は、先手を担当させた場合はほぼ弱解決の AI に近いためほぼ最強の AI となります。一方で、〇× ゲームは人間でも少し練習すればすべての局面で最善手を着手できるような単純なゲームなので、後手を担当させた場合は手ごたえのない弱い AI になります。

実際に確認したわけではないのですが、将棋や囲碁などの多くのゲームに対する原始モンテカルロ法の AI は先手でも後手でも初心者相手には十分勝てるくらいの強さの AI になるのではないかと思いますが、おそらく中級者にとっては物足りないくらいの強さになるのではないかと思います。実際に確認するためにはそのゲームのプログラムを実装する必要があるので複雑なゲームの場合はかなり大変だと思いますが、興味がある方はゲームを実装して実際に確認してみて下さい。

今回の記事のまとめ

今回の記事では、原始モンテカルロ法で最善手を計算する ai_pmc の実装を行い、ランダムな着手を行う ai2s と弱解決の AI である ai14s との対戦を行うことでその強さを検証しました。その結果、プレイアウトの回数を増やすほど ai2s との対戦成績が良くなり、勝率に関しては ai14s VS ai2s よりも高くなることが確認できました。一方で、敗率が 0 にならないことから弱解決の AI を作成できないことが確認できました。

原始モンテカルロ法の利点はゲームの性質について一切理解することなくそこそこ強い AI を作成することができるという点にありますが、一方で残念ながら弱解決の AI を作成することができないという欠点があります。

また、原始モンテカルロ法は、大数の法則からプレイアウトの回数が多い程計算の精度が高まるという性質があるため、プレイアウトの処理速度が高速あることが非常に重要です。そのため、ゲームの決着がつくまでに手数が多くかかるゲームや、オセロや囲碁のように着手によって局面が大きく変化する場合があるゲームではプレイアウトの処理時間が長くなるため、プレイアウトの回数が制限されてしまうという問題があります。

次回の記事では原始モンテカルロ法が計算する最善手の性質について検証する予定です。

本記事で入力したプログラム

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル
ai.py	本記事で更新した ai_new.py
util.py	本記事で更新した util_new.py

次回の記事

近日公開予定です

pure は純粋なという意味です。原始の英語表記である primitive を用いて primitive monte calro method と表記する場合もあるようです ↩
異なる合法手を着手した局面の勝率が 0 % 以外の場合で一致する可能性もありますが、プレイアウトの回数を一定以上多くした場合に勝率が完全に一致することはほぼないでしょう ↩
低確率でエラーが発生しない場合があります。発生しなかった場合は何度か実行するとエラーが発生するはずです ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Pythonで〇×ゲームのAIを一から作成する その234 原始モンテカルロ法による 〇× ゲームの AI の実装

目次と前回の記事

Python のバージョンとこれまでに作成したモジュール

原始モンテカルロ法による 〇× ゲームの AI の実装

ai_pmc の仕様

原始モンテカルロ法のアルゴリズム修正

ai_pmc の定義

ai_pmc の座標の表示の修正

ai_pmc の動作の確認

〇 の手番の局面での確認

× の手番の局面での確認

〇 が勝利できない局面での確認

プレイアウトの回数を変化させた場合の確認

エラーの原因の検証と修正

プレイアウトの回数を変化させた場合の検証

制限時間を変化させた場合の確認と検証

ai2 と ai14s との対戦

ai_pmc の改良

ai2s との対戦

ai14s との対戦

AI との対戦結果のまとめ

今回の記事のまとめ

本記事で入力したプログラム

次回の記事

Pythonで〇×ゲームのAIを一から作成する　その234　原始モンテカルロ法による〇× ゲームの AI の実装

原始モンテカルロ法による〇× ゲームの AI の実装

`ai_pmc` の仕様

`ai_pmc` の定義

`ai_pmc` の座標の表示の修正

`ai_pmc` の動作の確認

〇の手番の局面での確認

〇が勝利できない局面での確認

`ai2` と `ai14s` との対戦

`ai_pmc` の改良

`ai2s` との対戦

`ai14s` との対戦