例によって例のごとくpoh5+を続けているが、最短ステップクリアが出来ていない。
CASE3と4がタイムアウトしてしまう。いろんな手法を試したが全然間に合わない。
なおC#の限界時間は4秒である。
ここで原因を考察する。
反復深化深さ優先探索
再起によりメモリ使用を抑えられるのが利点。
評価関数の調整で近いところまで行けるがCASE3が69、CASE5が60となり最短ステップにならない。
評価値による計算打ち切りは時間制限をクリアするために必須である。
A*(未実装)
メモリ使用量を推測するとオーバーするので却下。速度面も期待できない。
ハッシュと重複排除
64bitの完全ハッシュ化で排除しようとしたがメモリ不足で断念。メモリが足りる間はかなり高速化できる。
逆方向探索
終了局面から20手程度全パターンを手順とともに記録してその盤面が現れた時点で終了するようにする。
しかし、反復深化で評価値による打ち切りを入れると最短にならない可能性があるので失敗した。
幅優先探索(未実装)
メモリ不足。どう考えても足りない。
(反復深化)山登り法
CASE3は評価関数が悪くなる方に移動しないと最短になる手順を発見できないので逆効果ですらある。
そうでないCASE5なら最短を見つけられる。