Pythonで〇×ゲームのAIを一から作成する その239 強化学習としての原始モンテカルロ法とプレイアウトに関するプログラムの修正

目次と前回の記事

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

今回の記事の内容

今回の記事では以前の記事で説明した強化学習の用語を用いて原始モンテカルロ法について説明します。その後で、一部のプログラムの修正を行います。

強化学習としての原始モンテカルロ法の説明

最初に一般的な 〇× ゲームの強化学習において 以前の記事で説明した強化学習の用語がどのように対応するかについて、これまでに実装したプログラムを例に挙げながら具体的に説明し、その後で原始モンテカルロ法による 〇× ゲームの強化学習の場合について説明します。

一般的な 〇× ゲームの強化学習と強化学習の用語の関係

下記は原始モンテカルロ法に限らない、一般的な 〇× ゲームの強化学習と強化学習の用語の関係の説明です。

エージェントと環境

以前の記事で説明したように、強化学習では学習を行うプログラムのことをエージェント（agent）、エージェントが様々な行動の試行錯誤を行い経験を得る対象のこと環境（environment）と呼びます。これまでに実装したプログラムの場合は ai_pmc と ai_pmc2 がエージェントで、〇× ゲームの処理を行う Marubatsu クラスのインスタンスが環境です。なお、以後の説明では環境を表す Marubatsu クラスのインスタンスのことを mb と表記することにします。

行動、方策、エピソード、ステップ

以前の記事で説明したように、エージェントが環境に対して行うふるまいのことを行動（action）と呼びます。〇× ゲームにおける行動とは局面の合法手の中から一つを選択して着手を行うことに相当します。具体的にはエージェントが環境である mb の move メソッドを呼び出して着手を行うことが行動になります。

以前の記事で説明したように、強化学習ではエージェントが現在の環境の状態で行動を選択する際に指針とする「どのような行動をとるべきか」の方針のことを方策（policy）と呼び、エージェントは方策に従って行動を選択します。一般的に方策は、学習の対象となる環境の「各状態」で取れる「各行動を選択する確率」として表現します。原始モンテカルロ法の場合の方策は、すべての状態（局面）で合法手を選択する確率を均等に割り振ります。

以前の記事で説明したように、エージェントが目的を達成するために行った一連の行動の集まりのことをエピソード（episode）と呼び、エピソード内の一つ一つの行動のことをステップ（step）と呼びます。〇× ゲームにおける一連の行動とは、現在の局面からゲームの決着が付くまで合法手を着手し続けるということを表すので、〇× ゲームの強化学習におけるエピソードとステップは下記のようになります。

• エピソード：現在の局面から決着が付くまで方策に従って合法手を選択し、move メソッドで着手し続ける一連の流れ
• ステップ：エピソード内で行われる一つ一つの行動（着手）

状態、観測

以前の記事で説明したように、環境内でエージェントが現在置かれている状況のことを状態（state）と呼び、〇× ゲームの場合は局面を表す「手番」、「ゲーム盤」、「ゲームの状況（プレイ中または結果）」、「合法手の一覧」などが状態です。

エージェントが環境から現在の状態の情報を得ることを観測（observation）と呼び、〇× ゲームの場合はエージェントが環境である mb の下記の属性とメソッドを利用することが観測に相当します。

属性、メソッド	意味
turn	手番
board	ゲーム盤
status	ゲームの状況（プレイ中または結果）
calc_legal_moves	合法手の一覧を返すメソッド

合法手の一覧はゲーム盤の情報から計算することができるので以前の記事の表では合法手の一覧を状態の中に入れていませんでした。しかし、ai_pmc では環境である mb の calc_legal_moves メソッドを用いて合法手の一覧を環境から得ているので今回の記事では合法手の一覧も観測によって得られる状態に含めることにしました。

即時報酬、累積報酬（収益）

以前の記事で説明したように、報酬（reward）はエージェントの行動の結果、目標に対してどれほどの成果が得られたかを表す数値で、一般的には大きい程得られた成果が高いことを表します。以前の記事で説明したように、報酬にはステップごとに得られる「即時報酬」とエピソード全体で得られる「累積報酬」（収益）があります。

〇× ゲームの場合の即時報酬は一般的に下記の表のように、ゲームの決着が付いていない局面の場合は 0 を、決着が付いた局面の場合は勝敗に応じた値を設定し、引き分けの場合は 0.5（0.5 勝）としてカウントします。

行動の結果	即時報酬
ゲームの決着が付いていない	0
〇 の勝利	1
引き分け	0.5
× の勝利	0

上記の即時報酬は 〇 の手番を基準としているため 〇 にとって有利なほど大きな値になります。逆に × の手番の場合は × にとって有利な方が小さな値になるため、実際の強化学習では × の手番の場合は上記の報酬に -1 を乗算して符号を反転させるという工夫が良く用いられます。

オセロ、将棋、囲碁などのようなゲームの場合も同様に、ゲームの決着が付いていない場合の報酬を 0 とし、決着が付いた場合に勝敗結果に応じた報酬を設定します。

一方で、点数のあるアクションゲームのような場合は、ゲームの途中で敵を倒すなどの行動によって得られる点数を即時報酬とします。

ゲームの決着が付いていない場合の即時報酬が 0 であることから、現在の局面から決着が付くまでの一連の行動（1 つのエピソード）で得られた即時報酬の合計は、下記の表のようにゲームの決着が付いた時に得られた即時報酬、すなわちゲームの勝敗結果を表す数値そのものになります。

プレイアウトの結果	即時報酬の合計
〇 の勝利	1
引き分け	0.5
× の勝利	0

一般的な強化学習では累積報酬（収益）を即時報酬の合計とは少し異なる方法で計算しますが、〇× ゲームのような途中の行動で報酬が得られず、最後の行動だけで報酬が得られるような場合などでは、即時報酬の合計そのものを累積報酬とする場合があります。実際に原始モンテカルロ法での累積報酬は即時報酬の合計で計算します。

原始モンテカルロ法の累積報酬を即時報酬の合計とは異なる方法で計算することもできます。一般的な強化学習で用いられる累積報酬の計算方法と、それを原始モンテカルロ法に適用した場合の特徴については今後の記事で説明する予定です。

探索と活用

この後の説明で必要となる強化学習の「探索」と「活用」という用語について説明します。

下記は以前の記事で説明した強化学習の目的です。

エージェントと環境が「方策に従う行動」と「その結果変化した状態と得られた報酬の報告」という相互作用を繰り返して得られた経験を元に方策を改善することで、累積報酬の期待値を最大化するような方策を学習するという仕組みである。

現実の世界で何かを自分の力だけで学ぶ際には以下のような手法を取るのが一般的です。

1. 未知の行動を行うことで新しい情報を集める（経験を得る）
2. これまでに得られた経験を元に最適だと思われる行動を取る（経験を活用する）

強化学習では前者の行動のことを「探索（exploration）」、後者の行動のことを「活用（exploitation）」と呼びます。また、先程説明した「エピソード」が 1 回の探索¹の作業に相当します。

以前の記事で紹介した「A 地点から B 地点の最短ルートを探す」という「最短経路の学習」を具体例に挙げて説明します。

探索の手法の一例として、取れる行動の中からランダムに行動を選択するというものがあります。最短経路の学習の場合は交差点に到着するたびにランダムに道を選択することに相当し、そのような探索を何度も繰り返して行うことで A 地点から B 地点までの様々なルートの所要時間の経験を得ることができます。

活用の一例としては、これまでに経験した最良の行動を選択するという方法があります。最短経路の学習の場合はこれまでに通った（経験した）ルートの中で最も所要時間が短かったルートを選択することが活用に当たります。

探索と活用のバランス

強化学習の手法の大きな違いの一つに「探索と活用をどのように行うか」というアプローチの差があります。

この後で説明するように、原始モンテカルロ法ではプレイアウトというランダムな行動を選択し続ける探索を数多く行い、探索によって得られた経験から行動を選択するという活用を行います。この手法は探索を完了してから活用を行う、すなわち「探索と活用を完全に独立して行う」という特徴があります。この手法では非常に幅広い経験を得ることができますが、一方でランダムな行動によって得られる経験はゲームの本質的な攻略にはあまり役に立たない場合が多いため効率が悪いという問題があります。このことは、お互いがほぼランダムに指し合う初心者同士の対局をいくら眺めても、上級者どうしの高いレベルの対局で通用するような良い経験がほとんど得られない点に良く似ています。

この問題を解決する手法として、これまでに得られた経験を活用しつつ、同時に新しい探索を混ぜて行うという「探索と活用を並行して行う」という手法があります。この手法の一例を「最短経路の学習」で説明すると、交差点で以下のような行動を選択するという探索を行うことに相当します。

• 基本的（例えば 90 % の確率）には、これまでに得た経験を元に B 地点に速くたどり着けると思われる道を選択する（活用）
• たまに（例えば 10 % の確率）ランダムに道を選択する（探索）

上記の「たまにランダムな道を選択する」ことを現実の世界で例えると、たまに気まぐれをおこして普段は通らない道を選択することに相当します。その結果、運が良ければ近道を見つけてより短い経路を発見することができるかもしれませんが、運が悪いと遠回りになるかもしれません。なお、遠回りになった場合でも「その道は遠回りになる」という経験が得られるためその探索が完全に無駄になるわけではありません。人間と同様に強化学習においても「失敗から学ぶ」ということは非常に重要です。

このように、探索と活用をバランスよく併用しながら経験を集めることによって、探索と活用を独立して行う場合よりも効率よく学習を進めることができるようになりますが、バランスが悪いと逆効果になってしまうという問題があります。例えば上記のランダムな道を選択する確率を 99 % のように非常に大きくすると、ランダムな選択だけを行う場合とほとんど変わらないことになります。逆に 0.01 % のように非常に小さい値にしてしまうと、ほとんどの探索でそれまでの経験の中の最短ルートを選択することになってしまうため、探索によって新しい経験がほとんど得られなくなってしまいます。

探索と活用をどのように行うかは強化学習の非常に重要なテーマとなっており、質の良い経験を効率的に得るための様々な手法が考案されています。それらの手法の一部については今後の記事で紹介する予定です。

まとめ

下記は 〇× ゲームにおける上記の用語の具体例をまとめた表です。探索と活用については強化学習の手法によって大きく異なるため省略しました。

用語	具体例
エージェント	ai_pmc などの強化学習を行う AI の関数
環境	Marubatsu クラスのインスタンス（本記事では mb と表記する）
行動	mb.move で合法手の中から一つを選択して着手を行うこと
方策	ゲームの各局面（状態）で各行動を選択する確率
エピソード	現在の局面から決着が付くまで行った一連の行動
ステップ	エピソード内の一つ一つの行動（着手）
状態	局面の情報（手番、ゲーム盤、ゲームの状況、合法手の一覧）
観測	mb の属性の参照とメソッドの呼び出し
即時報酬	行動の結果得られる 〇 にとっての有利さを表す数値 決着が付いていない場合は 0 が得られる
累積報酬	エピソードで得られる即時報酬の合計

ミニマックス法（αβ 法）と強化学習の違い

上記の説明から、これまでの記事で実装したミニマックス法や αβ 法を用いた AI の関数も、上記の表の用語で説明したものと同様の処理を行っていることから強化学習の一種ではないかと思った人がいるかもしれませんが、一般的にはミニマックス法や αβ 法は強化学習とはみなされないのでその理由について説明します。

強化学習の「方策」が「各行動を選択する確率」で表現されることからわかるように、強化学習は確率を用いた計算を行うアルゴリズムです。また、強化学習では環境の内部構造をすべて把握して机上で分析するのではなく、環境に対して実際に行動を起こした結果得られた状態や報酬を観測して学習することで最適解に近い近似解を計算するという、以前の記事で説明したヒューリスティックなアルゴリズムです。

それに対してミニマックス法や αβ 法は確率を用いず、計算を行うことができれば²確率に頼らない確定的な最適解を必ず導くことができるという、以前の記事で説明した演繹法によるアルゴリズムです。

上記の違いを「A 地点から B 地点の最短ルートを探す」という問題で説明すると以下のようになります。

• 強化学習の手法：地図を見ずに A 地点から B 地点まで様々なルートで歩くという経験を積み重ねることで最短ルートと思われる経路を探すというアプローチに相当する。経験を積めば積むほど所要時間が短いルートが見つかるが、そのルートが本当の最短ルートであるという保証はない
• ミニマックス法の手法：手元にある地図を見て A 地点から B 地点までのすべてのルートの所要時間を机上で計算することで最短ルートを探すというアプローチに相当する。すべてのルートの所要時間を計算できれば必ず最短ルートを見つけることができるが、ルートの数が膨大になると計算に時間がかかりすぎて現実的な時間内では答えが見つからない場合がある

原始モンテカルロ法による 〇× ゲームの強化学習と強化学習の用語の関係

次に、原始モンテカルロ法による 〇× ゲームの強化学習と強化学習の用語の関係について説明します。

原始モンテカルロ法による強化学習は、一般的な強化学習と比べて様々な条件が限定されています。そのため、一般的な強化学習で必要となる高度な数学的知識を必要としないという特徴があり、その性質から強化学習を学ぶ際の最初の題材として良く取り上げられます。

エージェント、環境、行動、報酬

エージェント、環境、行動、報酬に関しては先ほどの説明と同様です。

探索、活用、エピソード

下記の原始モンテカルロ法のアルゴリズムは、手順 1 がランダムな行動を選択し続けることで経験を得るという「探索」に相当し、手順 2 が得られた経験から行動を選択する「活用」に相当します。また、手順 1-1 で行う一回のプレイアウトの作業が強化学習における 1 回の「エピソード」に相当します。

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

なお、上記の「プレイアウトの評価値」は前回の記事で説明したように引き分けを 0.5 勝として計算した場合の勝率を表します。

上記の手順 1 からわかるように、原始モンテカルロ法ではプレイアウトという探索を何度も行いますが、探索を行う際にそれ以前に行った探索の知識を利用（活用）することはありません。手順 2 の「活用」は手順 1 の「探索」の作業が完全に完了してから行われるため、原始モンテカルロ法では「探索と活用を独立して行う」という強い特徴があります。

探索の方法と方策

「現在の局面から合法手を着手したすべての局面」という表記は長いので、今回の記事では以後はそれらの局面のことを「次の局面」と表記することにします。

原始モンテカルロ法では、次の局面に対してあらかじめ決めておいた回数または制限時間がくるまでランダムな着手を行い続けるというプレイアウトを行います。そのため、原始モンテカルロ法では局面を表す「状態」と行動の方針を表す「方策」の関係は下記の表のようになり、この方策に従って「探索」が行われます。

状態	方策
現在の局面	それぞれの合法手を順番に選択する（すべての合法手を等確率で選択する）
それ以外の局面	常に合法手の中からランダムに選択する（すべての合法手を等確率で選択する）

原始モンテカルロ法は探索と活用が独立しているため、「すべての探索で常に上記の同一の方策が使われ続ける」という特徴があります。

活用の方法

強化学習における活用は、探索によって得られた経験から累積報酬の期待値を最大化する方策を求めるというもので、原始モンテカルロ法での活用は以下のようになります。

「次の局面のプレイアウトの評価値が最も高くなる合法手を選択する」

上記を強化学習の用語で置き換えると下記のようになります。

現在の局面での方策を以下のように改善する。

• 次の局面のプレイアウトの評価値が最も高くなる合法手を選択する確率を 1（100 %）とする。そのような合法手が複数存在する場合はそれらの合法手を選択する確率を均等に割り振る
• それ以外の合法手を選択する確率を 0（0 %）とする

常に同じ行動を選択する方策の事を決定論的方策（deterministic policy）、確率によって行動を選択する方策の事を確率論的方策（stochastic policy）と呼びます。

なお、特定の行動を選択する確率を 100 % とすることで確率論的方策を用いて決定論的方策を表現することができるので、強化学習における方策は確率論的方策として表現するのが一般的で、本記事における方策も確率論的方策を用います。

活用の方法の妥当性

上記の方策で累積報酬の期待値が最大化されることを説明します。

先程説明したように、現在の局面から決着が付くまでの一連の行動（1 つのエピソード）で得られた累積報酬（即時報酬の合計）は下記の表のように引き分けを 0.5 勝とした場合の 〇 の勝敗結果に応じた報酬として設定します。これは、現在の局面に限らず任意の局面からプレイアウトを行った場合に得られる累積報酬でも同様です。

プレイアウトの結果	累積報酬（即時報酬の合計）
〇 の勝利	1
引き分け	0.5
× の勝利	0

原始モンテカルロ法では次の局面に対して複数回のプレイアウトを行った結果得られたプレイアウトの評価値を用いて活用を行いますが、以前の記事で説明したようにそのプレイアウトの評価値を計算する式は「累積報酬の平均値」を計算する式そのものです。従って、原始モンテカルロ法における活用は、次の局面の中から探索（プレイアウト）によって最も高い累積報酬の平均値が得られた合法手を選択するという処理を行います。

プレイアウトではランダムな合法手を選択するので、プレイアウトによって得られる累積報酬を確率変数 $X$ で表すと、累積報酬の期待値は下記の式で表されます。

$E[X] = 0 × P(X=0) + 0.5 × P(X=0.5) + 1 × P(X=1)$

ただし、$P(X=x)$ はプレイアウトによって累積報酬 $x$ が得られる確率を表します。確率について忘れた方は以前の記事を復習して下さい。

$P(X=x)$ は確率を表すので 0 以上 1 以下の値であるため、累積報酬の期待値は必ず有限な値になります。また、原始モンテカルロ法ではすべての探索（プレイアウト）が毎回同じ方策で完全に独立して行われるため、累積報酬は「ある確率分布から無作為復元抽出されたデータ」とみなすことができます。この性質から以前の記事で説明した大数の法則を適用することができ、プレイアウトを複数回行った際に得られる累積報酬の平均値は、プレイアウトを行う回数を増やせば増やすほど理論上の値である累積報酬の期待値に近づいていくことになります。

上記から、プレイアウトの回数を多くすればするほど、次の局面のプレイアウトの評価値が最も高くなる合法手を選択するという方策が、累積報酬の期待値を最大化する最善の方策に一致する確率が極めて高くなることが証明されました。

このように、原始モンテカルロ法における活用の妥当性は、大数の法則だけでシンプルに説明することができます。これは探索と活用を独立して行っているからこそ成り立つ大きなメリットです。一方、探索と活用を並行して行うような一般的な強化学習の場合は、より複雑な数学的な概念を用いる必要があります。それらの高度な手法については今後の記事で説明する予定です。

原始モンテカルロ法を直観的な言葉でまとめる以下のようになります。

• どの合法手が良いかの見当がまったくつかないので、ランダムな着手を行い続けるというプレイアウトを何度も行うことで経験を集める（探索）
• その際に、〇 の勝利を 1、引き分けを 0.5、× の勝利を 0 とした報酬を設定することで、得られた経験の良し悪しを数値化する
• 最終的に、次の局面の累積報酬の平均（プレイアウトの評価値）が最も高くなる合法手を、最も勝ちやすい合法手とみなして選択する（活用）

原始モンテカルロ法の問題点

原始モンテカルロ法の大きな問題の一つは、探索で利用する方策が常に同じであるため、探索で得られた経験を探索がすべて終了するまで活かすことができないというものです。人間が学習を行う場合は、得られた経験を即座に次の探索に活かすのが一般的ではないでしょうか？例えば大きな失敗をしてしまった場合は、次の行動では即座にその失敗を行わないような行動を選択するのが一般的ですが、原始モンテカルロ法では常に同じ方策で探索を行うため、何度も大きな失敗をするような探索を行ってしまう可能性が高くなります。

もう一つの大きな問題としては、原始モンテカルロ法では現在の局面に対する方策のみを計算するというものです。AI の目的は強い相手に対して勝利できるような合法手を選択することですが、プレイアウトによって得られる経験はランダムな着手を行った対局であるため、得られた経験の多くは弱い相手との対戦結果になります。この問題を解決するためには現在の局面以外の局面の方策を得られた経験によって更新することで、次の探索を行う際に最善手に近い合法手を選択する確率が高くなるようにする必要があります。

これらの問題点を解決すためには、現在の局面だけでなくプレイアウトの途中で通過した様々な局面の方策も同時に記録・更新していく仕組みが必要です。探索によって得られた経験を次の探索に即座にフィードバックできれば、探索を進めることでより最善手に近い精度の高い合法手を選択できるようになります。そういったより効率的で高度な強化学習の手法については次回以降の記事で紹介します。

ai_pmc と ai_pmc2 の修正

原始モンテカルロ法で 〇× ゲームの着手を選択する現状の ai_pmc と ai_pmc2 が行う処理にいくつかの問題があることに気が付きましたので修正することにします。

現状の処理の問題点

現状の処理の問題点について説明します。

下記は原始モンテカルロ法のアルゴリズムの再掲です。

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

上記の手順 1 は次の局面（現在の局面から合法手を着手したすべての局面）に対して特定の回数または制限時間までプレイアウトを行うというものですが、現状の ai_pmc と ai_pmc2 は以前の記事で説明した制限時間に関する処理の問題から、上記とは若干異なる下記のアルゴリズムでプレイアウトを行っています。

現在の局面から「特定の回数」または「特定の時間が経過するまで」プレイアウトを行い、最初に着手を行った合法手ごとにプレイアウトの結果の集計を行う。

プレイアウトの回数が少ない場合の問題

上記のアルゴリズムは、プレイアウトの回数が多くなればなるほど大数の法則から最初の着手が合法手の中から均等に選択されるようになるため、プレイアウトの回数が多い場合は元の原始モンテカルロ法のアルゴリズムとほぼ同じ処理が行われます。逆に言えば、プレイアウトの回数が少ない場合は最初の着手でそれぞれの合法手が選択される割合にばらつきが生じるという問題があります。さらに、以前の記事で説明したように、プレイアウトの回数を減らすと特定の合法手が選択されない場合が生じるという問題もあります。

行なわれる処理の見え方の問題

原始モンテカルロ法でプレイアウトを行うのは現在の局面ではなく次の局面（現在の局面から合法手を着手したすべての局面）です。

それに対して現状の ai_pmc と ai_pmc2 では、現在の局面から何度もプレイアウトを行い、その結果を最初に着手を行った合法手で分類して集計するという処理を行っているため、原始モンテカルロ法が「プレイアウトを現在の局面から行う」というアルゴリズムのように見えてしまうという問題があります。

Marubatsu クラスの playout メソッドの処理

Marubatsu クラスの playout メソッドは複数回のプレイアウトの処理と、次の局面ごとのプレイアウトの結果の集計処理を行いますが、これはメソッドの名前である「プレイアウト」の処理というよりは、原始モンテカルロ法そのものの処理であるため、メソッドの名前と処理の内容が一致していないという問題があります。

また、現状の playout メソッドは原始モンテカルロ法の処理を行うように実装されているため、プレイアウトの処理を必要とする他の強化学習のアルゴリズムで playout メソッドを利用することができないという問題があります。例えば今後の記事で紹介するモンテカルロゲーム木探索の処理では原始モンテカルロ法と異なる状況でプレイアウトを行うため、現状の playout メソッドをそのまま利用することはできません。

修正方法

上記のことから、以下のような修正を行うことにします。

• Marubatsu クラスの playout メソッドが 1 回のプレイアウトの処理だけを行う
• 制限時間の処理は playout では行わない
• ai_pmc と ai_pmc2 が本来の原始モンテカルロ法のアルゴリズムで処理を行う
• Marubatsu クラスの playout メソッドで行っていた制限時間の処理や、プレイアウトの結果の集計処理を ai_pmc と ai_pmc2 で行う

Marubatsu クラスの playout メソッドの修正

原始モンテカルロ法では、現在の局面から特定の合法手を着手した局面に対してプレイアウトを行います。そこで Marubatsu クラスの playout メソッドに現在の局面に対して着手する合法手を代入する仮引数を追加することにし、下記のように修正することにします。

• 仮引数 move に現在の局面に対して行う着手を代入する
• プレイアウトの処理は 1 度だけ行い、勝敗結果を表す値を返り値として返すようにする
• 現状の playout メソッドと同様に、playout メソッドの処理によって局面の状況が変化しないようにする。具体的な方法について忘れた方は 以前の記事を復習すること

下記はそのように playout メソッドを修正したプログラムです。なお、大幅な修正を行うため修正箇所は省略します。

• 4 行目：仮引数を最初の着手を代入する move のみとする。なお、今後の記事で紹介するモンテカルロゲーム木探索では現在の局面からプレイアウトを行う場合があるため、デフォルト値を None としたデフォルト引数とし、None の場合は現在の局面からプレイアウトを行うものとした
• 5 行目の前にあった result の初期化や制限時間に関する処理を削除する。なお、5 行目の現在のゲーム盤の情報を保存する処理は元と同じである
• 6 ~ 8 行目：現在の手番、手数、状態をローカル変数に代入する
• 9 ~ 17 行目：決着が付くまで繰り返し処理を行う
• 10、11 行目：move が None の場合に次の着手がランダムに選択されるようにすることで、仮引数 move に最初に着手する合法手が代入されていた場合は最初にその合法手が着手されるようにする
• 13 ~ 16 行目：move の着手を行いゲームの状態を計算する。この部分は元の playout の処理と同じ
• 17 行目：次の着手がランダムに選択されるようにするために move に None を代入する
• 18 行目：ゲーム盤をプレイアウトを行う前の状態に戻す
• 19 行目：ゲームの結果を返り値として返す

 1  from marubatsu import Marubatsu
 2  import random
 3  
 4  def playout(self, move=None):
 5      board = self.board.save()
 6      turn = self.turn
 7      move_count = self.move_count
 8      status = self.status
 9      while status == self.PLAYING:
10          if move is None:
11              move = random.choice(self.calc_legal_moves())
12          self.board.setmark_by_move(move, turn)
13          last_turn = turn
14          turn = self.CROSS if turn == self.CIRCLE else self.CIRCLE
15          move_count += 1
16          status = self.board.judge(last_turn, move, move_count)
17          move = None
18      self.board.load(board)
19      return status
20  
21  Marubatsu.playout = playout

行番号のないプログラム

from marubatsu import Marubatsu
import random

def playout(self, move=None):
    board = self.board.save()
    turn = self.turn
    move_count = self.move_count
    status = self.status
    while status == self.PLAYING:
        if move is None:
            move = random.choice(self.calc_legal_moves())
        self.board.setmark_by_move(move, turn)
        last_turn = turn
        turn = self.CROSS if turn == self.CIRCLE else self.CIRCLE
        move_count += 1
        status = self.board.judge(last_turn, move, move_count)
        move = None
    self.board.load(board)
    return status

Marubatsu.playout = playout

ai_pmc の修正

本来の原始モンテカルロ法のアルゴリズムで処理を行うようにするために、以下のように ai_pmc を修正することにします。

• それぞれの合法手を着手した局面に対して pnum 回のプレイアウトを行うようにする
• 制限時間を設定した場合の時間経過による打ち切り処理を、それぞれの合法手を着手した局面に対して 1 回ずつプレイアウトを行うたびに行うようにする

上記のように修正することでプレイアウトを行う回数が修正前の pnum 回から 「pnum × 現在の局面の合法手の数」回に増えますが、本来の原始モンテカルロ法のアルゴリズムのようにすべての合法手を着手した局面で必ず同じ回数のプレイアウトが行われるようになります。また、プレイアウトの回数が少ない場合や制限時間が短い場合³でも、必ずそれぞれの合法手を着手した局面に対して 1 回以上のプレイアウトが行われるようになります。

上記のように修正すると、それぞれの合法手を着手した局面に対して 1 回ずつプレイアウトが行われるまで処理が中断されなくなるため、合法手の数が非常に多く、1 回のプレイアウトの処理に時間がかかるような局面では ai_pmc の処理時間が制限時間をかなり超えてしまう可能性が生じる点に注意が必要です。

なお、〇× ゲームの場合は合法手の数が最大で 9 で、一回のプレイアウトの処理時間は非常に短いのでそのことが問題になることはないでしょう。

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

• 6 行目の前にあった、retval = mb.playout(pnum, timelimit) を削除する
• 6 ~ 13 行目：それぞれの合法手を着手した局面に対するプレイアウトの結果を記録する result を初期化する。この処理は修正前の playout メソッド内に記述されていたものと同じである
• 14 行目：それぞれの合法手を着手した局面に対して行われたプレイアウトの回数を数える変数を 0 で初期化する
• 15 ~ 20 行目：それぞれの合法手を着手した局面に対する pnum 回のプレイアウトの処理を行う
• 16、17 行目：制限時間を超えていた場合はそこでプレイアウトの処理を中断する
• 18、19 行目：それぞれの合法手を着手した局面に対するプレイアウトの処理を mb.playout(move) で行い、返り値を利用して勝敗結果を result に集計する
• 20 行目：それぞれの合法手を着手した局面に対して 1 回ずつプレイアウトの処理を行ったので、playout_num を 1 増やす
• 22 行目以降の処理は元のプログラムと基本的には同じだが、下記の点を修正した
• 27 行目：retval["result"].items() を result に修正した
• 28 行目：sum(count.values()) を playout_num に修正した。なお、pnum が 0 以下の場合などで playout_num が 0 となる場合があるため、後で 0 除算が行われないようにするために組み込み関数 max で totalcount の最小値を 1 とする必要がある
• 30 ~ 33、39 行目：score_by_move のキーにはゲーム盤の座標が記録される点が表示した際にわかりづらいので、dict 内包表記と xy_to_move メソッドを利用してキーを (x, y) の座標に変換した score_by_movexy を計算し、39 行目でその値も返り値として返すように修正した
• 37 行目：retval["count"] を playout_num に修正した

 1  from ai import dprint
 2  from random import choice
 3  from time import perf_counter
 4
 5  def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
元と同じなので省略
 6      result = {}
 7      legal_moves = mb.calc_legal_moves()
 8      for move in legal_moves:
 9          result[move] = {
10              mb.CIRCLE: 0,
11              mb.CROSS: 0,
12              mb.DRAW: 0,
13          }  
14      playout_num = 0
15      for _ in range(pnum):
16          if timelimit is not None and perf_counter() > timelimit_pc:
17              break
18          for move in legal_moves:
19              result[move][mb.playout(move)] += 1
20          playout_num += 1
21  
22      best_moves = []
23      best_movesxy = []
24      best_ratio = (-1, 0)
25      if analyze:
26          ratio_by_move = {}
27      for move, count in result.items():
28          totalcount = max(1, playout_num)
元と同じなので省略
29      if analyze:
元と同じなので省略
30      score_by_movexy = {
31          mb.board.move_to_xy(move): score 
32          for move, score in score_by_move.items()
33      } 
34      return {
35          "candidate": best_movesxy,
36          "ratio_by_move": ratio_by_move,
37          "playout num": playout_num,
38          "score_by_move": score_by_move,
39          "score_by_movexy": score_by_movexy,
40      }
41      else:
42          return choice(best_moves) 

行番号のないプログラム

from ai import dprint
from random import choice
from time import perf_counter

def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
    if mb.move_count == 8:
        best_move = mb.calc_legal_moves()[0]
        if analyze:
            return {
                "candidate": [mb.board.move_to_xy(best_move)],
                "ratio_by_move": {},
                "playout num": 0,
                "score_by_move": {best_move: 1},                
            }
        else:
            return best_move
   
    if timelimit is not None:   
        starttime = perf_counter()
        timelimit_pc = starttime + timelimit
    result = {}
    legal_moves = mb.calc_legal_moves()
    for move in legal_moves:
        result[move] = {
            mb.CIRCLE: 0,
            mb.CROSS: 0,
            mb.DRAW: 0,
        }
    playout_num = 0
    for _ in range(pnum):
        if timelimit is not None and perf_counter() > timelimit_pc:
            break
        for move in legal_moves:
            result[move][mb.playout(move)] += 1
        playout_num += 1

    best_moves = []
    best_movesxy = []
    best_ratio = (-1, 0)
    if analyze:
        ratio_by_move = {}
    for move, count in result.items():
        totalcount = max(1, playout_num)
        winratio = count[mb.turn] / totalcount
        drawratio = count[mb.DRAW] / totalcount
        movexy = mb.board.move_to_xy(move)
        dprint(debug, "=" * 50)
        dprint(debug, f"move {movexy}")
        dprint(debug, f"ratio      win: {winratio:.3f} draw {drawratio:.3f}")
        dprint(debug, f"best ratio win: {best_ratio[0]:.3f} draw {best_ratio[1]:.3f}", )
        if best_ratio is None or winratio > best_ratio[0] or (winratio == best_ratio[0] and drawratio > best_ratio[1]):
            best_ratio = (winratio, drawratio)
            best_moves = [move]
            best_movesxy = [movexy]
            dprint(debug, "UPDATE")
            dprint(debug, f"  best score {best_ratio}")
            dprint(debug, f"  best moves {best_movesxy}")
        elif winratio == best_ratio[0] and drawratio == best_ratio[1]:
            best_moves.append(move)
            best_movesxy.append(movexy)
            dprint(debug, "APPEND")
            dprint(debug, f"  best moves {best_movesxy}")
        if analyze:
            ratio_by_move[movexy] = (winratio, drawratio)
    if analyze:
        score_by_move = {mb.board.xy_to_move(x, y): round(winratio, 3) 
                         for (x, y), (winratio, drawratio) in ratio_by_move.items() }
        if mb.status == mb.PLAYING and max(score_by_move.values()) == 0:
            score_by_move = {mb.board.xy_to_move(x, y): round(drawratio, 3) 
                             for (x, y), (winratio, drawratio) in ratio_by_move.items() }         
        score_by_movexy = {
            mb.board.move_to_xy(move): score 
            for move, score in score_by_move.items()
        } 
        return {
            "candidate": best_movesxy,
            "ratio_by_move": ratio_by_move,
            "playout num": playout_num,
            "score_by_move": score_by_move,
            "score_by_movexy": score_by_movexy,
        }
    else:
        return choice(best_moves) 

修正箇所

from ai import dprint
from random import choice
from time import perf_counter

def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
元と同じなので省略
-   retval = mb.playout(pnum, timelimit)
+   result = {}
+   legal_moves = mb.calc_legal_moves()
+   for move in legal_moves:
+       result[move] = {
+           mb.CIRCLE: 0,
+           mb.CROSS: 0,
+           mb.DRAW: 0,
+       }
+   playout_num = 0
+   for _ in range(pnum):
+       if timelimit is not None and perf_counter() > timelimit_pc:
+           break
+       for move in legal_moves:
+           result[move][mb.playout(move)] += 1
+       playout_num += 1

    best_moves = []
    best_movesxy = []
    best_ratio = (-1, 0)
    if analyze:
        ratio_by_move = {}
-   for move, count in retval["result"].items():
+   for move, count in result.items():
-       totalcount = max(1, playout_num)
+       totalcount = max(1, sum(count.values()))
元と同じなので省略
    if analyze:
元と同じなので省略
+       score_by_movexy = {
+           mb.board.move_to_xy(move): score 
+           for move, score in score_by_move.items()
+       } 
        return {
            "candidate": best_movesxy,
            "ratio_by_move": ratio_by_move,
-           "playout num": retval["count"],
+           "playout num": playout_num,
            "score_by_move": score_by_move,
+           "score_by_movexy": score_by_movexy
        }
    else:
        return choice(best_moves) 

上記の修正後に下記のプログラムでゲーム開始時の局面に対する処理を ai_pmc で行うと、実行結果から修正前と同様の手順で計算が行われ、(1, 1) が最善手として計算されることが確認できました。

mb = Marubatsu()

ai_pmc(mb, pnum=10000, analyze=True, debug=True)

実行結果

==================================================
move (0, 0)
ratio      win: 0.601 draw 0.128
best ratio win: -1.000 draw 0.000
UPDATE
  best score (0.6006, 0.1275)
  best moves [(0, 0)]
==================================================
move (0, 1)
ratio      win: 0.531 draw 0.132
best ratio win: 0.601 draw 0.128
==================================================
move (0, 2)
ratio      win: 0.603 draw 0.128
best ratio win: 0.601 draw 0.128
UPDATE
  best score (0.6034, 0.1281)
  best moves [(0, 2)]
==================================================
move (1, 0)
ratio      win: 0.542 draw 0.126
best ratio win: 0.603 draw 0.128
==================================================
move (1, 1)
ratio      win: 0.697 draw 0.112
best ratio win: 0.603 draw 0.128
UPDATE
  best score (0.6972, 0.1121)
  best moves [(1, 1)]
==================================================
move (1, 2)
ratio      win: 0.536 draw 0.136
best ratio win: 0.697 draw 0.112
==================================================
move (2, 0)
ratio      win: 0.604 draw 0.130
best ratio win: 0.697 draw 0.112
==================================================
move (2, 1)
ratio      win: 0.534 draw 0.130
best ratio win: 0.697 draw 0.112
==================================================
move (2, 2)
ratio      win: 0.606 draw 0.128
best ratio win: 0.697 draw 0.112

{'candidate': [(1, 1)],
 'ratio_by_move': {(0, 0): (0.6006, 0.1275),
  (0, 1): (0.5311, 0.1318),
  (0, 2): (0.6034, 0.1281),
  (1, 0): (0.5417, 0.1259),
  (1, 1): (0.6972, 0.1121),
  (1, 2): (0.536, 0.1357),
  (2, 0): (0.6038, 0.1295),
  (2, 1): (0.5337, 0.1296),
  (2, 2): (0.6057, 0.1277)},
 'playout num': 10000,
 'score_by_move': {1: 0.601,
  2: 0.531,
  4: 0.603,
  8: 0.542,
  16: 0.697,
  32: 0.536,
  64: 0.604,
  128: 0.534,
  256: 0.606},
 'score_by_movexy': {(0, 0): 0.601,
  (0, 1): 0.531,
  (0, 2): 0.603,
  (1, 0): 0.542,
  (1, 1): 0.697,
  (1, 2): 0.536,
  (2, 0): 0.604,
  (2, 1): 0.534,
  (2, 2): 0.606}}

修正前の ai_pmc では返り値の "playout num" のキーの値は行ったプレイアウトの総数を表していましたが、修正後の ai_pmc ではそれぞれの合法手を着手した局面に対して行ったプレイアウトの回数を表すように変更された点に注意して下さい。

上記の場合は、ゲーム開始時の合法手の数は 9 なのでプレイアウトは合計 10000 × 9 = 9 万回行っています。

下記は以前の記事で計算したそれぞれの局面のプレイアウトの結果の理論値と上記の実行結果の ratio_by_move をまとめた表で ai_pmc の結果とほぼ同じであることが確認できます

局面	〇 の勝率/引き分け率	ai_pmc の〇勝率/の引き分け率
o..　..o　...　... ...　...　...　... ...　...　o..　..o	0.607/0.127	0.600/0.128 0.604/0.130 0.603/0.128 0.606/0.128
...　.o.　...　... o..　...　..o　... ...　...　...　.o.	0.536/0.129	0.531/0.132 0.542/0.126 0.536/0.136 0.534/0.130
... .o. ...	0.693/0.114	0.697/0.112

下記は ai2s と ai14s との対戦を行うプログラムです。修正前と修正後の ai_pmc では仮引数 pnum の意味が変化したので、以前の記事の修正前の ai_pmc との対戦結果と比較できるように仮引数の意味が変わらない timelimit で制限時間を 0.1 秒として対戦を行いました。

from ai import ai_match, ai2s, ai14s

ai_match(ai=[ai_pmc, ai2s], params=[{"pnum": 100000000, "timelimit": 0.1}, {}], match_num=1000)
ai_match(ai=[ai_pmc, ai14s], params=[{"pnum": 100000000, "timelimit": 0.1}, {}], match_num=1000)

実行結果

ai_pmc VS ai2s
100%|██████████| 1000/1000 [10:43<00:00,  1.55it/s]
count     win    lose    draw
o         989       0      11
x         895      88      17
total    1884      88      28

ratio     win    lose    draw
o       98.9%    0.0%    1.1%
x       89.5%    8.8%    1.7%
total   94.2%    4.4%    1.4%

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

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

下記は上記の実行結果と以前の記事で制限時間を同じ 0.1 秒とした場合の結果をまとめた表で、修正前と修正後でほぼ同じ対戦成績になったことが確認できます。

対戦	先手の成績	後手の成績	通算成績
修正前の ai_pmc VS ai2s	98.9/ 0.0/ 1.1	90.6/ 7.5/ 1.9	94.8/ 3.8/ 1.5
修正後の ai_pmc VS ai2s	98.9/ 0.0/ 1.1	89.5/ 8.8/ 1.7	94.2/ 4.4/ 1.4
修正前の ai_pmc VS ai14s	0.0/ 0.2/ 99.8	0.0/100.0/ 0.0	0.0/50.1/49.9
修正後の ai_pmc VS ai14s	0.0/ 0.0/100.0	0.0/100.0/ 0.0	50.0/ 50.0/ 0.0

上記から、修正した ai_pmc が正しい処理を行うことが確認できました。

ai_pmc2 の修正

ai_pmc2 に対しても同様に下記のプログラムのように修正します。なお、大幅な修正を行うため修正箇所は省略します。

• 8 行目：合法手ごとのプレイアウトの評価値を記録する変数を float 型の 0 をデフォルト値とする defaultdict で初期化する
• 11 ~ 20 行目：ai_pmc と同じ方法で指定した回数または制限時間になるまでプレイアウトを行う
• 16 ~ 19 行目：プレイアウトの評価値は、局面の手番のプレイヤーが勝利した場合を 1、引き分けの場合を 0.5 とした場合の合計をプレイアウトの回数で割った値（平均値）なので、それぞれの合法手を着手した場合の値の合計を計算する
• 21、22 行目：上記で計算した合計をプレイアウトを行った回数で割ることでプレイアウトの評価値を計算する。なお、playout_num が 0 になる可能性があるため、組み込み関数 max で除算する数の最小値を 1 とする必要がある点に注意すること
• 26 行目：プレイアウトの評価値の最大値を記録する変数を 0 で初期化する
• 27 ~ 44 行目：score_by_move の中で最も高い評価値の合法手を計算するように修正した

 1  from collections import defaultdict
 2  
 3  def ai_pmc2(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
元と同じなので省略
 4      if timelimit is not None:   
 5          starttime = perf_counter()
 6          timelimit_pc = starttime + timelimit
 7      legal_moves = mb.calc_legal_moves()
 8      score_by_move = defaultdict(float)
 9  
10      playout_num = 0
11      for _ in range(pnum):
12          if timelimit is not None and perf_counter() > timelimit_pc:
13              break
14          for move in legal_moves:
15              status = mb.playout(move)
16              if status == mb.turn:
17                  score_by_move[move] += 1
18              elif status == mb.DRAW:
19                  score_by_move[move] += 0.5
20          playout_num += 1
21      for move in legal_moves:
22          score_by_move[move] /= max(1, playout_num)
23  
24      best_moves = []
25      best_movesxy = []
26      best_score = 0
27      for move, score in score_by_move.items():
28          movexy = mb.board.move_to_xy(move)
29          dprint(debug, "=" * 50)
30          dprint(debug, f"move {movexy}")
31          dprint(debug, f"score:      {score:.3f}")
32          dprint(debug, f"best score: {best_score:.3f}")
33          if score > best_score:
34              best_score = score
35              best_moves = [move]
36              best_movesxy = [movexy]
37              dprint(debug, "UPDATE")
38              dprint(debug, f"  best score {best_score}")
39              dprint(debug, f"  best moves {best_movesxy}")
40          elif score == best_score:
41              best_moves.append(move)
42              best_movesxy.append(movexy)
43              dprint(debug, "APPEND")
44              dprint(debug, f"  best moves {best_movesxy}")
45      if analyze:
46          score_by_movexy = {
47              mb.board.move_to_xy(move): score 
48              for move, score in score_by_move.items()
49          }
50          return {
51              "candidate": best_movesxy,
52              "playout num": playout_num,
53              "score_by_move": score_by_movexy
54          }
55      else:
56          return choice(best_moves) 

行番号のないプログラム

from collections import defaultdict

def ai_pmc2(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
    if mb.move_count == 8:
        best_move = mb.calc_legal_moves()[0]
        if analyze:
            return {
                "candidate": [mb.board.move_to_xy(best_move)],
                "ratio_by_move": {},
                "playout num": 0,
                "score_by_move": {best_move: 1},                
            }
        else:
            return best_move
    
    if timelimit is not None:   
        starttime = perf_counter()
        timelimit_pc = starttime + timelimit
    legal_moves = mb.calc_legal_moves()
    score_by_move = defaultdict(float)

    playout_num = 0
    for _ in range(pnum):
        if timelimit is not None and perf_counter() > timelimit_pc:
            break
        for move in legal_moves:
            status = mb.playout(move)
            if status == mb.turn:
                score_by_move[move] += 1
            elif status == mb.DRAW:
                score_by_move[move] += 0.5
        playout_num += 1
    for move in legal_moves:
        score_by_move[move] /= max(1, playout_num)

    best_moves = []
    best_movesxy = []
    best_score = 0
    for move, score in score_by_move.items():
        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_movexy = {
            mb.board.move_to_xy(move): score 
            for move, score in score_by_move.items()
        }
        return {
            "candidate": best_movesxy,
            "playout num": playout_num,
            "score_by_move": score_by_movexy
        }
    else:
        return choice(best_moves) 

上記の修正後に下記のプログラムでゲーム開始時の局面に対する処理を ai_pmc2 で行うと、実行結果から修正前と同様の手順で計算が行われ、(1, 1) が最善手として計算されることが確認できました。

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

実行結果

==================================================
move (0, 0)
score:      0.667
best score: 0.000
UPDATE
  best score 0.6668
  best moves [(0, 0)]
==================================================
move (0, 1)
score:      0.603
best score: 0.667
==================================================
move (0, 2)
score:      0.683
best score: 0.667
UPDATE
  best score 0.68345
  best moves [(0, 2)]
==================================================
move (1, 0)
score:      0.599
best score: 0.683
==================================================
move (1, 1)
score:      0.747
best score: 0.683
UPDATE
  best score 0.74665
  best moves [(1, 1)]
==================================================
move (2, 1)
score:      0.600
best score: 0.747
==================================================
move (1, 2)
score:      0.600
best score: 0.747
==================================================
move (2, 0)
score:      0.673
best score: 0.747
==================================================
move (2, 2)
score:      0.670
best score: 0.747

{'candidate': [(1, 1)],
 'playout num': 10000,
 'score_by_move': {(0, 0): 0.6668,
  (0, 1): 0.603,
  (0, 2): 0.68345,
  (1, 0): 0.59895,
  (1, 1): 0.74665,
  (2, 1): 0.5996,
  (1, 2): 0.59975,
  (2, 0): 0.67295,
  (2, 2): 0.67}}

下記は以前の記事で計算して Mbtree_GUI で表示した上記の合法手を着手した局面のプレイアウトの評価値の理論値と上記の実行結果をまとめた表で、ai_pmc2 が理論値とほぼ同じ値を計算することが確認できました。

合法手	ai_pmc2 が計算したプレイアウトの評価値	理論値
(0, 0)	0.667	0.671
(0, 1)	0.603	0.600
(0, 2)	0.683	0.671
(1, 0)	0.599	0.600
(1, 1)	0.747	0.750
(1, 2)	0.600	0.600
(2, 0)	0.673	0.671
(2, 1)	0.600	0.600
(2, 2)	0.670	0.671

下記は先ほどと同様に ai_pmc2 の制限時間を 0.1 秒として ai2s と ai14s との対戦を行うプログラムです。

ai_match(ai=[ai_pmc2, ai2s], params=[{"pnum": 100000000, "timelimit": 0.1}, {}], match_num=1000)
ai_match(ai=[ai_pmc2, ai14s], params=[{"pnum": 100000000, "timelimit": 0.1}, {}], match_num=1000)

実行結果

ai_pmc2 VS ai2s
100%|██████████| 1000/1000 [10:42<00:00,  1.56it/s]
count     win    lose    draw
o         987       0      13
x         888      42      70
total    1875      42      83

ratio     win    lose    draw
o       98.7%    0.0%    1.3%
x       88.8%    4.2%    7.0%
total   93.8%    2.1%    4.2%

ai_pmc2 VS ai14s
100%|██████████| 1000/1000 [12:32<00:00,  1.33it/s]
count     win    lose    draw
o           0       0    1000
x           0     497     503
total       0     497    1503

ratio     win    lose    draw
o        0.0%    0.0%  100.0%
x        0.0%   49.7%   50.3%
total    0.0%   24.9%   75.1%

下記は上記の実行結果と前回の記事で制限時間を 0.1 秒とした場合の結果をまとめた表で、修正前と修正後でほぼ同じ対戦成績になったことが確認できます。

対戦	先手の成績	後手の成績	通算成績
修正前の ai_pmc2 VS ai2s	99.1/ 0.0/ 0.9	90.3/ 3.9/ 5.8	94.7/ 1.9/ 3.4
修正後の ai_pmc2 VS ai2s	98.7/ 0.0/ 1.3	88.8/ 4.2/ 7.0	93.8/ 2.1/ 4.2
修正前の ai_pmc2 VS ai14s	0.0/ 0.0/100.0	0.0/51.6/48.4	0.0/25.8/74.2
修正後の ai_pmc2 VS ai14s	0.0/ 0.0/ 100.0	0.0/49.7/50.3	0.0/24.9/75.1

上記から、修正した ai_pmc2 が正しい処理を行うことが確認できました。

今回の記事のまとめ

今回の記事では強化学習としての原始モンテカルロ法の説明を行い、原始モンテカルロ法が行う探索と活用の妥当性と原始モンテカルロ法の問題点について説明しました。

また、プレイアウトを行うメソッドと原始モンテカルロ法で着手を選択する関数を修正しました。

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

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

次回の記事

近日公開予定です

1. 本記事（原始モンテカルロ法）の文脈では「1 回のエピソード（プレイアウト）＝ 1 回の探索」として説明していますが、一般的な強化学習においては、1 回のエピソード内で行われる「未知の行動を試すステップ」のことを探索と呼ぶ場合もあります ↩

2. ゲーム木の規模が大きい場合などでは計算時間が長すぎて実質的に計算を行うことができない場合があります ↩

3. 当然ですが pnum が 0 以下の場合や、timelimit が 0 以下の場合は除きます ↩