Think-Box

By: Michael Höhle

Think-boxでは、サイコロの単純なゲームの説明から必勝法を見つける支援をするインフルエンス・ダイアグラムをどのようにして得ることができるのかというわかりやすくかつ詳細な説明をします。

Think-box - Download

Think-Box

このドキュメントは"Think-box"と呼ばれる単純化されたサイコロ・ゲームをモデルとしたインフルエンス･ダイアグラムの構築方法を説明する。このモデリングの目的は、敵の推定される戦略に対して勝てる戦略を見つけることにある。インフルエンス･ダイアグラムが設計され、その後、Hugin GUIに実装される。最終的に、この実装は、敵の推定される戦略に対して最適の対抗戦略を決定するために用いられる。

単純化されたThink-Box

次のような単純化されたバージョンのサイコロ・ゲームThink-boxを考えてみよう。ArneとBente（典型的なデンマーク人の名前）という名の2人のプレイヤーがゲームに参加する。プレイヤーはそれぞれ、2つに分けられた（ラベル "1"と"2"）サイコロを持つ。

:まず、プレイヤーは2人とも、お互い結果を見せずにサイコロを振る。ゲームの目的は、一方のサイコロの知識をもとに、いくつ同じ目が現れたかを推定することである。次のようなビッドが可能である:

• 1 (少なくとも1つが"1")
• 2 (少なくとも1つが"2")
• 2・1 (両方のサイコロとも"1"示している)
• 2・2 (両方のサイコロとも"2"示している)

Arneがゲームを始めたと仮定する。彼は上記4ビッドのうち1つを選ばなくてはならない。Arneのビッドの後、BenteはArneのビッドを信じるかどうか決めなくてはならず、したがって、ビッドアップかコールをしなくてはならない。もし、Benteがコールしなければ、Benteの最後のビッドを考えるため、Arneの番になる。ゲームはプレイヤーの１人がコールを決めるまで続く。コールにより、プレイヤーは二人ともサイコロを見せ、求められたビッドがテーブルの上にあるかどうかに決着がつくこととなる。この過程でゲームの勝者と敗者が決まる。

インフルエンス・ダイアグラムと単純化されたThink-Box

ある霧深い夜パブで親友Arneに上記のゲームを何ラウンドかしようと持ちかけているところを想像してみよう。より面白くするために、それぞれのゲームの敗者は次のラウンドのビールをおごることとする。あなたが酔っぱらうまでArneにおごらせるにはどうすればよいだろうか？つまり、Benteに良い戦略は何であろうか？

いくつかアプローチがある、たとえば、ある人は、ゲーム理論により上記のゲームを分析することもできるし、インフルエンス･ダイアグラムを用いようとすることもできる。ゲーム理論は、非常に複雑で扱いにくい傾向があるので、後者に焦点をあてる。

Arneの戦略の推定に基づいて、最適な対抗戦略を見つけるため、インフルエンス･ダイアグラムを解くことにする。Arneと単純Think-boxのゲームを非常に多くの回数行っており、それゆえに、彼の戦略をかなり理解していると仮定する。

Hugin GUIに実装された単純Think-Boxのインフルエンス・ダイアグラム

単純化のため、今からArneはいつも先手であると仮定する、つまり彼はいつもゲームではビッドするのは最初である。.

確率変数と決定変数を決める

最初に、必要な確率変数と決定変数およびそれらが持っているはずのステートを見つけ出す必要がある。これを得るための懸命な方法は、ゲームの参加者と彼らが行うはずの行動を見つけることだ。

1ゲーム中の最大連続ビッドを分析することにより、各プレイヤーの最大ビッド量を決める。

Arneは1ゲームの間、最大3ビッドをする。Benteの最大は2ビッドである。

今すべての行動が、次のルールに従って、確率変数や決定変数に変換される: もしその行動が意思決定者によってなされなければならない決定であれば、決定変数に変換され、そうでなければ、確率変数になる。結果は:

Benteはサイコロを振った結果に影響を及ぼさないので、自分のサイコロを振ったBenteの結果に相当する変数"Bente's dice"は確率変数になっていることに注意。.

インプルエンス・ダイアグラムの変数を見つけたら、それらが持つステートを考える。dice変数のステートは、サイコロを振った結果を表している一方、ビッド変数のステートは、ビッド変数のその時点で可能なビットを反映している。どのようにステートの数が最大ビッド連続数に基づいているかに注意。

原因と情報の依存性

:次の作業は、見つけられた変数の従属関係-矢印によって表される-を設けることである。矢印の目的は2つある:

• 矢印はゲームの進行を示している
• プレイヤーXのビッド変数の1つに向かう矢印は次のものを反映している: Xのビッド戦略は矢印のくる変数のステートに関する情報に基づいている

単純Think-boxからの経験で、ビッドするとき、たいてい自分のサイコロと敵の最後のビッドのことしか考えていない。その2つと上記の経験の結果図 1に示すようなダイアグラムができる。

図 1: インフルエンス･ダイアグラム中の確率変数と決定変数とそれらの依存性

Arneの最初のビッドの戦略は、彼のサイコロの値のみに頼っていることに注意せよ。彼の戦略を正確に知ることはできないが、我々は最も良い推測を用いていく。

効用関数

決定変数を導入すると、意思決定の結果を決める効用関数を追加することも必要になってくる。効用関数には２つの目的がある

• プレイヤーがコールすると、Benteが勝つか負けるかを決めること
• Benteが妥当な行動しかしないことを確実にすること（たとえば、Arneが2をビット下後1をビッドすることを制限する）

すべての効用を持つ結果のダイアグラムを図 2に示す。項目1を確かにするために、効用関数が連続ビッドの間に置かれる(たとえば、BB1とAB2の間のU5)。これらの関数は、連続ビッド変数と2つのサイコロ変数の両方につながっている。この情報のすべては、もし後者のビッドがコールだったか、もしそうなら、そのコール以前のビッドが存在したかどうかチェックするために必要である。このステップで、効用関数U4、U5、U6、U7となる。項目2は、AB2とBB2の間（U2）だけでなく、AB1とBB1の間（U1)の効用関数を置くことによって達成される。後で効用関数に値が割り振られるとき、不当な行動のすべてに非常に低い値 が割り当てられる。

図 2: モデルU1とU2のインフルエンス･ダイアグラムは、Benteのビッドは妥当であることを保証しており、U4、U5、U6、U7はBenteが勝つかどうかを決めている

U1の親は、U4の親の部分集合なので、2つを追加的な方法で組み合わせることができる。これは単純に、U1の効用値が、U4である適切な列にあるU4の値に加えられることを意味している。同様にU2とU6が組み合わせられる。結果のインフルエンス・ダイアグラムを図 3に示す。

.図 3: 単純Think-boxをモデルにした最終的なインフルエンス･ダイアグラム。どのように効用関数が組み合わさっているかに注意。

変数への確率と効用関数の割り当て

変数、関数、依存関係が決まると、確率変数に条件付き確率を、効用関数に効用値を割り当てる必要がある。この作業は3つのサブタスクに分かれている。Huginシステムに実装されている正確な表の持ついやになるほどの細かいところは、重要ではないが、興味深いことが含まれている。

1. 2つのサイコロ変数への確率の割り当て
2. Arneの戦略の推論に基づいてArneのビッド変数に条件付き確率を割り当て

この作業を遂行するには、Arneの戦略についてよい推論をする必要がある。物事を単純にするため、彼が次のようにとても合理的な決定論的戦略に従うことを仮定する:

• 最初、彼はサイコロが示したものをビッドする。これにより、彼のビッドはいつもテーブルの上にあるということになる。
• もしBenteが2をビッドして、彼が "1"を振れば、その時はコールする
• もしBenteが2をビッドして、彼が "2"を振れば、そのときは2・2をビッドする
• もしBenteが2・1か2・2をベッドしたときは、彼はいつもコールする。

実際のゲームでは、本当の戦略を隠すためArneは決定論的戦略でないものにも従う可能性はある。どのように最適な対抗戦略を見つけるのかのコツを掴んでしまえば、決定論的でない戦略に対して対抗戦略を見つけるときにもインフルエンス･ダイアグラムを使うことができる。

3. 効用関数への値の割り当て、これで前節からの要求を満たすことになる。

最適戦略の発見

.Arneの戦略に対するBenteの最適な対抗戦略を見つけるためにインフルエンス･ダイアグラムを使う準備ができた。

:Huginの以下のアルゴリズムが、要求される結果を与えてくれます。:

1. ネットワークを初期化
2. Benteのサイコロ変数の各ステートXに関して、100%のエビデンスとしてXを入力 (実行モードでXをクリック)
3. ArneのAB１変数の推定ステートYに関して、100%のエビデンスとしてXを入力 (実行モードでYをクリック)
4. ArneのAB１変数の可能な各ステートYに関してSUM伝播を行う
5. )BB1でのBenteに最善のビッドは、最高の期待効用をもつBB1での行動である(図 4参照)。

図 4: エビデンスBD=1とAB=1を入力し、その後sum-propagateしたHuginからのスクリーンショット。
BB1における2・1が最も高い期待効用を持つ。
(期待効用 = 1).

ステップ2.1で我々はAB1の可能ステートのみを通ってループする。Arneの戦略では、たとえばArneがAB1で2・1をビッドすることは不可能である。

もしゲームが長くなっていたならば、BB1にエビデンスとして最適行動を挿入したり、BB2での最適行動を決めるためにAB2のステートを通ってループをする必要があっただろう。しかし、Benteは本当に2回目をビッドさせないので、このステップはアルゴリズムに含まれない。

:このアルゴリズムを適用することで、次のようなBenteのための対抗戦略が決まる。

たとえば、もしBenteが2を出し、最初のビッドでArneが2をビッドしたとすると、戦略はBnteに2・2をビッドするように示している。Benteが1を出し、Arneが2をビッドする状況では、3つの行動（2・1、2・2、call）が同程度に適している。決定論的戦略を得るため、単純に可能性の1つを取り上げるのは重要である。表中のNAは、Arneの選択戦略を用いるとその状況が起こるはずがないことを表している。したがって、Benteの選択肢のすべては、同様に適している。

.問題は、この対抗戦略が実際にどれぐらい優れているかである。

Cheers!サイコロの4つの可能コンフィグレーション([AD=1とBD=1]、[AD=1とBD=2]、[AD=2とBD=1] 、[AD=2とBD=2])において、2つの戦略間でゲームをシュミレートすることによって、Benteは75%のゲームに勝つことが明らかになる。つまりビールをかけた12ラウンドのうち、Benteは3回しか支払う必要はなく、一方Arneは9回支払わなくてはならない。乾杯！

結論

ゲームThink-boxの単純バージョンをモデルにしたインフルエンス・ダイアグラムが設計され、その後Hugin GUIに実装された。結果のダイアグラムは図 3に示しており、Hugin実装はダウンロードもできる。

Arneの戦略が推測され、ダイアグラムの表に入力された。エビデンスの入力や伝播するためHuginを用い、75%のゲームに勝つBenteに最適な対抗戦略が見つかった

展望

このゲームのゲーム理論的分析で、Arneに関して仮定した戦略があまりいい戦略ではないことが明らかになった。彼はたとえば、いつも2・（彼が出す何でも）をビッドする戦略を好んでいるかもしれない。それゆえに、彼がゲームに50%勝つことは確かである-インフルエンス･ダイアグラムで見つけたBenteのカウンター戦略に対してさえも！(ゲーム理論的な注意: 方法論的戦略の組み合わせは、プレイヤー両方がゼロの謝金をとるナッシュ均衡になる)

Arneが決定論的戦略にしたがっているという仮説は、かなりもっともらしくない。Arneのビッド変数をの表の値を変えることにより、Arneは、乱塊戦略でプレイすることを簡単に修正される。 5節で説明したアルゴリズムもまた、Arneの乱塊戦術に対する決定論的な対立戦略を見つけるのに役立ちます。

単純Think-boxはかなりつまらないゲームである。楽しみを増やすための可能な強化として：サイコロの面を増やす、プレイヤーに対するサイコロを増やす、 ジョーカーの概念を入れたり、プレイヤーを増やしたりがある。問題は、小さな強化でもインフルエンス･ダイアグラムムの複雑性を急増させてしまうということである。

このネットワークはHuginソフトウェアと一緒にコンピュータにインストールされています。Huginでこのネットワークを開いてください。このネットワークは、Huginのインストールの. Samples サブディレクトリにあります。