（マルコフ連鎖を利用したモデリングゲーム）
改善後のタイトルは以下の通りです： 『マルコフ連鎖を活用したモデリングゲーム』
「しゃっとざぼっくす」を使った確率モデリングの探求
はじめに
友達とトランプゲームをすることからルーレットテーブルでお金を勝ち取ることまで、素晴らしいゲームの楽しさはほとんどの人にとって抵抗できないものです。しかし、どんなに楽しいゲームでも、数回負けると最も楽観的なプレイヤーでさえ「ゲームは不正なのか？」と尋ねたくなることがあります。確率に関する知識がある私たちにとって、この質問に答えずにおくことは非常に不満です。この記事では、このような質問に答えるための確率モデルの一種を探求します。具体的には、「しゃっとざぼっくす」というゲームにマルコフ連鎖を適用する方法を紹介し、自分自身のゲームに関連する質問に確率を使って答えるように皆さんにインスピレーションを与えることを目指します。
マルコフ連鎖とは何か、そしてゲームとはどのような関係があるのか
マルコフ連鎖は、シンプルでよく研究された確率モデルであり、多くの現実世界の確率過程のモデリングを可能にします。具体的には、マルコフ連鎖の目的は、イベントの確率的な連続列をモデル化することであり、イベントは状態というセットから取られます。この目標を達成するために、マルコフ連鎖は状態間の遷移の確率をマトリックスとして保存します。状態と遷移行列に加えて、確率過程の振る舞いを指定するマルコフ連鎖の特徴的な特性は、マルコフ特性です。直感的には、この特性は、現在の状態が、これまでにシーケンス内で発生したどの状態に関係なく、次の状態への遷移の確率を決定するための必要な情報を保持していると主張します。このような特性を持つ任意の確率過程は、マルコフ連鎖を使用してモデル化することができるため、非常に強力なツールとなります。これらの概念、および一般的なマルコフ連鎖について理解を深めるために、シンプルなゲームの例を見てみましょう。
たとえば、公平なコインを連続して投げてギャンブルに参加するとします。ゲームの開始時には5ドルを持っており、各コイン投げの前に結果（表または裏）を予想します。コインの表裏を正しく予想した場合、1ドル獲得し、間違えた場合は1ドル失います。ゲームは、所持金が0ドルまたは10ドルになった場合に終了します。
ゲームの状態をコイン投げの後のプレイヤーの所持金バランスで定義すると、マルコフ特性が成立し、幸運なことにこのゲームをマルコフ連鎖を使ってモデル化することができます！図のように、このマルコフ連鎖の状態と遷移確率を表現することができます：
上記の図では、オレンジ色の円はゲームの状態を表し、矢印は状態間の遷移確率を表しています。すべての遷移確率は0.5であり、公平なコイン投げの結果を正確に予想することが状態の変化に必要です。さらに、状態0と10には、ゲームの終了状態である確率1の自己遷移があります。
この記事の残りを読んだ後、上記のシンプルなゲームに関してこれらの質問に答える方法について考えることをお勧めします。
「しゃっとざぼっくす」のゲームの説明
マルコフ連鎖を用いた確率モデリングに関連する複雑さを本当に探求するために、私たちは「しゃっとざぼっくす」というゲームに焦点を当てます。このゲームについては、インスタグラムのリールをスクロールしているときに偶然見つけ、ルールについて漠然と理解しながら勝つことがどれほど難しいかを調べることにしました。
シャット・ザ・ボックスは、9つのタイル（1から9までのラベルが付いている）と2つの6面ダイスで構成されるボードを使用してプレイされるマルチプレイヤーゲームです。各プレーヤーのターンでは、すべてのタイルが直立した状態で始まります。その後、2つのダイスが振られ、プレイヤーは2つのダイスの合計と等しい値を持つタイルを下げることが許されます。プレーヤーはこのダイスを振り、タイルを下げるプロセスを、直立したタイルの部分集合が2つのダイスの合計と等しい値になるものが存在しなくなるまで繰り返します。この時点で、プレーヤーのターンは終了し、ボード上にまだ直立しているタイルの合計がそのプレーヤーのスコアとなります。このバージョンのゲームでは、すべてのプレーヤーが自分のターンを終えた後、最低スコアのプレーヤーが勝者とされます。ただし、プレーヤーのターンが終了したときにすべてのタイルを下げることができた場合（つまり「ボックスを閉じる」）、自動的にゲームに勝利します。特に、このルールが私の注意を引き、この探求の焦点となるでしょう。具体的には、どれほど「ボックスを閉じる」のが難しいのかという問いに答えたかったのです。
マルコフ連鎖を使用して「シャット・ザ・ボックス」をモデル化する
前のセクションから明らかなように、私たちは「シャット・ザ・ボックス」をマルコフ連鎖としてモデル化する必要があります。これは直感的な次のステップに思えるかもしれませんが、マルコフ性質が成立することを確認しましょう。これには、このゲームのユニークな状態を、{1、2、3、4、5、6、7、8、9}のすべての部分集合として定義します。これは、プレイヤーのターン中の任意の瞬間が、どのタイルが上げられ、下げられているかで一意に特徴付けられるためです。数値的には、これらの状態を9桁の2進数の数字（直立したタイルは1）と考えることができ、512のユニークな状態があります。この状態の定義の下では、マルコフ性質は、サイコロの確率的特性、現在の状態、およびゲームのルールのみが、状態間の遷移の確率を決定することを意味します。最も重要なことは、現在の状態を知っている場合、プレーヤーのターン中に到達した前の状態は、将来の他の状態に到達する確率に影響を与えないということです。
状態が明確に定義されたことと、「シャット・ザ・ボックス」をマルコフ連鎖としてモデル化できることが確認されたので、唯一残る要素は遷移行列Tの定義です。具体的には、Tᵢₖ（第i行k列のエントリ）は状態iから状態kへの遷移の確率を表します。これらの確率を決定することによって、このゲームをモデル化する際の興味深い複雑さが現れます。
ある状態から別の状態への遷移の確率を知るためには、「状態を変化させるためにゲームで何が起こる必要があるか」という質問に答える必要があります。興味のあるゲームである「シャット・ザ・ボックス」では、次の状態に遷移するために発生する確率的なアクションが2つあります：ダイスを振ることと下げるタイルを選択することです。まずは、ダイスの役割を見て、状態iと状態kの間の遷移を考えましょう。まず、SᵢとSₖをそれぞれ状態iと状態kに含まれる直立した数字を含む集合とします。状態iから状態kへの遷移の確率がゼロでないためには、SₖはSᵢの適切な部分集合である必要があります。なぜなら、状態間の遷移では直立したタイルの数が減少しなければならず、一度下げたタイルは上げられないからです。この状態表現とSₖ ⊂ Sᵢの仮定の下で、状態iと状態kの間の遷移の過程で下げられた数は、集合D = Sᵢ – Sₖ（Sₖに含まれていないSᵢの要素）を構成します。
したがって、この遷移が発生するための必要条件の1つは、振られたダイスの合計がDの要素の合計と等しい必要があります。形式的には、次の式が成立する必要があります。
ここで、X₁とX₂は2つの6面ダイスの値を表す離散確率変数です。Dの要素の合計をzとすると、この式が2つの6面ダイスで成立する確率は次のように導出されます。
zが2未満または12より大きい場合、状態iから状態kへの遷移確率がゼロであるため、通常の2つのサイコロの出目の合計がzに等しくなることはありません。
遷移行列のエントリーを埋めるために必要な確率計算はこれだけのように見えるかもしれませんが、状態遷移にはサイコロの出目に一致する他の多くのオプションと一致する可能性のある、プレイヤーが適切な手を選択することも含まれます。
人間の戦略の要素をモデル化するために、プレーヤーがランダムに選ぶことができる可能なタイルのセットから均一に選択するという仮定をします。この仮定の下で、プレイヤーが状態kを選択する確率は1/Nᵢₖであり、NᵢₖはSᵢの合計がzに等しい空でない部分集合の数です。
上記の情報を元に、遷移行列のエントリーを形式的に定義することができます。遷移行列の各エントリーは次の2つのイベントの発生確率を表します：
- サイコロの出目の合計がzに等しいこと（イベント1）
- プレーヤーが特定のタイルセットをランダムに選んで、状態iから状態kに変化させる（イベント2）
したがって、遷移行列のエントリーは次のように定義されます：
上記の遷移行列の定義には、プレーヤーのターンが終わる確率は考慮されていません。これは、プレーヤーが「シャット・ザ・ボックス」するか、サイコロの出目を観察した後にタイルをひっくり返せる状態がない場合に起こる可能性があります。これらの場合、1/Nᵢₖは定義されていないため、独自に扱う必要があります。
前述の状態のバイナリ表現では、状態i = 0はすべてのタイルがひっくり返されていることを表します。「シャット・ザ・ボックス」はゲームの「勝ち」の状態であるため、遷移行列を修正して状態0にとどまる確率が1となるようにします（つまり、T₀₀ = 1）。
最後に、プレーヤーのターンが「不運な」サイコロの出目により終了することを表す「負け」の状態(L)を追加します。具体的には、この状態を遷移行列に組み込むために、Sᵢの部分集合のいずれもX₁ + X₂（2つのサイコロの合計）となる確率を知る必要があります。これを明示的に計算することは可能かもしれませんが、他の遷移行列の値に対して相対的に定義することができます：
なぜならば、遷移行列の各行は確率分布を表し、それらは合計が1になる必要があるからです。さらに、ゲームの最終状態であるため、この状態からの遷移確率は0です。
上記の正確な遷移確率の結果を使って、マルコフ連鎖の素晴らしい特性のいくつかを活用して、「ボックスを閉める」ことがどれだけ難しいかという問いに答えることができるようになりました。具体的には、完全にランダムな戦略を使用してプレイヤーが「ボックスを閉める」確率は何ですか、という問いに答えることができます。
Pythonを使用して「ボックスを閉める」勝率を計算する
このゲームの「勝ち負け」の確率を計算しようとする際、遷移行列の有用性を理解することが重要です。マルコフ連鎖の場合、遷移行列は、ただ1回の遷移後に状態の確率分布がどのように変化するかを、単一の行列-ベクトルの乗算を使って探索することを可能にします。数学的には、これを次のように簡単に表現することができます：
ここで、Tは遷移行列であり、πₜはt回の遷移後のすべての状態に対する確率分布を示す行ベクトルです。したがって、現在どの状態にいる確率を知っている場合、次のダイスの出目でランダムにタイルを返すことを選択するときの「任意の状態にいる確率」の問いに答えることができます。さらに、ゲームの決定論的な初期状態（すべてのタイルが裏向き）に関する知識を使用して、π₀を定義し、Tと再帰的に乗算して任意の数の遷移（ダイスの出目+タイルの裏返し）後の状態の分布を決定することも容易です。この再帰的なプロセスは、次の閉形式の式としてπₜのために書き直すことができます：
「ボックスを閉める」をモデル化するマルコフ連鎖は、勝ちと負けの2つの最終状態があり、一度入ると出ることができない（吸収状態とも呼ばれる）ことが分かっています。したがって、すべての状態にわたる分布が有限回の遷移後に2つの状態に収束することが確認できます。直感的には、「ボックスを閉める」の場合、プレイヤーのターンは「ボックスを閉める」か、それをしないことで終わる必要があり、したがって1つのターンでのプレイヤーの動きの回数には有限の制限があります。
この上限を見つけるために、次のダイスの出目ごとにタイルを1つずつ裏返す動作が続き、タイル「1」が直立状態の場合、次のダイスの出目で「ボックスを閉める」ことができないという状態になるまでの最長のターンを考えます。このアクションの連続は、合計で9回の動きを必要とします。全体としては9枚のタイルがあるため、t ≥ 9として、πₜを計算することで、勝率を解くことができます。πₜを計算した後、ランダムな戦略でプレイヤーが「ボックスを閉める」確率は、πₜの最初のエントリである「すべてのタイルが裏返されている」状態に対応しています（S₀）。また、状態の分布を進化させる再帰プロセスを、分布が収束するまで0から始めて繰り返すこともできます。さらに、この場合にπₜを計算するための高速な方法もありますが、この投稿では説明しません。これらは、吸収状態の存在と遷移行列の特殊な定義を活用しています。以下のリンクで詳細をご覧いただけます：https://en.wikipedia.org/wiki/Absorbing_Markov_chain
Pythonで勝率を計算するためには、科学計算ライブラリNumpyに完全に依存します。まず、タイルの数、ダイスの数、ゲームの状態の数をそれぞれ9、2、513と定義します。
num_tiles = 9num_dice = 2num_states = (2**num_tiles)+1 # ゲームオーバー/敗北の状態に+1を加えるこれらのシンプルなパラメータを使用して、以下に示すように、各状態の集合表現Sᵢを、バイナリ文字列表現を使用して生成することができます。
# すべての可能な状態の表現を生成するtile_nums = [i for i in range(1, num_tiles+1)]states = []for i in range(0, 2**num_tiles): binary_rep = np.binary_repr(int(i), width=num_tiles) states.append([tile_nums[idx] for idx, a in enumerate(binary_rep) if a == '1'])ここでは、Numpyのbinary_repr関数が非常に役立ちます。この関数は整数iを使用して状態のバイナリ表現を生成します。したがって、この文字列内の1の位置を見つけることで、状態iで正立しているタイルを特定することができます。
状態表現を処理した後、次のコードを使用して遷移行列を生成します：
# 遷移行列の生成
transition_matrix = np.zeros((num_states, num_states))
for i in range(num_states):
for j in range(num_states):
transition_matrix[i][j] = compute_transition_probability(i, j)
transition_matrix[i][num_states-1] = 1 - transition_matrix[i][:num_states-1].sum()
assert np.allclose(transition_matrix[i].sum(), 1), "遷移行列が確率的でありません"最後に、遷移行列を使用してこの探求の中心的な問題である、プレイヤーが完全にランダムな戦略を使用して「ボックスを閉じる」確率は何であるかを求めます。これを行うためには、次のようにすべての状態に対する初期分布π₀を定義する必要があります：
# 初期状態分布の定義
init_state_dist = np.zeros((1, num_states))
init_state_dist[:, num_states-2] = 1ゲームは常にすべてのタイルが正立して始まるため、状態に対する分布は全てのエントリーがゼロである長さ513の行ベクトルで、511番目のエントリー（ゼロベースのインデックス）だけが1になっています。これは、511の2進数表現が文字列 ‘111111111’ に対応し、全てのタイルが正立している状態を表しています。
初期分布が定義されたら、「ボックスを閉じる」確率は、t = 9で収束した状態分布を求めるために、πₜ = π₀Tᵗの式を使用して決定できます。再度、tを9と設定できるのは、π₉T = π₉であり、したがってtに9より大きな値を使用することは不必要な計算につながるためです。この目的を達成するためのコードは以下の通りです：
# 勝利確率と敗北確率を計算して表示
t = 9
multiple_transition_matrix = np.linalg.matrix_power(transition_matrix, t)
final_dist = np.matmul(init_state_dist, multiple_transition_matrix)
win_prob = final_dist[0, 0]
lose_prob = final_dist[0, num_states-1]
# 結果を小数点以下4桁で表示
print("勝利確率：{:.4f}".format(win_prob))
print("敗北確率：{:.4f}".format(lose_prob))このコード片では、Numpyのmatrix_power関数とmatmul（行列の乗算）関数を使用して、T₉とπ₉を計算します。これらの結果を使用して、「ボックスを閉じる」確率は、π₉の最初の要素として単純に保存されます。この要素は、正立したタイルのない状態（2進数で ‘000000000’）に対応します。この洞察を使用すると、完全にランダムな戦略を使用して「ボックスを閉じる」ことは非常に困難であることが最終的に分かります（確率値の詳細は以下に報告されています）。
上記のコードとモデルの定式化は、いくつかの修正を加えることで、タイルの数やサイコロの数などの異なるバリアントの「ボックスを閉じる」をサポートするように拡張できます。そのため、以下のようにサイコロの数とタイルの数が変化するにつれた勝率のグラフを可視化しました：
結論
この記事を通じて、「シャット・ザ・ボックス」というゲームに関する質問に答えるためのマルコフチェーンとその特定の応用について探求しました。ただし、私が強調した技術は、一部を改変し、批判的な思考と修正を加えることで、様々なゲームのモデリングに使用することができます。したがって、「ボックスを閉じる」確率が100回中2回だけであるかもしれませんが、確率モデリングを使用してお気に入りのゲームに関する質問に答える際には、より多くの成功を約束します。
特に記載がない限り、すべての画像は著者によるものです。
We will continue to update VoAGI; if you have any questions or suggestions, please contact us!
Was this article helpful?
93 out of 132 found this helpful
Related articles
