http://codepad.org/Xn1p1UUG
GDD2010のDevQuizのパックマソのアレのコード晒し
C++で自動探索
最初はずっとGAベースで作っていたのだけど、どうも評価関数の設定が難しくて特性がなかなか改善しないので、シミュレータ処理だけ残して残りを全部バッサリ捨てて、シンプルな枝切り付き深さ優先探索にした。
出したLV3の答えは
lkklllkllllkkkkkkkkllllllkkkhhhhhhhhhhhhhhhhhhhjjjhhhhhhhhhhhhhhhhkkkhhhhhhhhhh
jjjjjjjjjjjhhhhjjjlllllkkklllllllllllllllllllllllllkklllllllllkkkkkkhhhhhhhhhhhhhhhhhjjjjjjjjhhhjjjlllllllllllkkllljjll
lkklllkkkjjllllllllllllhhlllllljjjhhhhhhkkkllkkkhhhhllllkkkkkhhllllllkkkhhhhhhhhhhhhjjjjjjjjjjjlllllljjjh
hhhhhhhhhkkkkkhhhhhhhhhkkkkkklllllllllkkkhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
hhhhhhhjjjlllljjjjjjjjhhhhjjjllllllllllllllllkkkhhkkkkkkkhhhhhhjjjl
で553点。
実装は割とシンプルで、490行目まではシミュレータ処理の実装、そこから後が探索処理。
探索方針もシンプルで以下のルールで探索する
・立ち止まり一切不可
・通路では後退しない。つまり交差点から交差点までは一気に進む
↑この2点を決め打つだけで探索空間は劇的に減って速度が上がる。ただしLV1とかLV2は「刈りすぎ」て解の品質が悪くなる(そこそこのスコアでは解けるけど)
・交差点では、まずエサがあればそちらを優先的に探索し、エサがない時は(直前の位置を覚えておき)「正面」「右折」「左折」「反転」の順に探索する。
↑方向が「上下左右」ではなく「前後左右」になっているのは反転の見込みは大抵悪いから。でも深さ優先の全探索では結局反転も評価するので今回のロジックではあまり意味はない(GA使ってた時の名残)
・それ以外はNode::isJunkNode()～Node::getCurrentMaxHunger()のロジックで枝を切る
基本的には「エサを食べていない状態で長時間放浪すると諦める」というもの。
一応工夫っぽいポイントは「(エサが豊富な)序盤では少しエサを食べられない時間があるとすぐ諦める」というところ。序盤の分岐は探索範囲が爆発する元なので、空白地をウロウロするルートは早期に切り捨てる。
微妙に変な式になってるところ(634行目とか)あるけど試行錯誤の途中で投げ出したせいです。。。
このコードにする前に、GA(遺伝的アルゴリズム)とか学習無しの単純乱択も試した。
その時は最終的に遺伝子を「交差点で曲がる優先順位」と定義し、表現型では死んでもバックトラックするような仕組みにしていた。つまりどんな遺伝子も、クリアするか700歩歩いて餓死するかのどちらかを意味する。
GAは色々試したのだけど、とにかくチューニングが難しい(初期収束が荒ぶりすぎ……)し、評価関数の設定といい表現型の定義といい、枝切り法に比べると難度は凄まじく高い。万能アルゴリズムであるメタヒューリスティクスの難しさを痛感させられた。
正直GAでLV3が解けた人ってかなり少ないんじゃないだろうか。解けるレベルの人は早期にor最初からGAは捨ててそうだし。
あ、ちなみにGAでも乱択でも一応答えは出ました。GAで517点、乱択は460点、くらいはすんなり出る。