私はボードゲームStackExchangeでこの質問をしました。どのキャラクターが、ボタンメンの試合に勝つ可能性が高いかについてです。それで、妥当な時間内に質問に答えるための具体的なアプローチについて考えさせられました。ゲームのルールはかなり単純です。
ゲームの開始時に、各プレイヤーは多面体のサイコロを振ります。
ダイスが最も低いプレイヤーが最初になります（タイは次に低いダイスを使用します）。
プレイヤーは、2つの可能な方法で敵の死を捕らえることができます。
1）パワーアタック：1つ以上の値を持つダイスを使用します（その後、そのダイスをリロールします）。
2）スキルアタック：対戦相手が死ぬのとまったく同じ複数のサイコロを使用します（キャプチャで使用されたすべてのサイコロをリロールします）。
3）プレイヤーが敵の死を捕らえることができない場合、彼らは合格しなければなりません。
サイコロがなくなるとゲームは終了します。各プレイヤーは、対戦相手からキャプチャしたdXごとにXポイントを獲得し、残りのサイコロごとに0.5dXを獲得します。（つまり、対戦相手のd4、d4、d10、d12、d20をキャプチャし、それでも自分のd20を持っている場合、スコアは（4 + 4 + 10 + 12 + 20 + 0.5 * 20）= 60ポイントになります。）
強引な エイビスキャラクターは、d4、d4、d10、d12、およびdXをロールします（dXはd4、d6、d8、d10、d12、またはd20です）。これは、最初のロール後に最大（4 * 4 * 10 * 12 * 20）38,400の状態があることを意味します。イアーゴーのキャラクターは最大4d20（「dX」スイングダイにd20を使用する場合）で、160,000の開始状態が可能です。合わせて、それは61億4400万の可能な開始状態につながり、事態はここから悪化します。最良の動きを整理しようとする知性がなければ、考えられるすべての動きを試す必要があります。最悪の場合、プレイヤーはスキル攻撃ですべてのサイコロを振り直す可能性があります。ゲームが終了する前に最大8回のキャプチャを行う必要があるため、各サイドのパワーアタックで1つのd20をリロールしても、合計されます（20 ^ 8 = 256億）。強引な方法は、157以上のQuintillion以上の可能な状態を評価することにつながる可能性があります。これは実行可能ではありませんが、より良い方法があります。ブルートフォースメソッドは、同じゲーム状態を複数回再評価していました。
マルコフ連鎖 最終的にエンドゲームに移行する一連の可能な状態をゲームで見ると、ゲーム内のある状態から別の状態に逆方向に移動する確率を評価し、最終的に各キャラクターが勝つ確率に到達できます。ゲームの開始。ゲームは（比較的言えば）いくつかの可能な状態でのみ終了します。1人のプレーヤーにはサイコロがなく、もう1人のプレーヤーには自分のサイコロの組み合わせが残っています（以下の例では、dXスイングダイスがd20として選択されています。これは現在の概念実証にすぎないので、心配しないでください。このサイコロはゲームごとに異なります）。
エイビス：d4 | d10 | d12 | d20
エイビス：d4、d4 | d4、d10 | d4、d12 | d4、d20
エイビス：d4、d4、d10 | d4、d4、d12 | d4、d4、d20 | d4、d10、d12 | d4、d10、d20 | d4、d12、d20 | d10、d12、d20
エイビス：d4、d4、d10、d12 | d4、d4、d10、d20 | d4、d10、d12、d20
エイビス：d4、d4、d10、d12、d20
イアーゴ：d20
イアーゴ：d20、d20
イアーゴ：d20、d20、d20
イアーゴ：d20、d20、d20、d20
これらのゲーム終了状態が各プレイヤーに対してスコアリングされ、その状態が各キャラクターの勝ち負けであるかどうかが判断されると、「最後から2番目」のゲーム状態を調べることができます。同様の方法で、各「最後から2番目」のゲーム状態がエンドゲーム状態の1つにつながる可能性についてオッズを決定できます。いくつかの簡単なスプレッドシートの計算により、約99億のゲーム状態の結果が得られます（ゲーム状態の勝ち負けの性質を保存するだけでよいので、この情報を1ビットにまとめることができるはずですよね？）。これは、保存/評価するゲームの状態の数が克服できないほどではないようです。
マルコフ連鎖を使用して、妥当な時間で、かなり安価なハードウェアを使用して、どのキャラクターが優れているかを答えることは可能ですか？
この種の問題を解決するためのより良い方法はありますか？