SFC『鮫亀』: さめがめ「かんたん」モードの最大スコアを探索するソルバー

こちらは古い版です。新しい版: https://github.com/taotao54321/SameGameSFCSmall2

動作環境

• BMI2 命令に対応した x64 CPU
• RAM 16GB 以上

Linux でのみ動作確認している。

使い方

solve_many バイナリで最大スコアを実現する乱数と手順を求める。 既知の最大スコアは 844。適当に最大スコアの初期値を与えると枝刈りが捗る。

cargo run --example=solve_many --profile=release-lto -- --best-score-ini 500 > many.out 2> many.log

注意

ハッシュ衝突については特に対策していないので、不運な衝突により最適解が得られていない可能性はある(ハッシュテーブル内のインデックス衝突については linear probing で対策している)。 ハッシュ値は 64bit で、初期局面からの状態数は高々数 M 個程度なので、衝突確率は十分低いと考えられるが...。

ゲーム内の乱数は NMI カウンタに依存しているが、盤面生成中にも 1 回 NMI が発生し、そのタイミングには微妙に幅がある。 よって、乱数は CPU サイクルに依存する。 おそらく駒を 39 または 40 個配置した時点で NMI が発生すると思われるので、本ソルバーではそのように仮定しているが、このタイミングをさらにずらす方法があるかもしれない。