CODINGAME FALL CHALLENGE 2020 参加記

 はてなブログ初投稿媼、名を小竹と申します...

www.codingame.com

CodinGameで2020/11/13から2020/11/23にかけて開催されていたFALL CHALLENGE2020に参加しました。

マラソン形式のコンテストにがっつり参加したのは今回が初めて

序盤

 周りの人々が参加表明をしていたので、流れに乗って参加

tsukammo.hatenablog.com

 ツカモさんがルールを翻訳して宇宙一わかりやすい記事を出してくださったので、すんなりとルールを理解することができました。

ただ、こどげのデフォルトのINPUT処理がかなり分かりづらくて最初何を受け取っているのか理解するのに時間がかかってしまう（そうでもない？）

とりあえずWood2とWood1ではルールがシンプルなので、簡潔なコードで改善を試みます。

 無事BRONZEまでたどりつくことができました。

この段階でインベントリ・魔法・ポーションのクラスを作って、dfsで生成することが可能なポーションを探すといった実装をしていました。

中盤

 3日後にスキップします　こどげを触っていませんでした（何？）

 とりあえずWood1のときのカスdfsから実装を変えていなかったのでいじります

 ここでインベントリのすべての状態が $_{14}C_4 = 1001$ 通りしかないことに気づきます。

そこで10個の手持ちの状態を4つの1で区切って 01000100010010 のように14bitで符号化してあげます。右（最下位ビット）からtier0,1,2,3, 空のように管理します。

これで 0100001000100 ⇔ {1, 2, 3, 3} のようにインベントリの状態を整数値で表すことができました。

1ターン50msといえど、頂点数が1001通りであれば適当にBFSかdijkstraしても余裕で間に合いそうなので実装しました。

 

 急ピッチで実装したので案の定バグります。

この時点では、RESTとrepeatableを考慮せずにBFSで必要ターン数を計算しています。

なんとかデバッグしてBRONZE内でもいい感じの順位に落ち着くことができました。

 11/16 02:00にSILVERランクが解放され、すぐに昇格することができました（嬉しい）

 人の泊まりにいき、家主が寝ている中こどげをしていました（は？）

このあたりからコード改善を試してもうまくいかないことが続きます。

 11/19 02:00にGOLDランクが解放されましたが、到底辿りつけそうにない状態でした。

  • （敵の行動を考慮しなければ）REST込みで正確な最小ターンを得られるようなdijkstra法を実装
  • LEARNで得る魔法は消費する素材、生成する素材のうち、手に入れてない組合せを優先
  • ポーションの獲得戦略を現在までの獲得個数に応じて変更

上記のような改善を追加しても目に見えて強くなることはありませんでした。

RESTとrepeatableを考慮したdijkstra法がかなり重かったのもあって、たまにTLEを起こしてしまうのも良くなかったです。

終盤

有効な改善案を探すために、強い人の婆の行動を観察していたところ、1つのポーションを作成した後も一定数素材が残っていることに気づきます。

そこで、ポーションを作成できる条件に付加価値の概念を増やしてぴったり素材を消費することが無いように変更しました。

 

 この変更がかなりうまく作用してくれました。

 この調子でLEGENDも目指そう！と意気込んだものの、Link044が強すぎる

 2ターン毎にポーションを作成する行動は僕のおばあちゃんには出来ません・・・

 最後のあがきで#pragma GCC optimize("O2") をしてみたところ、10倍くらい高速化されました（マジ？）

 そこで、時間がネックとなって試せていなかった 1個目のポーションを取った後、2個目のポーションまでの必要ターン数まで計算する処理を実装しました。

ちょっとだけin ARENAのコードより改善できたっぽいので提出して最終日は就寝

 結果は全体210位（ゴールド内130位）でした。

マラソン系コンテスト実質初参加だし、かなり満足しています。

反省点

戦略らしい戦略としては、dijkstra法で必要ターン数を求めたことくらいなので、ゲームAIらしい探索をしてなくてかなりもったいない気持ちです。

Twitterでよくみる人々はビームサーチやChokudaiサーチを上手く駆使していたので、スゲ～～～～～～～～～～～～～～～～～って思いながら眺めてるだけだった

AtCoderでもマラソンコンテストが更に生えてきそうなので、マラソンの基本戦略やアルゴリズムを勉強したいね

次回の目標はLEGENDに行くことです　頑張るぞ

おまけ

 ところで錬金術といえば、12/3(Steam版 1/26)にライザのアトリエ2が発売します！

アトリエシリーズをやったことない人、まずはライザのアトリエ1をプレイしてみよう！

かなり面白いです