CodinGame -Green Circle- 参加記

CodinGame Green Circle コンテストに参加しました。

www.codingame.com

順位は、総合145位、Goldリーグ88位でした。
やった内容と感想について書いていきます。

ルール

例によってツカモさんが解説記事を書いてくれているので*1こちらをご参照ください。
tsukammo.hatenablog.com

今回は特にルール読解がきつい回だったので、メチャクチャ重宝しました。
解説記事が無かったら、読解フェーズで心折れて辞めてたかもしれないです。

最終解法

ルールベースのみって感じでした。 大枠の方針は、良い感じのところを周りつつCIでボーナスを４つ送ることを目指していくって感じです。

もう少し詳しくは、以下のようなルールを入れました。

  • 0,1,5,6,7 を迷惑料を避けつつ巡回
  • ドロー系 => CONTINUOUS_INTEGRATION 8*2 の優先順でスキルを使用。余ったスキル使用枠は possibleMove から適当に選ぶ。
  • 負債２以下でリリース出来る場合は実行。
  • Automated にボーナスが４つ溜まっている場合は、リリース可能なものの内で負債が一番小さいものをリリース。
  • 残り１リリースの状況では、リリースに都合の良い移動先を探すようにする。

解法周りの感想

Twitter のタイムラインの情報をかなり採用しました。共有情報が(たぶん)豊富な日本勢が今回有利だったんじゃないかなとかを思ったり。

ルールベース実装がつらかったので、今回はほどほどのところで打ち切りました。
個人的に、最近は途中で飽きて投げ出し気味なので、なにかもうちょい楽しむ工夫をしなきゃなのかなあとかを思っています。

所感

序盤の印象は、ルールの難解さとかもあってハズレ回かなって気持ちだったんですが、やっていくと当初思ってたよりずっと楽しめました。
ゴールド中位くらいまでは、良い感じのif分岐を１ケース差し込めるだけで割と順位が上がっていく感じがあって、楽しかったです。その先が魔境な感じがありますが。

スキルの強さのバランスが崩れてる感じだった(はず)のとかもあって、ゴリゴリのルールベース回かと思っていましたが、上位勢は結構探索を入れてるっぽくて意外でした。

*1:いつもありがとうございます。

*2:ボーナスのCI

CodinGame Spring Challenge 2022 ~Spider Attack~ 参加記

CodinGame Spring Challenge 2022に参加しました。

www.codingame.com

順位はGoldリーグの1,769位でした。
やった内容と感想について書いていきます。

問題内容

対戦型タワーディフェンスって感じのゲームでした。

  • ３ユニット操作
  • 盤面のブラインド有り
  • 非グリッド（実質）

辺りがクセの強い箇所だったように感じます。

詳しいルールはツカモさんの解説記事*1をご参照ください。
https://tsukammo.hatenablog.com/entry/2022/04/22/010522

最終内容

Gold昇格できるラインでできるだけ軽めの実装を、みたいな方針で作ってました。

大枠の方針はルールベースです。

最初30ターンは、全ユニットがモンスターの発生口近辺に張って、マナ稼ぎをします。
ここの実装は、移動可能範囲に1,000点ランダムプロットして一番敵数を巻き込める位置を選ぶ*2、という風にしました。

それ以降のターンは、DF２人とFW１人に分け、以下の方針で動かしました。

  • DFの１人は、自ゴールから距離約600の位置に固定配置して、WINDを打ちまくる。
  • もう一人のDFは、自ゴールから距離約5,000のエリアでマナ稼ぎ。
  • FWは、相手ゴールから90度に引いた直線上を距離400~3,500の範囲でランダムウォークしながら、見つけたモンスターを敵陣に向けてWINDする。

感想

今回はルールベースマシマシ実装のつらさからか、いまいち気持ちが乗らなかったのもあってGold昇格のタイミングで切り上げてしまいました。
ルールベースや非グリッドはあんまり好きじゃないかなあ*3とかを感じたり。
次回は無理なくゲーム木探索できるような問題が出て欲しいですね。今年は秋は開催されるのでしょうか？

今回、コドゲでは初めて Rust で参加してみました。
AHCとかだと、トレイトやポリモーフィズム周りの機能をあんまり使ってこなかったのですが、今回その辺りを勉強するきっかけになって良かった気がします。
Rust 開発用のスクリプトも色々用意できたので*4、次回に繋がりそうでこの辺も収穫でした。

*1:いつもありがとうございます。

*2:原始モンテカルロ法？

*3:コドゲの中で相対的に

*4:複数ファイルでの実装を一つにまとめるスクリプトとか、簡素なコード生成スクリプトとか。

AtCoder Heuristic Contest 010 ~Loop Lines~ でやったこと

70,980点で 192位/678人 でした。

今回は方針を途中までしか実装できず、苦しい回でした。

正直かなりやらかしたつもりだったのですが、それでも上位30%には入れていたので、
他の参加者も同じく苦戦していたのではないかと思っています。4時間だとちょっと短すぎたような。

解法

方針

枠に沿って二重四角を描く方針を取りました。

具体的な手法としては、ビームサーチを使いました。
設定は、

  • 状態: フォーカスする座標と、どの方向からそこへ入ったか
  • 遷移: 回転することで可能な移動全て
  • 評価値: 四角形を描く方向に進んでいるかどうか
  • ビーム幅: 2,000

としました。

しかし、実装は終わりきらず、下画像のように大外の四角を作るところで終わってしまいました。
評価値も雑で、あんまり壁沿いにできてもいないです。

提出コードはこちらです。
Submission #31233452 - ALGO ARTIS Programming Contest 2022（AtCoder Heuristic Contest 010）

方針の考察

ビジュアライザの手動操作モードで遊んだところ、そもそも閉じるのが難しくない？という気持ちになったので、できるだけ単純な図形を大きく用意しようと考えて、二重四角を描く方針を取りました。

が、コンテスト後のTLを見ていると、DFSをやれば割と自然に環は閉じられるっぽいですね。

所感

冒頭で書いた通り、実装時間が足りなくて苦しかったですね。

TLを見た感じだと、上位勢はDFS+焼きなましが多そうでした。
AHC002が似たような感じだったので、これを思い出して試そうと思えたら良かったのですが。。

AtCoder Heuristic Contest 009 ~Robust Memory of Commuting Routes~ でやったこと

6,493,441,713点で 109位/799人 でした。

提出コードがこちらで、
Submission #30422442 - Monoxer Programming Contest 2022（AtCoder Heuristic Contest 009）

Seed1のビジュアライズ結果が以下になります*1。

解法とコンテスト中の流れについて書いていきます。

解法

ビームサーチをしました。
設定は、

  • 遷移: 移動全パターンを１回実行
  • 評価値: 各マスについての (そのマスに居る確率) * (ゴールからの距離) の合算値（小さい方が優位）
  • ビーム幅: 400

としています。

コンテスト中の思考・行動の流れ

  1. とりあえず空文字を出力する。0点。
  2. "UDLR" を繰り返し出力。88K点。
  3. 入力制限的に、、必ず自宅の右下にオフィスがあることが分かったので、"DR" を繰り返し出力。393M点。
  4. ビジュアライザから、詰まってしまうケースが多いことに気づいたので、たまに上左への移動を交えた、"DRDRURDRDL" を繰り返し出力して 1.9G点。ここまでで30分くらい。
  5. 一旦問題文をじっくり読む。
    • 入力生成は別段特徴は無さそうだなと思った。
    • 得点計算式は、早くゴールできる加点よりも、オフィスに到達できないケースの減点の方がウェイトが大きいように見えた。けどだからどうすればいいのかは浮かばず。
  6. ビジュアライザの赤色情報(そのマスに居る確率)は、解法作る上でもかなり役立ちそうだなあとかを思う。
  7. ローカルビジュアライザから、そのマスに居る確率の計算コードを移植する。バグったりもあって、ここまでで2時間くらい。
  8. 貪欲法を組む。移動方向ごとに、(移動による各マスのゴールからの距離の変動) * (移動元のマスに居る確率) を合算し、最もスコアが良かった方向に移動するというもの*2。4.3G点。バグり散らかしてここまでで3時間15分くらい。順位も218位と微妙で焦る。
  9. 「残り45分で試せそうな方法って何かな」「がっつり残してる実行時間を使えると良さそうだな」とかを考えて、解法章で説明したビームサーチを試した。幸い当たりで、スコアが伸び6.49G点。これが最終スコアになる。
  10. 評価値 (そのマスに居る確率) * (ゴールからの距離) の (ゴールからの距離) を1.2乗倍する、を試していたが、TLEを踏んでコンテスト終了*3。

所感

まずまず自分的には良い順位が取れたので、満足感は高かったです。

移動結果が確率的に扱われる問題をマラソンで触れたのは、個人的には初な気がしました。 あんまりセオリー的なところも分からず、理詰めでどうこうってよりは、まあこうすれば良くなるはずだよなって感覚のところを試し打っていく方針になって た気がします。
ただ、実装を結構バグらせてしまい、試行よりもそこの修正に時間を取られてしまったのがやや残念でした。

TLを眺めてた感じだと上位陣は焼きなまし解が多そうに見えましたが、遷移とかどうしているのでしょうか。 じっくり読んでいこうと思います。

*1:Seed0 は盤面の難度が低いので避けました

*2:気持ち的には、マスごとの居る確率で重みづけした多数決って感じ。

*3:コンテスト後に間に合うビーム幅で試したけど、最終スコアは超えませんでした

AtCoder Heuristic Contest 006 ~Food Delivery~ でやったこと

1,509,391点で 163位/549人 でした。

今回の問題は個人的に、

  • まず始点を全部巡ってそのあと終点のTSP解くのが楽だけど、とはいえ上手いこと入り混じりながら進みたい
  • 1,000注文からどう50注文を選ぶ？
  • 4時間でどこまでやれる？

あたりが悩みどころでしたね。

最終提出コードがこちらで、
Submission #27260292 - Kyocera Programming Contest（AtCoder Heuristic Contest 006）

入力例0000のビジュアライズ結果が下図な感じでした。

f:id:gobi_tk:20211119000038p:plain:w400

ざっくりと解法と感想について書いていきます。

最終提出の内容

  • AtCoderオフィスを中心とする一辺450の正方形を用意し、選択対象注文を、その範囲に始点終点が収まる注文に絞る
  • 先に始点を巡り切ってから、終点を巡り始める。ただし、始点巡り中に無理なく踏めそうな終点だけは踏む。
    • 移動対象の二点を頂点とする長方形内に、消化可能な終点が含まれている場合は踏む*1。
      • ただ、ビジュアライザを見た感じだとあんまヒットしてませんでした。
  • 始点の巡回路は、「最後に訪れた点-注文の始点 間の距離の短さ」と、「注文の 始点-終点 間の距離の短さ」を考慮して決める
    • (「最後に訪れた点」と「注文の始点」間の距離) + (注文の始点-終点間の距離) / n
      • 整数 n は、[2, 6]の５パターンを試して、一番良かった結果を採用しました。
  • 終点の巡回路は、TSPを2-opt山登りで計算して決める

ということをしました。

大まかな方向性は、４時間で問題無く実装できるもので、ある程度安定して成果が見込めそうな内容*2をやるって感じでした。
良い具合に時間が余ったら、そこで得られた結果を元により良い解法を〜、みたいなお気持ちでいたのですが、
大枠の内容が終わった時点で３時間強が経過していたので、残りの時間はパラメータ調整やパラメータ複数パターン試行、みたいなところに割いて終えました。

時間があればやりたかったこと

焼きなまし方面の試行錯誤をやりたかったな、をとても思いました。
色々と考えられましたよね。注文の選び方だったり並べ順だったり。貪欲でなくそっちの試行に主に時間を割くべきだったかなってコンテスト途中から結構思ってましたね。

コンテスト後半に大枠の方針ミスってそうだなって思った時は、どうするのがいいんでしょうね？
方針ミスってるなりに頑張るのか、ムリくり方針変えにいくべきなのか。
レートシステムを考えたら、変えに行くべきって気はしますが*3。

所感

個人的には凄く好きな問題でしたね。
巡回路問題に良い感じに制約を足して、さあどうするの？って感じが色々と考えようがあって面白かったです(小並)。長期で出されてもいい感じにハマれそうな気がしましたね。

実際、TL見てると結構いろんな方針の解法がありそうな気配で、復習するのが楽しみです。どっかで時間割かねば。

*1:距離のロスなく踏めるので得しかしない。

*2:主観

*3:こけないことよりも、一発大きく当てる方がレートへの影響は良いらしいです。

HACK TO THE FUTURE 2022 予選 参加記

HACK TO THE FUTURE 2022 予選 に参加し、プレテストが 82,569点 の 399位/823人 でした。

今回は機械学習やってくださいと言わんばかりの問題でしたね。

AHC003の時も食らったのですが、私は機械学習的なアプローチ技法を持っていないので、この手の問題は手の出し用がありませんでした。。

なので今回は、基本方針を「チームメンバーの区別をせずにできること」だけに絞った、
レートの下支えと飛び賞賞金だけを目指した参加の仕方にしました（逃亡）。

やったこと

手が空いたチームメンバーに対して、タスク番号の最も若い未着手タスクを割り当てる、というシンプルな方針を取りました。
タスクの依存関係 (u_i, v_i) は、 u_i < v_i を満たすので、この優先度で割り当てるだけで、依存によるブロックは生じずらくなっています*1。

ただし、次数が0のタスク(他のタスクをブロックしないタスク)だけは割り当てを一番後に回し、さらにその中でも要求技能レベルの合算値が大きいものから順に見ていくようにしました。
こうすることで、ゲーム終盤での依存解決待ち発生の軽減を目指しています。

感想

今後もこの手の機械学習寄りの問題がRatedに来る感じなんですかね？流石に対策しないと不味い気がしています。。
とりあえず今回分の復習を頑張ってみようと思います。ありがたいことに解説放送もあるっぽいですし。

そして飛び賞ほしい！！

*1:はず

「天下一 Game Battle Contest 2021 Autumn」参加記

天下一 Game Battle Contest 2021 Autumn

KLabさん主催のゲームAIコンテスト「天下一 Game Battle Contest 2021 Autumn」に参加して、51位でした*1。
思ったことややったことについて書いていきます。

問題概要

一辺の長さが30の正方形内で、5台の資源回収車を操作して、フィールド内に生成される資源を収穫するゲーム。

ゲーム操作はWebAPIへのリクエストを通して行い、全プレイヤーが同一盤面上でプレイします。
ゲームはコンテスト時間中ずっと進行します*2。

資源には出現期間と重みが割り当てられており、出現期間中に同一座標に資源回収車を置くと、
(重み) / (その資源を収穫している全参加者の資源回収車数) が1msごとに得られます。

回収車の移動は (ユークリッド距離) * 100 (ms) かかります。

資源は3種類あり、その中で最も総回収量が少なかった種類の総回収量で勝敗が(概ね)決まります。

詳しいルールはこちらです。

過去回からの変更点についての所感

過去のコンテストだと、１時間ごとに獲得スコアが大幅に*3増える、かつ途中で実行中断するとかなり不利という形式だったため、最後の１時間は再デプロイが実質出来なかったのですが*4、
今回のコンテストでは中断がさほど不利にならないのと、テスト実行環境が提供されるようになったことで、コンテスト終盤までプログラムが変更できる形式になっていました。

個人的にはかなり良い改善に感じました。

やったこと

大筋は、サンプルコードの無難(?)な改修をしてたって感じでした。

サンプルコードはこちらで提供されていて、

移動先に資源が無い回収車を、ランダムに選んだ出現中の資源へと移動させる
ただしこのとき２台以上の回収車が同じ資源を選ばないようにする

というものでした。

これに対して、

  • 近くの資源を取りに行く
  • 回収対象資源が消えた直後に次の対象に向かうように予約移動を入れる
  • 到着するまでに消える資源は取りに行かない
  • 出現 500ms 前の資源も選択候補に入れる
  • 複数回収車が同一資源に向かうことをある程度許す

といった変更を加えました。

ゲーム終盤は、上のルールに沿いつつ種類ごと最小値が最大になるように、資源選択を手動調整してました。

コードはこちら。

所感

過去コンテストの所感的に、無難なことをやり切るだけでもコンテスト時間が短いのでそこそこ良い順位が出せるって感覚を持っていて、実際そうなったなって感想でした。
賞金圏内目指して、もうちょっと思い切ったことを試みても良かったのかもしれないなあとかをちょっと思いました。なんか目標がふわっとした状態で出てしまっていた感はあったり。

問題把握するまでに結構時間掛かっちゃったのと、考察があまり詰められず、問題の本質的なところが何なのかは結局分からないままでした*5。

サンプルコードを使いたい都合で、普段使いでない Python をこのコンテストでは使っているのですが、ここが実装速度の遅さや、自作ライブラリが無いからこの方針は辞めとこうを産んでいて、まあまあ良くない気がしているので、
次回は事前準備をして、普段使いの Rust を試験的に使ってみようかなとかをチョット思ってます。
ただ、この手のアドホックなJSONパースを良い感じに扱うライブラリが提供されているのかはまあまあ怪しい気はしていたり。

上位解法をざっくり見ての感想

資源が出現した瞬間を狙うのが有力だったっぽいですね。
２位のchokudaiさんのこの考察とかがかなりしっくり来ました。

終わりに

順位的にはもう一押し行きたい気持ちでしたが、楽しかったです（小並）。ビジュアライザがリッチだとテンションが上がりますね。

*1:総参加人数は不明(ランキングが100位までしか表示されないため)

*2:ので、プレイしながらプログラムの改善をしていく形になります

*3:その前の１時間を無視していいレベル

*4:なので、コンテスト時間は実質3時間だった(と思っている)

*5:まあでもそもそも短時間コンテストってそういうものかもですが。不完全情報もまあまああるし。