
多人数のICM計算

chatGPTがどのように計算をしているかの説明です
96人の ICM を「正面から」解こうとするとどうなるか
プレイヤー数を (n) 人とすると、ICM の定義は
・全ての順位パターン(最大で (n!) 通り)
・それぞれのパターンが起こる確率
・そのときにもらえる賞金
を全部掛け合わせて足し上げる、という形になっている。
今回のように 96人 いると、理屈の上では
という数の順位パターンを足し合わせることになる。
10¹⁵⁰というのは、
・地球上の砂粒の数(およそ 10²⁴〜10²⁵)をはるかに超え
・宇宙にある原子の数(およそ 10⁸⁰)よりも、さらに 10⁷⁰倍くらい大きい
レベルの「常識では扱えない超巨大な数」だ。
たとえば世界最高クラスのスーパーコンピューター El Capitan は、理論上およそ毎秒 (1.8\times10^{18}) 回の計算ができるとされている。
仮に、「順位パターン1通りあたり計算1回」で済む、メモリアクセスは一切無視という超・超楽観的な前提で見積もっても、
くらいかかるオーダーになる。
宇宙の年齢(約 10¹⁰ 年)の、さらに 10¹¹⁴倍くらい。
物理的に絶対ムリという世界だとわかる。
再帰式・動的計画法を使っても「指数爆発」は避けられない
実際の ICM 実装では、同じ形の部分問題をまとめるために
・再帰式
・動的計画法(Dynamic Programming, DP)
を使うことで、96! 通りすべてを愚直に列挙することは避けている。
それでも計算量自体は 指数オーダー(ざっくり (2^n) の世界) からは逃げられない。
(n=96) として、これもまた「1サブ問題=計算1回」という超楽観で見積もると、
の計算が必要になる。
これを先ほどの El Capitan が毎秒 (2\times10^{18}) 回計算するとして割ると、
しかも実際には 1サブ問題あたり何十〜何百回も演算するので、
現実的には もっと長い時間 が必要になる。
研究レベルの ICM でも、
・10人程度までは厳密 ICM
・それ以上の人数は Monte Carlo ICM(モンテカルロ近似)
に切り替える、といった方針が普通に採用されている。
多人数を「きっちり厳密に」やろうとすると、計算が重すぎて話にならないからだ。
だから 96人 ICM は Monte Carlo で近似する
・スタック配分を入力すればICM の確率ルールに従ってトーナメントをランダムに何十万回もシミュレーションする
・その結果から各スタックの賞金期待値(ICM $EV)を推定する
という Monte Carlo ICM の形で計算している。
chatGPTが中でpythonのコードを書いて目安として使える精度で計算結果だけを教えてくれる。(同スタックを入れると計算結果が微妙にズレます。)
スタック配分も自然に近い形でchatGPTが作ってくれます。