様々な実力を持つゲームプレイヤのモデル化

著者 飯田 弘之

雑誌名 静岡大学情報学研究

巻 2

ページ 1‑24

発行年 1997‑03‑31

出版者 静岡大学情報学部

URL http://doi.org/10.14945/00008607

様 々な実力 を持つゲ ーム プ レイヤのモデル化

How to lⅥodel Game Players with Various Strength

飯 田 弘 之

Hiroyuki HDA

ゲームをプレイす る計算機 プログラムは一般 にゲーム木探索理論 に基づいている. ミニマ ックス あるいはその改良版 としての イ アルゴ リズムは,実際のゲームプレイングシステム に とって現在 で も主流である。 この ように,ゲーム木探索の分野 における従来の研究 は,主として ミニマ ックス 戦略の枠組 の中で とりわけ探索の効率化 に焦点が当て られて きた.これ まで提案 された様々な効率 化アルゴ リズムのふ るまいを実験的 に調べ るために,い くつかのゲーム木モデルが提案 されて きた^.

これ ら従来のゲーム木モデルのほ とん どは,利害が完全 に相反す る二人のプレイヤのモデル を含 ん でいる.

本稿で は従来 と異なるゲーム木モデル,すなわち,あるプレイヤに対 して,それ とは恒等的には 等 し くない他のプレイヤのモデル を含 むゲーム木モデルについて議論す る.また,近年注 目を浴び るようになった相手モデル探索の ような ミニマ ックスの枠組 みを超 えた戦略 によるふ るまいをこの ゲーム木モデルを用いた実験 によって考察す る.さ らに,そのゲーム木モデルをペアプレイにおけ るペアプレイヤのモデル化への応用 について述べ る。本稿で示すそれぞれの実験的ふるまいはわれ われの直観的理解 と合致 してお り,こ こで述べ るゲーム木モデルが様々な実力 を持つゲームプレイ ヤを適切 にモデル化 していることを示す ものである^.

1  は じめに

チ ェスや碁・ 将棋 な どの二人完全情報零和ゲームを対象 としたプログラ ミングは,一般 にゲーム 木探索理論 ([12][29]参照)に基づいている。従来のゲーム木探索理論の主流 は ミニマ ックス理論 [24]の考 え方であつた. ミニマ ッタスあるいはその改良版 としての ィ アルゴ リズム^[20]は,実際 のゲームプレイ ングシステム[21][27][38]に とって現在 で もなお有力かつ強力 なアプローチで あ る.そのため,ゲーム木探索の分野 における従来の研究 は主 として, ミニマ ックスの枠組の中でそ の結果 を保証す る範囲内で行 なわれ る探索の効率化 ^(すなわち高速化)に焦点が当て られて きた^.

一方,人間プレイヤの思考法・戦略の分析^([5]参照)は これ までゲームプログラ ミング^(特にチェ ス)に少 なか らず影響 を与 えてはきたが,その結果 は ミニマ ックスの枠組 みを超 える理論 を生み出 すには至 らなかった。 ところが,近年 のゲームエキスパー トの思考法分析[6][33][32][37]を 通 し て,従来 の ミニマ ックスを超 えた枠組 みの戦略[16]がエキスパー トによって用い られていること,

しか もそれ らがプロの トップレベルの試合 では非常 に重要な役割 を果た していること^[28][34]が明 らか にな り,そのような戦略の定式化[7]が提案 され るようになった.これ らの枠組み(相手モデル 探索 と呼 ばれ る)では,相手 プレイヤに対 して 自分 とは恒等的 には等 し くないモデル^([3][15]参照)

要 概

を仮定する.

従来の ミニマ ックスに基づいたその効率化の研究では,数多 く提案 された様々な効率化 アルゴ リ ズム([18][36]参照)に よる実験的ふ るまいを調べ るために,いくつかのゲーム木モデル([22][23]

参照)が提案 されて きた。基本的には,ゲーム木の (葉)ノー ドに対 してランダムにスコアを割 り 当てる方法で これ らのゲーム木モデルが構築 される.これ ら従来のゲーム木モデルは,ミ^{ニマ ック} スに基づいているため,利害が完全 に相反す る,つま り零和の関係 にある二人のプレイヤのモデル だけが考慮 された。 そのため,これ まで提案 されて きたゲーム木モデルでは,相手モデル探索な ど のふ るまいに関する実験がで きないので,新たなゲーム木モデルが必要になった.

本稿 は,上述 した背景 に基づいて新 しく提案 された,自分 とは恒等的には等 し くない相手 プレイ ヤのモデル を含むゲーム木モデルについて議論する。また,そ のゲーム木モデルの応用 として,様々 な実力 を持つゲームプレイヤのモデル化 について述べる.第2節で は,自分 とは恒等的には等 しく ない相手プレイヤのモデル を含むゲーム木モデルの基本的な概念 について,その構築法 とともに述 べ る.第^3節では,相手モデル探索のアルゴ リズム とその実験的ふ るまいを第2節で詳述す るゲー ム木モデル を用いて考察する.第^4節では,相手 プレイヤのモデル を予測 して行 なう相手モデル探 索の実験的ふ るまいを考察するために,ゲーム木モデルをさらに拡張する.第5節では,ゲ^ームプ

レイングにおける教授戦略のアルゴ リズム とその実験的ふるまいを同様 に考察する.第^6節では,

ペアプレイにおける協調戦略のアルゴ リズム とその実験的ふるまいを考察するために,ペアプレイ におけるペアプレイヤのモデル を含むゲーム木モデルを提案する.最後 に,今後 の研究課題 につい て述べ る.

2 様 々な実力を持つプ レイヤのモデルを含むゲーム木モデル

従来のゲーム木モデルの構築法 は,ランダムゲーム木 (多くの場合,分岐因数 と探索本の深 さを 一定 とす る均質な木)の各葉 ノー ドにランダムスコアを割 り当てる ([22][23]参照)のが一般的で ある。ただ し,その割 り当て方法のバ リエーションはい くつ もある. ミニマ ックスの枠組 みでの議 論であれば,他のプンイヤのモデルは,葉ノー ドに割 り当てたスコアの符号 を変 えたスコアによっ て表現で きる.これはプレイヤ同士の利得 に関す る零和性 に基づいている。 ところが,次節で述べ るように,一方のプレイヤ とは恒等的には等 しくない他方のプレイヤのモデル を考 える必要がある 場合 には,従来のゲーム木モデルでは正 しく状況 をモデル化で きない.そこで,相手モデル を含む ゲーム木モデルが提案[12]された。

最初 にわれわれは ミニマ ックス と相手モデル探索の直観的相違 を説明 し,次に相手モデル を含む ゲーム木モデルの構築法,そのゲーム木モデルを用いた場合の評価基準,そ^して,そのゲーム木モ デルの性質について述べる.

2.1  なぜ ミニマ ックスではいけないのか ?

3つ先 に並べた方が勝 ち とい うゲーム・三 日並べ (TicTacTOe)で具体例[10]を示 そ う.よ く知 られていることだが,このゲームはお互 いが (負けまい として)最善 を尽 くす と引 き分 けになる.

別の視点か らす ると,ある程度 このゲームに精通 したプレイヤは,いかなる相手 に対 して も常 に ミ ニマ ックス方式でプレイすると仮定すれば勝つ可能性 をまった く見い出せない,こ とになる.これ は相手が 自分の視点で常 に最強のプレイをして くると想定 しているか らである.

ところが現実的には,三日並べ をよ く知 らない,いわゅる初心者 と対戦す るな らば,勝つ可能性 は十分 にある,こ とは直観的に理解で きる.初心者 という漠然 とした表現 をよリー般化 して考 えて みる.つまり,一方が他方の戦略 (プレイの方式)を知 っている場合 にゲームの結果 はどう変わ る

様々な実力を持つゲームプレイヤのモデル化

だろうか.いま相手が,

1.3つ並べ ることがで きればそ うせ よ

2.相手が3つ並ぶのを妨害せ よ

3.真ん中に打て

4.隅に打て

の4つの方針 (1,2はルール,3,4は経験則)から成 る戦略 にしたがってプレイす ると仮定す る^. まず自分が指 し手1,すると相手 は指 し手 2と 真 ん中に来 る.そ^こで,指し手 3と すると相手 は 指 し手 4と 隅へ来 る.これ は先の4つの方針 に忠実 にしたがったプレイである.そ^こで,指し手5 で先手の勝 ち となる (図 1参_照).

この三 日並べの例か らわれわれは何 を学ぶ ことがで きるだろうか.この例か らわれわれが主張 し たいのは,相手 プレイヤのモデル を自分 と恒等的 には等 し くない と仮定す ることが,現実的 には非 常 に理 にかなっている,とい うことである.つまり,自分 と恒等的には等 し くない相手 プレイヤの モデル を考慮す る相手モデル探索 (第3節_で詳述)は, ミニマ ックス と比べて より現実的でかつ有 効 なのである^.

2.2  ゲーム木モデルの構築法

一方のプレイヤ とは恒等的に等 し くない他のプレイヤのモデル を含むゲーム木モデルは,相手モ デルを含むゲーム木モデル[12]と して提案 された.こ こではその考 え方にしたがって,相手モデル

を含むゲーム木モデルの構築法 について述べ る^.

まず最初 に,このゲーム木モデル は均質木である。各葉 ノー ドには2種_{類 のスコア}[13]を割 り当 てる.慣習 にしたがって,ゲームに参加す る2人のプレイヤをマックスプ レイヤ とマイナスプ レイ ヤ として区別す るな らば,二つのスコアの一方 は,マックスプレイヤ用であ り,他方はマイナスプ レイヤ用である.そして,それぞれ葉 ノー ドのスコアを繰 り上 げて(その繰 り上 げ方は戦略 に依存),

与 えられた局面での最適手 を決定す る.た^{だ し},各葉 ノー ドのスコアは,探索木 においてルー トか らその葉 ノー ドまでのパスの上 にある各 ノー ドに対 して割 り当てるランダム数の総和で求 める.ラ

ンダム数の和 をとることによって,その値 は正規化 され完全 なランダム性 は失われ る.し^{か し},葉

ノー ドに対 してのみランダムスコアを割 り当てる従来の手法 と比較 して,「良い手 を指 した後 に生 じる局面群 は相対的に良い評価値 を得 る」 とい うゲームの現実性 をより正確 に反映 している,とわ れわれは認識 している.

このようにして,探索木 の (深さ グ とせ よ)ある葉 ノー ド(Pdとせ よ)に対 す るマ ックスプレイ ヤのス コアを式(1)に よって計算す る^.

ELaκ(Pつ =二^R(Pり,

ただ し,R(Pk)はルー トか らその葉 ノー ドまでのパス上 のノー ドPkに対 して割 り当てるマ ックス プレイヤ用のランダム数である.

指し手⁴ ムの一例 図1

指 し手2 指 し手⁵

次 に,マイナス プ レイヤのス コア (ELinとせ よ)は式(2)に よって計算 す る.

EL′π(Pつ =γ ^×ELαχ(Pつ +(1‑γ_)×

鳳 ″(Pり,

ここで_,″(Pk)は ルー トか らその葉 ノー ドまでのパス上のノー ドPkに対す るマイナスプレイヤ用の ランダム数であ り,変数 γは区間[0,1]内^1の実数 を表す。

このゲーム木モデルは,実力が恒等的には等 しくない両者 (マックスプレイヤ とマイナスプレイ ヤ)のモデル を反映 している.変数 γの値 を0から 1ま で変化 させ ることによって,実力 の異なる 様々な相手 プンイヤのモデル を模倣で きることに大 きな特徴がある。つ まり,γ=1の場合,マイナ スプレイヤはマ ックスプレイヤ とまった く同 じ実力 に相当 し,γ=0の場合,マイナスプ レイヤは マ ックスプレイヤか らみてまった くランダムにプレイする^2.

2.3  ゲーム木モデルを用いた場合の評価基準

ふ るまいの評価基準 として 〃 値 と呼ばれる値 を用いる.こ れは式(3)に よって計算 され,与えられ たゲーム木モデルに対 して正規化 された値である.

″0=      o

んin(P)とんax(P)は,マ ックスプレイヤの視点での,ル ー トノードPに対するゲーム木内の最小^, 最大の値を表す.7(P)と して,実験の対象となる戦略による値が用いられる.

1区間 を[‑1,1]と 拡張 して も本稿での議論の整合性 は保たれるが これ までの実験 は主 として区間 [0,1]

と限定 して行 った。

2バッグギャモンに代表 される不完全情報ゲーム (不確実性ゲーム とも呼ばれる)ではランダムにプレイ す ることがある程度有力な戦略になるので注意 を要する。

様々な実力を持つゲームプレイヤのモデル化

2.4  ゲーム木モデルの性質

式(2)に よってモデル化 されたマイナスプレイヤの実力 とは,現実的にはマ ックスプレイヤ とマイ ナスプレイヤの選択 の相違 (相手モデル探索では この相違 をミス と呼ぶ)である.まず最初 に,ミ スの頻度 とプレイヤの実力 との関係 について考察す る.次に,式(3)に よって計算 され る ″ 値 の理論 的解析 を示す^.

100 90 80 70 60 θ50 40 30 20 10 0

図2 マックスプレイヤとマイナスプレイヤの選択の相違の上ヒ率 ただし,探索木の深さを^6,̀分岐因数を10とした。θは相違の比率を表す.

ミスの頻度 とプ レイヤの実力

上述 したゲーム木モデルで,マイナスノー ド (マイナスプレイヤの手番)におけるマ ックスプン イヤ とマイナスプレイヤの最適手選択の相違が,γの変化 に対 して どの くらいの頻度で生 じるか を 調べた (図2参照).

ここで,マイナスノー ドで生 じるマ ックスプレイヤ とマイナスプレイヤの選択の相違 を^Attmとお き,端^inをゲーム木内の葉 ノー ドでない全マイナスノー ドの個数 とす る.この とき,相違 の比率(θ

とせ よ)を γの関数 として^, θ=Aらπ/馬

̀″

×100.

によって求めた.実際 はマ ックスプレイヤ とマイナスプレイヤの選択の相違 に関す る他の実験^[12]

も行 なった.これ らの実験か ら,相違 の比率 θは探索木の深 さには依存 しないが,探索本の分岐因 数が増 えるにつれて大 き くなることがわかっている^.

Hの値 に関する理論的考察 (γ=0の^場合)

本節で述べ るゲーム木モデル を用いた場合の, ミニマ ックスによる理論値 に関 して考察す る。一 般的な場合 について議論す ることは難 しいので,こ こでは γ=0の場合 に限定す る.ゲーム木モデル は均質木であると仮定 したので,こ こで探索木の深 さを グ とお く.便宜上,評価関数の値 (葉ノー

ドに割 り当て られたスコア)を区間 [‑1,1]上のスケール として考 える.

ミニマ ックスの根本原理[24]によれば,マ^'ックスノー ドでマ ックスプンイヤは最大の値 を とる指 し手 を選択 し,マイナスノー ドでマイナスプレイヤは (マックスプレイヤの視点で)最小 の値 とな る指 し手 を選択す るもの と仮定す る.それゆえ,γ=0のときの ミニマ ックスによる理論値(1‰mと せ よ)は式(4)で表 され る。

0 0。10。20.30.40.50。60。 70。80.9 1

乙π2(P)= 彫_%]一L%」

ゆえに, ミニマックスによる理論的なH値は,式(51によって得 られる.

〃0=   ×ЮQ        働

ここで,偶数dに対 しては,明らかに ‰m(P)=0であるから,H(P)=50と なる.一方,奇数 グ に対する理論的な ″ 値は式(6)に よって与えられる^.

〃(P)= (午 _一年 )/″+1

×100=ユ +50。

式(6)は,探索木の深 さが+∞までゆ くとき,ミ ニマ ックスによる ″ 値 は50に収束す ることを示 し ている.実際,図 3(探索木の深 さ7)で_γ=0のときの ″ 値 は57と58の間の数でほぼ理論値 になっ ている.

3 _{相手モデル探索}

本節では,まず最初 に相手モデル探索 (OM―search)の_{定式化 を示す}.次に,ゲーム木モデルを 用いた実験 によって,相手モデル探索のふ るまいを考察する.さ らに,相手モデル探索 に対する効 率化 を示 し,同様 に,ゲーム木モデル を用いた実験 の結果 を示す.

3.1  相手モデル探索の定式化

Pはノー ドを表 し,PゴはPの任意の子 ノー ドを表す もの とする./をすべての局面 に対 して定義 された関数 として,マックスプレイヤによる評価関数 とす る.便宜上,マイナスプレイヤは常 に何 らかの ミニマ ックス法 を用いる^3と仮定する。この とき,ミ ニマ ックスのアルゴ リズムは次の式(7)に

よって表 される[8][9].

川^=1紳):37ゴ

    0

ただ し,葉ノー ドに対 して定義 されたEVrlP)は ,マックスプレイヤの評価関数 によってノー ドP

に対 して静的に評価 された値 を表す.

同様 な方法で,相手 モデル探索のアルゴ リズムは式(8)と (9)によって表 され る.ここで,Fと′はす べての局面 に対 して定義 された評価関数で,Fはマ ックスプレイヤ用,′はマイナスプレイヤ用であ る。相手モデル探索では,ゲーム木内の任意のノー ドに対 して,マックスプレイヤの評価関数 によ る値 とマイナスプレイヤの評価関数 による値 を計算する.

3これは定式化 を容易にするための便宜上の仮定である。実際は、任意の局面でのマイナスプレイヤによ る選択 をマ ックスプレイヤが理解 していれば十分である。

)

F(P)=

様々な実力を持つゲームプレイヤのモデル化

P:マックス ノー ド ノwhere P:マイナスノー ド min g(鳥)

P:葉ノー ド

P:マックスノー ド

P:マイナスノー ド

P:葉ノー ド σ(P)=

ここで,E7g(P)は E7f(P)と 同様 で,マ イナスプレイヤの評価関数 によって静的 に評価 された値 を表す.

相手 モデル探索の特徴 は,式(8)のマイナスノー ドでの評価値の繰 り上が り方 にある.

ミニマ ックスでは,相手が常 に自分の観点か ら最適 な手 を選択す る (つま り,相手 プレイヤは自分 と同 じ実力)と仮定 しているが,相手モデル探索では,相手の視点での最適 な手 によって導かれ る 局面 に対 す る自分の視点での評価値 を繰 り上 げる.し^たがって,相手 と自分が同 じ観点でプレイす

る場合 (E7f=E7gに相 当),相手モデル探索 は ミニマ ックス と等価 な戦略 となる^.

3.2  相手モデル探索の実験的^.ζ、るまい

図 3に,相手モデルを含むゲーム木モデル^4を用いて,γ を0から1まで0.1ずつ変化させた とき の相手モデル探索 とミニマックスによる″ 値を示す.図3の 結果は,探索木の深さ7,分岐因数10 に対 して得 られた.図^3からわれわれは次のような知見を得た^.

100 90 80 70 60 ff 50 40 30 20 10 0

0  0.1 0。 2 0.3 0。4 0。5 0.6 0。7 0。8 0.9 γ

図3 相手 モデル検索 とミニマ ックスの。も、る まい 探索木の深 さを7,分岐因数 を10に固定.

4本稿で示すゲーム木モデル に関す る各実験では、ルー トノー ドに異 なる乱数の種 を与 え、実験 を百回 行 ってその平均 を求めた。

ｚ¨蟻印﹇

ｍ  Ｆ     Ｅ

助 助 σ Ｊ ぱ

ｍ．ｕ２島．．２ａｘ ⁰⁾

相手モデル探索 ミニマ ックス

●ミニマ ックスによる 〃 値 は相手の ミス (γの値)に関係 な く,常に一定である.

●相手モデル探索 は γの値が0に近づ くほ どミニマ ックスに比 べてH値_{が大 き くなる.相手の}

実力が弱いほ ど,相手モデル探索 によって得 られ る成果が大 きい ことに相当する.

●相手モデル探索は γの値が1に近づ くほ どミニマ ックスによる ″ 値 との差がな くなる.相手 の実力が相対的に強 くなるにつれて,相手モデル探索 によって得 られる成果 は小 さい ことに相 当す る。

3.3  相手モデル探索の効率化

探索効率化の手法 として,β枝刈 りとルー ト値枝刈 り[7][12]がある.β枝刈 りは相手モデル探索 の結果 を完全 に保証す る (証明 は[7]参照).一方,ルー ト値枝刈 りは相手モデル探索の結果 を完全 に保証 しないが,最悪の場合で もミニマ ックスによる値 を保証する (証明は[7]参照).探索効率化 の評価基準 となるゲーム木探索のコス トを,従来の一般的な考 え方同様,葉ノー ドに対す る静的評 価 の回数 によって検討す る.

β枝刈 りとは,ゲーム木内のマイナスノー ドPとその子 ノー ド鳥のそれぞれのマイナスプレイヤ 側の評価値が ′(P)≦ ′(鳥)(式(9)参照)を満たす時 に行われ る枝刈 りと,葉ノー ドがマ ックスノー ドの ときに,マイナスプレイヤの観点で評価値が最小 になるノー ドだけに対 してマ ックスプレイヤ の評価値 を計算するとい う2つの手続 きによって行われる枝刈 り手法である.こ の名前は,ミ ニマ ッ クスに対す る αβ アルゴ リズム[20]の β値枝刈 りにほぼ相 当す ることに由来 している.

最適 な場合 (探索木の各 ノー ドにおいて β枝刈 りに とって最 も好都合 な順序でノー ドを展開する 場合)のβ枝刈 りによる探索 コス ト(Cとせ よ)は次の漸化式で表 され る.

Cべ″,紗)=ω CF(d‑2,ω)十ω(紗‑1)Aみβ(グー3,ω)

ただ し,馬β(グ,")は αβアルゴ リズム[20]による最適 な場合の探索 コス トを表 し,

NaF(グ_,紗)=ω^呼1+ω L'̲1

である.式00は グ≧3に対して定義され,

Cべ1,")=2ω_,C(2,ω)=η (ω+1)

である.

一方,ルー ト値枝刈 りは,マックスプレイヤがあらか じめ ミニマ ックスによる探索 を行 い,ルー ト局面の評価値 (以下,7と^{せ よ})を得た と仮定す る.この時,相手モデル探索の探索中に現れる 任意のマ ックスノー ドPで,F(P)〉 7を_{満たす時 に,残りのノー ド(あるいは部分木)の探索 を省}

略する枝刈 りである.た^{だ し},この枝刈 りを実行す ると,マイナスプレイヤ側の評価値が不明確 と な り,その枝刈 りが起 こった上のノー ドで相手モデル探索による本来の繰 り上が りができな くなる.

それで も,「純粋戦略 よりは混合戦略」といった戦略の制御 とい う観点か ら,ルー ト値枝刈 りの仮定 は非常 に合理的かつ現実的であ り,さ らに,実時間内で着手 を決定するとい う制約条件下では有効 なヒュー リスティックである.ルー ト値枝刈 りの相手モデル探索 (図4参照)は最悪 の場合で もミ ニマ ックス法による値 を保証することも魅力的である.

前述 した ような意味で,ルー ト値枝刈 りの最適 な場合のコス トQは

lllll

ｎ〃 Ａｕ

G(グ,")=″ Cベグー3,")

様々 な実力 を持 つゲームプレイヤのモデル化

0  0,1 0。2 0。 3 0。4 0.5 0.6 0.7 0。8 0,9  1 γ

図4 ルー ト値枝刈 りの相手モデル探索の。^S、るまい 探索木の深さを7,分岐因数を10に 固定^.

と表 され,式(11)は グ≧4に対 して定義 され,

C(2,ω )=2", Ch(3,ω )=2ω²

で ある.

3.4  効率化 に関す る実験

前述 した2種類 の探 索効 率化 アル ゴ リズムの実験 的ふ るまい を考察 す るた めに,相手 モ デル を含 むゲーム木 モ デル を用 いて実験 を行 なった.こ^こで,実際 に静 的 に評価 した葉 ノー ドの数 (LEと せ よ)と 全葉 ノー ドの数 (Lとせ よ)を測 定 し,効率化 の割合 TLを式 (12)に よって計算 した.た^{だ し,}

TLの値 が小 さい ほ ど効 率化 は大 きい^.

FL=舟 ×100(%)       a21

β枝刈 りとルー ト値枝刈 りによる探索の効率化 と探索木の深 さお よび分岐因数 との関係 を調べ る 実験 を通 して,われわれは次のような知見 を得た。

1。 β枝刈 りの効率化 と探索木の深 さ

探索本の分岐因数 を6に固定 し,探索木の深 さを3から6ま で変化 させた β枝刈 りの効率化 と 探索木の深 さの関係 を図5に示す.図5には,γが0.0と 1.0の場合の結果 を示す.明らか に,探 索木の深 さが大 き くなるにしたがって効率化の割合 も大 き くなっている^.

2.β枝刈 りの効率化 と探索木の分岐因数

γが^{0̲0と1̲0の}それぞれの場合 に,探索木の深 さを6に固定 し,分岐因数 を2から6ま で変化 さ せた β枝刈 りの効率化 と探索木の分岐因数の関係 を図6に示す。分岐因数が大 き くなるにした がって効率化の割合 も大 き くなる^.

∬

５     ０ ５     ５

手モデル探索 リバージ ヨン

50 45 40 35

■、 30 25 20 15 103456

ゲーム木の深 さ

図5 β枝刈 りの効率化 と探索木の深 さ

各ノー ドでの分岐因数は6に 固定.■は効率化の割合を表す。

探索木の分岐数

図6 β枝刈 りの効率化と分岐因数 探索木の深さを6に固定.■は効率化の割合を表す.

β枝刈 りの効率化 と γ

図 5と 図6から,β枝刈 りによる効率化 は γの値 に依存 しない ことがわかる.これ は,β枝刈 りによる効率化 は相手の ミスの頻度 (つまり実力)に依存 しない ことに相当する.

０   ５   ０ ５   ０   ５   ０   ５

０   ５   ０ ６   ５   ５ ４   ４   ３   ３   ２   ２   １   １

■

γ=0。0‑

符 ^1。0‑

様々な実力を持つゲームプレイヤのモデル化

ルー ト値枝刈 りの効率化 と探索木の深 さ

γが^{0.0と 1.0の}それぞれの場合 に,探索木の分岐因数 を6に_{固定 し},

させたルー ト値枝刈 りの効率化 と探索木の深 さの関係 を図7に示す^. るにしたがって効率化の割合 も大 き くなる^.

深 さを3から6ま で変化 探索木の深 さが大 き くな

０

５   ０

５   ０   ５   ０   ５

０

５

０ ５   ４   ４   ３   ３   ２   ２   １

１

■

3456

探索木の分岐数

図7 ルー ト値枝刈 りの効率化 と探索木の深さ 探索木の分岐因数を^6に固定.■は効率化の割合を表す。

5。 ルー ト値枝刈 りの効率化 と探索本の分岐因数

γが^{0.0と 1.0の}それぞれの場合 に,探索本 の深 さを6に固定 し,分岐因数 を2から6ま で変化 させたルー ト値枝刈 りの効率化 と探索木の分岐因数の関係 を図8に示す。探索木の分岐因数が 大 き くなるにしたがつて効率化の割合 も大 き くなる^.

60 50 40

■  30 20

探索木の分岐数

図8 ルー ト値枝刈 りの効率化 と探索木の分岐因数 探索木の深さを6に 固定.TLは効率化の割合を表す。

6.ルー ト値枝刈 りの効率化 と γの値

図7から明 らか な よ うに,ルー ト値枝刈 りに よる効 率化 は γの値 が大 きいほ ど効率化 の割合 は 大 き くな る.す^{なわ ち},相手 の ミスが多 い ^(相手 が相対 的 に弱 い)ほ^ど,ルー ト値枝刈 りに よ

０     ０

:=::::=

る効率化 は大 き くなる.

4 相手ブ レイヤのモデルを予測 して行な う相手モデル探索

相手モデル探索では,相手プレイヤのモデルが完全 にわか ることを仮定 した.し^{か し},現実的に は完全 にわかるとい う状況 はまずあ り得ない.むしろ必要 に応 じて,相手 プレイヤの手 を予測 した 上で,相手モデル探索 を実行するや り方が合理的[6]である.こ のような相手モデル探索 を通常の場 合 と区別 して,予測相手モデル探索 (OM*―search)[14]と_呼ぶ.

4.1  予測相手モデル探索の定式化

前述 した ように,マイナスプレイヤの本当のスコアは式(2)に よって計算 され るが,マックスプン イヤが予測するマイナスプレイヤのスコア _(E7Minとせ よ)は式(13)に よって表 され る.

ELπ_(Pa)=δ ×E臨″(鳥)+(1‑の ^×3r(Pk),       aD

ここで δは γ同様,区間[0,1]内の実数 とす る.明らかに,γ =δ の とき,予測相手モデル探索 は相 手モデル探索 と等価 な戦略 になる^.

予測相手モデル探索 によって選択 される指 し手の評価値 は真の値ではない.つまり,相手 プレイ ヤのモデル を完全 に理解 して行 なう相手モデル探索 と比較 して誤差 (損失であるか ら,リスク と呼 ぶ)が生 じるはずである.予測相手 モデル探索 による真の値 を求 めるためのアル ゴ リズム は,式

(14),(15),(16)お よ09)によって表 され る.こ こで,F**,F*,力(P)は それぞれすべての局面 に対 して定義 された関数で, F**と F*はマ ックスプレイヤ用の評価関数であ り, バP)はマイナスプ レイヤ用の評価関数である。力(P)は相手 プンイヤのモデル をマ ックスプレイヤが予測 した ものであ り,そ の予測 したモデルに基づいて相手モデル探索を行なった場合の評価値 をF*は_{表 している.た} だ し,F*によって求 めた値 は真の値ではな く,真の値 はF**に_{よって得 られる}.

F**(P)=

F**(鳥_)withノ such that

F*(鳥)=maX F*(鳥)P:マ ックスノー ド F**(島_)withノ such that

σ_(鳥)=min g(鳥)  P:マ イナスノー ド

ELαχ(P)         P:葉 ノー ド

maxF*(P) P:マックス ノー ド

F*(P) F*(島_)withノ such that

λ_(島)=minヵ (鳥)P:マ イナスノー ド ^l151 ELαχ(P) P:葉ノー ド

maX力 _(鳥)P:マ ックス ノー ド

min力_(鳥)P:マ イナ ス ノー ド

EんJπ(P) P:葉 ^{ノー ド}

リハ 白 い

λ(P) = _l161

様々 な実力 を持 つゲームプレイヤのモデル化

4.2  予測相手モデル探索の実験的^.ζ、るまい

γと δの変化 ^(実験 では0.1ず つ変化 させた)に応 じた予測相手モデル探索 によるH値の集合 は,

二次元座標上の曲面 として表 され る(図9参照).なお,この実験 は探索木の深 さを4に_{固定 して行} なった.図^{9からわか るように},予測相手モデル探索 によるH値は,γ =δ=0(相手が実際 に非常 に弱 く,か^つ,そ^{の予測が正 しい)の}場合 に最大 とな り,γ=19δ=0(相手が実際 は非常 に強い が,非常 に弱 い と予測 した)の場合 に最小 となる^.

図9からわれわれは次の ような知見 を得た.

●予測相手モデル探索 は, ミニマ ックスによるH値より真 に大 きい場合 にゲインを得 る^. すなわち,予測 して (完全 に正 し くはない)でも相手モデル探索 を実行 して ミニマ ックスよ

り利得が期待で きる.

●予測相手モデル探索 は,ミ^{ニマ ックスによる}H値よ り真 に小 さい場合 に リスクを被 る.

このような場合,予測 して相手モデル探索 を実行するのは合理的でない^.

●マ ックスプレイヤがマイナスプレイヤの実力 を正確 に予測で きるな ら,予測相手モデル探索 は,相手モデル探索 と同 じ程度 にゲインを得 る^.

●マ ックスプレイヤがマイナスプレイヤの ことを過大評価 した場合 (δ>γ に相当),予測相手 モデル探索の実行 には リスクが伴わない.

●マ ックスプレイヤがマイナスプレイヤの ことを過小評価 した場合 ^(δ<γ かつおよそ γ≧^0.4 に相 当),予測相手モデル探索の実行 には リスクが伴 う^.

予測相手モデル探索 ―一

― フ ヽヽ′″ ア ー

H-value

V・υ

   l.O      V

図9 予測 相 手 モデル探索 とミニマ ックスのしヽ、る まい 探索の深 さ,分岐因数はそれぞれ4,10に固定. ８

  ７   ７   ６   ６   ５   ５   ４   ４

ミニ マ ックス

5 ゲームにおける教授戦略 としての^TU―Search

ゲームを題材 とした教授戦略に関 して,Burtonの研究[1]が知 られている。Burtonは_{ゲームプレ} イングでの コーチに要求 される12の原則[2]を提案 し,それ を計算機上で実現 しようと試みた.12の 原則の特徴 は,学習者の誤 りに応 じてゲームを中断 し,良い候補手 を教 え,やり直 し ( 待 った^") のチャンスを与 え,そして,コーチである計算機 は常 に最適プレイをする,などである.

一方,TU―search[11][13]と 呼 ばれ る教授戦略 は,学習者 に悟 られないように負 けるか,あるい は学習者 にで きるだけ勝つ可能性 を高めるようにプレイするための戦略である[33].

TU―searchは Burtonらが提案 した12の原則 と以下の点で大 き く異なる^.

●学習者 にや り直 しを許すためにゲームを中断するのは好 ましくない.特に,将棋や碁 な どの伝 統的なゲームでは礼儀 に反す る。   ^・

●コーチが常に勝 とうとして最適プレイすることは必ず しも妥当ではない.むしろ,必要 に応 じ て,学習者 に悟 られないように負 けるか,あるいは勝 つチャンスを与 えるべ きである.

●た とえ偶然であって も,好手や絶妙手 を助言なしで発見 し,しか も勝利 を得 るな らば,学習者 はゲームヘの関心 をさらに高める.

また,故意 に弱い (悪い)手をプレイすることを目的 とした場合,探索の先読 みの深 さを小 さ く す ることで柔軟 に対処で きる[25][26]ように思 える.ところが,相手モデル探索の概念か ら明 らか なように,自分の視点で弱い手 をやったつ もりで も,相手がそれ を咎め られない場合 は,その弱い 手がかえって良い手 になって しまうことは注意 を要す る.さ らに,ここで述べ る TU―searchは,相 手の相対的な実力 に適合 して,故意 に弱い手 をプレイ しようとするが,相手の実力 に関係 な く,常

に一定 して弱 くプレイす るための負 け指向の戦略 もある[12].

以下,TU―^searchの基本概念 とその定式化,そして,先に述べたゲーム木モデルによる実験的ふ るまいを示す.

5.l TU―searchの基本概念 とその定式化

TU―searchが実行 され るい くつかの状況 ごとに,戦略の内容 を分類す る.いま,与え られた局面 (Pとせ よ)でマ ックスプレイヤが TU― searchを 用いるとしよう.図^10は局面Pに_{対す る深 さ}2 の探索木 を表 している.図中の現在局面Pで,故意の ミスが2通り(P→^P2と P→P3)あること に注意 されたい.こ^こで,故意の ミス とは,相手モデルがわかっている状況で ミニマ ックスの結果 より劣 る指 し手 を選択することである。故意の ミスによる評価値 とミニマックスによる値の差 は損 失限界値 (loss limit)と呼 ばれ る.以下,損失限界値 (ε とせ よ)の範囲に応 じて,TU―^searchを

行 な う状況 として次の3つ_{の場合 に分類す る}.

1。 もし ε<3ならば,マックスプレイヤはTULsearChに _よって,故意 の ミスを選択 しない.な ぜな ら,マイナスプレイヤ (学習者)がそれに気がつ くか らである.

様々な実力を持つゲームプレイヤのモデル化

I=v?2,/*1."

C=4f2,/-1."

図10 TU―Searchに よる探索の例。

ノー ドの上の数字はTU―^Searchによって繰 り上げられる値を表す。同様に,ノ ードの横の数字は 相手モデル探索による値で,上がマックスプレイヤ用で,下がマイナスプレイヤ用である.ノ^ー

ド内の数字はミニマックスによる値を表す^.

2.も し3≦ε<4ならば,マ ックスプ レイヤ はTU― searchに よって,故意 の ミスP→ P2を 選択 す る.これ に よって,マイナスプ レイヤが この故意 の ミスに気 がつか ないか らで あ る.こ ^こで,も

うひ とつ の故意 の ミスP→ P3を 選択 すれ ば,マイナ ス プ レイヤ はそれ に気がつ くで あろ う.

3.もし4≦εで あれ ば,マ ックス プ レイヤ はTU一searchに よって,故意 の ミスP→P2かP→P3の どち らか を選択 す る。この場合,いずれ を選択 して もマイナスプレイヤは故意 の ミスに気がつかない.

い ま,rをすべ ての局面Pに対 して定義 された関数 とす る.ただ し,T(P)は マ ックスプ レイヤ に よるTU―search戦略 に よる局面Pでの値 で あ る.葉ノー ドと葉 ノー ドで ないマ イナス ノー ドに お いて,TU―^searchは相 手 モ デル探 索 と同 じよ うに手 を選択 す る.葉ノー ドで ないマ ックス ノー ド で,TU―^searchは上述 した ように状 況 に応 じた戦略 を実行 す る。

それ ゆ え,こ こで意 図す る教授戦 略 のアル ゴ リズム は次 の ようにな る^. :マックス ノー ド

:マイナ ス ノー ド :葉ノー ド 戦略1(葉ノー ドでないマ ックスノー ドでの TU―search)

Pを葉 ノー ドでないマ ックスノー ドとする.この とき,教授戦略^TU―鍵頷ぬは3つ の場合に分類される.

● _(タイプ ス)

ノー ドPで故意の ミスが まった く存在 しない場合,次の式 を満たす指 し手P→PJを選択せ よ^. T(鳥)=min T(鳥)

● (タイプ3)

ノー ドPでマイナスプレイヤに悟 られて しまう故意の ミス しか存在 しない場合,次の式 を満た す指 し手P→ PJを選択せ よ.

F(鳥)=min F(PJ),

ただ し,P′ は次の関係 を満たす もの とする^.

７ ２

Ｐ     Ｐ   Ｐ

ｔｈａ ｕｃｈ均

Ｓ ︻

  ｎ

Ｐ Ｔ

071