読み切りコスト

id:Voluntasに出された宿題。最中限を読み切るのにかかるコストを計算する。

最終ラウンド、自分の手札は5枚、そしてまだオープンされていないカードが11枚ある。自分の手の出し方が 5P3 通り。自分以外の手の出し方が 11P6通り。

>>> def p(n, m):
...     result = 1
...     for i in range(m):
...             result *= n
...             n -= 1
...     return result
... 
>>> p(5, 3)
60
>>> p(11, 6)
332640
>>> _ * 60
19958400

よって最初のターンで「最終ラウンドに出されうるすべての手のパターンをなめて最も勝つ確率の高いカードを出す」の「すべての手」はだいたい2千万件。C++で書いたこれを読みきるプログラムを2.4GHz Core2DuoのMacBookで走らせると4秒程度。特に並列実行するようにしてはいないのでコアは片方しか使ってないだろうから、半分に割って分担するだけでも2秒にはなるのかな。

第4ラウンド、自分の手札は8枚、まだオープンされていないカードは17枚ある。8P3 * 17P3 = 2994001920。最終ラウンドの読み切りの150倍。単純計算で10分。ただしもちろん例えば「第4ラウンドをに出されうるすべての手のパターンをなめて最も真ん中に入る可能性の確率の高いカードを出す」の計算だけでこれなので「それをプレイした後の残りのカードでは最終ターンを持ちこたえられないぞ」とかがわからない。最後まで読み切るならこれに掛ける2千万。単純計算で19億年。あってる？

第3ラウンドだけを読む場合のパターンの数は71955021600。だいたい4時間。3ラウンド以降全部の読み切りには宇宙がいくつか必要。

というわけでAmazonECでいくらかかるか見積もる、って宿題だったけど、無理だろJKということでファイナルアンサー。Erlangで、とかHaskellで、とかいうレベルの問題じゃない。方針自体を見直す必要がある。

ウェブアプリで負荷が30億倍に増えるなんてことは(人数の2乗のオーダで負荷が増えるとかでもないかぎり)考えにくい。ユーザが2人からいきなり60億人に増えたりしない。でもこういうゲームの手の読み切りは読む深さをちょっと増やしただけで平然と何十億倍の計算量になる。とてもおそろしい。