CodinGame Spring Challenge 2023 解法まとめ
-
- いいね！0
takumi152💉💉💉💉
@takumi152
やったこと ・各資源をできるだけ少ないのアリの数で取れるような配置をBFSで求めて、それをアリの移動先とする ・取りに行く資源の種類はルールベースで決める ・ビーコンの置き方は焼きなましで求める。移動先と移動後のアリを貪欲にマッチングさせたときの距離の総和を評価関数とした
2023-06-05 17:18:25
MON.T+α
@montplusa
方針 1.重要度の高い順にこのターン狙うポイントとそれらをつなぐ道を貪欲に決める あとは時間いっぱい2~3をやる 2.アリの合計数と同じだけ道上にランダムに置く（選出確率はこれまでの最善の置き方にほぼ比例させる） 3.移動を計算、移動後のアリの位置を手作り評価関数に突っ込む
2023-06-05 17:10:50
七枝
@tech_nanaeda
各ターンの方針は 1. 卵かクリスタルへの良さそうなChainを選び確定する。 2. 蟻を使い切るまで1を繰り返す。 3. 次のターンに蟻のいるべき場所を最小費用流と山登りで決める。 4. ビーコンの初期配置を気合の入ったヒューリスティックで決める。 5. 時間切れまでビーコンの位置を山登る。
2023-06-05 17:18:32
七枝
@tech_nanaeda
卵優先かクリスタル優先かはよくわからないから諦めた。探索しないと答えでなそうだったし探索は方法がわからなかった。1ターンかけて卵をとってもクリスタルを取り切るターン数が2ターン以上減らなかったらクリスタル優先という方針を取ったけど、ほとんどの試合で出遅れてる。
2023-06-05 17:37:21
しゅんぴー(Shun_PI)
@Shun___PI
基本的にはビーコン配置を焼きなまししてシミュレーションするだけ 評価関数は取得した資源の価値の自分ー相手 をターンごとに減衰する重みを掛けながら10ターン分 卵の価値を資源の残り数÷自分の蟻の数に比例する形で決める ループは場合によっては10回とかしか回らなくて全然探索できず
2023-06-05 17:15:50
kahuka
@kahuka0005
こどげ方針 1.目的地までの経路はすでにアリがいるセルが優先されるようにBFSで決定． 2.目的地と各セルに置くビーコン数を山登りで決めて4ターン分シミュレーション． 3.スコアは獲得するクリスタルと卵の数で計算．序盤は卵，終盤はクリスタルに重きを置く．
2023-06-05 17:29:30
ボンド@競プロ
@bond_cmprog
こどげお疲れ様でした〜 取得した🐜の卵の個数によるルールベース 15%未満:卵のみ:卵のマスの総数/2+1 30%未満:両方:卵・クリスタルマスの総数/2+1（卵優先） それ以上:両方:卵・クリスタルマスの総数/2+1 狙うマスはダイクストラで近い順、距離関数には1/(そのマスにいる自分の🐜の数+1) 以上（え？）
2023-06-05 17:01:59
ツカモ
@tsukammo
コドゲSpring2023お疲れ様でした。 ・各ベース毎に貪欲で決定 ・卵を一定獲得しつつ相手と自分の位置が近い資源から順に取る ・各ベース毎に最小全域木を作る ・その他細かい例外挙動を埋める
2023-06-05 17:37:56
ツカモ
@tsukammo
あ、ビーコンの置き方はちょっと変なことしてるかも。基本は作った最小全域木に添って置くんだけど、同じ重さじゃなく、先端を重くしている。
2023-06-05 17:41:30
ヴァル
@ValGrowth
コドゲ春2023 １．目的地をルールベースで決めて、いっぱいBFSして経路を決める ２．クリスタルや卵をいっぱいとれるかつ、１で決めた経路の近くにアリが行くようなビーコンの置き方を山登りで決定 です。
2023-06-05 17:07:56
ヴァル
@ValGrowth
山登り ・ビーコン配置を山登り ・評価値は序盤はとにかく卵を、中盤以降は目的地に定めた場所から採ったクリスタルを高く評価 ・自分と相手を交互に山登り（これはFallChallenge2022でも同じことをした）
2023-06-05 17:16:26
ヴァル
@ValGrowth
目的地の決め方 ・最初５ターンぐらいは卵優先 ・それ以降は中間地点付近のクリスタルを優先 ・自陣に近いクリスタルは後回しにする（ただし自分より相手のほうが近づいている場合は守りに行く） ・↑こんな感じで優先順位を決めて、大事な目的地から順に拠点に経路をつなぐ
2023-06-05 17:12:59
ヴァル
@ValGrowth
シミュレーションを速くするテク ・AttackChainと卵取得・クリスタル取得はそれぞれダイクストラ法で書ける ・アリが目的地に向かって移動する方向は「セル[i]からセル[j]への最短経路の最初の１歩目リスト」を全部１ターン目に作っておいたら一瞬で求まる
2023-06-05 17:29:23
ヴァル
@ValGrowth
木の末端にビーコンいっぱい置いてアリを向かわせるやつ試してないんだけど、２次元空間だと木の他の枝にアリを吸われそうで乱戦で崩壊しちゃうのかなぁって思ってる
2023-06-05 17:54:02
yunix
@yunix91201367
コドゲお疲れ様でしたー。 1. 戦略 リソースがある場所をノードにして、どこをアリで繋ぐかを木として管理しました。エッジはノード間の最短経路をあらかじめ計算しておきました。序盤は卵・敵との中間地点のクリスタルに優先して手をつけます。これで各セルに何匹の🐜が必要か決めます。
2023-06-05 17:45:09
yunix
@yunix91201367
2. ビーコンの置き方 現状と理想のアリの配置の間にマッチングをとって、セル間でどれだけのアリを動かすかを決めました。マッチングは最小費用流で、セル間の移動コストは距離の二乗にしました。これは最大の移動距離を小さくしたいという思想です。
2023-06-05 17:47:25
yunix
@yunix91201367
各セルのアリを最終的にどこに動かしたいかをマッチングをとって決めた後に、次のターンでどこに行かせたいかを決めました。これは基本的には最終的な目的地への最短経路の一歩目です。ただし最短経路が複数ある場合には現在アリが多い方を選びます。
2023-06-05 17:50:00
yunix
@yunix91201367
次にどこに行きたいかが決まるとそれに沿ってビーコンを置いていきます。ここは若干ややこしい工夫が必要で、 a. 各セルにとどまるアリの数だけビーコンを置く b. 一歩移動するアリの数を移動先のセルにビーコンを置く。ただし、aのルールですでにビーコンが置かれていた場合にはそこにおきません。
2023-06-05 17:52:46
bowwowforeach
@bowwowforeach
コドゲ方針 ・次にどのリソースに辺をつなげるかをchokudaiサーチ ・辺上のセルにアリをルールベースで割り当て ・ビーコンの配置を2種類ルールベースで考えてchokudaiサーチにまとめて入れる ・アリは行列を引っ張るイメージでビーコンを置く ・基地2つの場合は総当たり
2023-06-05 17:11:38
bowwowforeach
@bowwowforeach
BFSとダイクストラで目的地が見つかった時点終了するけど、キューを保存しておけばでおけばまた別な目的地への探索が再開できる。アリの移動は大抵は近い場所への移動が多いからグリッド全体計算するより早かった。
2023-06-05 17:43:08