算数は苦手なので - 西尾泰和のはてなダイアリー

どうぶつしょうぎの続編。僕の算数力の限界に近づいてきている。で、場合の数の数え上げみたいな作業を人間がするのは間違っていると思ったので

r = Resource(10, "X")
Player = Choice(2)
Mochigoma = Choice(1)

Kirin = Unordered(
    And(
        Or(r.take(), Mochigoma),
        Player))

とか書くと

Or(
    Or(
        Unordered(
            And(Take(Resource(X)), Choice(2))), 
        And(
            And(Take(Resource(X)), Choice(2)), 
            And(Choice(1), Choice(2)))), 
    Unordered(And(Choice(1), Choice(2))))

という展開が行われて(見やすい改行とインデントは手動でつけた)

print Kirin.size({r: r.n}) # -> 223

と簡単に計算結果が出るようにした。Kirin.make_cpp()でC++のコードを吐いてくれるといいなぁ。まだそこまでは作っていない。

で、

Zou = Unordered(
    And(
        Or(r.take(), Mochigoma),
        Player))

print And(Kirin, Zou).size({r: r.n}) #-> 34449
print 223 * 223 #-> 49729

前回、生身の脳の計算力の限界に達して「ゾウもキリンと同様に223あれば十分」で計算したら49729だが、ちゃんと計算すると34449だ。大分削減になるね。展開結果は下のような感じ。

Or(Or(Or(Or(And(Unordered(And(Take(Resource(X)), Choice(2))), Unordered(And(Take(Resource(X)), Choice(2)))), And(Unordered(And(Take(Resource(X)), Choice(2))), And(And(Take(Resource(X)), Choice(2)), And(Choice(1), Choice(2))))), And(Unordered(And(Take(Resource(X)), Choice(2))), Unordered(And(Choice(1), Choice(2))))), Or(Or(And(And(And(Take(Resource(X)), Choice(2)), And(Choice(1), Choice(2))), Unordered(And(Take(Resource(X)), Choice(2)))), And(And(And(Take(Resource(X)), Choice(2)), And(Choice(1), Choice(2))), And(And(Take(Resource(X)), Choice(2)), And(Choice(1), Choice(2))))), And(And(And(Take(Resource(X)), Choice(2)), And(Choice(1), Choice(2))), Unordered(And(Choice(1), Choice(2)))))), Or(Or(And(Unordered(And(Choice(1), Choice(2))), Unordered(And(Take(Resource(X)), Choice(2)))), And(Unordered(And(Choice(1), Choice(2))), And(And(Take(Resource(X)), Choice(2)), And(Choice(1), Choice(2))))), And(Unordered(And(Choice(1), Choice(2))), Unordered(And(Choice(1), Choice(2))))))

もちろんヒヨコもやる。

IsNiwatoru = Choice(2)
Hiyoko = Unordered(
    And(
        Or(
            And(
                r.take(), 
                IsNiwatoru),
            Mochigoma),
        Player))

で、ライオンも含めた計算結果は1,567,925,964。前回手動で計算した結果が6,095,273,976なので74%の削減になったわけだな。ただ、これは「ヒヨコが一番奥にはいない」という条件と「左右をひっくり返して重なる局面は同一視していい」という条件は使われていない。この枠組みでもできなくはないんだな。いま一様な12マスの盤面を一塊で消費されるリソースとして扱っているけどこれをOr(Resource(9), Resource(3))にすればいいのか。

対称性の方はもっと厄介で、まだしっかり考えていないのだけども3x4で左右対称な盤面に駒を1個置く方法は8通りだよね。
区別できる2個置く方法は、1個目が中央の4つに置かれている場合まだ対称性が失われていないので4 * 7、そうでない場合は失われているので4 * 11。
3個置く方法は、「1個目が中央で2個目がそうでない 4 * 4 * 10」「1個目が中央で2個目も中央 4 * 3 * 6」「1個目が中央でない 4 * 11 * 10」…
とうぜんキリンが片方のプレイヤーに2つあったりするとその二つの順序は関係なくなるので…むう。

ここで田中先生のコメントをもう一度読んでみると

「持ち駒でない駒が盤面をしめる効果」だけでは1,567,925,964までしか局面数は減りませんし，「左右の対称性」を入れてもその半分程度にしかなりません．

上で求めた結果も1,567,925,964なのでここまでは同じ結果です。

「初期局面から到達可能な局面」のみをuint32でencodingすることはできないので，それぞれの局面をuint64でencodingして，「初期局面から到達可能な局面」をすべて含んだsorted vectorを作ることにしました．一度出来てしまえば，使用するメモリは2GB程度ですが，作る際にはhash_setを使って13GB程度かかりました．メモリが足りなければ，もっと工夫することも考えたのですが，とりあえず足りてしまったのでそんなに頑張っていません．

これは最初に読んだときにはなぜ1,567,925,964 < 2 ** 32なのにuint32でencodeできないのかさっぱり意味が分からなかったのですけど、それは要するに僕がメモリ2GBのMacBookで動かすつもりでいたので暗黙のうちに「局面からなるべく小さい範囲の整数へencode/decodeする*C言語的な意味でのfunction*を作る」ことを考えてしまったせいですね。8枚の駒が(盤面12ヶ所+持ち駒1) * プレイヤー2、という実装が簡単でスカスカなencodingでも26 ** 8 == 208,827,064,576なのでuint64tには余裕で収まるので、その方法でencodeした到達可能な局面をvectorにつっこんでソートすることで「局面からなるべく小さい範囲の整数への*数学的な意味でのfunction*」が得られるというわけですね。なるほど。

hash_setは使ったことがないので詳しくないですけど、名前から想像すると入っているかどうかのチェックがO(1)でできそうな雰囲気なのできっと勝ち局面のhash_setと負け局面のhash_setを作るのでしょう。

「局面からなるべく小さい範囲の整数へencode/decodeする*C言語的な意味でのfunction*を作る」というアプローチを押し進める意味でもこのライブラリにさっさとC++のコードを出力する機能をつけるべきですね。

ソースコードを一応リンクしておく: http://svn.coderepos.org/share/lang/python/retrograde/mapgenerator.py
なんかいつの間にか正しい値が出なくなっている！なにやってるんだテスト書け自分！

Unorderedは子ノードの名前を書き換えたがるからやっかいだな、と思ったけども、落ち着いて考えればレンダリング時に参照するためにコンテキストを渡しているんだからそこにsuffixを入れればいいんじゃないか。