Marathon Match 148 Frogs 参加記
問題
方針
各カエルの行動をなるべくコインが集まるように焼きなましで決定する。
提出コード
焼きなましによる行動探索
各カエルごとに「このターンに移動する方向」の情報を持たせ、任意のカエルの移動方向を変更させながら一番コインを集めるような移動パターンを探索します。
任意のカエルの移動パターンを 1箇所ランダムに変更する
変更したあとの行動を実際にシミュレーションして評価が良くなっているかどうかを確認する。変更範囲としては6ターンを先読みしています。
行動の評価
序盤は下の方に移動、中盤はコイン集め、終盤はビーチに戻るを基本行動として行動を評価していきます。
評価項目
- 序盤は下の方向に移動するように評価
- 池に落ちる (-9999)
- コイン
- 下の方にあるコインの評価を高くする
池ポチャ確定回避
6ターンしか先読みしてないので「この先どう移動しても池ポチャしていまう」という状況でも生存判定をしてしまう可能性があるので、そうなるパターンをある程度列挙して回避するようにしています。
同じ方向に流れる行が 3箇所連続している中心部分がその対象となります。
行動範囲の制限
スタート地点に戻ってこないとスコアにならないので時間経過で行動できる盤面の範囲を制限する。
少しずつ行動できる範囲を狭めていく。（移動できなくするというよりはそこに移動した時に評価値を下げる。そこでコインを取得しても評価しない等）
基本的には残りターンが 4 * H を切ったら徐々に範囲を狭めていく。
LOG の先読み
基本的にはスライドした時に出現するオブジェクトは水で固定しているが、以下のパターンでは別のものを生成する。
確定で LOG が出るとき
既に水が KW 個出ている場合は次のオブジェクトは確定で LOG なのでそれにする
KW = 1 の場合
水が 2個連続する可能性はないので次は LOG で確定
1マススライドする余裕がある場合に確実に移動できる場合
KW = 3 とした場合に、次にくるオブジェクトが水か LOG かわからない状態があるとします。
LOG の場合
水の場合
水が来た場合は左に 1マス移動すれば次は確実に LOG が来るので移動することができます。
このように今連続している水の数が KW - 1個の場合に「横に 1マススライドできる場合だけ移動できる LOG」生成します。
感想
1箇所を変更するとあとの行動に大きく影響するので焼きなましはあまり良くなかったかも。上位はビームサーチだったらしいけどここまでコインの探索効率変わるのかと思った。「とりあえず試す力」みたいななのが落ちている気がする。
