はじめに
そもそものきっかけは、ベイズ推定とは何？という程度の知識レベルで、AtcoderのAH030を解こうとすると、適当なロジックで試行錯誤して、時間を浪費したところで大してスコアも伸びずギブアップするだけなので、ゼロから手を動かして知識を得たい。
一方で、従来型の独学での自習は限度があるので、NotebookLMを使うとどのようなメリットがあるのか試してみようかと思いました。
- NotebookLMを初めて使っての気づき 【NotebookLM編】
- AHC030に関する気づき
- 1.機械的にjavaへ移植
- 2.ランダムな占い
- 3.相互情報量を最大化する占い
- 4.事後確率とgiveup改良
- 5.数を絞ったランダムなプール【この記事】
- 6.なんちゃってテキスト変換ツールでcppソースをjavaソースに変換
- 7.java完成版
とっても参考になる題材はこちら→AHC典型解法シリーズ第3弾「ベイズ推定」
Zobrist Hashによる重複チェック
まずは、M=2の総当たりのランダムな占いにおいて、Hashによる重複チェックを行う。
なお、ここで、問題を見つけてしまった。
手作業でニコイチでソースをマージする。
- Xorshift.next()を追加（内部でrand.nextLong();）
- OilLayout.hashを追加
- OilState.hashesを追加
- State.hashを追加
- State(Input input)にてoilStates[i].hashes[ij]とhashを初期化
- State(Input input)にてvolumes = input.getVolume(topLefts);を初期化（なぜかvolumesを入れてmoveToで差分更新していなかった）
- State.moveToでhashを更新
- solveでMap hashLikelihoodを使い重複チェックしながらpoolに追加
- 毎ターンプールサイズを出力
以前の03/04_all_pool_random_divination.javaをseed20で実行すると、
0031: pool.size()=360 total=41
0042:0 pool.get(0).pxIfR=0.002777777777777778
：
0070:13 pool.get(0).pxIfR=0.8312959909236446
0071:!Complete
Score = 1858524
今回修正した04_all_pool_random_divination.javaをseed20で実行すると、
0029: pool.size()=360 total=41
0040:0 pool.size()=360 pool.get(0).pxIfR=0.002777777777777778
：
0074:18 pool.size()=360 pool.get(0).pxIfR=0.840085799009986
0075:!Complete
Score = 2592522
ここで結果が変わるのは想定外だったが、Hashを発行する際に乱数がかなり回っているので、そのためかと。確認したいのは、プールサイズが360で変わっていない。
次に、油田の形が重複するデータとして、2x2マスが2つ並んでいるやつ。n=10版を作った。
10 2 0.01
4 0 0 0 1 1 0 1 1
4 0 0 0 1 1 0 1 1
1 1
1 1
0 0 0 0 0 0 0 0 0 0
0 2 2 0 0 0 0 0 0 0
0 2 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
以前の03/04_all_pool_random_divination.javaを実行すると、
0036: pool.size()=6561 total=8
0054:0 pool.get(0).pxIfR=1.5241579027587258E-4
：
0117:10 pool.get(0).pxIfR=0.9816729853555295
0118:!Complete
Score = 1424334
今回修正した04_all_pool_random_divination.javaを実行すると、
0033: pool.size()=3241 total=8
0047:0 pool.size()=3241 pool.get(0).pxIfR=3.08546744831842E-4
：
1519:200 pool.size()=3241 pool.get(0).pxIfR=0.7554389296700191
1519:giveup by query
1520:!Abort
Score = 1000000000
ここで、Hashの問題を見つけてしまった。やれやれ。
プールサイズの理論値を計算する。
油田A、油田Bとし、油田Aを左上（lefttop=0）からlefttop+1していくことを考える。
油田Aがlefttop=0のとき、油田Bもすべての候補(n-maxi)*(n-maxj)=9*9=81通り。
油田Aがlefttop=1のとき、油田Bはlefttop=0以外の80通り。
最後、油田Aがlefttop=88のとき、油田Bはlefttop=88のみ1通り。
lefttopの数が変なようで、lefttop=8の次が9をスキップし次の行のlefttop=10となる。
このため、1から81までの和なので、81*82/2=3321あるはず。
これが3241=3321-80しかない理由が、油田Aと油田Bが同じlefttopに置いたとき、Hashは同じ座標に同じHash値なので、XORを取ると0になる。つまり、lefttop=0やlefttop=11は別の組み合わせだが、Hashはすべて0で、同じlefttopの組み合わせは81通りのうち、1つだけ早いもの勝ち(lefttop=0のみ）が登録できた。
AIチャットに聞こうと思ったら、先にXOR取ると0になるぞといきなり警告されて、回避方法としては、XORでなく、加算減算で計算が一般的らしい。
またHashの衝突が気になるのなら、異なる乱数テーブル２つ用意してダブルハッシュを比較すれば、両方が衝突する確率はほぼないとのこと。乱数テーブル１つで、XORのハッシュと、加算減算のハッシュをダブルハッシュにしてもよいなど。
XORと加算減算の違いは、State.moveToの
hash ^= os.hashes[topLefts[oilId]] ^ os.hashes[newTopLeft];
を
hash += -os.hashes[topLefts[oilId]] + os.hashes[newTopLeft];
に変えるだけ。
これにより、プールサイズが理論値になり、無事回答できた。
0032: pool.size()=3321 total=8
0047:0 pool.size()=3321 pool.get(0).pxIfR=3.0111412225233364E-4
：
0087:9 pool.size()=3321 pool.get(0).pxIfR=0.8867084302762236
0087:!Complete
Score = 1228344
尤度が低いものを削除
今度は相互情報量を最大化する占いの尤度が低いものを削除を組み込んで比較してみる。
// 尤度が低いものを削除
while (pool.size() > 1 && pool.get(pool.size()-1).pxIfR < 1e-9) pool.remove(pool.size()-1);
以前の04/03_all_pool_hill_climb.javaをseed25で実行すると、giveupする。
0034: pool.size()=5544 total=27
0050:0 pool.get(0).pxIfR=1.8037518037518038E-4
0469:1 pool.get(0).pxIfR=5.19020929933627E-4
0810:2 pool.get(0).pxIfR=0.0010237791673828513
1157:3 pool.get(0).pxIfR=0.002552500281909218
1467:4 pool.get(0).pxIfR=0.006728824768125
1805:5 pool.get(0).pxIfR=0.00982593047406106
2146:6 pool.get(0).pxIfR=0.007038245739977934
2462:7 pool.get(0).pxIfR=0.011112465663302186
2812:8 pool.get(0).pxIfR=0.04006837741377529
3110:giveup start
Score = 91208916
今回修正した03_all_pool_hill_climb.javaをseed25で実行すると、やはりgiveupする。
プールサイズは減っているが、何も変わらなかった。cppからの翻訳ミスかと思ったら、cppも同じだった。
おそらく慎重なんだろうな。
0033: pool.size()=5544 total=27
0050:0 pool.size()=5544 pool.get(0).pxIfR=1.8037518037518038E-4
0469:1 pool.size()=5544 pool.get(0).pxIfR=5.19020929933627E-4
0818:2 pool.size()=5544 pool.get(0).pxIfR=0.0010237791673828513
1167:3 pool.size()=5293 pool.get(0).pxIfR=0.002552500281909218
1481:4 pool.size()=5293 pool.get(0).pxIfR=0.006728825790503551
1813:5 pool.size()=5024 pool.get(0).pxIfR=0.009825931171782244
2127:6 pool.size()=4852 pool.get(0).pxIfR=0.007038246693423032
2413:7 pool.size()=4778 pool.get(0).pxIfR=0.011112466714789323
2717:8 pool.size()=4512 pool.get(0).pxIfR=0.040068383005350844
2967:giveup start
Score = 91208916
実験として、1e-9を8,7,6・・・と大きくしていく。
1e-8
2843:10 pool.size()=1943 pool.get(0).pxIfR=0.06460004191575443
2939:giveup start
Score = 91536061
1e-7
0036: pool.size()=5544 total=27
0052:0 pool.size()=5544 pool.get(0).pxIfR=1.8037518037518038E-4
0470:1 pool.size()=5544 pool.get(0).pxIfR=5.19020929933627E-4
0817:2 pool.size()=5520 pool.get(0).pxIfR=0.0010237791673828513
1162:3 pool.size()=4225 pool.get(0).pxIfR=0.0025525002868443045
1405:4 pool.size()=4147 pool.get(0).pxIfR=0.0067292628087366035
1661:5 pool.size()=3989 pool.get(0).pxIfR=0.009826491905463057
1908:6 pool.size()=3726 pool.get(0).pxIfR=0.007038922650822594
2122:7 pool.size()=3592 pool.get(0).pxIfR=0.011114235294470984
2352:8 pool.size()=3405 pool.get(0).pxIfR=0.04007104835575847
2538:9 pool.size()=1539 pool.get(0).pxIfR=0.06051955003897106
2618:10 pool.size()=1350 pool.get(0).pxIfR=0.06460313501445415
2688:11 pool.size()=1331 pool.get(0).pxIfR=0.11819659018951836
2753:12 pool.size()=521 pool.get(0).pxIfR=0.16694562302723293
2767:13 pool.size()=164 pool.get(0).pxIfR=0.306460425388413
2771:14 pool.size()=109 pool.get(0).pxIfR=0.3321544330319665
2775:15 pool.size()=80 pool.get(0).pxIfR=0.4729408486688204
2777:16 pool.size()=65 pool.get(0).pxIfR=0.5742595817577878
2780:17 pool.size()=30 pool.get(0).pxIfR=0.9896880511874884
2781:!Complete
Score = 3041963
1e-6
0032: pool.size()=5544 total=27
0050:0 pool.size()=5544 pool.get(0).pxIfR=1.8037518037518038E-4
0475:1 pool.size()=4804 pool.get(0).pxIfR=5.19020929933627E-4
0773:2 pool.size()=4665 pool.get(0).pxIfR=0.0010243093303357036
1064:3 pool.size()=3368 pool.get(0).pxIfR=0.0025528868059521647
1259:4 pool.size()=3118 pool.get(0).pxIfR=0.006734981374648358
1447:5 pool.size()=2949 pool.get(0).pxIfR=0.009835917426024245
1625:6 pool.size()=2657 pool.get(0).pxIfR=0.007049909374305322
1774:7 pool.size()=2549 pool.get(0).pxIfR=0.01114231143744663
1927:8 pool.size()=2452 pool.get(0).pxIfR=0.040125604635978404
2056:9 pool.size()=1011 pool.get(0).pxIfR=0.06052505798696211
2105:10 pool.size()=845 pool.get(0).pxIfR=0.06462942621954898
2147:11 pool.size()=828 pool.get(0).pxIfR=0.11826923844467571
2184:12 pool.size()=368 pool.get(0).pxIfR=0.16717267237997172
2198:13 pool.size()=116 pool.get(0).pxIfR=0.32308575297176856
2202:14 pool.size()=85 pool.get(0).pxIfR=0.4487861572625267
2206:15 pool.size()=78 pool.get(0).pxIfR=0.5867224662803926
2208:16 pool.size()=37 pool.get(0).pxIfR=0.8000052885944788
2209:17 pool.size()=36 pool.get(0).pxIfR=0.7858609041029546
2212:18 pool.size()=27 pool.get(0).pxIfR=0.923072550181568
2213:!Complete
Score = 3862080
1e-5
0034: pool.size()=5544 total=27
0050:0 pool.size()=5544 pool.get(0).pxIfR=1.8037518037518038E-4
0475:1 pool.size()=4050 pool.get(0).pxIfR=5.19020929933627E-4
0724:2 pool.size()=3608 pool.get(0).pxIfR=0.0010281167764561458
0947:3 pool.size()=2415 pool.get(0).pxIfR=0.0026645102950936263
1081:4 pool.size()=2164 pool.get(0).pxIfR=0.006891339832086216
1208:5 pool.size()=1931 pool.get(0).pxIfR=0.011569274018421559
1311:6 pool.size()=1658 pool.get(0).pxIfR=0.01362714975417048
1406:7 pool.size()=1388 pool.get(0).pxIfR=0.016967508204221007
1484:8 pool.size()=1142 pool.get(0).pxIfR=0.026693342263163274
1541:9 pool.size()=798 pool.get(0).pxIfR=0.048518209490712234
1578:10 pool.size()=720 pool.get(0).pxIfR=0.04148009254506219
1614:11 pool.size()=690 pool.get(0).pxIfR=0.04489753394823418
1648:12 pool.size()=632 pool.get(0).pxIfR=0.043500648759633054
1678:13 pool.size()=206 pool.get(0).pxIfR=0.11655445327099342
1688:14 pool.size()=75 pool.get(0).pxIfR=0.2906507171014463
1691:15 pool.size()=48 pool.get(0).pxIfR=0.4762046797301441
1693:16 pool.size()=43 pool.get(0).pxIfR=0.5696291754623107
1695:17 pool.size()=38 pool.get(0).pxIfR=0.40114588786959643
1697:18 pool.size()=37 pool.get(0).pxIfR=0.7275730203859168
1699:19 pool.size()=18 pool.get(0).pxIfR=0.9804587270417274
1700:!Complete
Score = 3597329
1e-4
0037: pool.size()=5544 total=27
0056:0 pool.size()=5544 pool.get(0).pxIfR=1.8037518037518038E-4
0492:1 pool.size()=2989 pool.get(0).pxIfR=5.19020929933627E-4
0670:2 pool.size()=2263 pool.get(0).pxIfR=0.0010186641303384673
0802:3 pool.size()=1390 pool.get(0).pxIfR=0.0025448977232149757
0882:4 pool.size()=1151 pool.get(0).pxIfR=0.004592099382988505
0942:5 pool.size()=1012 pool.get(0).pxIfR=0.007350226325221506
0995:6 pool.size()=721 pool.get(0).pxIfR=0.01347609304491213
1030:7 pool.size()=613 pool.get(0).pxIfR=0.01781007866609905
1060:8 pool.size()=434 pool.get(0).pxIfR=0.04054849616447308
1081:9 pool.size()=388 pool.get(0).pxIfR=0.0328605951229743
1098:10 pool.size()=298 pool.get(0).pxIfR=0.04233221231649026
1112:11 pool.size()=282 pool.get(0).pxIfR=0.05320198798241339
1129:12 pool.size()=145 pool.get(0).pxIfR=0.2080741136916666
1136:13 pool.size()=25 pool.get(0).pxIfR=0.45315695528809
1137:14 pool.size()=17 pool.get(0).pxIfR=0.47116058925443594
1139:15 pool.size()=6 pool.get(0).pxIfR=0.989960427932173
1140:!Complete
Score = 2474705
1e-3
0163:338 pool.size()=1 pool.get(0).pxIfR=1.0
0163:giveup by ans
Score = 1000000000
1e-9,1e-8は慎重すぎて、プールサイズが減らなくて、計算コストがかかる相互情報量が計算できずタイムアウト。
意外にも1e-7から1e-4まで、プールサイズが失敗なく減って、クエリ数が増えるので回答までたどり着けた。
1e-3で、初手で正解をうっかり消してしまって、もう正解のないプール1をひたすら。
数を絞ったランダムなプール
M=2の制限を外して、Hashで重複チェックしながら、ITER = 4000000 / (2 * input.n2)個初期プールを用意し、尤度が低いものを削除しながら、クエリを出していく。
クエリはランダムな占いと、相互情報量を最大化する占いの両パターンで比較する。
なお、Hashの重複チェックのHashMapはt=0のループの前で、過去すべてのHashと比較するものと思っていたが、試しにcpp版を修正したら、恐ろしく悪化したので、ループの都度その時点のpoolからHashMapを作る方法にする。
ランダムな占い
HashMapの位置により結果が異なる例を挙げる。
seed21(N=13,M=2) 毎ターンが勝ち
毎ターンにHashMapを作る。
2271:111 hash.size()=2652 pool.size()=290 pool.get(0).pxIfR=0.8953422711520449
2306:112 hash.size()=2656 pool.size()=282 pool.get(0).pxIfR=0.9049719600600008
2307:!Complete
Score = 12214365
t=0ループ前にHashMapを作る。
2893:139 hash.size()=2688 pool.size()=46 pool.get(0).pxIfR=0.6614191442341186
2930:140 hash.size()=2688 pool.size()=46 pool.get(0).pxIfR=0.6828795690546898
2930:giveup start
Score = 99606991
seed26(N=17,M=3) 毎ターンが勝ち
毎ターンにHashMapを作る。
0482:21 hash.size()=7405 pool.size()=531 pool.get(0).pxIfR=0.8794035307420299
0499:22 hash.size()=7379 pool.size()=263 pool.get(0).pxIfR=0.9313061744935779
0500:!Complete
Score = 1835625
t=0ループ前にHashMapを作る。
2899:128 hash.size()=302940 pool.size()=3 pool.get(0).pxIfR=0.9999117627360962
2927:129 hash.size()=303343 pool.size()=2 pool.get(0).pxIfR=0.9906235404142587
2928:giveup start
Score = 182758496
seed54(N=11,M=4) 毎ターンが勝ち
毎ターンにHashMapを作る。
1735:41 hash.size()=16521 pool.size()=13 pool.get(0).pxIfR=0.9989220293515487
1787:42 hash.size()=16524 pool.size()=1 pool.get(0).pxIfR=0.9999999999985509
1788:!Complete
Score = 9766610
t=0ループ前にHashMapを作る。
2895:57 hash.size()=895075 pool.size()=12 pool.get(0).pxIfR=0.5114560563493408
2994:58 hash.size()=909371 pool.size()=13 pool.get(0).pxIfR=0.6595011851902202
2994:giveup start
Score = 90837000
seed49(N=12,M=3) t=0ループ前が勝ち
毎ターンにHashMapを作る。
2897:61 hash.size()=13652 pool.size()=398 pool.get(0).pxIfR=0.3106162931813486
2945:62 hash.size()=13652 pool.size()=379 pool.get(0).pxIfR=0.2880224805714477
2946:giveup start
Score = 88596496
t=0ループ前にHashMapを作る。
2589:59 hash.size()=149943 pool.size()=1638 pool.get(0).pxIfR=0.8787138306346255
2622:60 hash.size()=149995 pool.size()=949 pool.get(0).pxIfR=0.9636363873333164
2623:!Complete
Score = 7067838
3勝1敗で、毎ターンにHashMapを作るが優勢。理由として、1e-9の条件で削除した候補が実は正解だったため、もう復活できないと見つけられない。
相互情報量を最大化する占い
seed96(N=14,M=3) 毎ターンが勝ち
毎ターンにHashMapを作る。
2734:32 hash.size()=10118 pool.size()=9 pool.get(0).pxIfR=0.9170025778996431
2760:33 hash.size()=10124 pool.size()=1 pool.get(0).pxIfR=0.9999999999999973
2760:!Complete
Score = 9994312
t=0ループ前にHashMapを作る。
2886:34 hash.size()=274695 pool.size()=25 pool.get(0).pxIfR=0.9537910560995514
2911:35 hash.size()=280586 pool.size()=20 pool.get(0).pxIfR=0.8124696451671878
2911:giveup start
Score = 89146797
seed26(N=17,M=3) t=0ループ前が勝ち
毎ターンにHashMapを作る。
2687:4 hash.size()=8206 pool.size()=1139 pool.get(0).pxIfR=0.09200071095497751
2803:5 hash.size()=7955 pool.size()=1148 pool.get(0).pxIfR=0.19942045740523415
2901:giveup start
Score = 143356965
t=0ループ前にHashMapを作る。
2737:6 hash.size()=45013 pool.size()=44 pool.get(0).pxIfR=0.5033156364552246
2754:7 hash.size()=50856 pool.size()=5 pool.get(0).pxIfR=0.9999997705052979
2755:!Complete
Score = 498486
1勝1敗でどっちもどっち。興味深いのが、seed26が、ランダムな占いは毎ターンがよく、相互情報量を最大化する占いはt=0ループ前がよい。いろいろな意味で難しい。
ソース置き場
- 06 数を絞ったランダムなプール
- 04_all_pool_random_divination.java Zobrist Hashによる重複チェック
- 03_all_pool_hill_climb.java 尤度が低いものを削除