情報処理学会研究報告IPSJ SIG Technical Report
キングメーカーノードを含むゲーム木の均衡点
水野悠†1鶴岡慶雅†1近山隆†1
プレイヤーの数が 3 人以上の多人数ゲームでは，maxn アルゴリズムが各ノードでの最善手を導くために用いられることが多い．maxn アルゴリズムはゲーム理論の部分ゲーム均衡点に相当する．しかし 2 値ゲームにはキングメーカーノードが多くの場合含まれる．キングメーカーノードにおいて maxn アルゴリズムは手番プレイヤーの合理的な振る舞いを一意に決定することが出来ず，各ノードに対する最善手が複数導かれてしまう．このような状況においては，複数の最善手をどのような確率で選ぶ戦略も，部分ゲーム完全均衡点となる．本稿では既存手法で考えられてきたプレイヤーの合理性の概念を拡張し，そこから導かれる均衡点を定義した．この均衡点によりキングメーカーノードを含む 2 値ゲームにおいて，より多くのノードに対して合理的な最善手を導くことを可能にした．
Equilibrium Points of Game Trees with King Maker Nodes
Yu Mizuno,†1 Yoshimasa Tsuruoka†1
and Takashi Chikayama †1
For multiplayer games, games with more than 2 players,the maxn algorithmis often used to decide the best moves for each node.the maxn algorithm corre-sponds to deciding the subgame perfect Nash equilibrium point in game theory.In two-value payoﬀ games, however, game trees often contain kingmakernodes. The maxn algorithm cannot decide rational strategy uniquely for king-maker nodes, and more than one best move exists for each such node.Thesegames have an inﬁnite number of subgame perfect equilibrium points.In this paper, we propose a new framework of equilibrium points, extendingthe notion of players’ rationality. The framework introduces the a more rationalequilibrium point, which can give the rational best moves for kingmaker nodesat certain game situations of two-value payoﬀ games.
1.は じ め に
多人数ゲームのコンピュータゲームプレイヤーでは，maxn アルゴリズム1) が広く用いら
れており，この手法が各ノードでの最善手を導くことを前提として議論や手法の提案・改良
がなされることが多い．この maxn アルゴリズムとは各プレイヤーが自分の利得が最大で
ある子ノードを選ぶことを仮定して他のプレイヤーの行動を予測する手法である．maxn ア
ルゴリズムで求める最善手は，ゲーム理論の分野の部分ゲーム完全均衡点4) に相当し，多
くのゲームで合理的な解を導くことが出来る．
しかしプレイヤーの目的が勝利することのみである「2 値ゲーム」では，どの子ノードを
選んでも自分の敗北が確定している「キングメーカーノード」が多くの場合存在する．キン
グメーカーノードにおいて maxn アルゴリズムは手番プレイヤーの合理的な振る舞いを一
意に決定することが出来ず，各ノードに対する最善手が複数導かれてしまう．このような状
況においては，複数の最善手をどのような確率で選ぶ戦略も部分ゲーム完全均衡点となる．
また，キングメーカーノードでの振る舞いを根拠を持って予測できないため，キングメー
カーノードを子孫に持つノードでは，子ノードの利得を正しく予測できず，根拠のない最善
手が複数導かれてしまう．ゲーム木全体に対しても同様である．
本稿ではゲーム理論の分野からアプローチを行い，部分ゲーム完全均衡点を定義する際に
仮定している各プレイヤーの合理性よりも，より強い合理性を各プレイヤーが持つことが
自然な仮定であることを示し，この仮定によって導かれる「部分ゲーム完全一段階予測均衡
点」を定義した．
本研究で定義した部分ゲーム完全一段階予測均衡点により，maxn アルゴリズムで一意に
振る舞いを定めることが出来なかった多くのノードで，合理的な振る舞いを一意に決定する
ことが可能となった. また，特に 3 人定和 2 値ゲームで部分ゲーム完全一段階予測均衡点を
求めると，2 人のプレイヤーの全ての手番での合理的な振る舞いを決定することが出来るこ
†1 東京大学大学院 工学系研究科Graduate School of Engineering, The University of Tokyo
1c⃝ 2012 Information Processing Society of Japan
Vol.2012-GI-27 No.8
2012/3/2
情報処理学会研究報告IPSJ SIG Technical Report
図 1全探索可能な場合の maxn アルゴリズム
2.既 存 手 法
2.1Maxn アルゴリズム
maxn アルゴリズム1) とは展開形ゲームの局面での最善手を求めるアルゴリズムである．
多人数ゲームでは「maxn アルゴリズムが最善手を導く」ことを前提として議論されること
全探索可能なゲーム木に対する maxn アルゴリズムは「自分以外のプレイヤーは自分の
利得を最大にするように行動する」という合理的な仮定に基づき，与えられた局面における
最善手を求める．各リーフには各プレイヤーの利得を表す n 次の利得ベクトルが対応付け
られている．
各ノードでは手番ノードの利得が最も大きな子ノードが選ばれる．末端のノードから順
に，最善手とノードの持つ利得ベクトルを求めていく．図 1 に全探索が可能な木に対して
maxn アルゴリズムを適用した例を示す．ルートノードでの最善手は右のノードを選ぶこと
であると求めることができる．
全探索が不可能なゲーム木に対しては，利得ベクトルの代わりに評価値ベクトルを用いる．
2.2部分ゲーム完全均衡点
maxn アルゴリズムが各ノードに対して合理的な最善手を導くことの根拠になっているの
が，ゲーム理論の分野における部分ゲーム完全均衡点4) である．
まず，ゲーム理論の基礎について述べる．ゲーム木の構造を持つゲームは展開形ゲームと
呼ばれ，各プレイヤーがそれぞれの手番ノードで「戦略」をとる．各ノードにおける戦略に
は「常に同じ手を選ぶ順戦略」と「あらかじめ決めた確率で手を選ぶ局所戦略」が許されて
いる．局所戦略を用いるプレイヤーがいるときは, 利得ではなく利得の期待値である「期
待利得」を用いる．各プレイヤーは合理的 (十分な推論能力を持つ) かつ理性的 (自分が他の
プレイヤーの立場に立ったらどうするかを考えることができる) であることが仮定されてお
り，自分の期待利得を最大化することを目的としている．
ゲームの解として最も基礎的な概念であるナッシュ均衡点2),3) について述べる．ナッシュ
均衡点とは，「他のプレイヤーが戦略を変えない限り自分も戦略を変える動機を持たない戦
略の組」のことである．ナッシュ均衡点である戦略の組では，各プレイヤーの戦略は，他の
プレイヤーの戦略に対する「最適応答」になっている．最適応答とは他のプレイヤーの戦略
に対して，最も利得を大きくすることのできる戦略のことである．
ゲーム全体ではナッシュ均衡点となっている戦略の組でも，部分ゲームではナッシュ均衡
点となっていない戦略の組が存在し，そのような戦略の組は各プレイヤーの合理性と矛盾
する．各プレイヤーの合理性を正しく満たしている均衡点が部分ゲーム完全均衡点である．
その定義はゲーム木の全ての部分木に対してナッシュ均衡点を導くような戦略の組である．
maxn アルゴリズムが各ノードに対して導く最善手と，部分ゲーム完全均衡点はほとんど
の場合一致する．一致しないのは，手番プレイヤーの利得が最大である子ノードが複数存
在するノードがゲーム木に含まれる場合である．maxn アルゴリズムでは何らかの方法で子
ノードから 1 つを選ぶが，利得が最大の子ノードらを任意の確率で選択する局所戦略の全
てが部分ゲーム完全均衡点となる．
3.2 値ゲームと既存手法の問題点
3.12 値ゲームとキングメーカーノード
前章で述べた既存手法は，基本的に各プレイヤーの利得を「実数」であるとしている．こ
れを実際のゲームに当てはめると，ゲームが終わった時点での「得点」や「儲け」について
考えているといえる．一方，実際のゲームでは「勝敗」のみが意味を持ち，「得点」や「儲
け」は意味を持たないことも多々ある．特に将棋やチェスをはじめとボードゲーム類にはそ
もそも「得点」の概念がないものも多く存在する．
このようなゲームでは，どの手をとっても自分が勝つ可能性はないが，自分のとる手に
よって勝者が決まってしまう，というような局面が存在しうる．「勝敗」よりも「得点」が重
要な意味を持つゲームでは，自分が 1 位になることがなくなっても，少しでも得点を大きく
なる手を選ぼうという動機を持つが，「勝敗」のみが意味を持つゲームでは自分の勝利の可
能性がなくなれば，どの手を選ぶ動機もなくなってしまう．こういった局面を「キングメー
2c⃝ 2012 Information Processing Society of Japan
Vol.2012-GI-27 No.8
2012/3/2
情報処理学会研究報告IPSJ SIG Technical Report
カーノード」と名付け，以下に定義した．
まず「勝敗」のみが意味を持つゲームでは各プレイヤーの利得が「勝ち」を意味する「1」
と「負け」を意味する「0」の 2 値しかとらないものとする．この利得が 1, 0 の 2 値をとる
ゲームを「2 値ゲーム」と名づける．プレイヤー i が利得 1 を得ることを「プレイヤー i が
勝利する」，利得 0 を得ることを「プレイヤー i が敗北する」という言葉で表すことにする．
以降の議論では基本的に勝者が 1 人である「等和 2 値ゲーム」を対象とする．
確定定和 2 値ゲームにおいて，「この手番に到達すれば，プレイヤー i の勝利が確定する
ノード」を「プレイヤー i の必勝ノード」と呼ぶことにする．定義は以下のとおりで，直感
的な意味は「そのノードに到達後，プレイヤー i が正しく手を選べば，必ず勝利するノー
ド」である．
定義 3.1 (必勝ノード). まず「プレイヤー i の利得が 1 であるリーフ」を，プレイヤー i の
必勝ノードとする．また，再帰的に，ノード x とその子ノードの集合 A(x) について，「A(x)
が全てプレイヤー i の必勝ノードである」または，「ノード x の手番がプレイヤー i かつ，
A(x) にプレイヤー i の必勝ノードが含まれる」という状態のとき，ノード x をプレイヤー
i の必勝ノードとする．
続いて，キングメーカーノードを定義する．
定義 3.2 (キングメーカーノード). プレイヤー i の手番ノード x とその子ノードの集合 A(x)
について，「A(x) は全て，プレイヤー i 以外のプレイヤーの必勝ノード」かつ「A(x) に 2 人
以上のプレイヤーの必勝ノードが含まれる」とき，ノード x を「プレイヤー i のキングメー
カーノード」という．
図 2 にキングメーカーノードの例を示す．三角のノードは中に書かれたプレイヤーの必
勝ノードを表す．以下の図中でも同様である．実際のゲームにおけるキングメーカーノード
は「自分は勝つ可能性がないが，自分の選択によって勝者が変わるノード」「自分が勝利出
来ないが，勝利者を決める権利を有するノード」に相当する．なお，キングメーカーノード
の定義からも分かるが，2 人ゲームではキングメーカーノードは発生しない．
3.2既存手法の問題点
前章で述べた，maxn アルゴリズムや部分ゲーム完全均衡点ではキングメーカーノードを
含むゲームで，各ノードの手番プレイヤーがどのような戦略を選ぶかを一意に定めることが
キングメーカーノードでは，複数の子ノードのうちどれを選んでも手番プレイヤーの利得
が変わらないため，それぞれの子ノードを任意の確率分布で選ぶ戦略が全て部分ゲーム完全
図 2キングメーカーノードの例
図 3キングメーカーノードを含むツリーでの部分ゲーム完全均衡点
均衡点となる．キングメーカーノードを子孫ノードに持つノードでは, キングメーカーノー
ドでとられる戦略をナッシュ均衡点となっている戦略から１つ「適当に」選んで，それに対
する最善手をとることになる．こうして考えられた最善手は子孫ノードへの予測が「適当
な」ことから，根拠のないものとなってしまう．
図 3 にキングメーカーノードを含んだゲームの例を示す．各プレイヤーが戦略を決定す
ることは，自分の手番においてそれぞれの子ノードを選ぶ確率を決定することと等価であ
る．それぞれのノードで左の子ノードを選ぶ確率を p1, p2, p3 とおいた．従って，それぞれ
のノードで右の子ノードが選ばれる確率は 1 − p1, 1 − p2, 1 − p3 である．p1, p2, p3 は確率
を表すので，0 ≤ p1, p2, p3 ≤ 1 の式を満たす．
このゲームの部分ゲーム完全均衡点は次の 3 つの条件のいずれかを満たす任意の p1, p2, p3
の組である．
0 ≤ p2 < p1 ≤ 1 ,p3 = 1(1)
0 ≤ p1 = p2 ≤ 1 , 0 ≤ p3 ≤ 1(2)
0 ≤ p1 < p2 ≤ 1 ,p3 = 0(3)
図 4 に式 (1), 式 (2), 式 (3), の条件を満たす部分ゲーム完全均衡点の例を示す．
図 4部分ゲーム完全均衡点の例
3c⃝ 2012 Information Processing Society of Japan
Vol.2012-GI-27 No.8
2012/3/2
情報処理学会研究報告IPSJ SIG Technical Report
プレイヤー 3 がプレイヤー 1 とプレイヤー 2 の戦略を正しく予測できたときは，各プレ
イヤーの戦略の組はこの図に示したように部分ゲーム完全均衡点となるが，プレイヤー 3 が
正しく予測をできることに合理的な根拠はなく，プレイヤー 3 が誤った戦略をとってしま
い，各プレイヤーの戦略の組が部分ゲーム完全均衡点にならないこともあり得る．
4.提 案 手 法
4.1kmn-η 則
キングメーカーノードを含むゲーム木において，子孫ノードでとられる戦略の予測によっ
ては「自分の戦略をどのように選んでも利得が 0 になるので，どのような戦略を選んでも変
わらないと推定する」という状況になりうる．例えば図 6 に示すゲーム木のルートノード
でプレイヤー 3 は，子ノードであるプレイヤー 1 の手番ノードでとられる戦略を「プレイ
ヤー 3 の必勝ノードをとる確率は 0」と予測したとする．この時プレイヤー 3 は自分の手番
ではどのような戦略をとっても期待利得は 0 であるので，どのような戦略をとってもそれは
部分ゲーム完全均衡となる．しかし，プレイヤー 3 がこのように手を選ぶのは以下の観点か
ら不自然であるといえる．プレイヤー 3 の選択できる 2 つの子ノードを比べると，右の子
ノードを選ぶとプレイヤー 3 の期待利得は必ず 0 になるのに対し，左の子ノードを選ぶと
プレイヤー 3 の期待利得は 0 より大きくなる可能性がある．したがって，プレイヤー 3 は
左の子ノードを確率 1 で選ぶという戦略をとることが自然である．
また，図 5 のゲーム木についてプレイヤー 1 と 3 が左の子ノードを選ぶ確率をそれぞれ
p1, p3 とおくと，プレイヤー 3 の期待利得 h3 は h3 = p3 · p1 であるので，p3 = 1 とする
戦略によるプレイヤー 3 の利得 h3|p3=1 と，0 ≤ p3 < 1 とする戦略による戦略によるプレ
イヤー 3 の利得 h3|0≤p3<1 との関係は h3|p3=1 ≥ h3|0≤p3<1 となる．等号が成立するのは
p1 = 0 の場合のみである．すなわち，p3 = 1 とする戦略はその他の戦略より大きいか同じ
利得を必ず得られることが分かる．この観点からもプレイヤー 3 は左の子ノードを確率 1 で
選ぶという戦略をとることが自然であるといえる．
次に図 6 に示した，「自分の戦略をどのように選んでも利得が 1 になるので，どのような戦
略を選んでも変わらないと推定する」という状況について考える．プレイヤー 3 は，子ノー
ドであるプレイヤー 1 の手番ノードでとられる戦略を「プレイヤー 3 の必勝ノードをとる確
率は 1」と予測したとする．この時プレイヤー 3 は自分の手番ではどのような戦略をとって
も期待利得は 1 であるので，どのような戦略をとってもそれは部分ゲーム完全均衡となる．
しかしこのプレイヤー 3 の戦略は先述の例と同様に 2 つの観点から，不自然な戦略である．
プレイヤー 3 の選択できる 2 つの子ノードを比べると，右の子ノードは常に利得が 1 に
なるのに対し，左の子ノードは利得が 1 より小さくなることがあるので，プレイヤー 3 は
確率 1 で右の子ノードを選ぶ戦略をとるべきである．また，プレイヤー 1,3 が左の子ノード
を選ぶ確率をそれぞれ p1, p3 とおくと，p3 = 0 とする戦略はその他の戦略より大きいか同
じ利得を得られることが分かり，プレイヤー 3 は p3 = 0 である戦略をとることが自然であ
るといえる．p3 = 0 とする戦略とその他の戦略の期待利得が同じになるのは，p1 = 1 の場
合のみである．
以上の 2 つの例でも見たように，各プレイヤーが到達することが望ましいと考える「ノー
ドの選択好順」は「自分の利得が必ず 1 となるノード」，「自分の利得が 0 から 1 の間にな
るノード」，「自分の利得が必ず 0 となるノード」の順であるとするのが自然である．それ
ぞれの性質を持つノードについて考えると，選択好順は「自分の必勝ノード」，「誰の必勝
ノードでもなく，子孫に自分の必勝ノードを含むノード」，「他人の必勝ノード，および，誰
の必勝ノードでもなく子孫に自分の必勝ノードを含まないノード」の順であると言い換える
ことが出来る．この選択好順は自分の手番ノードでの選択のみでなく，他のプレイヤーの手
番ノードで選択される際にも望ましい順を示している．この選択好順に従った，戦略の選択
を各プレイヤーに行わせるために，次に定義する kmn-η 則を導入する．なお「kmn」とは
King Maker Node の頭文字をとったものである．
定義 4.1 (kmn-η 則). 子ノード A(x) にプレイヤー i の必勝ノードが含まれるキングメーカー
ノード x に関して，プレイヤー i がこのキングメーカーノード x でとられる戦略を予測すると
き，「自分の必勝ノードが選ばれる確率 pwin−i は, η を微小な正の数として η ≤ pwin−i ≤ 1−η
である」と予測するものとする．この条件を「kmn-η 則」と呼ぶ．
実際のゲームでこの kmn-η 則が意味するところは，「他プレイヤーのキングメーカーノー
ドでは，自分を勝たせる手を必ずとろうとしたり，必ずとらないようにしようとはしない」
と予測することである．あるいは「他プレイヤーのキングメーカーノードでは，微小な確率
で手がすべって戦略とは異なる手をとる可能性がある」と考えることに相当すると言うこと
この kmn-η 則により先述の自然な選択好順が導かれる．図 5 と図 6 で見た例に関して，
プレイヤー 3 は図 7 で示すように，自然な戦略をとるようになる．図 7 のそれぞれのツリー
でプレイヤー 3 は，期待利得が大きくなる子ノードを確率 1 で選ぶ戦略をとることになり，
いずれも自然な選択好順に一致している．本節の以降の議論では各プレイヤーは kmn-η 則
に従うことを仮定する．
4c⃝ 2012 Information Processing Society of Japan
Vol.2012-GI-27 No.8
2012/3/2
情報処理学会研究報告IPSJ SIG Technical Report
図 5どの戦略を選んでも利得が 0 と推論してしまう例
図 6どの戦略を選んでも利得が 1 と推論してしまう例
図 7kmn-η 則による自然な選択好順
4.2一段階予測均衡点
3.2 節で述べたように，2 値ゲームにおいてはナッシュ均衡点および部分ゲーム完全均衡
点ではキングメーカーノードにおける最善な戦略を一意に定めることが出来ない．したがっ
てキングメーカーノードを子孫ノードに持つノードはキングメーカーノードでとられる戦略
を「適当に」予測し，それに基づいた最適応答をとることになる．あるノードで子孫である
キングメーカーノードの戦略を予測した結果，子ノードの利得が全て同じになり，そのノー
ドでもキングメーカーノード同様，最善な戦略を一意に定められない，といったことも起こ
キングメーカーノードやその先祖ノードで最善手を一意に定められるようにするため，
ゲーム理論の前提となっている「各プレイヤーの持つ十分な論理的思考力」をより強いもの
として考える．ナッシュ均衡点や部分ゲーム完全均衡点において，各プレイヤーは，他のプ
レイヤーの戦略に対する最適応答をとり「他のプレイヤーも自分やそのプレイヤー以外の戦
略に対する最適応答をとっている」ことを知っているため「戦略を変えても利得が増えるこ
とはないので，誰も戦略を変える動機はない」という推論を行っている．
しかし，キングメーカーノードを含むツリーでは, ナッシュ均衡点および部分ゲーム完全
均衡点においても，「現在とっている戦略と異なる戦略に変えても利得が増えることも減る
こともないので，戦略を変えない動機もない」という状況が多く存在する．プレイヤー i が
さらに深い推論を行うことが可能であるとすると，「自分の利得が変化しない範囲で戦略を
b′i に変更すると，他のプレイヤーが戦略を変更する動機を持つようになる」という状況が
あり得ることが分かる．この「戦略を変更する動機を持ったプレイヤー」が，実際に戦略を
変更することによりプレイヤー i の利得が増加するならば，プレイヤー i は戦略を今のまま
にしておくより b′i に変更すべきである．以上の話をまとめて，次のような概念を導入する．
部分ゲーム完全均衡点である戦略の組 b = (b1, . . . , bn) において，プレイヤー i が部分
ゲーム完全均衡点の範囲で戦略を b′i に変えると，その変更に対して，少なくとも 1 人のプ
レイヤー j が戦略を b′j に変更する動機を持ち，その変更の結果，プレイヤー i の利得が初
めの状態 hi(b) より大きくなる場合，「b においてプレイヤー i は一段階予測に基づく戦略変
更の動機を持つ」という．定義は以下の通りである．b−i は戦略の組 b から第 i 番目の要素
を除いたもの，b−ij は戦略の組 b から第 i 番目の要素と第 j 番目の要素を除いたものであ
る．また b′ は戦略の組 b′ = (b′1, . . . , b′n) を意味する．Bi(b−i) は戦略の組 b−i に対するプ
レイヤー i の最適応答の全体を示す．
定義 4.2 (一段階予測に基づく戦略変更の動機). 部分ゲーム完全均衡点である行動戦略の
組 b = (b1, . . . , bn) に関して，以下の 2 式を満たす，プレイヤー i の行動戦略 b′i が存在する
とき「b においてプレイヤー i は一段階予測に基づく戦略変更の動機を持つ」という．
• b′i ∈ Bi(b−i)
• j= 1, . . . , i − 1, i + 1, . . . , n に対して，bj∈ Bj(b′i, b−ij) であれば b′j= bj,
bj /∈ Bj(b′i, b−ij) であれば b′j は Bj(b′i, b−ij) の任意の要素とし，hi(b′) > hi(b)
例として，図 8 にて一段階予測に基づく戦略変更の動機の概念を説明する．左のゲーム
木で各プレイヤーがとっている戦略 p1 = 0.6, p2 = 0.2, p3 = 1 は部分ゲーム完全均衡点の
一つである．ここでプレイヤー 1 が戦略を p1 = 0.6 から p1 = 0.1 へと変更することを考
える．まず，プレイヤー 1 はどのような戦略をとっても自分の利得 h1 = 0 が変化すること
はないので，プレイヤー 1 のこの戦略 p1 = 0.1 は他のプレイヤーの戦略 p2 = 0.2, p3 = 1
に対する最適応答である．このプレイヤー 1 の戦略変更に対し，プレイヤー 2 の現在とっ
ている戦略 p2 = 0.2 は p1 = 0.1, p3 = 1 に対する最適応答の 1 つなので，戦略を変更す
る動機を持たず，そのままの戦略をとる．プレイヤー 3 は現在とっている戦略 p3 = 1 は
p1 = 0.6, p2 = 0.2 に対する最適応答でなくなり，p3 = 0 が最適応答になるので，動機を持っ
て p3 = 0 に戦略を変更する．この結果，各プレイヤーの戦略は p1 = 0.1, p2 = 0.2, p3 = 0
となり，再び部分ゲーム完全均衡点となる．プレイヤー 1 の期待利得 h1 の変化を見ると，
戦略変更後のほうが増加していることが分かる．以上の議論より，プレイヤー 1 は初めの状
態 p1 = 0.6, p2 = 0.2, p3 = 1 において，戦略を p1 = 0.1 に変更する動機を持つので，一段
階予測に基づく戦略変更の動機を持つことが分かった．
図 4 のゲーム木の (1)p1 > p2, p3 = 1 である部分ゲーム完全均衡点では，プレイヤー 1
のみが 0 ≤ p1 < p2 とする一段階予測に基づく戦略変更の動機を持つ．p2 = 0 の場合でも
kmn-η 則によりプレイヤー 1 は 0 < p2 = η と予測するので，同様の動機を持つ．
図 4 のゲーム木の (3)p1 < p2, p3 = 0 である部分ゲーム完全均衡点では，p1 ̸= 0 の場合
5c⃝ 2012 Information Processing Society of Japan
Vol.2012-GI-27 No.8
2012/3/2
情報処理学会研究報告IPSJ SIG Technical Report
はプレイヤー 2 のみが 0 ≤ p2 < p1 とする一段階予測に基づく戦略変更の動機を持つ．
図 4 のゲーム木の (2)p1 = p2, 0 ≤ p3 ≤ 1 である部分ゲーム完全均衡点では，p1 = p2 ̸= 0
の場合はプレイヤー 1 が 0 ≤ p1 < p2，プレイヤー 2 が 0 ≤ p2 < p1 とする一段階予測に
基づく戦略変更の動機を持つ．p1 = p2 = 0 の場合はどのプレイヤーも一段階予測に基づく
戦略変更の動機を持たない．
各プレイヤーが十分な推論能力を持ち，一段階予測に基づく戦略変更の動機にも考えが及
ぶ場合，部分ゲーム完全均衡点でも誰かが一段階予測に基づく戦略変更の動機を持っている
場合は，戦略を変更すべきであると考える．どのプレイヤーも戦略を変更しなくなるのは，
どのプレイヤーも一段階予測に基づく戦略変更の動機を持たないような部分ゲーム完全均
衡点のみである．このような戦略の組を「一段階予測均衡点」と定義する．
定義 4.3 (一段階予測均衡点). 部分ゲーム完全均衡点である行動戦略の組 b = (b1, . . . , bn)
において，どのプレイヤーも一段階予測に基づく戦略変更の動機を持たないとき，b は一段
階予測均衡点であるという．
図 9 に示したゲーム木について kmn-η 則が成り立つとすると，今までに見てきた一段階予
測に基づく戦略変更の動機に関する議論より，一段階予測均衡点は p1 = p2 = 0, 0 ≤ p3 ≤ 1
のみであることが分かる．
図 8一段階予測に基づく戦略変更の動機
図 9一段階予測均衡点
4.3部分ゲーム完全一段階予測均衡点
ゲーム全体でナッシュ均衡点となっていても，部分ゲームではナッシュ均衡点でない戦略
の組がプレイヤーの合理性を正しく表現していないのと同様に，ゲーム全体では一段階予測
均衡点となっていても部分ゲームでは一段階予測均衡点でない戦略の組はプレイヤーの合理
性を正しく表現していない．
プレイヤーの合理性を正しく表現している均衡点として部分ゲーム完全一段階予測均衡点
を定義する．部分ゲーム完全一段階予測均衡点は任意のゲーム木に対して少なくとも 1 つ
は存在する．
定義 4.4 (部分ゲーム完全一段階予測均衡点). 戦略の組 b = (b1, . . . , bn) が，展開形ゲーム
Γ の任意の部分ゲームに対して一段階予測均衡点を導くとき，b を Γ の「部分ゲーム完全一
段階予測均衡点」であるという．
5.3 人 2 値ゲーム
全探索が可能な 3 人 2 値定和ゲームについて考える．部分ゲーム完全均衡点の範囲で考
えると無数の均衡点が存在する．各プレイヤーは手番ノードにおいて，子孫ノードの戦略を
「適当に」予測し，それに対する最適応答となる戦略をとることになる．
各プレイヤーが kmn-η 則に従い，十分な論理的思考力を持つため，部分ゲーム完全一段
階予測均衡点にあたる戦略をとろうとしている場合について考える．ルートノードがいずれ
かのプレイヤー i の必勝ノードである場合は，必ずプレイヤー i が勝利する．
一方，ルートノードが必勝ノードでない場合は必ずプレイで一度はキングメーカーノード
に到達することになる．3 人 2 値ゲームにおいて，各プレイヤーが kmn-η 即に従い，部分
ゲーム完全一段階予測均衡点にしたがった戦略をとると，戦略が一意に定まらないキング
メーカーノードは全て同じプレイヤーの手番ノードとなる．残りの 2 人のプレイヤーのキ
ングメーカーノードでは必ず戦略が一意に定まる．この時定まる戦略はどちらかの子ノード
を確率 1 で選択するものである．
また，各ノードでの戦略が決まった後，「どのプレイヤーの勝利ノードに到達する可能性
があるか」と「それを決めることができるプレイヤーは誰か」がゲーム木の「本質」である
と考えると，ゲーム木を次のように単純化できる．これらの単純化を「同値変換」と呼ぶこ
とにする．図 10 に (1) から (4) の例を示す．
( 1 )あるノード x においてとられる戦略が，子ノード y を確率 1 で選ぶものである場合，
x の親ノード z から x につながるエッジを y へと直接つなぎ替え，x の y 以外の子
ノードと x を削除する．「プレイでノード x に到達した場合，必ずノード y へ到達す
る」というゲーム木の本質を表現したまま，ゲーム木を単純化している．
( 2 )あるノード x と，その子ノード y の手番プレイヤーが同じ場合，x から y の子ノード
らへ直接エッジをつなぎ，ノード y を削除する．「ノード x とノード y の子ノードの
どれに到達するかは手番プレイヤーが選べる」というゲーム木の本質を残したまま，
ゲーム木を単純化している．
( 3 )あるノードの子ノードに同じプレイヤーの必勝ノードが複数ある場合，それらの子
6c⃝ 2012 Information Processing Society of Japan
Vol.2012-GI-27 No.8
2012/3/2
情報処理学会研究報告IPSJ SIG Technical Report
ノードは本質的には同じものであるので，1 つを残して削除する．
( 4 )あるノードの子ノードに同じプレイヤーの手番，かつ，全く同じプレイヤーらが勝利
する可能性があるキングメーカーノードが複数ある場合，それらの子ノードは本質的
には同じものであるので，1 つを残して削除する．
図 10同値変換
それぞれの変換を順不同で何度繰り返しても，ゲーム木の本質は失われない．3 人 2 値
ゲームで，各プレイヤーが kmn-η 即に従い，部分ゲーム完全一段階予測均衡点にしたがっ
た戦略がとられるゲーム木を考え，この同値変形を適用すると，図 11 に示すように 1 つの
キングメーカーノードと 2 つのリーフからなるゲーム木へと単純化される．このキングメー
カーノードでとられる戦略を決定することは出来ないが，元のゲーム木で勝ち目のあるプレ
イヤーが 2 人しかおらず，それが誰なのかを求めることが出来る．
3 人 2 値ゲームの場合これらの同値変形の結果は，1 人だけキングメーカーノードが残っ
たプレイヤー i が，i 以外の 2 人のうち片方のプレイヤー j を勝たせる戦略を選ぶ確率が全
てのキングメーカーで等しいと仮定したときの，ゲームのプレイの様子を表しているともい
6.実験と評価
6.1実 験 方 法
実際に存在する 3 人 2 値定和ゲームの例として 3 人ダイヤモンドゲームを用いて実験を
行った．各プレイヤーが順番に自分のコマを動かして，最も早く自分のコマを全てゴールに
到達させたプレイヤーが勝ち，というゲームである．通常は 3 人のプレイヤーで行われる．
完全情報・確定の性質を持つので，多人数ゲームの例としてしばしば研究の対象にされて
ダイヤモンドゲームには盤面の大きさが様々なものが存在し，大きさによって各プレイ
ヤーのコマの数が変わる．今回は全探索が可能なサイズで実験を行うため，図 12 に示す
最小の大きさのダイヤモンドゲームを用いた．各プレイヤーは 1 つづつのコマを動かして，
ゴールに最も早く到達させることを目指す．コマは現在いるマスの隣り合ったマスか，隣の
マスにある他のプレイヤーのコマを飛び越した先のマスに移動させることが出来る．他のプ
レイヤーのスタートマスやゴールマスに自分のコマを動かすことは出来ない．また，ゲーム
が有限回の手番で終わるようにするため，以前に到達した局面に再び到達するようなコマの
移動は禁止した．
図 113 人 2 値ゲームの同値変換後
図 12ダイヤモンドゲーム
6.2各種実験と結果
6.2.1最善手が一意に定まるノードの数
各種手法でゲーム木でどれだけのノードで最善手を一意に定めることが出来るかを調べた．
図 1 にその結果を示す．「既存手法」は maxn アルゴリズム，「kmn-η」は kmn-η 則，「kmn-η，
均衡点」は kmn-η 則と部分ゲーム完全一段階予測均衡点をそれぞれ適用した場合に，最善
手が一意に定まるノードと定まらないノードの数を示す．また，一意に定まった最善手に各
プレイヤーが従っている時に，ルートノードからのプレイで到達する可能性のあるノードの
数を示す．「既存手法」，「kmn-η」，「kmn-η，均衡点」の順に，最善手が一意に定まるノード
の数が増加していることが分かる．
6.2.2ゲーム木の同値変形
同値変形によりゲーム木をどれだけノードの数を減らし単純化出来るかを調べた．図 ??
にその結果を示す．上から順に，そのままのゲーム木，同値変形したゲーム木，kmn-η 則
を適用後に同値変形したゲーム木，kmn-η 則を適用し部分ゲーム完全一段階予測均衡点を
求めた後同値変形したゲーム木である．順にノードの数が減っていき，部分ゲーム完全一段
7c⃝ 2012 Information Processing Society of Japan
Vol.2012-GI-27 No.8
2012/3/2
情報処理学会研究報告IPSJ SIG Technical Report
表 1最善手が一意に定まらないノードの数
うち，一意に定まる/
定まらないノード数到達しうるノード数
うち，一意に定まる/
定まらないノード数
既存手法840 / 84840 / 84
kmn-η8425 / 596920 / 49
kmn-η，均衡点8438 / 466328 / 35
階予測均衡点ではキングメーカーノードが 1 つあるだけの木まで単純化できた．
表 2同値変形によるノードの数の削減
ノード数リーフ数キングメーカーノードの数
元のゲームツリー8411226
同値変形728519
kmn-η，同値変形9105
kmn-η，均衡点，同値変形121
6.2.3既存手法と提案手法の対戦
4 つの手法を用意しダイヤモンドゲームで対戦を行った．4 つの戦略は，全てのノードでラ
ンダムに手を選ぶ「RNDall」，kmn-η 則に従い候補からランダムに手を選ぶ「RNDeta」，
maxn アルゴリズムを用いて予想利得が最大である子ノードを当確率で選ぶ「eqprob」，
kmn-η 即と部分ゲーム一段階予測均衡点に従い最善手が定まらないノードでは勝者を当確
率で選ぶ「1EP」である．対戦は「戦略 1EP を使うプレイヤーが 1 人と，他の戦略を使う
プレイヤーが 2 人」「1EP を使うプレイヤーが 2 人と他の戦略を使うプレイヤーが 1 人」で
行い，プレイヤーの各手番順を 1 回ずつ行った時に得られる期待利得の平均をとった．
各プレイヤーが他のプレイヤーの戦略を知らず，他のプレイヤーが自分と同じ戦略を用い
ていると仮定して手を選ぶ場合の結果を表 3 に，各プレイヤーが他のプレイヤーの戦略を
知っている場合の結果を表 4 に示す．2 つの組み合わせを除き 1EP が他の戦略を上回って
いることが分かる．唯一下回っているのは「戦略 1EP が 1 人，eqprob が 2 人」，同点と
なっているのが「戦略 1EP が 2 人，eqprob が 1 人」の場合である．1EP の戦略は「自分
の戦略の変更によって，他のプレイヤーに戦略を変えさせることにより自分の利得を上げ
る」というものであるので，お互いの戦略を適当に予測する状況では効果が小さくなってい
ることが確認された．また 1EP を用いるプレイヤー a は「プレイヤー b のうち片方はプレ
イヤー c を勝たせないように振る舞う」と仮定して最善手を決めているが，プレイヤー b が
実際は eqprob を用いているためにこの仮定が間違っており，結果として得られる利得が悪
くなっているという状況も見られた．a と b の戦略が逆の場合にも同様の状況が見られた．
表 3相手の戦略を知らない場合の各戦略の平均利得
戦略平均利得戦略平均利得
1EP 1 人0.374RNDall 2 人0.313
1EP 2 人0.421RNDall 1 人0.157
1EP 1 人0.347RNDeta 2 人0.327
1EP 2 人0.359RNDeta 1 人0.281
1EP 1 人0.213eqprob 2 人0.394
1EP 2 人0.333eqprob 1 人0.333
表 4相手の戦略を知る場合の各戦略の平均利得
戦略平均利得戦略平均利得
1EP 1 人0.615RNDall 2 人0.192
1EP 2 人0.431RNDall 1 人0.139
1EP 1 人0.449RNDeta 2 人0.276
1EP 2 人0.458RNDeta 1 人0.083
1EP 1 人0.472eqprob 2 人0.264
1EP 2 人0.417eqprob 1 人0.167
7.お わ り に
本稿では既存手法で考えられてきたプレイヤーの合理性の概念を拡張することで導かれ
る，部分ゲーム完全一段階予測均衡点を定義した．この均衡点によって既存手法では最善手
を複数導かれてしまった多くのキングメーカーノード上で，最善手を一意に導かれることを
今後の課題としては，評価値を使った maxn アルゴリズムや利得が実数のゲームにおい
て，この部分ゲーム完全一段階予測均衡点が有効な働きをするのかどうかの検証や，そのた
めの均衡点の概念の改良が考えられる．
1) C.Luckhardt and K.Irani. An algorithmic solution of n-person games. In Proceed-ings of the 5th National Conference on Artiﬁcial Intelligence (AAAI), pp. 158–162,1986.2) J.Nash. Non-cooperative games. The Annals of Mathematics, Vol.54, No.2, pp.286–295, 1951.3) J.F. Nash, etal. Equilibrium points in n-person games. Proceedings of the nationalacademy of sciences, Vol.36, No.1, pp. 48–49, 1950.4) R. Selten.Spieltheoretischebehandlungeinesoligopolmodellsmitnach-fragetr¨agheit: Teil i: Bestimmung des dynamischen preisgleichgewichts. Zeitschriftf¨ur die gesamte Staatswissenschaft/Journal of Institutional and Theoretical Eco-nomics, Vol. 121, No.2, pp. 301–324, 1965.
8c⃝ 2012 Information Processing Society of Japan
Vol.2012-GI-27 No.8
2012/3/2