Pythonで〇×ゲームのAIを一から作成する　その232　プレイアウトの実装と大数の法則

Posted at 2026-06-14

目次と前回の記事

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 の実装と、その強さの検証やアルゴリズムの改善方法については今後の記事で説明する予定です。

プレイアウトの確率の計算

最初に〇× ゲームの任意の局面に対してプレイアウトを行った（決着がつくまでランダムな着手を行い続けた）場合の「〇の勝利」、「× の勝利」、「引き分け」のそれぞれの発生確率の計算方法について説明し、実際にその計算を行うことにします。

〇× ゲームの局面（state）を $S$ と表記すると、$S$ に対してプレイアウトを行った場合の結果は「〇の勝利」、「× の勝利」、「引き分け」のいずれかになり、それぞれの発生確率の合計は 1 になります。なお、$S$ は決着がついた局面も含むものとし、その場合は当然ですがランダムな着手は行われず、その局面の結果の確率が 1、それ以外の確率が 0 になります。

局面 $S$ に対してプレイアウトの結果を表す確率変数 $X_S$ と表記すると、それぞれの結果が発生する確率は確率質量関数 $P$ を用いて下記の表のように表記できます。ただし、表記を簡潔にするために確率変数 $X_S$ の値は「〇の勝利」の場合は「〇」、「× の勝利」の場合は「×」、「引き分け」の場合は「△」としました。

	意味
$P(X_S=〇)$	〇の勝率
$P(X_S=×)$	× が勝率
$P(X_S=△)$	引き分け率

今回の記事ではこれらの値を計算し、プレイアウトの回数を増やすとそれぞれの割合がこれらの理論値に近づいていくことを示します。

確率質量関数の計算式

$P(X_S=〇)$、$P(X_S=×)$、$P(X_S=△)$ の具体的な計算方法について説明します。

局面 $S$ が決着がついた局面の場合は以下の表のようになります。

	〇の勝利	× の勝利	引き分け
$P(X_S=〇)$	1	0	0
$P(X_S=×)$	0	1	0
$P(X_S=△)$	0	0	1

局面 $S$ が決着がついていない局面の場合は、その局面の合法手の数を $n$、それぞれの合法手を着手した局面を $S_1$、$S_2$、・・・、$S_n$ と表記すると、ランダムな着手によってそれぞれの合法手が $\frac{1}{n}$ という等確率で選択されます。その結果、$P(X_S=〇)$ はそれぞれの合法手を着手した局面で〇が勝利する確率の平均を表す下記の式で計算することができます。

$P(X_S=〇) = \sum_{i=1}^{n}\frac{1}{n}P(X_{S_i}=〇)= \frac{1}{n}\sum_{i=1}^{n}P(X_{S_i}=〇)$

同様の理由から $P(X_S=×)$ と $P(X_S=△)$ も下記の式で計算することができます。

$P(X_S=×) = \frac{1}{n}\sum_{i=1}^{n}P(X_{S_i}=×)$

$P(X_S=△) = \frac{1}{n}\sum_{i=1}^{n}P(X_{S_i}=△)$

ゲームの決着がついた局面は以前の記事で説明した〇× ゲームのゲーム木のリーフノードに相当し、$X_{S_i}$ の局面は $X_{S}$ の局面の子ノードに相当します。従って、上記の式は下記の計算を行うことを表します。

リーフノードの確率を計算する
子ノードの確率から親ノードの確率を計算する

この性質は以前の記事で説明した、ゲーム木の各ノードの評価値を計算するミニマックス法と同じであるため、ミニマックス法と同様のアルゴリズムで計算を行うことができます。

深さ優先アルゴリズムによる計算の実装

以前の記事では幅優先アルゴリズムと深さ優先アルゴリズムの 2 種類のアルゴリズムでミニマックス法を実装する方法を紹介しましたが、どちらの方法で実装しても結果は変わらないので今回の記事ではより簡単に実装できる深さ優先（depth first）アルゴリズムで実装することにします。興味がある方は幅優先アルゴリズムで実装してみて下さい。

ミニマックス法を深さ優先アルゴリズムで行う処理は、ゲーム木を表す Mbtree クラスの calc_score_by_df ¹というメソッドで実装しました。同様に深さ優先アルゴリズムでプレイアウトを行った場合の各ノードのそれぞれの結果の確率（probability）の計算を Mbtree クラスの calc_playout_prob_by_df というメソッドで定義することにします。

プレイアウトを行った場合のそれぞれの割合はゲームの状態を表す Marubatsu クラスの status 属性の値をキーとした下記の表の dict で表現し、ゲーム木のノードを表す Node クラスのインスタンスの playout_prob という属性に代入することにします。なお、mb はノードの局面を表す Marubatsu クラスのインスタンスです。

キー	キーの値
`mb.CIRCLE`	〇の勝率
`mb.CROSS`	× の勝率
`mb.DRAW`	引き分け率

下記は Mbtree クラスの calc_playout_prob_by_df メソッドの定義です。

4 行目：calc_playout_prob_by_df メソッドを、計算の対象となる局面を表すゲーム木のノードを代入する仮引数 node を持つメソッドとして定義する
5 ~ 9 行目：局面からランダムな着手を行い続けた場合の〇の勝率、× の勝率、引分の確率を表す playout_prob 属性を、それぞれの確率を 0 とした dict で初期化する
10、11 行目：node の局面が決着がついている場合は playout_prob 属性に代入された dict の対応するキーの値を 1 としてその確率を 100 % に設定する
12 ~ 17 行目：決着がついていない場合の処理を行う
13 行目：子ノード（合法手）の数を計算して childnum に代入する
14 行目：それぞれの子ノード（合法手を着手した局面）に対して繰り返し処理を行う
15 行目：子ノードに対して calc_playout_prob_by_df を再帰呼び出しすることで、深さ優先アルゴリズムで子ノードのそれぞれの確率を計算する
16、17 行目：15 行目の再帰呼び出しによって子ノードのそれぞれの確率が playout_prob 属性に計算されるので、それぞれの確率を childnum で割った値を playout_prob 属性の対応する確率に加算することで平均値を計算する

 1  from tree import Mbtree
 2  from marubatsu import Marubatsu
 3  
 4  def calc_playout_prob_by_df(self, node):
 5      node.playout_prob = {
 6          node.mb.CIRCLE: 0.0,
 7          node.mb.CROSS: 0.0,
 8          node.mb.DRAW: 0.0
 9      }
10      if node.mb.status != Marubatsu.PLAYING:
11          node.playout_prob[node.mb.status] = 1.0
12      else:
13          childnum = len(node.children)
14          for childnode in node.children:
15              self.calc_playout_prob_by_df(childnode)
16              for status, prob in childnode.playout_prob.items():
17                  node.playout_prob[status] += prob / childnum
18  
19  Mbtree.calc_playout_prob_by_df = calc_playout_prob_by_df

行番号のないプログラム

from tree import Mbtree
from marubatsu import Marubatsu

def calc_playout_prob_by_df(self, node):
    node.playout_prob = {
        node.mb.CIRCLE: 0.0,
        node.mb.CROSS: 0.0,
        node.mb.DRAW: 0.0
    }
    if node.mb.status != Marubatsu.PLAYING:
        node.playout_prob[node.mb.status] = 1.0
    else:
        childnum = len(node.children)
        for childnode in node.children:
            self.calc_playout_prob_by_df(childnode)
            for status, prob in childnode.playout_prob.items():
                node.playout_prob[status] += prob / childnum
                 
Mbtree.calc_playout_prob_by_df = calc_playout_prob_by_df

`init` メソッドの修正と動作の確認

次に、Mbtree クラスの __init__ メソッドの 16 行目に下記のプログラムのように calc_playout_prob_by_df の実引数にゲーム木のルートノードを記述して呼び出すことで、すべての局面に対するプレイアウトの結果の確率を計算する処理を追加します。

 1  from tree import Node
 2
 3  def __init__(self, algo="bf", shortest_victory=False, 
 4               recalculate_draw_score=False, subtree=None):
元と同じなので省略
 5      if self.algo == "bf":  
 6          self.create_tree_by_bf()
 7          self.calc_score_by_bf()
 8      else:
 9          self.nodelist = [self.root]
10          self.nodelist_by_depth = [[] for _ in range(10)]
11          self.nodelist_by_depth[0].append(self.root)
12          self.nodenum = 0
13          self.create_tree_by_df(self.root)
14          self.nodelist_by_score = []
15          self.calc_score_by_df(self.root)
16      self.calc_playout_prob_by_df(self.root)
元と同じなので省略
17  
18  Mbtree.__init__ = __init__

行番号のないプログラム

from tree import Node

def __init__(self, algo="bf", shortest_victory=False, 
             recalculate_draw_score=False, subtree=None):
    if subtree is not None:
        self.subtree = subtree
        self.create_subtree()
        return

    self.algo = algo
    self.shortest_victory = shortest_victory
    self.recalculate_draw_score = recalculate_draw_score
    Node.count = 0
    self.root = Node(Marubatsu())
    if self.algo == "bf":  
        self.create_tree_by_bf()
        self.calc_score_by_bf()
    else:
        self.nodelist = [self.root]
        self.nodelist_by_depth = [[] for _ in range(10)]
        self.nodelist_by_depth[0].append(self.root)
        self.nodenum = 0
        self.create_tree_by_df(self.root)
        self.nodelist_by_score = []
        self.calc_score_by_df(self.root)
    self.calc_playout_prob_by_df(self.root)
    if self.recalculate_draw_score:
        self.recalculate_score()
    self.nodelist_by_mb = {}
    self.bestmoves_by_mb = {}
    self.calc_bestmoves(self.root)
    
Mbtree.__init__ = __init__

修正箇所

from tree import Node

def __init__(self, algo="bf", shortest_victory=False, 
             recalculate_draw_score=False, subtree=None):
元と同じなので省略
    if self.algo == "bf":  
        self.create_tree_by_bf()
        self.calc_score_by_bf()
    else:
        self.nodelist = [self.root]
        self.nodelist_by_depth = [[] for _ in range(10)]
        self.nodelist_by_depth[0].append(self.root)
        self.nodenum = 0
        self.create_tree_by_df(self.root)
        self.nodelist_by_score = []
        self.calc_score_by_df(self.root)
+   self.calc_playout_prob_by_df(self.root)
元と同じなので省略
    
Mbtree.__init__ = __init__

5 ~ 16 行目の条件分岐では algo 属性の値によって幅優先と深さ優先のどちらのアルゴリズムで計算を行うかを変えていますが、今回の記事では幅優先（breadth first）アルゴリズムで処理を行う calc_playout_prob_by_bf メソッドを実装していないので、その条件分岐の後で必ず深さ優先アルゴリズムによる calc_playout_prob_by_df を実行するようにしました。

どちらのアルゴリズムで計算しても結果は変わらないのでこのままでも問題はありませんが、余裕がある方は幅優先アルゴリズムで計算を行う calc_playout_prob_by_bf メソッドを実装して algo の属性の値によって呼び出すメソッドを変えるプログラムを実装してみて下さい。

上記の修正後に下記のプログラムを実行して新しい Mbtree クラスのインスタンスを作成し、ゲーム開始時の局面とその局面に合法手を着手した局面に対するプレイアウトの結果のそれぞれの確率を表示します。

1 行目：新しい Mbtree クラスのインスタンスを作成する
2 行目：ゲーム開始時の局面を表す mbtree.root を要素とする list と、その子ノードの一覧を表す list を + 演算子で結合した list に対して繰り返し処理を行うことで、ゲーム開始時のノードとその子ノードに対する繰り返し処理を行う
3 ~ 7行目：node の局面とプレイアウトの結果のそれぞれの確率を表示する

1  mbtree = Mbtree()
2  for node in [mbtree.root] + mbtree.root.children:
3      print(node.mb)
4      print(f"o    {node.playout_prob[node.mb.CIRCLE] * 100:5.1f}%")
5      print(f"x    {node.playout_prob[node.mb.CROSS] * 100:5.1f}%")
6      print(f"draw {node.playout_prob[node.mb.DRAW] * 100:5.1f}%")
7      print()

行番号のないプログラム

mbtree = Mbtree()
for node in [mbtree.root] + mbtree.root.children:
    print(node.mb)
    print(f"o    {node.playout_prob[node.mb.CIRCLE] * 100:5.1f}%")
    print(f"x    {node.playout_prob[node.mb.CROSS] * 100:5.1f}%")
    print(f"draw {node.playout_prob[node.mb.DRAW] * 100:5.1f}%")
    print()

実行結果

     9 depth 1 node created
    72 depth 2 node created
   504 depth 3 node created
  3024 depth 4 node created
 15120 depth 5 node created
 54720 depth 6 node created
148176 depth 7 node created
200448 depth 8 node created
127872 depth 9 node created
     0 depth 10 node created
total node num = 549946
Turn o
...
...
...

o     58.5%
x     28.8%
draw  12.7%

Turn x
O..
...
...

o     60.7%
x     26.4%
draw  12.9%

Turn x
...
O..
...

o     53.6%
x     33.6%
draw  12.9%

Turn x
...
...
O..

o     60.7%
x     26.4%
draw  12.9%

Turn x
.O.
...
...

o     53.6%
x     33.6%
draw  12.9%

Turn x
...
.O.
...

o     69.3%
x     19.3%
draw  11.4%

Turn x
...
...
.O.

o     53.6%
x     33.6%
draw  12.9%

Turn x
..O
...
...

o     60.7%
x     26.4%
draw  12.9%

Turn x
...
..O
...

o     53.6%
x     33.6%
draw  12.9%

Turn x
...
...
..O

o     60.7%
x     26.4%
draw  12.9%

下記は上記の実行結果をまとめた表です。それぞれの確率を % 表記に直し、小数点以下第 2 位で四捨五入しました。

局面	〇の勝率	× の勝率	引き分け率
`...` `...` `...`	58.5%	28.8%	12.7 %
`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 %

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

四辺と四隅に着手した場合のそれぞれの確率は同じである
真ん中＞四隅＞四辺の順で〇の勝率が高くなる
いずれの局面でも〇の勝率が 50 % を超える

上記の 1 つ目の、四隅に着手した場合と四辺に着手した場合の局面は同一局面なので確率が等しくなることは当然と言えます。

2 つ目の結果は以前の記事で考察したように、〇の勝利につながる「自1敵0空2」となる直線が多い順で〇が有利になるため勝率が高くなることを表します。従って、原始モンテカルロ法の AI はゲーム開始時の局面で真ん中の合法手を選びます。

3 つ目からこのゲームはランダムな着手を行い続ける場合は〇が有利なゲームであることがわかります。

ただし、上記の 2 つ目と 3 つ目はランダムな着手を行い続けた場合の性質です。〇× ゲームは引き分けのゲームなので、お互いが最善手を着手し続ける場合はゲーム開始時でどの着手を行っても引き分けになります。

ファイルへのデータの保存

Mbtree のインスタンスの計算は時間がかかる²ため、計算したゲーム木のデータを下記のプログラムで Mbtree の save メソッドを利用して playout.mbtree という名前でデータを保存するフォルダにそのファイルを保存することにします。

mbtree.save("../data/playout")

下記は上記で保存したファイルを load メソッドで読み込んで mbtree2 という変数に代入し、ゲーム開始時の局面を表すルートノードの playout_prob 属性を表示するプログラムです。実行結果から先程の表のゲーム開始時の局面の確率が表示されることが確認できます。

mbtree2 = Mbtree.load("../data/playout")
print(mbtree2.root.playout_prob)

実行結果

{0: 0.5849206349206348, 1: 0.2880952380952381, 'draw': 0.126984126984127}

プレイアウトの処理の実装

次に、任意の局面に対してプレイアウトを「指定した回数」または「指定した時間が経過するまで」行い、それぞれの合法手を着手した局面に対する「〇の勝利」、「× の勝利」、「引き分け」の回数を計算する playout という関数を実装します。大数の法則に従うことを確認するためには実際に何回プレイアウトが実行されたかという情報が必要となるので、playout は割合ではなく回数を計算して返すことにしました。

`playout` のアルゴリズム

最初に説明した原始モンテカルロ法のアルゴリズムでは、現在の局面のそれぞれの合法手を着手した局面に対して「特定の回数」または「特定の時間が経過するまで」プレイアウトを行うと説明しましたが、局面によってゲームの決着がつくまでの平均の手数が異なることから、1 回のプレイアウトの処理時間の平均は局面によって異なります。そのため、合法手を着手したそれぞれの局面に対して同じ制限時間を設けたプレイアウトを行うと、局面ごとにプレイアウトの回数が異なるため、プレイアウトの集計結果の精度が局面ごとに異なるという問題が発生します。

そこで、playout の実装では合法手を着手した局面ではなく、現在の局面から「特定の回数」または「特定の時間が経過するまで」プレイアウトを行い、最初に着手を行った合法手ごとにプレイアウトの結果の集計を行うことにします。この方法ではそれぞれの合法手が選択される回数は等しくなりませんが、大数の法則からプレイアウトの回数が増えれば増えるほどそれぞれの合法手が選択される割合が均等に近づくため、上記の問題をうまく解決することができます。

`playout` の仮引数と返り値

下記は playout の仮引数の一覧です。

仮引数	意味
`mborig`	プレイアウトを開始する局面。`playout` の処理の中で `mborig` をコピーして利用するので、コピー元のオリジナル（original）なデータであることを明確にするために `mborig` とした
`pnum`	プレイアウトを行う回数
`ptime`	プレイアウトを行う制限時間（単位は秒）。デフォルト値を `None` とするデフォルト引数とし、`None` が代入されている場合は制限時間を設けないものとする

playout の返り値は下記のような dict を入れ子にしたデータ構造とします。

キー	キーの値
`result`	プレイアウトの集計結果（result）を表す下記の dict
`count`	実際にプレイアウトを行った回数

キー	キーの値
プレイアウトの最初の着手を表すデータ	最初にその着手を行った場合のプレイアウトのそれぞれの結果の回数を表す下記の dict

キー	キーの値
`mb.CIRCLE`	〇の勝利の回数
`mb.CROSS`	× の勝利の回数
`mb.DRAW`	引き分けの回数

下記は playout の定義を行うプログラムです。なお、時間の計測は以前の記事で説明した perf_counter という time モジュールで定義された関数を利用しています。忘れた方は復習して下さい。

5 行目：上記の表の仮引数を持つように playout を定義する
6 ~ 8 行目：timelimit が None でない場合は perf_counter() で現在の時間を計測し、それに timelimit を加算することで制限時間での perf_counter() の値を計算して timelimit_pc に代入する
9 ~ 15 行目：プレイアウトの集計結果を記録する result に空の dict を代入し、それぞれの合法手をキーとし、そのキーの値に〇の勝利と × の勝利と引き分けの回数がそれぞれ 0 であることを表す dict を代入する
16 行目：プレイアウトを行った回数を記録する変数を 0 で初期化する
17 行目：繰り返し処理で pnum 回のプレイアウトを行う
18、19 行目：timelimit が None でない場合は perf_counter() で時間を計測し、timelimit_pc を超えていた場合は制限時間を超えているので break で繰り返し処理を中断する
20 行目：プレイアウトは毎回 mborig の局面から行う必要があるので、deepcopy で mborig の深いコピーを行った mb に対してプレイアウトの処理を行うようにする
21 行目：最初の着手を記録する変数を None で初期化する
22 ~ 26 行目：繰り返し処理で決着がつくまでランダムな着手を行う
23 行目：random.choice を利用して合法手の中からランダムな合法手を選択する
24、25 行目：firstmove が None の場合に合法手を firstmove に代入することで最初に行った着手を記録する
26 行目：ランダムに選択した合法手を着手する
27、28 行目：result の firstmove のキーに代入された dict の mb.status キーの値を 1 増やすことで集計を行い、プレイアウトを行った回数を表す count に 1 を加算する
29 ~ 32 行目：先程説明したデータ構造の返り値を返す

 1  from time import perf_counter
 2  from copy import deepcopy
 3  import random 
 4  
 5  def playout(mborig, pnum, timelimit=None):
 6      if timelimit is not None:   
 7          starttime = perf_counter()
 8          timelimit_pc = starttime + timelimit        
 9      result = {}
10      for move in mborig.calc_legal_moves():
11          result[move] = {
12              mborig.CIRCLE: 0,
13              mborig.CROSS: 0,
14              mborig.DRAW: 0,
15          }
16      count = 0
17      for _ in range(pnum):
18          if timelimit is not None and perf_counter() > timelimit_pc:
19              break
20          mb = deepcopy(mborig)
21          firstmove = None
22          while mb.status == mb.PLAYING:
23              move = random.choice(mb.calc_legal_moves())
24              if firstmove is None:
25                  firstmove = move
26              mb.move(move)
27          result[firstmove][mb.status] += 1
28          count += 1
29      return {
30          "result": result,
31          "count": count,
32      }

行番号のないプログラム

from time import perf_counter
from copy import deepcopy
import random 

def playout(mborig, pnum, timelimit=None):
    if timelimit is not None:   
        starttime = perf_counter()
        timelimit_pc = starttime + timelimit        
    result = {}
    for move in mborig.calc_legal_moves():
        result[move] = {
            mborig.CIRCLE: 0,
            mborig.CROSS: 0,
            mborig.DRAW: 0,
        }
    count = 0
    for _ in range(pnum):
        if timelimit is not None and perf_counter() > timelimit_pc:
            break
        mb = deepcopy(mborig)
        firstmove = None
        while mb.status == mb.PLAYING:
            move = random.choice(mb.calc_legal_moves())
            if firstmove is None:
                firstmove = move
            mb.move(move)
        result[firstmove][mb.status] += 1
        count += 1
    return {
        "result": result,
        "count": count,
    }

17 行目を for count in range(pnum): のように変更することでプレイアウトの回数を数えることができると思った方がいるかもしれませんが³、その場合は繰り返し処理が中断されなかった場合に count の値が pnum - 1 になります。

プレイアウトの結果の表示

下記はゲーム開始時の局面に対して制限時間を設けずにプレイアウトを 10000 回行い、その結果を表示するプログラムです。

1、2 行目：ゲーム開始時の局面を表すデータを mb に代入してゲーム盤を表示する
3 行目：制限時間を設けずに playout で 10000 回のプレイアウトを行い、結果を retval に代入する
4 行目：プレイアウトが実際に行われた回数を表示する
5 行目：retval['result'] の各キー（最初の着手）とキーの値（その着手に対する各結果の回数）に対して繰り返し処理を行う
6 ~ 8 行目：直前の着手に対する表示と区別しやすいように空行と横棒を表示する
9 行目：move にはプレイアウトで最初に着手を行った合法手を表すデータが代入されているが、そのデータ構造は (x, y) のような tuple であるとは限らないので mb.board.move_to_xy で (x, y) の座標に変換して表示する
10 ~ 12 行目：move の着手を行ってその局面を表示し、次の繰り返し処理で mb を元の局面に戻す必要があるので unmove を呼び出す
13 行目：それぞれの結果の割合を計算するために counts のキーの値の合計を計算する
14 行目：counts の各キー（結果）とキーの値（個数）に対して繰り返し処理を行う
15 行目：結果、個数、その割合を計算して表示する。なお、結果を表すデータはゲーム盤を表すクラスによって異なるので、以前の記事で導入したゲーム盤を表すクラスの board.MARK_TABLE 属性を利用して勝敗結果を表す文字列に変換する必要がある

 1  mb = Marubatsu()
 2  print(mb)
 3  retval = playout(mb, 10000)
 4  print(f"playout count = {retval['count']}")
 5  for move, counts in retval["result"].items():
 6      print()
 7      print("---------------------")
 8      print()
 9      print(f"move {mb.board.move_to_xy(move)}")
10      mb.move(move)
11      print(mb)
12      mb.unmove()
13      total = sum(counts.values())
14      for status, count in counts.items():
15          print(f"{mb.board.MARK_TABLE[status]:4s}: {count:7d} {count/total*100:6.1f}%")

行番号のないプログラム

mb = Marubatsu()
print(mb)
retval = playout(mb, 10000)
print(f"playout count = {retval['count']}")
for move, counts in retval["result"].items():
    print()
    print("---------------------")
    print()
    print(f"move {mb.board.move_to_xy(move)}")
    mb.move(move)
    print(mb)
    mb.unmove()
    total = sum(counts.values())
    for status, count in counts.items():
        print(f"{mb.board.MARK_TABLE[status]:4s}: {count:7d} {count/total*100:6.1f}%")

実行結果

Turn o
...
...
...

playout count = 10000

---------------------

move (0, 0)
Turn x
O..
...
...

o   :     710   61.0%
x   :     298   25.6%
draw:     156   13.4%

---------------------

move (0, 1)
Turn x
...
O..
...

o   :     574   55.5%
x   :     329   31.8%
draw:     132   12.8%

---------------------

move (0, 2)
Turn x
...
...
O..

o   :     670   60.2%
x   :     307   27.6%
draw:     136   12.2%

---------------------

move (1, 0)
Turn x
.O.
...
...

o   :     596   51.5%
x   :     418   36.1%
draw:     143   12.4%

---------------------

move (1, 1)
Turn x
...
.O.
...

o   :     761   68.4%
x   :     202   18.2%
draw:     149   13.4%

---------------------

move (1, 2)
Turn x
...
...
.O.

o   :     620   54.6%
x   :     365   32.1%
draw:     151   13.3%

---------------------

move (2, 0)
Turn x
..O
...
...

o   :     675   62.6%
x   :     263   24.4%
draw:     141   13.1%

---------------------

move (2, 1)
Turn x
...
..O
...

o   :     593   53.5%
x   :     374   33.7%
draw:     142   12.8%

---------------------

move (2, 2)
Turn x
...
...
..O

o   :     658   60.1%
x   :     285   26.0%
draw:     152   13.9%

実行結果から制限時間を設けていないため 10000 回のプレイアウトが行われたことが確認できます。集計結果については後でまとめます。

次に制限時間を設定した場合の処理を確認します。上記の 10000 回のプレイアウトは筆者のパソコンでは約 0.4 秒で実行されました。そのため、下記のプログラムのように制限時間を 1 秒、プレイアウトの回数を 100 万としてプレイアウトが実際に行われた回数だけを表示すると、実行結果のように 1 秒後に繰り返し処理の途中で中断されて約 25000 回のプレイアウトが実行されたことが確認できます。

retval = playout(mb, 1000000, timelimit=1)
print(f"playout count = {retval['count']}")

実行結果

playout count = 25758

理論上の確率との比較

上記の結果が大数の法則に従っているかどうかを確認できるように、先程計算した各局面の理論上の確率との差分とその局面での差分の平均を計算して比較できるようにします。また、その際に、プログラムを再利用できるように analyze_playout という関数を下記のプログラムのように定義することにしました。

1 行目：分析する playout の返り値を代入する仮引数 retval と、各局面からプレイアウトを行った場合のそれぞれの確率が代入された Mbtree クラスのインスタンスを代入する仮引数 mbtree を持つ関数として analyze_playout を定義する
3、4 行目：各局面の差分の合計と差分の個数を計算する変数を 0 で初期化する
9 行目：mb の局面に対応するゲーム木のノードは、mbtree の nodelist_by_mb 属性に代入された dict の tuple(mb.records) のキーの値に代入されているので、それを node に代入する。忘れた方は以前の記事を復習すること
12 行目：結果の一覧の見出しを表示する。prob は mbtree に記録された理論上の確率を、diff はプレイアウトで計算された割合と理論上の確率の差分（differnce）を表す
14 ~ 17 行目：20 行目の記述を短くするために、20 行目で表示する内容を計算して変数に代入する
16 行目：node.playout_prob から対応する理論上の確率（単位は %）を計算する
17 行目：プレイアウトで計算された割合と理論上の確率の差分（絶対値）を計算する
18、19 行目：差分の合計と差分を計算した回数を計算する
20 行目：結果を並べて表示する。なお、プレイアウトの回数を増やした場合に精度が高くなることを考慮して小数点以下第 2 桁まで表示するように修正した
24 行目：差分の平均を計算して表示する

 1  def analyze_playout(mb, retval, mbtree):
 2      print(f"playout count = {retval['count']}")
 3      diffsum = 0
 4      diffcount = 0
 5      for move, counts in retval["result"].items():
 6          print(f"move {mb.board.move_to_xy(move)}")
 7          mb.move(move)
 8          print(mb)
 9          node = mbtree.nodelist_by_mb[tuple(mb.records)]
10          mb.unmove()
11          total = sum(counts.values())
12          print("        count   ratio    prob    diff")
13          for status, count in counts.items():
14              mark = mb.board.MARK_TABLE[status]
15              ratio = count / total * 100
16              prob = node.playout_prob[status] * 100
17              diff = abs(ratio - prob)
18              diffsum += diff
19              diffcount += 1
20              print(f"{mark:4s}: {count:7d} {ratio:6.2f}% {prob:6.2f}% {diff:6.2f}%")
21          print()
22          print("-------------------------------------")
23          print()
24      print(f"diff average = {diffsum / diffcount:6.2f}%")
25      print()

行番号のないプログラム

def analyze_playout(mb, retval, mbtree):
    print(f"playout count = {retval['count']}")
    diffsum = 0
    diffcount = 0
    for move, counts in retval["result"].items():
        print(f"move {mb.board.move_to_xy(move)}")
        mb.move(move)
        print(mb)
        node = mbtree.nodelist_by_mb[tuple(mb.records)]
        mb.unmove()
        total = sum(counts.values())
        print("        count   ratio    prob    diff")
        for status, count in counts.items():
            mark = mb.board.MARK_TABLE[status]
            ratio = count / total * 100
            prob = node.playout_prob[status] * 100
            diff = abs(ratio - prob)
            diffsum += diff
            diffcount += 1
            print(f"{mark:4s}: {count:7d} {ratio:6.2f}% {prob:6.2f}% {diff:6.2f}%")
        print()
        print("-------------------------------------")
        print()
    print(f"diff average = {diffsum / diffcount:6.2f}%")
    print()

大数の法則が成り立つことの確認

下記はプレイアウトの回数を 100、1000、1 万回、10 万回、100 万回にした場合の結果を analyze_playout で表示するプログラムです。実行結果は長いので折りたたみました。

for pnum in [100, 1000, 10000, 100000, 1000000]:
    retval = playout(mb, pnum=pnum)
    analyze_playout(mb, retval, mbtree)

実行結果

playout count = 100
move (0, 0)
Turn x
O..
...
...

        count   ratio    prob    diff
o   :      14  73.68%  60.71%  12.97%
x   :       5  26.32%  26.43%   0.11%
draw:       0   0.00%  12.86%  12.86%

-------------------------------------

move (0, 1)
Turn x
...
O..
...

        count   ratio    prob    diff
o   :       2  16.67%  53.57%  36.90%
x   :       6  50.00%  33.57%  16.43%
draw:       4  33.33%  12.86%  20.48%

-------------------------------------

move (0, 2)
Turn x
...
...
O..

        count   ratio    prob    diff
o   :       7  70.00%  60.71%   9.29%
x   :       3  30.00%  26.43%   3.57%
draw:       0   0.00%  12.86%  12.86%

-------------------------------------

move (1, 0)
Turn x
.O.
...
...

        count   ratio    prob    diff
o   :       1  16.67%  53.57%  36.90%
x   :       3  50.00%  33.57%  16.43%
draw:       2  33.33%  12.86%  20.48%

-------------------------------------

move (1, 1)
Turn x
...
.O.
...

        count   ratio    prob    diff
o   :      11  84.62%  69.29%  15.33%
x   :       2  15.38%  19.29%   3.90%
draw:       0   0.00%  11.43%  11.43%

-------------------------------------

move (1, 2)
Turn x
...
...
.O.

        count   ratio    prob    diff
o   :       5  45.45%  53.57%   8.12%
x   :       5  45.45%  33.57%  11.88%
draw:       1   9.09%  12.86%   3.77%

-------------------------------------

move (2, 0)
Turn x
..O
...
...

        count   ratio    prob    diff
o   :       4  44.44%  60.71%  16.27%
x   :       5  55.56%  26.43%  29.13%
draw:       0   0.00%  12.86%  12.86%

-------------------------------------

move (2, 1)
Turn x
...
..O
...

        count   ratio    prob    diff
o   :       6  75.00%  53.57%  21.43%
x   :       0   0.00%  33.57%  33.57%
draw:       2  25.00%  12.86%  12.14%

-------------------------------------

move (2, 2)
Turn x
...
...
..O

        count   ratio    prob    diff
o   :       7  58.33%  60.71%   2.38%
x   :       4  33.33%  26.43%   6.90%
draw:       1   8.33%  12.86%   4.52%

-------------------------------------

diff average =  14.55%

playout count = 1000
move (0, 0)
Turn x
O..
...
...

        count   ratio    prob    diff
o   :      84  63.64%  60.71%   2.92%
x   :      40  30.30%  26.43%   3.87%
draw:       8   6.06%  12.86%   6.80%

-------------------------------------

move (0, 1)
Turn x
...
O..
...

        count   ratio    prob    diff
o   :      53  56.99%  53.57%   3.42%
x   :      30  32.26%  33.57%   1.31%
draw:      10  10.75%  12.86%   2.10%

-------------------------------------

move (0, 2)
Turn x
...
...
O..

        count   ratio    prob    diff
o   :      79  69.30%  60.71%   8.58%
x   :      22  19.30%  26.43%   7.13%
draw:      13  11.40%  12.86%   1.45%

-------------------------------------

move (1, 0)
Turn x
.O.
...
...

        count   ratio    prob    diff
o   :      63  60.00%  53.57%   6.43%
x   :      32  30.48%  33.57%   3.10%
draw:      10   9.52%  12.86%   3.33%

-------------------------------------

move (1, 1)
Turn x
...
.O.
...

        count   ratio    prob    diff
o   :      77  74.04%  69.29%   4.75%
x   :      19  18.27%  19.29%   1.02%
draw:       8   7.69%  11.43%   3.74%

-------------------------------------

move (1, 2)
Turn x
...
...
.O.

        count   ratio    prob    diff
o   :      72  54.14%  53.57%   0.56%
x   :      45  33.83%  33.57%   0.26%
draw:      16  12.03%  12.86%   0.83%

-------------------------------------

move (2, 0)
Turn x
..O
...
...

        count   ratio    prob    diff
o   :      66  60.55%  60.71%   0.16%
x   :      34  31.19%  26.43%   4.76%
draw:       9   8.26%  12.86%   4.60%

-------------------------------------

move (2, 1)
Turn x
...
..O
...

        count   ratio    prob    diff
o   :      53  51.96%  53.57%   1.61%
x   :      35  34.31%  33.57%   0.74%
draw:      14  13.73%  12.86%   0.87%

-------------------------------------

move (2, 2)
Turn x
...
...
..O

        count   ratio    prob    diff
o   :      65  60.19%  60.71%   0.53%
x   :      37  34.26%  26.43%   7.83%
draw:       6   5.56%  12.86%   7.30%

-------------------------------------

diff average =   3.33%

playout count = 10000
move (0, 0)
Turn x
O..
...
...

        count   ratio    prob    diff
o   :     702  62.51%  60.71%   1.80%
x   :     273  24.31%  26.43%   2.12%
draw:     148  13.18%  12.86%   0.32%

-------------------------------------

move (0, 1)
Turn x
...
O..
...

        count   ratio    prob    diff
o   :     561  51.52%  53.57%   2.06%
x   :     383  35.17%  33.57%   1.60%
draw:     145  13.31%  12.86%   0.46%

-------------------------------------

move (0, 2)
Turn x
...
...
O..

        count   ratio    prob    diff
o   :     703  60.71%  60.71%   0.01%
x   :     321  27.72%  26.43%   1.29%
draw:     134  11.57%  12.86%   1.29%

-------------------------------------

move (1, 0)
Turn x
.O.
...
...

        count   ratio    prob    diff
o   :     595  54.59%  53.57%   1.02%
x   :     357  32.75%  33.57%   0.82%
draw:     138  12.66%  12.86%   0.20%

-------------------------------------

move (1, 1)
Turn x
...
.O.
...

        count   ratio    prob    diff
o   :     750  67.63%  69.29%   1.66%
x   :     227  20.47%  19.29%   1.18%
draw:     132  11.90%  11.43%   0.47%

-------------------------------------

move (1, 2)
Turn x
...
...
.O.

        count   ratio    prob    diff
o   :     588  54.85%  53.57%   1.28%
x   :     360  33.58%  33.57%   0.01%
draw:     124  11.57%  12.86%   1.29%

-------------------------------------

move (2, 0)
Turn x
..O
...
...

        count   ratio    prob    diff
o   :     672  60.60%  60.71%   0.12%
x   :     295  26.60%  26.43%   0.17%
draw:     142  12.80%  12.86%   0.05%

-------------------------------------

move (2, 1)
Turn x
...
..O
...

        count   ratio    prob    diff
o   :     612  54.79%  53.57%   1.22%
x   :     379  33.93%  33.57%   0.36%
draw:     126  11.28%  12.86%   1.58%

-------------------------------------

move (2, 2)
Turn x
...
...
..O

        count   ratio    prob    diff
o   :     693  61.17%  60.71%   0.45%
x   :     302  26.65%  26.43%   0.23%
draw:     138  12.18%  12.86%   0.68%

-------------------------------------

diff average =   0.88%

playout count = 100000
move (0, 0)
Turn x
O..
...
...

        count   ratio    prob    diff
o   :    6748  60.45%  60.71%   0.26%
x   :    2989  26.78%  26.43%   0.35%
draw:    1426  12.77%  12.86%   0.08%

-------------------------------------

move (0, 1)
Turn x
...
O..
...

        count   ratio    prob    diff
o   :    6028  53.74%  53.57%   0.16%
x   :    3724  33.20%  33.57%   0.37%
draw:    1466  13.07%  12.86%   0.21%

-------------------------------------

move (0, 2)
Turn x
...
...
O..

        count   ratio    prob    diff
o   :    6748  61.25%  60.71%   0.54%
x   :    2878  26.12%  26.43%   0.31%
draw:    1391  12.63%  12.86%   0.23%

-------------------------------------

move (1, 0)
Turn x
.O.
...
...

        count   ratio    prob    diff
o   :    5979  54.58%  53.57%   1.01%
x   :    3603  32.89%  33.57%   0.68%
draw:    1372  12.53%  12.86%   0.33%

-------------------------------------

move (1, 1)
Turn x
...
.O.
...

        count   ratio    prob    diff
o   :    7832  69.97%  69.29%   0.69%
x   :    2108  18.83%  19.29%   0.45%
draw:    1253  11.19%  11.43%   0.23%

-------------------------------------

move (1, 2)
Turn x
...
...
.O.

        count   ratio    prob    diff
o   :    6088  55.10%  53.57%   1.52%
x   :    3595  32.53%  33.57%   1.04%
draw:    1367  12.37%  12.86%   0.49%

-------------------------------------

move (2, 0)
Turn x
..O
...
...

        count   ratio    prob    diff
o   :    6925  62.05%  60.71%   1.34%
x   :    2893  25.92%  26.43%   0.51%
draw:    1342  12.03%  12.86%   0.83%

-------------------------------------

move (2, 1)
Turn x
...
..O
...

        count   ratio    prob    diff
o   :    5985  53.67%  53.57%   0.10%
x   :    3671  32.92%  33.57%   0.65%
draw:    1496  13.41%  12.86%   0.56%

-------------------------------------

move (2, 2)
Turn x
...
...
..O

        count   ratio    prob    diff
o   :    6702  60.42%  60.71%   0.30%
x   :    3000  27.04%  26.43%   0.62%
draw:    1391  12.54%  12.86%   0.32%

-------------------------------------

diff average =   0.52%

playout count = 1000000
move (0, 0)
Turn x
O..
...
...

        count   ratio    prob    diff
o   :   67704  60.95%  60.71%   0.23%
x   :   29128  26.22%  26.43%   0.21%
draw:   14256  12.83%  12.86%   0.02%

-------------------------------------

move (0, 1)
Turn x
...
O..
...

        count   ratio    prob    diff
o   :   59670  53.60%  53.57%   0.03%
x   :   37473  33.66%  33.57%   0.09%
draw:   14185  12.74%  12.86%   0.12%

-------------------------------------

move (0, 2)
Turn x
...
...
O..

        count   ratio    prob    diff
o   :   67231  60.51%  60.71%   0.20%
x   :   29493  26.55%  26.43%   0.12%
draw:   14375  12.94%  12.86%   0.08%

-------------------------------------

move (1, 0)
Turn x
.O.
...
...

        count   ratio    prob    diff
o   :   59769  53.71%  53.57%   0.14%
x   :   37156  33.39%  33.57%   0.18%
draw:   14348  12.89%  12.86%   0.04%

-------------------------------------

move (1, 1)
Turn x
...
.O.
...

        count   ratio    prob    diff
o   :   76943  69.20%  69.29%   0.09%
x   :   21572  19.40%  19.29%   0.11%
draw:   12679  11.40%  11.43%   0.03%

-------------------------------------

move (1, 2)
Turn x
...
...
.O.

        count   ratio    prob    diff
o   :   59745  53.77%  53.57%   0.20%
x   :   37098  33.39%  33.57%   0.18%
draw:   14267  12.84%  12.86%   0.02%

-------------------------------------

move (2, 0)
Turn x
..O
...
...

        count   ratio    prob    diff
o   :   67435  60.80%  60.71%   0.08%
x   :   29203  26.33%  26.43%   0.10%
draw:   14283  12.88%  12.86%   0.02%

-------------------------------------

move (2, 1)
Turn x
...
..O
...

        count   ratio    prob    diff
o   :   59804  53.66%  53.57%   0.09%
x   :   37307  33.48%  33.57%   0.10%
draw:   14333  12.86%  12.86%   0.00%

-------------------------------------

move (2, 2)
Turn x
...
...
..O

        count   ratio    prob    diff
o   :   67169  60.76%  60.71%   0.05%
x   :   29234  26.45%  26.43%   0.02%
draw:   14140  12.79%  12.86%   0.07%

-------------------------------------

diff average =   0.10%

下記は上記の実行結果から差分だけを取り出した表で、それぞれの列はプレイアウトで最初に着手した合法手の座標を表します。また、表のセルの数値は上から順に「〇の勝利」、「× の勝利」、「引き分け」で単位は % です。

回数	0, 0	0, 1	0, 2	1, 0	1, 1	1, 2	2, 0	2, 1	2, 2	平均
100	3.57 5.00 8.57	6.43 3.57 2.86	19.54 26.51 6.97	13.10 0.24 12.86	5.71 2.62 3.10	3.57 16.43 12.86	2.92 0.84 3.77	39.29 23.57 15.71	9.29 26.43 17.14	14.55
1000	5.95 0.42 6.38	0.12 1.77 1.65	3.25 3.91 0.66	8.69 6.21 2.48	0.24 3.10 2.86	5.56 1.40 4.16	1.45 3.01 1.56	3.34 2.68 0.66	1.67 3.10 1.43	3.33
1万	1.80 0.97 0.83	2.45 1.85 0.60	1.73 0.12 1.61	1.44 0.83 0.61	1.58 1.83 0.25	0.80 0.06 0.74	0.84 0.92 0.08	0.86 0.09 0.77	0.09 1.02 0.93	0.88
10万	0.15 0.21 0.06	0.19 0.39 0.20	0.38 0.16 0.22	0.99 0.62 0.36	0.70 0.53 0.17	1.58 1.04 0.54	1.46 0.52 0.94	0.15 0.60 0.45	0.24 0.62 0.37	0.52
100万	0.23 0.21 0.02	0.03 0.09 0.11	0.20 0.11 0.09	0.16 0.20 0.04	0.08 1.12 0.04	0.20 0.18 0.02	0.08 0.10 0.02	0.09 0.10 0.01	0.05 0.02 0.06	0.10

表からプレイアウトの回数を多くすると明らかに差分が小さくなることから、それぞれの割合が理論上の確率に近づいていることがわかります。このことから、原始モンテカルロ法は大数の法則を利用したアルゴリズムであることが確認できました。

ゲーム木のサイズと原始モンテカルロ法

〇×ゲームはゲーム木のサイズが小さいため、任意の局面に対して実際に $P(X_S=〇)$、$P(X_S=×)$、$P(X_S=△)$ の正確な値をあらかじめ計算することができます。そのため、実際には上記で行ったようにわざわざ原始モンテカルロ法でその近似値の計算を行う必要はありませんが、原始モンテカルロ法が有効であることを示すために今後の記事で作成する AI でも原始モンテカルロ法を引き続き利用することにします。

一方、オセロや将棋などの多くのゲームはゲーム木が大きすぎるため、ミニマックス法で厳密な評価値を計算できないのと同様に、それらの値を実際に計算することは不可能です。

原始モンテカルロ法は、そのような場合でも実際に計算することができない理論上の $P(X_S=〇)$、$P(X_S=×)$、$P(X_S=△)$ の近似値を、大数の法則を利用して計算することができる点が優れています。

今回の記事のまとめ

今回の記事では原始モンテカルロ法で必要となる〇× ゲームのプレイアウトを行う関数を定義し、プレイアウトの回数を増やすことで計算されたプレイアウトの結果を集計した近似値が、大数の法則によって理論上の確率に実際に近づいていくことを示しました。

また、このことからプレイアウトの回数はなるべく多いほうが望ましいことがわかりますが、今回の記事で実装した playout の関数が行っている処理には効率が悪い点がいくつかあるため処理速度が遅いという問題があります。そこで、次回の記事では playout の処理を効率化して、同じ時間でより多くのプレイアウトを行うことができるようにします。

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

今回の記事で定義した playout と analyze_playout は util.py に保存することにします。

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

次回の記事

近日公開予定です

calc_score_by_df の定義はかなり前の記事で行ったので、忘れた方は以前の記事を復習して下さい ↩
筆者のパソコンでは約 30 秒ほどかかりました ↩
筆者は最初にそのように実装して後から間違いに気づきました ↩

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を一から作成する その232 プレイアウトの実装と大数の法則

目次と前回の記事

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

今回の記事の内容

プレイアウトの確率の計算

確率質量関数の計算式

深さ優先アルゴリズムによる計算の実装

__init__ メソッドの修正と動作の確認

ファイルへのデータの保存

プレイアウトの処理の実装

playout のアルゴリズム

playout の仮引数と返り値

プレイアウトの結果の表示

理論上の確率との比較

大数の法則が成り立つことの確認

ゲーム木のサイズと原始モンテカルロ法

今回の記事のまとめ

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

次回の記事

Pythonで〇×ゲームのAIを一から作成する　その232　プレイアウトの実装と大数の法則

`init` メソッドの修正と動作の確認

`playout` のアルゴリズム

`playout` の仮引数と返り値