daruma3940の日記

理解や文章に間違い等あればどんなことでもご指摘お願いします

A*craftにっき

内容。
ロボットの状態は（座標、向き）で指定される。ロボットが同じ状態を取らないように床に矢印を置いてロボットの行動を指定していく感じ。

問題を見る。
そうだよこういう問題を待ってたんだよ！！（良い順位を取れるとは言っていない）

ロボットを動かしたとき動作停止する場所を調べ、その一つ前に違う方向の矢印を置くというのが基本的な方針。

どの方向の矢印を置くかは何パターンかあるので最善を求めるためにそれぞれのロボットについて順番に深さ優先探索。
DFSをするロボットの順番はnextpermutationで変えながら。

深さ優先探索では上手くスコアが伸びないケースもあるのでその場合はビームサーチ。

というか実際は最初にビームサーチを思いついてそれで上手くいかないケースを補うために深さ優先探索を使ったんだけど。

深さ優先探索とビームサーチは盤面によって使い分けたが、本番のテストで使い分けが上手く行かない可能性もあってここが怖かった。

というかビームサーチはHyperSonic向けみたいな感じ（そうか？）。

あと動作停止する場所に矢印を置くだけではHyperSonicでスコアが全然稼げなかったので動作停止した場所に一番近い、通過した交差点にも矢印を置くようにした。

もう少し細かいこともしてますがそれはまあ…はい


今回はメリハリをつけて参加することにした。
あんまりだらだら時間をかけてみても疲れてくると結局はパラメーター調整するだけとかの闇落ちムーブしかできないんで。
というかだらだら参加する時間はなかった。
パラメーター調整とか、高速化とかはほとんどしなかった。やってもよかったんだけどもっと本質的なところで戦いたかった。（まあいうてそんな本質的なことはできなかったが）(パラメーターを変えることでどう結果が変わるのか見て考察をするのは許してほしい)
（というかそういう守りに入った戦い方をしても大してスコアは伸びず、攻めた戦い方をする人に抜かされるだけなので）
ヘトヘトだけど爽やかなお気持ち（良いスコアを取れたとは言っていない）

どんどん最終順位表が完成してくるのドキドキしていいですね。
一位はtourist。
というか時間計測をどこから開始すべきかがあんまり良く分からんかった。





これ絶対焼けないでしょと思ったけど焼けるの..........
というかTCO MM2018 round2みたいな問題が焼けるのならこの問題も普通に焼けるよなぁ....（touristのforum postを見ての感想）

        • フォーラムを読んで

www.codingame.com

まずは一位tourist

半分の時間で大きな焼きなましをする。
もう半分の時間でちいさな焼きなましをする
最善解からランダムに5*5の正方形サブグリッドをとってきて、固定された回数のイテレーションでSAをし矢印を配置しスコアが上がるかどうかを試す
これはTCO MM2018 R2でeldidouにおそわった。

そういえばMM100でもサブグリッドを撮ってきてそこで焼きなますということ上位の人はしてたな...もしかして典型か？
自分の典型にしていこうな

大きなSAで矢印を置くセルの集合を8近傍に空白以外を持つセルに限定した。
これらのセルは将来的に矢印が置かれる可能性が最も高い。

それは確かに気が付いていてだから通過した交差点にも矢印を置くようにしたというのがある
しかし言われてみれば気づいていたという程度だな。

2位 eldidou

SAをつかった。しかし直接矢印を弄るのではなくわっかの集合を用いた（開始時点では空集合）

焼きなましとしては、ある状態から別の状態へ移動するためにサイクルの集合に別の小さいサイクルを追加した。
もし端点が2回存在した場合それはとりのぞいたした。（なのでこれは別のサイクルとxorをとってから追加をした）

この方法の良い点はこれは探索空間をなめらかにできる
つまりこれは1つの良い状態から別の状態へ”””評価関数の低すぎるところを経由することなく”””行ける　焼きなましにとってこれはしばしば致命的になる

悪い点としてはロボットになんとかしてサイクルに入らせないといけない、
またはそのようなことをしてほしい時それによってスコアがとてもわるくなってしまうのでその時はbrute-force敵に解を見つけないといけない

これすごいなとおもうが私が実装してもかなり重い実装になってしまいそうだし
ロボットがちゃんとサイクルに入ってくれ無ければ悲劇でそれは難しそうで手を出しにくいなというのがある.....
というか盤面が一直線だったりした場合それはどう処理するつもりなんだ？別の方法を使うのか？

3位　ClisetAI

単純に制限時間いっぱい焼きなましをした
可能な遷移としては一つセルの状態を変えた
矢印を落ちる方向にはおかない---それ以外の制約はない
スコア関数にペナルティをつけた。ペナルティは8近傍に空白しかないところに矢印を置くことに対するものである
なので端のほうにしか矢印は置かれず間は2回往復される

こちらは矢印を置くセルを限定するのではなくペナルティを与える感じか。
確かに8近傍に何もなくても矢印置くのがいい場合もあるかもしれないしな。
でもtouristのやり方のほうが探索空間が減って、結局いいスコアが出そうな気がするな（実際出てるし）

5位　eulerscheZahl

事前にボードを端から落ちないように埋めておく。それ以外は何も変えない
その後、時間いっぱい矢印の向きを変えたり追加したり、取り除いたりをする
それぞれの変更で1~３個のやじるしを変更して、もし以前のbestと同じぐらい良ければそれを保持する（ちょっと悪くなった場合も局所解に陥らないように保持する）
最初のprefillを変更しながら1sの間にこれを4回繰り返す。
4回のそれぞれにおいて最初の1/3の時間で一つのロボットが最長の道のりを見つけるようにする、普通それはほかのロボットにとっても良い。
スコアは単純にゲームのスコアを用いる
他人に比べると私のシムレイションは遅い

探索空間を削減するためにいくつかの場所には矢印を置かないようにする
長い廊下の途中には矢印を置かない。
矢印が向かい合わないようにする
シムレイションにおいて、最初のロボットに矢印を再配置することを許した、これは180度ターンによるループを妨げる

リプレイを見るとほとんどの矢印が境界に置かれていることがわかる
なのでやじるしを変更するときにそれらを考慮に入れる：：
もし我々が調整したいセルが隣にプレセットの矢印、落ちる場所を持っていない場合、ほとんどの場合その場所の矢印は消すことになる
そうでない場合、矢印はランダムにとる

いくらかのマップはいくつかの領域に分けられる。
それらを発見するためにWFSでロボットがどれだけの領域にたどり着けるかを確認する
2つのロボットが任意の2つの空セルを共有していたとこそれらは同じ構成要素(たとえそれぞれの開始地点に到達できなくても)
構成要素たちは重なる可能性もある、しかしそれはプレセットされた矢印の受けだけである
異なる構成要素は独立して最適化される
これはよりハイスコアを与える

そうか確かに複数のロボットが同じルートをたどっているケースが多かったことは気づいていた。
だから最初のロボットに時間をかけるようにすればほかのロボットにも良いのか。

そしてマップの領域を分けるのもなるほどという感じだなぁ。
subgridに分ける方法と領域を分けるの組み合わせるとよさそうな感じがする。