Pythonで〇×ゲームのAIを一から作成する　その238　引き分けを考慮した評価値を用いた原始モンテカルロ法の実装と検証

Posted at 2026-07-26

目次と前回の記事

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 の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

引き分けを考慮した評価値を用いた原始モンテカルロ法

今回の記事では原始モンテカルロ法がどのような強化学習を行っているかについて説明する予定だったのですが、これまでに説明したものと異なるアルゴリズムで勝率を計算する原始モンテカルロ法があり、そちらのアルゴリズムのほうが一般的であることに気が付きました。そこで今回の記事ではそのアルゴリズムの実装とその性質の検証を行うことにします。

下記は以前の記事で説明した原始モンテカルロ法のアルゴリズムの再掲です。

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

なお、以後の説明では表記を短くするために「勝率」、「引き分け率」、「敗率」をその局面で複数回のプレイアウトを行った際の結果を表すものとします。

上記の手順 2 では「最も高い勝率」と表記していますが、〇× ゲームのよう引き分けが存在するゲームの場合は、単純に最も高い勝率だけを用いて最善手を計算すると、引き分けが考慮されないという問題が発生します。例えば、すべての合法手を着手した局面の勝率が 0 の場合は、引き分け率の大きさに関わらずすべての合法手が最善手として計算されてしまいます。そこで、以前の記事で説明したように、原始モンテカルロ法で最善手を計算する AI である ai_pmc では、上記の手順 2 の処理を下記のアルゴリズムで計算することにしました。

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

このアルゴリズムは、最高勝率が等しい場合に引き分け率を用いて最善手を計算する必要があるため、勝率と引き分け率という 2 つの数値を用いた 2 段階の手順で最善手を計算する点が複雑であるという問題があります。

引き分けを考慮した評価値を用いるアルゴリズム

別のアルゴリズムとして引き分けを 0.5 勝として考慮するという方法があるので、そのアルゴリズムについて説明します。

記号の定義

以下の説明では表記を簡潔にするために下記の記号を用いることにします。なお、「プレイアウトの評価値」の意味についてはこの後ですぐに説明します。

記号	意味
$wr$	プレイアウトでの〇の勝率。win ratio の略
$dr$	プレイアウトでの引き分け率。draw ratio の略
$lr$	プレイアウトでの × の勝率
$ps_先$	プレイアウトの〇の手番での評価値。ps は playout score の略
$ps_後$	プレイアウトの × の手番での評価値

プレイアウトの評価値の意味と計算式

このアルゴリズムでは、〇の手番の場合は合法手を着手した局面の中で下記の式によって計算される「引き分けを 0.5 勝として計算した〇の勝率」が最も高い合法手を最善手として計算します。

$wr + dr × 0.5$

最も高い値を取る合法手を最善手として計算するという点から、この値は以前の記事で説明した「評価値」であると考えることができるので、本記事ではこの値の事を「プレイアウトの〇の評価値」と呼び、$ps_〇$ と表記することにします。従って、$ps_〇$ は下記の式で計算されます。

$ps_〇 = wr + dr × 0.5$

同様に、× の手番の場合は合法手を着手した局面の中で下記の式によって計算される「引き分けを 0.5 勝として計算した × の勝率」が最も高い合法手を最善手として計算します。本記事ではこの値の事を「× のプレイアウトの評価値」と呼び、$ps_×$ と表記することにします。

$ps_× = lr + dr × 0.5$

最善手を計算するアルゴリズム

従って、最善手は下記のアルゴリズムで計算されます。

〇の手番では、合法手を着手した局面の中で $ps_〇$ が最大となる合法手を最善手とする
× の手番では、合法手を着手した局面の中で $ps_×$ が最大となる合法手を最善手とする

ただし、$ps_〇$ と $ps_×$ は下記の式で計算するものとする。

$ps_〇 = wr + dr × 0.5$

$ps_× = lr + dr × 0.5$

以下の説明では $ps_〇$ と $ps_×$ をひとまとめにしたものを「プレイアウトの評価値」と表現することにします。

プレイアウトの評価値の性質

$ps_〇$ と $ps_×$ には以下のような性質があります。

$0 ≦ ps_〇 ≦ 1$
$0 ≦ ps_× ≦ 1$
$ps_〇 + ps_× = 1$

それぞれについて証明します。

$0 ≦ ps_〇 ≦ 1$ は下記の理由から常に成り立ちます。$0 ≦ ps_× ≦ 1$ も同様です。この性質から $ps_〇$ と $ps_×$ は確率の一種であると考えることができます。

$wr$、$dr$、$lr$ は確率なのでそれぞれ 0 以上 1 以下の値になるため $0 ≦ ps_〇$ が成り立つ
〇の勝率と引き分け率と × の勝率の合計は 1 になるので下記の式が成り立つ
$wr + dr + lr = 1$
$0 ≦ dr$、$0 ≦ lr$ から下記の式が成り立つ
$ps_〇 = wr + dr × 0.5 ≦ wr + dr + lr = 1$

$ps_〇$ と $ps_×$ の計算式を $ps_〇 + ps_×$ に当てはめると下記のように 1 になります。

$ps_〇 + ps_× = wr + dr × 0.5 + lr + dr × 0.5$

$= wr + dr + lr = 1$

このことから、$ps_× = 1 - ps_〇$ が成り立つので、$ps_×$ は $ps_〇$ が大きい程小さな値になります。従って、下記のように最善手を $ps_〇$ だけを利用して求めることもできます。

〇の手番では、合法手を着手した局面の中で $ps_〇$ が最大となる合法手を最善手とする
× の手番では、合法手を着手した局面の中で $ps_〇$ が最小となる合法手を最善手とする

このアルゴリズムでは $ps_〇$ の値だけを基準に最善手を計算できるので、勝率と引き分け率を別々に扱うアルゴリズムより計算方法がシンプルになるという利点があります。また、プレイアウトの評価値の中に引き分け率が含まれているので、すべての合法手を着手した局面の勝率が 0 % の場合でも引き分け率を考慮した最善手を計算することができます。

下記の Wikipedia の記事に記載があるように、モンテカルロ法を利用したアルゴリズムでは引き分けを 0.5 勝として扱うことが一般的なようです。

アルゴリズムの優劣

計算の複雑さを除くと、どちらが良いアルゴリズムであるかを断言することはできません。

例えば下記のような 5 つの合法手が存在する〇の手番の局面の場合を考えることにします。

着手するとその後にお互いがどのような着手を行っても〇が 100 % 勝利する合法手が 1 つ存在する
着手するとその後にお互いがどのような着手を行っても 100 % 引き分けになる合法手が 3 つ存在する
着手するとその後にお互いがどのような着手を行っても〇が 100 % 敗北する合法手が 1 つ存在する

上記の場合のそれぞれのアルゴリズムで計算される値は下記のように大幅に異なります。

勝率を用いるアルゴリズムの場合は 1 ÷ 5 = 0.2 となる
引き分けを考慮した $ps_〇$ を用いるアルゴリズムの場合は (1 + 3 * 0.5) ÷ 5 = 0.5 となる

勝率を用いるアルゴリズムは勝利以外を無視するため「勝利のみを重視する」合法手が、引き分けを考慮する $ps_〇$ を用いるアルゴリズムは引き分けを勝利の半分として計算するため「勝利と引き分けを重視」、すなわち「敗北を避ける」合法手が選択されやすくなります。

このように 2 つのアルゴリズムは重視するものが異なるため、どちらのアルゴリズムを選ぶかは何を重視するかによって選択する必要があります。例えば、次の対戦は引き分けでも良い場合は引き分けを考慮した $ps_〇$ を用いたアルゴリズムを選んだほうが良いでしょう。

あらかじめ想定する対戦相手（または対戦相手とほぼ同等の能力を持つ相手）と何度も対戦を行うことができるような場合は、両方のアルゴリズムで対戦を行い、対戦成績が良い方を選択するという方法もあります。

$ps_〇$ や $ps_×$ を計算する際に、引き分け率である $dr$ に乗算する値を 0 ~ 1 の範囲で設定することで、引き分けをどの程度考慮するかを調整することができます。具体的には $ps_〇$ と $ps_×$ を下記の式で計算します。

$ps_〇 = wr + dr × α$ （ただし、$0 ≦ α ≦ 1$ とする）
$ps_× = lr + dr × α$ （ただし、$0 ≦ α ≦ 1$ とする）

この式の $α$ は引き分けを何勝として計算するかを表す値で、例えば $α = 0.2$ とした場合の $ps_〇$ は下記のように引き分けを 0.2 勝として計算します。

$ps_〇 = wr + dr × 0.2$

また、$α = 0$ の場合は勝率が、$α = 1$ の場合は敗北しない率が計算されます。

なお、$α ≠ 0.5$ の場合は、下記のように $ps_〇 + ps_×$ が常に 1 になるとは限らない点に注意が必要です。

$ps_〇 + ps_× = wr + dr × α + lr + dr × α$
$= wr + 2α × dr + lr$
$= wr + dr + lr + (2α - 1) × dr$
$= 1 + (2α - 1) × dr$

アルゴリズムの違いが合法手の選択や特定の AI との対戦結果にどのような影響を及ぼすかを検証するために、今回の記事では引き分けを 0.5 勝として $ps_〇$ と $ps_×$ を計算する原始モンテカルロ法の AI である ai_pmc2 を実装し、ai_pmc との違いを検証することにします。

視覚化のための修正

ai_pmc2 を実装する前に、後で視覚的な検証を行えるようにするために各局面で無限回のプレイアウトを行った場合の $ps_〇$ の期待値¹を Mbtree クラスで計算してファイルに保存し、ゲーム木の視覚化を行う Marubatsu_GUI クラスで表示できるようにすることにします。なお、$ps_×$ は先ほど説明したように $1 - ps_〇$ という式で計算できるので、ファイルには $ps_〇$ の期待値だけを保存することにします。

Mbtree クラスの `calc_playout_prob_by_df` メソッドの修正

各局面で無限回のプレイアウトを行った場合の〇の勝率（$wr$）、引き分け率（$dr$）、× の勝率（$lr$）の期待値の計算は以前の記事で実装した Mbtree クラスの calc_playout_prob_by_df メソッドで行い、局面を表す Node クラスのインスタンスの playout_prob という属性に代入しました。

同様に、$ps_〇$ の期待値の計算と Node クラスの属性への代入処理もこのメソッドで行うことにします。その際に $ps_〇$ の期待値は playout_score という属性に代入することにします。

下記はそのように calc_playout_prob_by_df メソッドを修正したプログラムです。

12、13 行目：ゲームの決着がついた局面の場合に playout_score 属性に〇の勝利の場合に 1 を、引き分けの場合に 0.5 を代入する。なお、比較演算子の計算結果である true と false に対して演算を行うと、true は 1、false は 0 として計算が行われるので if 文を使わない 12、13 行目の式でそのような計算を行うことができる
20、21 行目：ゲームの決着が付いていない局面の場合は playout_prob 属性に代入された〇の勝率（$wr$）の期待値に引き分け率（$dr$）の期待値の半分を加算した値を $ps_〇$ の期待値として計算し、 playout_score 属性に代入する

 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          node.playout_score = (node.mb.status == node.mb.CIRCLE) * 1 + \
13                               (node.mb.status == node.mb.DRAW) * 0.5
14      else:
15          childnum = len(node.children)
16          for childnode in node.children:
17              self.calc_playout_prob_by_df(childnode)
18              for status, prob in childnode.playout_prob.items():
19                  node.playout_prob[status] += prob / childnum  
20              node.playout_score = node.playout_prob[node.mb.CIRCLE] + \
21                                   node.playout_prob[node.mb.DRAW] * 0.5
22  
23  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
        node.playout_score = (node.mb.status == node.mb.CIRCLE) * 1 + \
                             (node.mb.status == node.mb.DRAW) * 0.5
    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  
            node.playout_score = node.playout_prob[node.mb.CIRCLE] + \
                                 node.playout_prob[node.mb.DRAW] * 0.5
            
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
+       node.playout_score = (node.mb.status == node.mb.CIRCLE) * 1 + \
+                            (node.mb.status == node.mb.DRAW) * 0.5
    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  
+           node.playout_score = node.playout_prob[node.mb.CIRCLE] + \
+                                node.playout_prob[node.mb.DRAW] * 0.5
            
Mbtree.calc_playout_prob_by_df = calc_playout_prob_by_df

上記の修正後に下記のプログラムで Mbtree クラスのインスタンスを作成し、ゲーム開始時の局面を表すルートノードの playout_score 属性を表示すると、実行結果の最後の行のように $ps_〇$ の期待値として約 0.648 が計算されていることが確認できます。

mbtree = Mbtree()
print(mbtree.root.playout_score)

実行結果

     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
0.6484126984126983

Mbtree クラスの `calc_and_save_bestmoves_and_score_by_board` メソッドの修正

計算した $ps_〇$ の期待値を Mbtree_GUI クラスで表示するためには計算したデータをファイルに保存する必要があるので、その処理を行う calc_and_save_bestmoves_and_score_by_board メソッドを下記のプログラムのように修正します。

17 行目：ファイルに保存するデータの、各局面を表す dict の playout_score のキーの値に $ps_〇$ の期待値を代入する

 1  from tqdm import tqdm
 2  import gzip, pickle
 3  
 4  def calc_and_save_bestmoves_and_score_by_board(self, path):
 5      bestmoves_and_score_by_board = {}
 6      for node in tqdm(self.nodelist):
 7          txt = node.mb.board_to_str()
 8          if not txt in bestmoves_and_score_by_board.keys():
 9              bestmoves_and_score_by_board[txt] = {
10                  "bestmoves": [node.mb.board.move_to_xy(move) for move in node.bestmoves],
11                  "score": node.score,
12                  "playout_prob": { 
13                      node.mb.CIRCLE_STR: node.playout_prob[node.mb.CIRCLE],
14                      node.mb.CROSS_STR: node.playout_prob[node.mb.CROSS],
15                      node.mb.DRAW: node.playout_prob[node.mb.DRAW],
16                  },
17                  "playout_score": node.playout_score,
18              }
元と同じなので省略
19  
20  Mbtree.calc_and_save_bestmoves_and_score_by_board = calc_and_save_bestmoves_and_score_by_board

行番号のないプログラム

from tqdm import tqdm
import gzip, pickle

def calc_and_save_bestmoves_and_score_by_board(self, path):
    bestmoves_and_score_by_board = {}
    for node in tqdm(self.nodelist):
        txt = node.mb.board_to_str()
        if not txt in bestmoves_and_score_by_board.keys():
            bestmoves_and_score_by_board[txt] = {
                "bestmoves": [node.mb.board.move_to_xy(move) for move in node.bestmoves],
                "score": node.score,
                "playout_prob": { 
                    node.mb.CIRCLE_STR: node.playout_prob[node.mb.CIRCLE],
                    node.mb.CROSS_STR: node.playout_prob[node.mb.CROSS],
                    node.mb.DRAW: node.playout_prob[node.mb.DRAW],
                },
                "playout_score": node.playout_score,
            }

    with gzip.open(path, "wb") as f:
        pickle.dump(bestmoves_and_score_by_board, f)
    
    return bestmoves_and_score_by_board           

Mbtree.calc_and_save_bestmoves_and_score_by_board = calc_and_save_bestmoves_and_score_by_board

修正箇所

from tqdm import tqdm
import gzip, pickle

def calc_and_save_bestmoves_and_score_by_board(self, path):
    bestmoves_and_score_by_board = {}
    for node in tqdm(self.nodelist):
        txt = node.mb.board_to_str()
        if not txt in bestmoves_and_score_by_board.keys():
            bestmoves_and_score_by_board[txt] = {
                "bestmoves": [node.mb.board.move_to_xy(move) for move in node.bestmoves],
                "score": node.score,
                "playout_prob": { 
                    node.mb.CIRCLE_STR: node.playout_prob[node.mb.CIRCLE],
                    node.mb.CROSS_STR: node.playout_prob[node.mb.CROSS],
                    node.mb.DRAW: node.playout_prob[node.mb.DRAW],
                },
+               "playout_score": node.playout_score,
            }

元と同じなので省略   

Mbtree.calc_and_save_bestmoves_and_score_by_board = calc_and_save_bestmoves_and_score_by_board

上記の定義後に、下記のプログラムで Mbtree_GUI クラスで利用する 3 つのファイルを $ps_〇$ の期待値が記録されたデータで更新します。なお、実行結果は特に重要な情報は表示されないので省略します。

mbtree = Mbtree()
mbtree.calc_and_save_bestmoves_and_score_by_board("../data/bestmoves_and_score_by_board.dat")
mbtree2 = Mbtree(shortest_victory=True)
mbtree2.calc_and_save_bestmoves_and_score_by_board("../data/bestmoves_and_score_by_board_shortest_victory.dat")
mbtree3 = Mbtree(shortest_victory=True, recalculate_draw_score=True)
mbtree3.calc_and_save_bestmoves_and_score_by_board("../data/bestmoves_and_score_by_board_sv_rd.dat")

Mbtree_GUI クラスの `create_widget` メソッドの修正

次に $ps_〇$ と $ps_×$ の期待値を Mbtree_GUI クラスで表示できるようにします。具体的には Dropdown に $ps_〇$ と $ps_×$ の期待値を表示する項目を追加し、その項目を選択した際に局面の上部に対応する期待値を表示するように修正します。修正方法は以前の記事で行ったものと似ているのでそちらも参照して下さい。

最初に Dropdown を作成する Mbtree_GUI クラスの create_widets メソッドを下記のプログラムのように修正します。項目名は「プレイアウトの〇の評価値」、「プレイアウトの × の評価値」とし、それらの項目を選択した際の Dropdown の value 属性の値を "playout_score_o" と "playout_score_x" としました。

13、14 行目：Dropdown に上記で説明した項目を追加した

 1  from tree import Mbtree_GUI
 2  import matplotlib.pyplot as plt
 3  import ipywidgets as widgets
 4  
 5  def create_widgets(self):
元と同じなので省略
 6      self.data_dropdown= widgets.Dropdown(
 7          options = {
 8              "表示なし": False,
 9              "評価値": "score",
10              "プレイアウトでの〇の勝率": self.selectednode.mb.CIRCLE_STR,
11              "プレイアウトでの×の勝率": self.selectednode.mb.CROSS_STR,
12              "プレイアウトでの引き分け率": self.selectednode.mb.DRAW,
13              "プレイアウトの〇の評価値": "playout_score_o",
14              "プレイアウトの×の評価値": "playout_score_x",
15          },
16          description = "データの表示",
17          value = "score"
18      )
元と同じなので省略
19  
20  Mbtree_GUI.create_widgets = create_widgets

行番号のないプログラム

from tree import Mbtree_GUI
import matplotlib.pyplot as plt
import ipywidgets as widgets

def create_widgets(self):
    self.output = widgets.Output()  
    self.print_helpmessage()
    self.output.layout.display = "none"
    self.left_button = self.create_button("←", 50)
    self.up_button = self.create_button("↑", 50)
    self.right_button = self.create_button("→", 50)
    self.down_button = self.create_button("↓", 50)
    self.data_dropdown= widgets.Dropdown(
        options = {
            "表示なし": False,
            "評価値": "score",
            "プレイアウトでの〇の勝率": self.selectednode.mb.CIRCLE_STR,
            "プレイアウトでの×の勝率": self.selectednode.mb.CROSS_STR,
            "プレイアウトでの引き分け率": self.selectednode.mb.DRAW,
            "プレイアウトの〇の評価値": "playout_score_o",
            "プレイアウトの×の評価値": "playout_score_x",
        },
        description = "データの表示",
        value = "score"
    )
    self.size_slider = widgets.FloatSlider(min=0.05, max=0.25, step=0.01, description="size", value=self.size)
    self.help_button = self.create_button("？", 50)
    self.label = widgets.Label(value="", layout=widgets.Layout(width=f"50px"))
    
    with plt.ioff():
        self.fig = plt.figure(figsize=[self.width * self.size,
                                        self.height * self.size])
        self.ax = self.fig.add_axes([0, 0, 1, 1])
    self.fig.canvas.toolbar_visible = False
    self.fig.canvas.header_visible = False
    self.fig.canvas.footer_visible = False
    self.fig.canvas.resizable = False    
    
    self.dropdown = widgets.Dropdown(
        options=self.scoretable_dict,
        description="score table",
    )
    self.bestmoves_and_score_by_board = self.dropdown.value   
    
Mbtree_GUI.create_widgets = create_widgets

修正箇所

from tree import Mbtree_GUI
import matplotlib.pyplot as plt
import ipywidgets as widgets

def create_widgets(self):
元と同じなので省略
    self.data_dropdown= widgets.Dropdown(
        options = {
            "表示なし": False,
            "評価値": "score",
            "プレイアウトでの〇の勝率": self.selectednode.mb.CIRCLE_STR,
            "プレイアウトでの×の勝率": self.selectednode.mb.CROSS_STR,
            "プレイアウトでの引き分け率": self.selectednode.mb.DRAW,
+           "プレイアウトの〇の評価値": "playout_score_o",
+           "プレイアウトの×の評価値": "playout_score_x",

        },
        description = "データの表示",
        value = "score"
    )
元と同じなので省略
    
Mbtree_GUI.create_widgets = create_widgets

Node クラスの `init` と `draw_node` メソッドの修正

$ps_〇$ と $ps_×$ の期待値を局面の上部に表示するために Node クラスの __init__ メソッドと draw_node メソッドを下記のプログラムのように修正します。

10 行目：__init__ メソッド内で $ps_〇$ の期待値が代入されたデータを playout_score 属性に代入する
19 ~ 23 行目：draw_node メソッド内で Dropdown の選択項目を表す仮引数 show_score の値に応じて局面の上部に $ps_〇$ または $ps_×$ の期待値を表示する処理を追加する

 1  from tree import Node, Rect
 2  from marubatsu import Marubatsu_GUI
 3  
 4  def __init__(self, mb, parent=None, depth=0, bestmoves_and_score_by_board=None):
元と同じなので省略
 5      if bestmoves_and_score_by_board is not None:
 6          bestmoves_and_score = bestmoves_and_score_by_board[self.mb.board_to_str()]
 7          self.bestmoves = bestmoves_and_score["bestmoves"]
 8          self.score = bestmoves_and_score["score"]   
 9          self.playout_prob = bestmoves_and_score["playout_prob"]   
10          self.playout_score = bestmoves_and_score["playout_score"]
11  
12  Node.__init__ = __init__
13  
14  def draw_node(self, ax=None, maxdepth=None, emphasize=False, darkness=0, 
15                show_score=True, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
16      if hasattr(self, "playout_prob"):
17          if show_score in [self.mb.CIRCLE_STR, self.mb.CROSS_STR, self.mb.DRAW]:
18              ax.text(dx, y - 0.1, f"{self.playout_prob[show_score]:.3f}", fontsize=70*size)
19      if hasattr(self, "playout_score"):
20          if show_score == "playout_score_o":
21              ax.text(dx, y - 0.1, f"{self.playout_score:.3f}", fontsize=70*size)
22          if show_score == "playout_score_x":
23              ax.text(dx, y - 0.1, f"{1 - self.playout_score:.3f}", fontsize=70*size)
24      if hasattr(self, "score") and show_score in [True, "score"]:
25          ax.text(dx, y - 0.1, self.score, fontsize=70*size)
元と同じなので省略
26  
27  Node.draw_node = draw_node

行番号のないプログラム

from tree import Node, Rect
from marubatsu import Marubatsu_GUI

def __init__(self, mb, parent=None, depth=0, bestmoves_and_score_by_board=None):
    self.id = Node.count
    Node.count += 1
    self.mb = mb
    self.parent = parent
    self.depth = depth
    self.children = []
    self.children_by_move = {}   
    if bestmoves_and_score_by_board is not None:
        bestmoves_and_score = bestmoves_and_score_by_board[self.mb.board_to_str()]
        self.bestmoves = bestmoves_and_score["bestmoves"]
        self.score = bestmoves_and_score["score"]   
        self.playout_prob = bestmoves_and_score["playout_prob"]   
        self.playout_score = bestmoves_and_score["playout_score"]
        
Node.__init__ = __init__

def draw_node(self, ax=None, maxdepth=None, emphasize=False, darkness=0, 
              show_score=True, size=0.25, lw=0.8, dx=0, dy=0):
    width = 8
    if ax is None:
        height = len(self.children) * 4
        fig, ax = plt.subplots(figsize=(width * size, height * size))
        ax.set_xlim(0, width)
        ax.set_ylim(0, height)   
        ax.invert_yaxis()
        ax.axis("off")
        for childnode in self.children:
            childnode.height = 4
        self.height = height         
        
    # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
    y = dy + (self.height - 3) / 2
    bc = "red" if emphasize else None
    Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, 
                            score=getattr(self, "score", None), bc=bc, darkness=darkness, lw=lw, dx=dx, dy=y)
    if hasattr(self, "playout_prob"):
        if show_score in [self.mb.CIRCLE_STR, self.mb.CROSS_STR, self.mb.DRAW]:
            ax.text(dx, y - 0.1, f"{self.playout_prob[show_score]:.3f}", fontsize=70*size)
    if hasattr(self, "playout_score"):
        if show_score == "playout_score_o":
            ax.text(dx, y - 0.1, f"{self.playout_score:.3f}", fontsize=70*size)
        if show_score == "playout_score_x":
            ax.text(dx, y - 0.1, f"{1 - self.playout_score:.3f}", fontsize=70*size)
    if hasattr(self, "score") and show_score in [True, "score"]:
        ax.text(dx, y - 0.1, self.score, fontsize=70*size)
    rect = Rect(dx, y, 3, 3)
    # 子ノードが存在する場合に、エッジの線と子ノードを描画する
    if len(self.children) > 0:
        if maxdepth != self.depth:   
            ax.plot([dx + 3.5, dx + 4], [y + 1.5, y + 1.5], c="k", lw=lw)
            prevy = None
            for childnode in self.children:
                childnodey = dy + (childnode.height - 3) / 2
                if maxdepth is None:
                    Marubatsu_GUI.draw_board(ax, childnode.mb, show_result=True,
                                            score=getattr(childnode, "score", None), dx=dx+5, dy=childnodey, lw=lw)
                edgey = childnodey + 1.5
                ax.plot([dx + 4 , dx + 4.5], [edgey, edgey], c="k", lw=lw)
                if prevy is not None:
                    ax.plot([dx + 4 , dx + 4], [prevy, edgey], c="k", lw=lw)
                prevy = edgey
                dy += childnode.height
        else:
            ax.plot([dx + 3.5, dx + 4.5], [y + 1.5, y + 1.5], c="k", lw=lw)
            
    return rect

Node.draw_node = draw_node

修正箇所

from tree import Node, Rect
from marubatsu import Marubatsu_GUI

def __init__(self, mb, parent=None, depth=0, bestmoves_and_score_by_board=None):
元と同じなので省略
    if bestmoves_and_score_by_board is not None:
        bestmoves_and_score = bestmoves_and_score_by_board[self.mb.board_to_str()]
        self.bestmoves = bestmoves_and_score["bestmoves"]
        self.score = bestmoves_and_score["score"]   
        self.playout_prob = bestmoves_and_score["playout_prob"]   
+       self.playout_score = bestmoves_and_score["playout_score"]
        
Node.__init__ = __init__

def draw_node(self, ax=None, maxdepth=None, emphasize=False, darkness=0, 
              show_score=True, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
    if hasattr(self, "playout_prob"):
        if show_score in [self.mb.CIRCLE_STR, self.mb.CROSS_STR, self.mb.DRAW]:
            ax.text(dx, y - 0.1, f"{self.playout_prob[show_score]:.3f}", fontsize=70*size)
+   if hasattr(self, "playout_score"):
+       if show_score == "playout_score_o":
+           ax.text(dx, y - 0.1, f"{self.playout_score:.3f}", fontsize=70*size)
+       if show_score == "playout_score_x":
+           ax.text(dx, y - 0.1, f"{1 - self.playout_score:.3f}", fontsize=70*size)
    if hasattr(self, "score") and show_score in [True, "score"]:
        ax.text(dx, y - 0.1, self.score, fontsize=70*size)
元と同じなので省略

Node.draw_node = draw_node

上記の修正後に下記のプログラムを実行し、Dropdown に「プレイアウトの〇の評価値」を選択すると、実行結果のように局面の上部に $ps_〇$ の期待値が表示されるようになります。画像は省略しますが「プレイアウトの×の評価値」を選択した場合に $ps_× = 1 - ps_〇$ となる $ps_×$ の期待値が表示されることを確認して下さい。

Mbtree_GUI()

実行結果

また、Dropdown に「プレイアウトでの〇の勝率」を選択した場合の下図と比較して、引き分けを 0.5 勝として考慮した分だけ局面の上部に表示される数値が大きくなっていることが確認できます。

`ai_pmc2` の実装と検証

次に $ps_〇$ と $ps_×$ を用いて原始モンテカルロ法で最善手を計算する ai_pmc2 を下記のプログラムのように定義します。下記の説明と修正箇所には ai_pmc との違いを示します。また、下記の説明では〇の手番の場合の説明を行っていますが、× の手番の場合は $ps_〇$ が $ps_×$ になる点以外は同じなのでその説明は省略します。

7 行目：best_ratio を削除し、$ps_〇$ の最大値を記録する best_score を -1 で初期化する。$ps_〇$ の値の範囲は 0 ~ 1 なので初期化する値は 0 未満の値であれば何でも良い
9 行目：ratio_by_move を削除し、代わりにそれぞれの合法手に対する $ps_〇$ の値を記録する score_by_move を空の dict で初期化する
12 行目：winratio と drawratio を削除し、〇の手番の場合は $ps_〇 = wr + dr × 0.5$ を、× の手番の場合は $ps_× = lr + dr × 0.5$ を計算して score に代入する
16、17、23、24 行目：ratio と best_ratio のデバッグ表示を score と best_score の表示に修正した
18 ~ 24 行目：score が bestscore より大きい場合に最善手を更新する処理に修正した
25 ~ 29 行目：score と bestscore が等しい場合に最善手を追加する処理に修正した
31 行目：score_by_move の move のキーの値に $ps_〇$ を表す score を記録するように修正した。ratio_by_move の場合と異なり movexy ではなく move のキーの値に代入する必要がある点に注意すること。また、その際に前回の記事の ai_pmc と同様に gui_play で評価値を表示する場合を考慮して小数点以下第 4 桁で四捨五入した値を代入した
34 行目の次の行にあった ratio_by_move を返り値の一部として返す処理を削除した

 1  from ai import dprint
 2  from random import choice
 3  
 4  def ai_pmc2(mb, pnum, timelimit=None, debug=False, analyze=False, *args, **kwargs):
元と同じなので省略
 5      best_moves = []
 6      best_movesxy = []
 7      best_score = -1
 8      if analyze:
 9          score_by_move = {}
10      for move, count in retval["result"].items():
11          totalcount = max(1, sum(count.values()))
12          score = (count[mb.turn] + count[mb.DRAW] * 0.5) / totalcount
13          movexy = mb.board.move_to_xy(move)
14          dprint(debug, "=" * 50)
15          dprint(debug, f"move {movexy}")
16          dprint(debug, f"score     : {score:.3f}")
17          dprint(debug, f"best score: {best_score:.3f}", )
18          if score > best_score:
19              best_score = score
20              best_moves = [move]
21              best_movesxy = [movexy]
22              dprint(debug, "UPDATE")
23              dprint(debug, f"  best score {best_score}")
24              dprint(debug, f"  best moves {best_movesxy}")
25          elif score == best_score:
26              best_moves.append(move)
27              best_movesxy.append(movexy)
28              dprint(debug, "APPEND")
29              dprint(debug, f"  best moves {best_movesxy}")
30          if analyze:
31              score_by_move[move] = round(score, 3)
32      if analyze:
33          return {
34              "candidate": best_movesxy,
35              "playout num": retval["count"],
36              "score_by_move": score_by_move
37          }
38      else:
39          return choice(best_moves)

行番号のないプログラム

from ai import dprint
from random import choice

def ai_pmc2(mb, pnum, 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,
                "score_by_move": {best_move: 1},                
            }
        else:
            return best_move
    retval = mb.playout(pnum, timelimit)
    best_moves = []
    best_movesxy = []
    best_score = -1
    if analyze:
        score_by_move = {}
    for move, count in retval["result"].items():
        totalcount = max(1, sum(count.values()))
        score = (count[mb.turn] + count[mb.DRAW] * 0.5) / totalcount
        movexy = mb.board.move_to_xy(move)
        dprint(debug, "=" * 50)
        dprint(debug, f"move {movexy}")
        dprint(debug, f"score     : {score:.3f}")
        dprint(debug, f"best score: {best_score:.3f}", )
        if score > best_score:
            best_score = score
            best_moves = [move]
            best_movesxy = [movexy]
            dprint(debug, "UPDATE")
            dprint(debug, f"  best score {best_score}")
            dprint(debug, f"  best moves {best_movesxy}")
        elif score == best_score:
            best_moves.append(move)
            best_movesxy.append(movexy)
            dprint(debug, "APPEND")
            dprint(debug, f"  best moves {best_movesxy}")
        if analyze:
            score_by_move[move] = round(score, 3)
    if analyze:
        return {
            "candidate": best_movesxy,
            "playout num": retval["count"],
            "score_by_move": score_by_move
        }
    else:
        return choice(best_moves)

修正箇所

from ai import dprint
from random import choice

def ai_pmc2(mb, pnum, timelimit=None, debug=False, analyze=False, *args, **kwargs):
元と同じなので省略
    best_moves = []
    best_movesxy = []
-   best_ratio = (-1, 0)
+   best_score = -1
    if analyze:
-       ratio_by_move = {}
+       score_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
+       score = (count[mb.turn] + count[mb.DRAW] * 0.5) / 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}", )
+       dprint(debug, f"score     : {score:.3f}")
+       dprint(debug, f"best score: {best_score:.3f}", )
-       if best_ratio is None or winratio > best_ratio[0] or (winratio == best_ratio[0] and drawratio > best_ratio[1]):
+        if score > best_score:
-           best_ratio = (winratio, drawratio)
+           best_score = score
            best_moves = [move]
            best_movesxy = [movexy]
            dprint(debug, "UPDATE")
-           dprint(debug, f"  best ratio {best_ratio}")
-           dprint(debug, f"  best moves {best_movesxy}")
+           dprint(debug, f"  best score {best_score}")
+           dprint(debug, f"  best moves {best_movesxy}")
-       elif winratio == best_ratio[0] and drawratio == best_ratio[1]:
+       elif score == best_score:
            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)
+           score_by_move[move] = round(score, 3)
    if analyze:
        return {
            "candidate": best_movesxy,
-           "ratio_by_move": ratio_by_move,
            "playout num": retval["count"],
            "score_by_move": score_by_move
        }
    else:
        return choice(best_moves)

上記の ai_pmc2 の定義後に下記のプログラムで、ゲーム開始時の局面に対してキーワード引数として pnum=10000、debug=True、analyze=True を記述して ai_pmc2 で最善手を計算すると、実行結果のように各合法手の引き分け率を考慮した $ps_〇$ が計算され、最大値が計算された (1, 1) が最善手として計算されたことが確認できます。

mb = Marubatsu()
ai_pmc2(mb, pnum=10000, debug=True, analyze=True)

実行結果

==================================================
move (0, 0)
score     : 0.665
best score: -1.000
UPDATE
  best score 0.6653577661431065
  best moves [(0, 0)]
==================================================
move (0, 1)
score     : 0.612
best score: 0.665
==================================================
move (0, 2)
score     : 0.661
best score: 0.665
==================================================
move (1, 0)
score     : 0.613
best score: 0.665
==================================================
move (1, 1)
score     : 0.754
best score: 0.665
UPDATE
  best score 0.7541743970315399
  best moves [(1, 1)]
==================================================
move (1, 2)
score     : 0.607
best score: 0.754
==================================================
move (2, 0)
score     : 0.696
best score: 0.754
==================================================
move (2, 1)
score     : 0.603
best score: 0.754
==================================================
move (2, 2)
score     : 0.653
best score: 0.754

下記は実行結果の $ps_〇$ と先程の Marubatsu_GUI() で表示した $ps_〇$ の期待値をまとめた表で、10000 回のプレイアウトによって理論値に近い $ps_〇$ が計算されたことが確認できます。

合法手	$ps_〇$	$ps_〇$ の理論値
(0, 0)	0.665	0.671
(0, 1)	0.612	0.600
(0, 2)	0.661	0.671
(1, 0)	0.613	0.600
(1, 1)	0.754	0.750
(1, 2)	0.607	0.600
(2, 0)	0.696	0.671
(2, 1)	0.603	0.600
(2, 2)	0.653	0.671

`ai2s` と `ai14s` との対戦

ai_pmc2 の実力を計測するために、以前の記事で ai_pmc に対して行ったのと同様に、下記の条件でランダムな着手を行う ai2s と弱解決の AI である ai14s との対戦を行います。

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

下記はその対戦を行うプログラムと実行結果です。

from ai import ai_match, ai2s, ai14s

for pnum in [5, 10, 50, 100, 1000, 10000]:
    print(f"pnum {pnum}")
    ai_match(ai=[ai_pmc2, 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_pmc2, ai2s], params=[{"pnum": 100000000, "timelimit": timelimit}, {}],
             match_num=1000)

for pnum in [5, 10, 50, 100, 1000, 10000]:
    print(f"pnum {pnum}")
    ai_match(ai=[ai_pmc2, 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_pmc2, ai14s], params=[{"pnum": 100000000, "timelimit": timelimit}, {}],
             match_num=1000)

実行結果

pnum 5
ai_pmc2 VS ai2s
100%|██████████| 1000/1000 [00:00<00:00, 1673.41it/s]
count     win    lose    draw
o         781     129      90
x         576     292     132
total    1357     421     222

ratio     win    lose    draw
o       78.1%   12.9%    9.0%
x       57.6%   29.2%   13.2%
total   67.8%   21.1%   11.1%

pnum 10
ai_pmc2 VS ai2s
100%|██████████| 1000/1000 [00:00<00:00, 1172.12it/s]
count     win    lose    draw
o         850      87      63
x         684     223      93
total    1534     310     156

ratio     win    lose    draw
o       85.0%    8.7%    6.3%
x       68.4%   22.3%    9.3%
total   76.7%   15.5%    7.8%

pnum 50
ai_pmc2 VS ai2s
100%|██████████| 1000/1000 [00:03<00:00, 320.01it/s]
count     win    lose    draw
o         951      12      37
x         821     113      66
total    1772     125     103

ratio     win    lose    draw
o       95.1%    1.2%    3.7%
x       82.1%   11.3%    6.6%
total   88.6%    6.2%    5.1%

pnum 100
ai_pmc2 VS ai2s
100%|██████████| 1000/1000 [00:06<00:00, 166.25it/s]
count     win    lose    draw
o         973       2      25
x         853      73      74
total    1826      75      99

ratio     win    lose    draw
o       97.3%    0.2%    2.5%
x       85.3%    7.3%    7.4%
total   91.3%    3.8%    5.0%

pnum 1000
ai_pmc2 VS ai2s
100%|██████████| 1000/1000 [00:57<00:00, 17.51it/s]
count     win    lose    draw
o         983       0      17
x         904      31      65
total    1887      31      82

ratio     win    lose    draw
o       98.3%    0.0%    1.7%
x       90.4%    3.1%    6.5%
total   94.3%    1.6%    4.1%

pnum 10000
ai_pmc2 VS ai2s
100%|██████████| 1000/1000 [08:36<00:00,  1.94it/s]
count     win    lose    draw
o         991       0       9
x         886      48      66
total    1877      48      75

ratio     win    lose    draw
o       99.1%    0.0%    0.9%
x       88.6%    4.8%    6.6%
total   93.8%    2.4%    3.8%

timelimit 0.0001
ai_pmc2 VS ai2s
100%|██████████| 1000/1000 [00:01<00:00, 924.83it/s]
count     win    lose    draw
o         908      46      46
x         694     176     130
total    1602     222     176

ratio     win    lose    draw
o       90.8%    4.6%    4.6%
x       69.4%   17.6%   13.0%
total   80.1%   11.1%    8.8%

timelimit 0.0005
ai_pmc2 VS ai2s
100%|██████████| 1000/1000 [00:03<00:00, 262.80it/s]
count     win    lose    draw
o         964       9      27
x         806      98      96
total    1770     107     123

ratio     win    lose    draw
o       96.4%    0.9%    2.7%
x       80.6%    9.8%    9.6%
total   88.5%    5.3%    6.2%

timelimit 0.001
ai_pmc2 VS ai2s
100%|██████████| 1000/1000 [00:07<00:00, 139.96it/s]
count     win    lose    draw
o         973       4      23
x         859      68      73
total    1832      72      96

ratio     win    lose    draw
o       97.3%    0.4%    2.3%
x       85.9%    6.8%    7.3%
total   91.6%    3.6%    4.8%

timelimit 0.01
ai_pmc2 VS ai2s
100%|██████████| 1000/1000 [01:06<00:00, 15.15it/s]
count     win    lose    draw
o         985       0      15
x         901      27      72
total    1886      27      87

ratio     win    lose    draw
o       98.5%    0.0%    1.5%
x       90.1%    2.7%    7.2%
total   94.3%    1.4%    4.3%

timelimit 0.1
ai_pmc2 VS ai2s
100%|██████████| 1000/1000 [10:45<00:00,  1.55it/s]
count     win    lose    draw
o         991       0       9
x         903      39      58
total    1894      39      67

ratio     win    lose    draw
o       99.1%    0.0%    0.9%
x       90.3%    3.9%    5.8%
total   94.7%    1.9%    3.4%

pnum 5
ai_pmc2 VS ai14s
100%|██████████| 1000/1000 [00:00<00:00, 1284.22it/s]
count     win    lose    draw
o           0     719     281
x           0     936      64
total       0    1655     345

ratio     win    lose    draw
o        0.0%   71.9%   28.1%
x        0.0%   93.6%    6.4%
total    0.0%   82.8%   17.2%

pnum 10
ai_pmc2 VS ai14s
100%|██████████| 1000/1000 [00:01<00:00, 963.77it/s]
count     win    lose    draw
o           0     638     362
x           0     903      97
total       0    1541     459

ratio     win    lose    draw
o        0.0%   63.8%   36.2%
x        0.0%   90.3%    9.7%
total    0.0%   77.0%   22.9%

pnum 50
ai_pmc2 VS ai14s
100%|██████████| 1000/1000 [00:03<00:00, 296.90it/s]
count     win    lose    draw
o           0     266     734
x           0     773     227
total       0    1039     961

ratio     win    lose    draw
o        0.0%   26.6%   73.4%
x        0.0%   77.3%   22.7%
total    0.0%   51.9%   48.0%

pnum 100
ai_pmc2 VS ai14s
100%|██████████| 1000/1000 [00:06<00:00, 159.78it/s]
count     win    lose    draw
o           0     105     895
x           0     707     293
total       0     812    1188

ratio     win    lose    draw
o        0.0%   10.5%   89.5%
x        0.0%   70.7%   29.3%
total    0.0%   40.6%   59.4%

pnum 1000
ai_pmc2 VS ai14s
100%|██████████| 1000/1000 [00:59<00:00, 16.73it/s]
count     win    lose    draw
o           0       0    1000
x           0     521     479
total       0     521    1479

ratio     win    lose    draw
o        0.0%    0.0%  100.0%
x        0.0%   52.1%   47.9%
total    0.0%   26.1%   74.0%

pnum 10000
ai_pmc2 VS ai14s
100%|██████████| 1000/1000 [09:13<00:00,  1.81it/s]
count     win    lose    draw
o           0       0    1000
x           0     484     516
total       0     484    1516

ratio     win    lose    draw
o        0.0%    0.0%  100.0%
x        0.0%   48.4%   51.6%
total    0.0%   24.2%   75.8%

timelimit 0.0001
ai_pmc2 VS ai14s
100%|██████████| 1000/1000 [00:01<00:00, 771.46it/s]
count     win    lose    draw
o           0     561     439
x           0     912      88
total       0    1473     527

ratio     win    lose    draw
o        0.0%   56.1%   43.9%
x        0.0%   91.2%    8.8%
total    0.0%   73.7%   26.4%

timelimit 0.0005
ai_pmc2 VS ai14s
100%|██████████| 1000/1000 [00:04<00:00, 240.82it/s]
count     win    lose    draw
o           0     175     825
x           0     775     225
total       0     950    1050

ratio     win    lose    draw
o        0.0%   17.5%   82.5%
x        0.0%   77.5%   22.5%
total    0.0%   47.5%   52.5%

timelimit 0.001
ai_pmc2 VS ai14s
100%|██████████| 1000/1000 [00:07<00:00, 125.90it/s]
count     win    lose    draw
o           0      81     919
x           0     664     336
total       0     745    1255

ratio     win    lose    draw
o        0.0%    8.1%   91.9%
x        0.0%   66.4%   33.6%
total    0.0%   37.2%   62.7%

timelimit 0.01
ai_pmc2 VS ai14s
100%|██████████| 1000/1000 [01:16<00:00, 13.05it/s]
count     win    lose    draw
o           0       0    1000
x           0     474     526
total       0     474    1526

ratio     win    lose    draw
o        0.0%    0.0%  100.0%
x        0.0%   47.4%   52.6%
total    0.0%   23.7%   76.3%

timelimit 0.1
ai_pmc2 VS ai14s
100%|██████████| 1000/1000 [12:30<00:00,  1.33it/s]
count     win    lose    draw
o           0       0    1000
x           0     516     484
total       0     516    1484

ratio     win    lose    draw
o        0.0%    0.0%  100.0%
x        0.0%   51.6%   48.4%
total    0.0%   25.8%   74.2%

下記は上記の ai2s との対戦の実行結果と、以前の記事での ai_pmc VS ai2s の対戦結果をまとめた表です。左から ai2s に対する勝率、敗率、引分率の % を、上段が ai_pmc VS ai2s、下段が ai_pmc2 VS ai2s の対戦結果を表します。

回数または制限時間	先手の成績	後手の成績	通算成績	時間（分:秒）
5 回	80.7/11.9/ 7.4 78.1/12.9/ 9.0	57.3/30.0/20.9 57.6/29.2/13.2	69.0/20.9/10.1 67.8/21.1/11.1	0 0
10 回	86.5/ 7.7/ 5.8 85.0/ 8.7/ 6.3	67.5/25.8/ 6.7 68.4/22.3/ 9.3	77.0/16.8/ 6.2 76.7/15.5/ 7.8	0 0
50 回	95.7/ 2.1/ 2.2 95.1/ 1.2/ 3.7	80.7/15.5/ 3.8 82.1/11.3/ 6.6	88.2/ 8.8/ 3.0 88.6/ 6.2/ 5.1	3 3
100 回	97.8/ 1.2/ 1.0 97.3/ 0.2/ 2.5	85.3/12.5/ 2.2 85.3/ 7.3/ 7.4	91.5/ 6.9/ 1.6 91.3/ 3.8/ 5.0	6 6
1000 回	99.0/ 0.2/ 0.8 98.3/ 0.0/ 1.7	89.6/ 9.1/ 1.3 90.4/ 3.1/ 6.5	94.3/ 4.7/ 1.1 94.3/ 1.6/ 4.1	55 57
10000 回	99.0/ 0.0/ 1.0 99.1/ 0.0/ 0.9	91.7/ 7.0/ 1.3 88.6/ 4.8/ 6.6	95.3/ 3.5/11.1 93.8/ 2.4/ 3.8	8:12 8:36
0.0001 秒	90.4/ 6.2/ 3.4 90.8/ 4.6/ 4.6	71.5/21.5/ 7.0 69.4/17.6/13.0	81.0/13.9/ 5.2 80.1/11.1/8.8	1 1
0.0005 秒	95.7/ 2.4/ 1.9 96.4/ 0.9/ 2.7	81.3/15.8/ 2.9 80.6/ 9.8/ 9.6	88.5/ 9.1/ 2.4 88.5/ 5.3/ 6.2	3 3
0.001 秒	97.4/ 1.7/ 0.9 97.3/ 0.4/ 2.3	85.2/13.1/ 1.7 85.9/ 6.8/ 7.3	91.3/ 7.4/ 1.3 91.6/ 3.6/ 4.8	6 7
0.01 秒	98.4/ 0.2/ 1.4 98.5/ 0.0/ 1.5	91.5/ 7.7/ 0.8 90.1/ 2.7/ 7.2	95.0/ 4.0/ 1.1 94.3/ 1.4/ 4.3	1:05 1:06
0.1 秒	98.9/ 0.0/ 1.1 99.1/ 0.0/ 0.9	90.6/ 7.5/ 1.9 90.3/ 3.9/ 5.8	94.8/ 3.8/ 1.5 94.7/ 1.9/ 3.4	10:42 10:45

上記の表からプレイアウトの回数が多くなると下記のようになることが確認できました。

先手の場合は ai_pmc VS ai2s と ai_pmc2 VS ai2s の対戦成績はほぼ変わらず、いずれの場合も敗率が 0 % になる
後手の場合は ai_pmc2 VS ai2s のほうが勝率と敗率が若干低く、引き分け率が高くなる
処理時間はほぼ同じである

先手の場合に敗率が 0 % になることから ai_pmc2 も ai_pmc と同様に弱解決の AI である可能性が非常に高いことがわかり、実際にそうであることについてはこの後で確認します。

$ps_〇$ は引き分けを 0.5 勝として計算するため、ai_pmc2 は ai_pmc よりも引き分けを重視するような合法手を選択する傾向があり、実際に ai_pmc2 VS ai2s のほうが ai_pmc VS ai2s よりも後手の場合の引き分け率が高くなっています。後手で制限時間を最長の 0.1 秒とした場合の結果では引き分け率が 3.9 % 上昇したのに対して、勝率が 0.3 %、敗率が 3.6 % 減っていることから、引き分けを重視することによって勝率と敗率の両方が減ったことが確認できます。ただし、勝率の減り具合はかなり小さいため誤差である可能性があります。

このことから、ai_pmc2 のほうが ai_pmc よりも ai2s に対して若干負けにくい相性が良い AI であることがわかりました。

下記は上記の ai14s との対戦の実行結果と、以前の記事での ai_pmc との対戦結果をまとめた表です。左から ai14s に対する敗率、引分率の % を、上段が ai_pmc VS ai2s、下段が ai_pmc2 VS ai2s の対戦結果を表します。勝率はすべて 0 % になるので省略しました。

回数または制限時間	先手の成績	後手の成績	通算成績	時間（分:秒）
5 回	72.2/27.8 71.9/28.1	93.5/6.5 93.6/ 6.4	82.8/17.2 82.8/17.2	0 0
10 回	70.0/30.0 63.8/36.2	94.5/5.5 90.3/ 9.7	82.2/17.8 77.0/22.9	1 1
50 回	56.9/43.1 26.6/73.4	99.7/ 0.3 77.3/22.7	78.3/21.7 51.9/48.0	3 3
100 回	49.7/50.3 10.5/89.5	99.9/0.1 70.7/29.3	74.8/25.2 40.6/59.4	6 6
1000 回	19.6/80.4 0.0/100.0	100.0/ 0.0 52.1/47.9	59.8/40.2 26.1/74.8	1:00 59
10000 回	0.0/100.0 0.0/100.0	100.0/0.0 48.4/51.6	50.0/50.0 24.2/75.8	8:56 9:13
0.0001 秒	65.1/34.9 56.1/43.9	95.7/ 4.3 91.2/ 8.8	80.4/19.6 73.7/26.4	1 1
0.0005 秒	52.2/47.8 17.5/82.5	99.7/ 0.3 77.5/22.5	75.9/24.1 47.5/52.5	3 4
0.001 秒	47.5/52.5 8.1/91.9	100.0/ 0.0 66.4/33.6	73.8/26.2 37.2/62.7	7 7
0.01 秒	24.4/75.6 0.0/100.0	100.0/ 0.0 47.4/52.6	62.2/37.8 23.7/76.3	1:09 1:16
0.1 秒	0.2/ 99.8 0.0/100.0	100.0/ 0.0 51.6/48.4	50.1/49.9 25.8/74.2	11:42 12:30

上記の表からプレイアウトの回数が多くなると下記のようになることが確認できました。

先手の場合は ai_pmc VS ai14s と ai_pmc2 VS ai14s の対戦成績はほぼ変わらず、いずれの場合も引き分け率が 100 % になる
後手の場合は ai_pmc2 VS ai2s の対戦成績の敗率と引き分け率が約 50 % になる

後手の場合の ai_pmc VS ai2s の敗率が 100 % であったことから、ai_pmc2 VS ai2s のほうが明らかに対戦成績が良いことが確認できました。そのような結果になる理由についてはこの後で検証します。

上記の検証から ai_pmc よりも ai_pmc2 のほうが ai2s と ai14s に対して良い成績が得られることがわかりました。このことと最善手の計算しやすさから今後の記事では引き分けを 0.5 勝とした $ps_〇$ 用いて原始モンテカルロ法の最善手を計算することにします。

最善手を着手しない局面の計算

以前の記事で ai_pmc に対して行ったのと同様に、ai_pmc2 が最善手を計算しない局面の一覧を下記のプログラムで表示することにします。なお、下記のプログラムのアルゴリズムは以前の記事で ai_pmc に対して計算を行う場合と同様で、修正箇所はそのプログラムとの違いを表します。

8 行目：bestratio を bestscore に修正した
10 行目：winratio と drawratio を削除し、score に $ps_〇$ の期待値を代入するように修正した
11、12 行目：× の手番の場合は score に $ps_× = 1 - ps_〇$ を代入する
13、15、16 行目：winratio、drawratio、bestratio の代わりに score と bestscore を利用して計算するように修正した

 1  checkedmb = set()
 2  nodelist = []
 3  for node in mbtree.nodelist:
 4      if node.mb.board_to_hashable() in checkedmb:
 5          continue
 6      checkedmb |= node.mb.board.calc_same_hashables()
 7      bestmoves = []
 8      bestscore = -1
 9      for move in node.mb.calc_legal_moves():
10          score = node.children_by_move[move].playout_score
11          if node.mb.turn == mb.CROSS:
12              score = 1 - score
13          if score > bestscore:
14              bestmoves = [move]
15              bestscore = score
16          elif score == bestscore:
17              bestmoves.append(move)
18      if not(set(bestmoves) <= set(node.bestmoves)):
19          nodelist.append((node, set(bestmoves), set(node.bestmoves)))
20  
21  print(len(nodelist), len(mbtree.nodelist))

行番号のないプログラム

checkedmb = set()
nodelist = []
for node in mbtree.nodelist:
    if node.mb.board_to_hashable() in checkedmb:
        continue
    checkedmb |= node.mb.board.calc_same_hashables()
    bestmoves = []
    bestscore = -1
    for move in node.mb.calc_legal_moves():
        score = node.children_by_move[move].playout_score
        if node.mb.turn == mb.CROSS:
            score = 1 - score
        if score > bestscore:
            bestmoves = [move]
            bestscore = score
        elif score == bestscore:
            bestmoves.append(move)
    if not(set(bestmoves) <= set(node.bestmoves)):
        nodelist.append((node, set(bestmoves), set(node.bestmoves)))

print(len(nodelist), len(mbtree.nodelist))

修正箇所

checkedmb = set()
nodelist = []
for node in mbtree.nodelist:
    if node.mb.board_to_hashable() in checkedmb:
        continue
    checkedmb |= node.mb.board.calc_same_hashables()
    bestmoves = []
-   bestratio = [0, 0]
+   bestscore = -1
    for move in node.mb.calc_legal_moves():
-       winratio = node.children_by_move[move].playout_prob[node.mb.turn]
-       drawratio = node.children_by_move[move].playout_prob[node.mb.DRAW]
+       score = node.children_by_move[move].playout_score
+       if node.mb.turn == mb.CROSS:
+           score = 1 - score
-       if winratio > bestratio[0] or (winratio == bestratio[0] and drawratio > bestratio[1]):
+       if score > bestscore:
            bestmoves = [move]
-           bestratio = [winratio, drawratio]
+           bestscore = score
-       elif winratio == bestratio[0] and drawratio == bestratio[1]:
+       elif score == bestscore:
            bestmoves.append(move)
    if not(set(bestmoves) <= set(node.bestmoves)):
        nodelist.append((node, set(bestmoves), set(node.bestmoves)))

print(len(nodelist), len(mbtree.nodelist))

実行結果

26 549946

実行結果から ai_pmc2 が最善手を計算しない局面が 26 あり、ai_pmc が最善手を計算しない局面の数である 30 よりも少し少ないことが確認できました。

下記はそれらの局面の一覧を表示するプログラムで、以前の記事で ai_pmc に対して行ったものと同じです。

for node, pmcmoves, bestmoves in nodelist:
    pmcmoves = [node.mb.board.move_to_xy(move) for move in pmcmoves]
    bestmoves = [node.mb.board.move_to_xy(move) for move in bestmoves]
    print(f"pmcmoves  {pmcmoves}")
    print(f"bestmoves {bestmoves}")
    print(node.mb)

実行結果

pmcmoves  [(1, 1)]
bestmoves [(1, 0), (2, 2), (2, 0)]
Turn o
o..
...
X..

pmcmoves  [(1, 1)]
bestmoves [(0, 0)]
Turn o
..X
o..
...

pmcmoves  [(1, 1), (2, 2)]
bestmoves [(2, 0), (2, 2)]
Turn x
o..
x.O
...

pmcmoves  [(1, 1)]
bestmoves [(1, 2), (2, 2)]
Turn x
o..
O..
x..

pmcmoves  [(1, 1)]
bestmoves [(2, 2)]
Turn x
o..
..O
x..

pmcmoves  [(2, 0)]
bestmoves [(2, 1), (2, 2), (0, 1), (0, 2)]
Turn x
o..
.x.
.O.

pmcmoves  [(2, 0), (0, 2)]
bestmoves [(1, 0), (0, 1), (1, 2), (2, 1)]
Turn x
o..
.x.
..O

pmcmoves  [(2, 0)]
bestmoves [(2, 1)]
Turn x
x..
oO.
...

pmcmoves  [(1, 1)]
bestmoves [(2, 0)]
Turn x
x..
o..
.O.

pmcmoves  [(2, 0)]
bestmoves [(2, 2), (0, 2)]
Turn x
.x.
o..
.O.

pmcmoves  [(1, 1)]
bestmoves [(2, 2), (0, 0)]
Turn x
..x
o..
.O.

pmcmoves  [(1, 0), (2, 0)]
bestmoves [(1, 0)]
Turn o
o..
...
xoX

pmcmoves  [(1, 1), (2, 2)]
bestmoves [(2, 2)]
Turn x
ox.
x..
oO.

pmcmoves  [(1, 1), (2, 2), (2, 1)]
bestmoves [(2, 1)]
Turn x
oOx
x..
o..

pmcmoves  [(2, 0), (2, 2)]
bestmoves [(2, 0)]
Turn x
oo.
x.O
.x.

pmcmoves  [(1, 2), (2, 0)]
bestmoves [(2, 0)]
Turn x
oo.
x.O
..x

pmcmoves  [(1, 0), (2, 0)]
bestmoves [(1, 0)]
Turn x
o..
xo.
.Ox

pmcmoves  [(1, 0), (1, 1)]
bestmoves [(1, 0)]
Turn x
o.O
x..
.ox

pmcmoves  [(1, 0), (0, 2)]
bestmoves [(1, 0)]
Turn x
o.o
x.O
..x

pmcmoves  [(1, 0), (2, 1)]
bestmoves [(1, 0)]
Turn x
o..
.o.
xOx

pmcmoves  [(1, 0), (2, 1)]
bestmoves [(1, 0)]
Turn x
o.O
.x.
xo.

pmcmoves  [(2, 0), (0, 2)]
bestmoves [(0, 2)]
Turn x
o..
oxx
.O.

pmcmoves  [(2, 0), (0, 2)]
bestmoves [(0, 2)]
Turn x
o..
ox.
.Ox

pmcmoves  [(2, 1), (0, 2)]
bestmoves [(2, 1)]
Turn x
xo.
oO.
.x.

pmcmoves  [(1, 1), (2, 2)]
bestmoves [(1, 1)]
Turn x
xo.
o.O
.x.

pmcmoves  [(1, 0), (2, 0)]
bestmoves [(1, 0)]
Turn x
x..
oox
.O.

先手の手番の無限回の `ai_pmc2` が弱解決の AI であることの確認

上記の実行結果を用いて無限回のプレイアウトを行った場合の ai_pmc2 が、先手の場合は弱解決の AI であることを確認します。なお、以下の説明では無限回のプレイアウトを行った場合の ai_pmc2 を「無限回の ai_pmc2」と表記します。

上記の一覧の中で先手の〇の手番の局面は以下の 3 通りです。

pmcmoves  [(1, 1)]
bestmoves [(1, 0), (2, 2), (2, 0)]
Turn o
o..
...
X..

pmcmoves  [(1, 1)]
bestmoves [(0, 0)]
Turn o
..X
o..
...

pmcmoves  [(1, 0), (2, 0)]
bestmoves [(1, 0)]
Turn o
o..
...
xoX

先程示したように、無限回の ai_pmc2 はゲーム開始時の局面で (1, 1) を選択します。上記の局面の中に (1, 1) に〇が着手された局面は存在しないので無限回の ai_pmc2 が先手で対戦を行う場合に上記の局面は出現しません。また、上記以外の局面で無限回の ai_pmc2 は最善手を選択するため、無限回の ai_pmc2 は先手の場合は弱解決の AI になります。

後手の手番の無限回の `ai_pmc2` VS `ai14s` の対戦の検証

後手の手番の無限回の ai_pmc2 VS ai14s の対戦結果が、先程の対戦結果のように敗率が 50 %、引き分け率が 50 % になることを検証します。

検証方法は以前の記事での無限回の ai_pmc VS ai14s の検証と同じですが、図やプログラムの実行結果を記載すると記事がかなり長くなるので重要な部分以外では図やプログラムを省略してそれぞれの AI が選択する着手のみを記載します。興味がある方は以前の記事と同じ方法で確認して下さい。

ai14s はゲーム開始時の局面で必ず (1, 1) を選択し下記の局面になります。

Turn x
...
.O.
...

Marubatsu_GUI でこの局面を選択して「プレイアウトの × の評価値」を表示することで、無限回の ai_pmc2 がこの局面で四隅を選択することがわかり下記の局面になります。なお、四隅を着手した局面は同一局面なので (0, 0) を選択しました。

Turn o
X..
.o.
...

ai14s はこの局面で時の局面で (0, 2) または (2, 0) を選択します。それらを選択した局面は同一局面なので (0, 2) を選択すると下記の局面になります。

Turn x
x..
.o.
O..

Marubatsu_GUI から無限回の ai_pmc2 はこの局面で (2, 0) を選択することがわかり下記の局面になります。

Turn o
x.X
.o.
o..

ai14s はこの局面で時の局面で (1, 0) を選択して下記の局面になります。

Turn x
xOx
.o.
o..

Marubatsu_GUI で上記の局面を表示すると下図のようになることから無限回の ai_pmc2 はこの局面で $ps_×$ が最大の 0.333 となる (1, 2) と (2, 1) を選択することがわかります。

50 % の確率で (2, 1) を選択した場合は水色で表示される〇の必勝の局面となり、ai14s は弱解決の AI なので一度〇の勝利の局面になると必ず〇が勝利する着手を選択します。従って、この局面では 50 % の確率で〇が勝利することがわかりました。

残りの 50 % の確率で (1, 2) を選択した場合は下記の局面になります。

Turn o
xox
.o.
oX.

ai14s はこの局面で時の局面で (2, 1) を選択して下記の局面になります。

Turn x
xox
.oO
ox.

Marubatsu_GUI から無限回の ai_pmc2 はこの局面で (0, 1) を選択することがわかり、ai14s は残りの (2, 2) に着手して下記の局面になり引き分けになります。

winner draw
xox
xoo
oxO

上記から下記の局面で ai_pmc2 が 50 % の確率で (1, 2) を選択した場合は引き分けになり、50 % の確率で (2, 1) を選択した場合は〇が勝利します。

Turn x
xOx
.o.
o..

このことから無限回の ai_pmc2 VS ai14s は 50 % で引き分けに、50 % で ai_pmc が敗北になることが確認できました。

`ai_pmc` との違いの検証

最善手を選択しない局面が ai_pmc と ai_pmc2 とのように異なるかを検証することで、ai_pmc と ai_pmc2 の違いを検証することにします。

以前の記事で計算した ai_pmc が最善手を選択しない局面の一覧と、先程の ai_pmc が最善手を選択しない局面の一覧を見比べることで、ai_pmc だけが最善手を選択しない局面の一覧が下記の 7 種類であることがわかりました。

pmcmoves  [(2, 1)]
bestmoves [(1, 1)]
Turn x
o..
x..
O..

pmcmoves  [(0, 2)]
bestmoves [(2, 0)]
Turn x
oO.
...
.x.

pmcmoves  [(2, 2)]
bestmoves [(1, 1), (1, 2), (2, 1)]
Turn x
xO.
o..
...

pmcmoves  [(2, 2)]
bestmoves [(2, 0), (0, 0), (0, 2)]
Turn x
.O.
ox.
...

pmcmoves  [(0, 2)]
bestmoves [(1, 0), (1, 1), (2, 0), (2, 2)]
Turn o
x..
o.X
.o.

pmcmoves  [(2, 1)]
bestmoves [(2, 2)]
Turn x
o.x
x..
oO.

pmcmoves  [(1, 2)]
bestmoves [(1, 0)]
Turn x
o.O
ox.
x..

下記は ai_pmc2 だけが最善手を着手しない局面の一覧で、3 種類あることがわかりました。

pmcmoves  [(1, 1)]
bestmoves [(2, 0)]
Turn x
x..
o..
.O.

pmcmoves  [(1, 0), (2, 0)]
bestmoves [(1, 0)]
Turn o
o..
...
xoX

pmcmoves  [(1, 1), (2, 2), (2, 1)]
bestmoves [(2, 1)]
Turn x
oOx
x..
o..

上記の中からそれぞれ 1 つの局面を選択して ai_pmc と ai_pmc2 が選択する合法手の違いについて検証することにします。興味がある方は他の局面についても検証してみて下さい。

`ai_pmc` だけが最善手を選択しない局面の検証

下記の ai_pmc だけが最善手を着手しない × の手番局面の検証します。下記の pmcmoves と bestmoves から、ai_pmc がこの局面に対して最善手である (1, 0) とは異なる (1, 2) を選択することがわかります。

pmcmoves  [(1, 2)]
bestmoves [(1, 0)]
Turn x
o.O
ox.
x..

下図左は Mbtree_GUI で上記の局面を選択して ai_pmc が利用する「プレイアウトでの × の勝率」を、下図右は ai_pmc2 が利用する「プレイアウトの × の評価値」を選択した図です。

上図から、どちらの場合でも ai_pmc が選択する (1, 2) を着手した場合の × の勝率と $ps_×$ が同じ 0.500 であることが確認できます。これは、(1, 2) を着手した場合の局面からどのような着手を行っても引き分けになることがないからです。そのことは、上図の (1, 2) を着手した局面の右に黄色で表示される引き分けになる局面が存在しないことから確認できます。

一方、最善手である (1, 0) を選択した場合の × の勝率は 0.333 で 0.500 よりも小さく、$ps_×$ は 0.667 で 0.500 よりも大きくなっており、この違いが ai_pmc が最善手を選択せず、ai_pmc2 が最善手を選択する理由であることがわかります。

そこで (1, 0) に着手を行った局面を検証することにします。下記は (1, 0) を着手した局面のそれぞれの合法手を着手した場合の × の勝率と $ps_×$ を計算した表です。

合法手	合法手を着手した結果	× の勝率	引き分け率	$ps_×$
$(1, 2)$	次に × が何を着手しても引き分けになる	0 %	100 %	0 + 100 × 0.5 = 50 %
$(2, 1)$	次に × が (1, 2) を着手すれば × が勝利し、(2, 2) を着手すれば引き分けになる	50 %	50 %	50 + 50 × 0.5 = 75 %
$(2, 2)$	次に × が (1, 2) を着手すれば × が勝利し、(2, 1) を着手すれば引き分けになる	50 %	50 %	50 + 50 × 0.5 = 75 %

表から、この局面はどの合法手を選択しても引き分け率が 50 % 以上になることが確認できます。そのため、引き分けを 0.5 勝として計算する $ps_×$ の値が 0.667 という x の勝率の値である 0.333 よりもかなり大きな値として計算されます。

`ai_pmc2` だけが最善手を着手しない局面の検証

上記では引き分けを 0.5 勝として計算することによって良い結果がもたらされましたが、ai_pmc2 だけが最善手を着手しない局面が存在することからわかるように、そのことが必ずしも良い結果をもたらすとは限りません。そのことについて検証することにします。

具体的には下記の ai_pmc2 だけが最善手を着手しない × の手番の局面の検証します。下記の pmcmoves と bestmoves から、ai_pmc2 がこの局面に対して最善手である (2, 0) とは異なる (1, 1) を選択することがわかります。

pmcmoves  [(1, 1)]
bestmoves [(2, 0)]
Turn x
x..
o..
.O.

下図左は上図の局面で ai_pmc が利用する「プレイアウトでの × の勝率」を、下図右は ai_pmc2 が利用する「プレイアウトの × の評価値」を選択した場合の図です。

上図から、どちらの場合でも最善手である (2, 0) を選択した場合の × の勝率と $ps_×$ が同じ 0.600 であることが確認できます。これは、(2, 0) を着手した場合の局面からどのような着手を行っても引き分けになることがないからです。そのことは、下図の Dropdown に「プレイアウトでの引き分け率」を選択した場合の (1, 0) を着手した局面の上部に 0 が表示されることから確認することができます。先ほどの場合よりも子ノードが多くて大変ですが、興味がある方は (1, 0) を着手した局面の子孫ノードを選択して、引き分けを表す黄色の局面が 1 つも存在しないことを確認してみて下さい。

ai_pmc2 が選択する (1, 1) を選択した場合の × の勝率は 0.567 で 0.600 よりも小さい値ですが、$ps_×$ は 0.617 で 0.600 よりも大きな値になります。このことから以下のような場合に ai_pmc2 が最善手を選択しない可能性が高くなることが確認できました。

最善手を着手した局面と ai_pmc2 が選択する合法手を着手した局面の勝率が近い
最善手を着手した局面の引き分け率よりも ai_pmc2 が選択する合法手を着手した局面の引き分け率のほうが高い

以上の検証から、引き分けを考慮することによって最善手を選択できるようになる場合と、逆に選択できなくなる場合があることが確認できました。

`gui_play` への `ai_pmc2` の追加

折角なので gui_play で ai_pmc2 を選択できるように修正することにします。具体的には以前の記事で ai_pmc を選択できるようにしたのと同様に下記の表の回数のプレイアウトを行う ai_pmc の AI を追加することにします。

項目名	プレイアウトの回数
`ai_pmc2(5)`	5
`ai_pmc2(10)`	10
`ai_pmc2(100)`	100
`ai_pmc2(1000)`	1000
`ai_pmc2(10000)`	10000

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

8、9 行目：上記の AI を選択できるように ai_dict の値を追加した

 1  import ai as ai_module
 2  from ai import ai_gt7, ai_pmc
 3  from util import load_bestmoves
 4  
 5  def gui_play(ai=None, params=None, ai_dict=None, mbparams={}, seed=None):
元と同じなので省略
 6          for pnum in [5, 10, 100, 1000, 10000]:
 7              ai_dict[f"ai_pmc({pnum})"] = (ai_pmc, {"pnum": pnum})
 8          for pnum in [5, 10, 100, 1000, 10000]:
 9              ai_dict[f"ai_pmc2({pnum})"] = (ai_pmc2, {"pnum": pnum})
10  
11      mb = Marubatsu(**mbparams)
12      mb.play(ai=ai, params=params, ai_dict=ai_dict, seed=seed, gui=True)

行番号のないプログラム

import ai as ai_module
from ai import ai_gt7, ai_pmc
from util import load_bestmoves

def gui_play(ai=None, params=None, ai_dict=None, mbparams={}, seed=None):
    # ai が None の場合は、人間どうしの対戦を行う
    if ai is None:
        ai = [None, None]
    if params is None:
        params = [{}, {}]
    # ai_dict が None の場合は、ai1s ~ ai14s の Dropdown を作成するためのデータを計算する
    if ai_dict is None:
        ai_dict = { "人間": ( None, {} ) }
        for i in range(1, 15):
            ai_name = f"ai{i}s"  
            ai_dict[ai_name] = (getattr(ai_module, ai_name), {})
        bestmoves_and_score_by_board = load_bestmoves("../data/bestmoves_and_score_by_board.dat")
        ai_dict["ai_gt7"] = (ai_gt7, {"bestmoves_and_score_by_board": bestmoves_and_score_by_board})
        bestmoves_and_score_by_board_sv = load_bestmoves("../data/bestmoves_and_score_by_board_shortest_victory.dat")
        ai_dict["ai_gtsv"] = (ai_gt7, {"bestmoves_and_score_by_board": bestmoves_and_score_by_board_sv})
        bestmoves_and_score_by_board_svrd = load_bestmoves("../data/bestmoves_and_score_by_board_sv_rd.dat")
        ai_dict["ai_gtsvrd"] = (ai_gt7, {"bestmoves_and_score_by_board": bestmoves_and_score_by_board_svrd})
        for pnum in [5, 10, 100, 1000, 10000]:
            ai_dict[f"ai_pmc({pnum})"] = (ai_pmc, {"pnum": pnum})
        for pnum in [5, 10, 100, 1000, 10000]:
            ai_dict[f"ai_pmc2({pnum})"] = (ai_pmc2, {"pnum": pnum})

    mb = Marubatsu(**mbparams)
    mb.play(ai=ai, params=params, ai_dict=ai_dict, seed=seed, gui=True)

修正箇所

import ai as ai_module
from ai import ai_gt7, ai_pmc
from util import load_bestmoves

def gui_play(ai=None, params=None, ai_dict=None, mbparams={}, seed=None):
元と同じなので省略
        for pnum in [5, 10, 100, 1000, 10000]:
            ai_dict[f"ai_pmc({pnum})"] = (ai_pmc, {"pnum": pnum})
+       for pnum in [5, 10, 100, 1000, 10000]:
+           ai_dict[f"ai_pmc2({pnum})"] = (ai_pmc2, {"pnum": pnum})

    mb = Marubatsu(**mbparams)
    mb.play(ai=ai, params=params, ai_dict=ai_dict, seed=seed, gui=True)

上記の修正後に下記のプログラムを実行し、AI に ai_pmc2 選択して対戦を行うことができるようになったことを確認してみて下さい。

gui_play()

また、「状況」ボタンをクリックしてその右に「ai_pmc2(10000)」を選択すると、下図のように 10000 回のプレイアウトを行った ai_pmc が計算した各合法手の $ps_〇$ が表示されるようになります。興味がある方は他にも様々な操作を行ってみて下さい

今回の記事のまとめ

今回の記事では引き分けを考慮したプレイアウトの評価値を用いた原始モンテカルロ法について説明し、その方法で合法手を選択する ai_pmc2 の実装と、そのアルゴリズムの性質の検証を行いました。

検証の結果、下記の事が判明したため、今後の記事ではプレイアウトの評価値を用いた原始モンテカルロ法を採用することにします。

ai2s と ai14s に対する対戦成績が ai_pmc よりも良い
ai_pmc よりも計算を簡潔に行うことができる
モンテカルロ法を利用したゲームの AI のアルゴリズムでは引き分けを 0.5 勝として計算するのが一般的である

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

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

次回の記事

近日公開予定です

これまでの記事では理論値と表記していましたがこの値は期待値のことです。期待値の方がわかりやすい気がしましたので、今回の記事から期待値と表記することにします ↩

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を一から作成する その238 引き分けを考慮した評価値を用いた原始モンテカルロ法の実装と検証

目次と前回の記事

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

引き分けを考慮した評価値を用いた原始モンテカルロ法

引き分けを考慮した評価値を用いるアルゴリズム

記号の定義

プレイアウトの評価値の意味と計算式

最善手を計算するアルゴリズム

プレイアウトの評価値の性質

アルゴリズムの優劣

視覚化のための修正

Mbtree クラスの calc_playout_prob_by_df メソッドの修正

Mbtree クラスの calc_and_save_bestmoves_and_score_by_board メソッドの修正

Mbtree_GUI クラスの create_widget メソッドの修正

Node クラスの __init__ と draw_node メソッドの修正

ai_pmc2 の実装と検証

ai2s と ai14s との対戦

最善手を着手しない局面の計算

先手の手番の無限回の ai_pmc2 が弱解決の AI であることの確認

後手の手番の無限回の ai_pmc2 VS ai14s の対戦の検証

ai_pmc との違いの検証

ai_pmc だけが最善手を選択しない局面の検証

ai_pmc2 だけが最善手を着手しない局面の検証

gui_play への ai_pmc2 の追加

今回の記事のまとめ

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

次回の記事

Pythonで〇×ゲームのAIを一から作成する　その238　引き分けを考慮した評価値を用いた原始モンテカルロ法の実装と検証

Mbtree クラスの `calc_playout_prob_by_df` メソッドの修正

Mbtree クラスの `calc_and_save_bestmoves_and_score_by_board` メソッドの修正

Mbtree_GUI クラスの `create_widget` メソッドの修正

Node クラスの `init` と `draw_node` メソッドの修正

`ai_pmc2` の実装と検証

`ai2s` と `ai14s` との対戦

先手の手番の無限回の `ai_pmc2` が弱解決の AI であることの確認

後手の手番の無限回の `ai_pmc2` VS `ai14s` の対戦の検証

`ai_pmc` との違いの検証

`ai_pmc` だけが最善手を選択しない局面の検証

`ai_pmc2` だけが最善手を着手しない局面の検証

`gui_play` への `ai_pmc2` の追加