北国ぺんぎん

囲碁に将棋に土いじり・・・
完全に趣味はセカンドライフ世代と同じっす。
若さはどこに消えたんっすかね?
どうもぺんぎんっす( ◎v◎ )


[完成形からN手の盤面]をあらかじめ作ることによる
効果についてっす。前回の続きっす。

反復深化探索の時間計算量はO(b^d)っす。
STEP2は指数部dを小さくする狙いがあるっす。
ただし、終了条件を満たすかどうかの判定に
時間的なコストがかかるっす。
つまりは底bが増大してしまうっす。
損なのか得なのか、Nの分岐点とかは分かんないっす。

STEP3は反復深化探索の深さ制限値を更新するときには、
また最初から探索をすることに目をつけたっす。
浅い探索は何回も繰り返されるわけっすね。
そこであらかじめ、この繰り返される部分の結果を
保存しておくことによって、時間短縮を狙ったっす。
効果は一応あるっす。
でも、dが大きくなると、ほとんど無視されるかもっす。
深さ制限値の更新が何回も起きたとしても、
[更新回数]*[浅い探索の展開コスト]っすから、
たかが知れているっす。


提出したものには書いてないっす。
ウマイやり方が分かんなかったっす。
自分はN=5までしか入れられなかったっす。
64KB制限はキツイっす・・・