第9回 Asprova プログラミングコンテスト 参加記

第9回 Asprova プログラミングコンテスト に参加しましたー

1位でしたー！わーわー

コンテストページ

atcoder.jp

※問題文はコンテストに参加登録した人しか見れません

解法

稼働パターンの扱い

各週の稼働パターンは1～9の9パターンで平日/祝日それぞれ指定しますが、平日/休日を組み合わせて9×9=81パターンとして扱うことにしました。

この81パターンを稼働時間でソートすると、稼働時間をn段階減らす、増やすといった操作ができるようになります。

パターン同士のコストを比較すると「稼働時間は少ないのにコストが高い」といったパターンが見つかります。これらは無駄*1なパターンとして除外します。

すると30～36パターン程度まで減らせます。

さらに等間隔に間引いて26パターンぐらいにしました。（最終日にやってみたらスコア上がったから採用。コスパが悪いほうから順に間引いたほうがよかったかも。）

ファイナライズ

計画プログラムからのフィードバックで重要なものとして作業負荷率があります。これは稼働時間に対して実際に作業が行われた割合を示しています。

これがもし0%であれば全く作業が行われていないということなので、稼働を行わない稼働パターン1変えてしまって問題なさそうです。*2

そこで「すべての設備について、後ろの週から作業負荷率が0%が連続している範囲を稼働パターン1で埋める」という操作を考えます。フィードバック後に常にこの操作を行うことで確実に稼働パターンを減らせてスコアを上げることができます。

この操作をファイナライズと呼ぶことにします。

さらにファイナライズした状態のスコアをファイナライズスコアと呼ぶことにします。

※稼働パターン変更回数の上限に引っかかって稼働パターン1で埋めることができない場合もあって、実装は結構大変でした。

手順１：大まかに稼働パターンを決める

全設備/全週の稼働パターンをまとめて変更して出力、というのを二分探索的に繰り返し、納期に間に合い稼働時間のできるだけ少ない稼働パターンを見つけます。

ぎりぎりの境界を見つけるよりは、大雑把（途中で探索を打ち切る）なほうがスコア上がりました。

手順2：ちょっとずつ稼働パターンを減らしていくループ

(1)操作候補リスト作成

次の操作を候補とします。

• 1つの設備の全部の週の稼働パターンを1/2/4/8/16段階減らす
• 1つの設備のある週以降の稼働パターンを1/2/4/8段階減らす
• 1つの設備の1つの週の稼働パターンを1/2/4段階減らす

(2)操作候補の評価値算出

操作候補リストの操作すべてに対して評価値を算出します。

評価値はまず、操作後の設備稼働率を見積もり（前回のフィードバックの設備稼働率か大体計算できる）し、これを使って操作後のファイナライズスコアを算出します。

そして以下の情報を混ぜ合わせて評価値を算出します。

• ファイナライズスコア
• 操作によって後ろの週にずれる作業時間
• 設備番号
• 変更する段階数
• 変更する週の種類（全週 or 複数週 or 単週）
• 変更する週の数
• 計画プログラムとのやりとりの回数
• 手順2の試行回数

このような評価値になった経緯

ファイナライズスコアが高いほど良いけど、納期遅れになる確率が高いなら良くない。

納期遅れになる確率って推定できる？フィードバックされる情報からだと難しい気がする。大量のテストケースで事前学習しておくのがいいんじゃない？

ちゃんとした機械学習はできる気がしないし、とにかく影響ありそうなパラメータを評価値に足しこんでOptunaで調整させよう。

(3)評価値最大の操作の出力

評価値が一番高かった操作を出力し、フィードバックを得ます。フィードバックされた情報を使いファイナライズスコアを算出します。

ファイナライズスコアが今までで最大ならその状態を記録します。

(4)操作候補の枝刈り

フィードバックで納期遅れが発生してたら候補操作から無駄そうなものを削除します。今の稼働時間で納期遅れるのだったら、稼働時間をもっと減らすような操作は無駄だろうという観点です。

(5)終了判定

計画プログラムとのやりとりの回数が残り3回以上なら(2)に戻り繰り返します。もし操作候補リストが空なら手順2をはじめから行います。

計画プログラムとのやりとりの回数が残り2回なら手順3に進みます。

手順3：ファイナライズして出力

まず、今までのファイナライズスコア最大の状態を（ファイナライズ後の状態で）出力します。これで納期遅れなしのフィードバックが帰ってきたら、もう一度同じものを出力して終了です。

まれに納期遅れありがフィードバックされます。なぜ納期遅れが発生するかというと、作業負荷率が小数点3位までで切り捨てられているため、作業負荷率0%でも実際には作業を行っているためです。

この納期遅れを解消するために次の対策を入れました。

• 納期遅れのあった設備とそれより番号の大きい設備すべてについて、その設備の最終作業週の次の週の平日に稼働パターン2（午前中だけ働く）を設定して出力。*3

これで納期遅れが起こらない気がしていますが確証はないです（ジャッジプログラムを理解できてないの）

この納期遅れ対策のために、前の手順で計画プログラムとのやりとりの回数を2回残しておく必要がありました。

作ったビジュアライザ

ファイナライズ後の状態を表示したり、設備単位の合計コスト/稼働時間を表示できたのが便利でした。

感想

実行時間が短いのと乱数もないので、optunaで最適なパラメータがきれいに見つかるのが気持ちよかったです。

横軸：パラメータ、縦軸：スコアのグラフ↑

作業負荷率0%で実際には作業しているケースの対策に苦労しました。発生率自体は低いものの発生したときは無視できないぐらいのスコア減点があるので対応せざるを得ませんでした。正しく対応するにはジャッジコードをちゃんと理解する必要がありそうだったのですが、それよりは別なとこに力入れたほうがいいでしょ、という絶妙なスコア設定でした。

問題文が長く複雑で、問題文だけ見て参加やめてる人がいそうで、ちょっともったいない気がしました（大部分は理解しなくてもよくて、理解してもあまり活用できない……）

参加記のネタにしようとコンテスト中に日記を書きましたが、細かく記載しすぎてまとめるのが大変でした。時系列に改善していった様子を記事にしたかったのですが、難しすぎて断念しました。記録の仕方も工夫しないといけないかなあ。

時系列やったこと

1日目

• サンプルコード実行
• 公式ビジュアライザを動かす
• ビジュアライザ自作
• 設備稼働率100%超えてるので質問出す
• 遅れ作業の個数が公式ビジュアライザと合わない

2日目

• ジャッジの変更を反映
• 全設備全週同じ稼働パターンで埋めるのを全パターン試す実装
• 稼働パターンを1段階ずつ下げる貪欲を実装
• ファイナライズ実装

3日目

• 稼働パターンを平日/祝日を組み合わせ81パターンで扱う実装をした
  →1段階ずつ減らす操作だと局所解にはまる
• 1設備1週だけ変更する操作の実装
• 提出：154098562126点（7位）
• 1設備1週の休日だけ変更する操作の実装

4日目

• パラメータ大量に用意してoptunaで殴ると良さそう
• 稼働パターン81パターンから時間ソートして無駄なの省くとすごいパターン減る
• C=8のケースが見当たらない→テストケース生成プログラム見たら作られないみたい
• エクセルでパラメータとスコア表作った
• スコア予測処理実装
• 作業時間をもとにした納期遅れ判定実装

5日目

• 変更するときの段階数を4/2/1みたいにするといい感じ。二分探索みたいになるんだ。
• ファイナライズしても納期遅れ発生する。誤差で0%になってるということか。
  納期遅れだった設備の最後に祝日の稼働パターン2を入れるようにして対策→それでも再発→平日の稼働パターン2を入れるようにした。
• 設備単位、ある週より前の週全部を変更する操作を追加→驚くほどスコア変わらない

6日目

• すぐ局所解に陥って山登れてなさそう
• 設備単位、ある週以降の稼働時間を減らす操作を追加→かなり良い
• 二分探索みたいな操作を実装
• 問い合わせ回数を余らせないように繰り返し処理実装
• 提出：159,754,557,566（3位）
• 稼働パターンの変更手順フェーズ「全周変更」「指定週以降変更」「1週変更」の3つを、全設備で変更がなかったら次のフェーズに移行していたのを、設備単位で以降するようにしたらスコア上がった。

7日目

• 「全周変更」「指定週以降変更」「1週変更」の3フェーズ順不同の同時進行にしたらスコア上がった
• またファイナライズで納期発生する。ムキー！納期遅れのあった設備より後の設備全部に稼働稼働パターン2を入れて対応。
• スコアだけでなく評価値を使って操作を決めるようにした
• optuna回すために新しく買ったPCを開封した。めちゃ早い。
• ジャッジコードを高速化した

8日目

• optunaの結果を反映
• 提出：161,234,108,954（1位）
• 評価値追加
• optunaでパラメータ調整
• コードを少し変えて上がるなら採用を繰り返す
• 稼働パターン候補を間引きするとなぜかスコア上がるので採用
• 最終提出：161,413,266,352 点

*1:作業する時間帯が変わるので厳密ではない

*2:実は罠があります！

*3:稼働パターン変更回数の上限に引っかからないようにかなり面倒なことをしてます

RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013）参加記

RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013）に参加しました。

1位でした！

問題

atcoder.jp

はじめに

「コンピュータ」だと長いので「PC」と呼びます。

解法

PCの移動経路を変更する焼きなまし法で、PCの接続はBFSで行いました。

処理の流れ

1. 状態の初期化
2. 焼きなましループ：(a)～(c)を時間いっぱい繰り返す
   (a)状態を少し変更してみる
   (b)状態を評価する＝評価値算出
   (c)状態の採用判定
3. 一番スコアの高かった状態の移動と接続を出力

1.状態の初期化

プログラムに入力された情報で状態を初期化します。

状態は以下の情報を持ちます。

• 各セルにどの種類のPCがあるか
• 各セルにどのPCがあるか
• 各セルを通ったPCの履歴
• 各PCの現在のセル
• 各PCの移動経路
• 移動可能なPCリスト
• 巻き戻し可能なPCリスト
• 種類の優先度
• BFS起点PC（種類ごと）
• PCの移動回数合計

PCの接続に関する情報は持ちません。

2.焼きなましループ

(a)状態を少し変更してみる

以下の操作からランダムに1つ選び実行します（操作によって選択確率は変えてます）

• PCをランダムに1個選び、1～3マスランダムな方向に移動させる
• PCをランダムに1個選び、1～3マス巻き戻す
• PCをランダムに1個選び、1～3マス巻き戻してから1～3マスランダムな方向に移動させる
• PCをランダムに1個選び、1～2マスランダムな方向に移動させる、移動先に別なPCがあったらランダムな方向にどかしてから移動させる
• 種類の優先度をランダムに変える（低確率）
• PCの種類をランダムに1個選び、その種類のBFS起点PCをランダムに変える（低確率）

PCを「巻き戻す」とは、移動させたPCを1つ前のセルに戻し、移動させなかったことにする操作です。移動回数＋接続回数には上限があり、移動を巻き戻すことで接続回数が増やせるので重要な操作です。

ただし、操作の順序によっては巻き戻しができないケースがあります。

この図は、1番PCが下に1マス動いた後に、2番PCが左に2マス動いた状態です。

この状態から1番PCを巻き戻すことはできません。巻き戻してしまうと、2番PCが1番PCをすり抜けて移動したことになり、不正な操作になってしまいます。

これを判定するために、状態として「各セルを通ったPCの履歴」を記録しています。1番PCが元居たセルには1番PC→2番PCという履歴が記録されていて、巻き戻す場合はこの逆順にしなければならないという制限をかけています。

よって、この図では1番PCは元居た場所への「移動」は可能だが「巻き戻し」は不可能という状態になっています。

上記の制限や、周りが別なPCに囲まれていたりなどの理由で「移動」「巻き戻し」操作ができないPCがあります。状態として「移動可能なPCリスト」「巻き戻し可能なPCリスト」を持つことで、操作可能なPCを素早く選べるようにしています。

(b)状態を評価する＝評価値算出

起点となるPCから上下左右の直線上に調べていって、同一種類のPCがあったら接続、ということをBFSで行い、クラスタを作成します。

クラスタを作る順序は、状態として持っている「種類の優先度」「BFS起点PC」を使って次のようにします。

1. 1番優先度の高い種類のBFS起点PCからクラスタを1個作成
2. 2番目の優先度の種類のBFS起点PCからクラスタを1個作成
3. 優先度高い2種類について、それまでに作成したクラスタの累計スコアを比較し、スコアが低い方の種類のクラスタを1つ作成（起点PCはid順）
   これを2種類のクラスタが作成できなくなるまで繰り返す
4. 残り処理時間が少ない（10%以下）であれば、優先度3番以降の種類のPCも優先度順にクラスタを作成していく（起点PCはid順）

☆上記手順中に操作回数上限に達したらその時点で終了させます。

3番目の手順は、できるだけ2種類のクラスタを均等に大きくしようとしています。1種類のクラスタを大きくしてから2種類目を大きくしようとすると、1種類目のクラスタが邪魔になって2種類目のクラスタが大きくなりにくいためです。*1

4番目の手順は、2種類のクラスタをできるだけ大きくするのが高スコアにつながるため、優先度の低いPCは終盤にだけ計算することで処理時間をカットしています。

作られたクラスタからスコアを計算します。

このスコアに、以下のペナルティをかけたものが最終的な評価値となります。ペナルティ量は時間で減衰させ最終的に0にします。

• 行動回数が多いほど減点
• 移動回数が多いほど減点
• コネクタ長が長いほど減点

クラスタの結合

クラスタを1つ作成するごとに、それまでに作成したクラスタとの結合を試みます。

まず、クラスタ作成のBFS中に、他の種類のPCが見つかればそれをハブとして記憶しておきます。*2

BFS後、ハブとして記憶したPCを確認し、既存クラスタからもハブとして登録されているのであれば、そのハブを経由して既存クラスタと結合します。

複数ハブがあるのなら、結合できるものがなくなるまで結合処理を行います（スコアが減少するような結合は除く）

ハブを複数個経由して結合することは考慮していません。*3

(c)状態の採用判定

一般的な焼きなましと同様です。

評価値が上がっていればその状態を採用、評価値が下がっていても確率で採用。

採用しない場合は直前の変更操作の前の状態に戻します。

3.一番スコアの高かった状態の移動と接続を出力

状態として記録している「各PCの移動経路」をもとにPCの移動を決めていきます。

このPCを動かすには別なPCを先に動かさなければいけない、といった依存関係がありますが、状態として記録している「各セルを通ったPCの履歴」の通りになるような順序で移動させれば不整合はおきません。

接続は評価値算出に使用したものと同様の接続を行います。

その他効果のあったもの

各PCは3マスまでしか移動させない

パラメータを偶然いじったらスコアが上がったので採用しました（はじめは10マスまで移動を許可していた）

PCの初期位置には偏りがなく良い感じの間隔なので、それほど多く動かさなくてもいいということだと思います。巻き戻し制限の関係で、遠くに移動しすぎたPCがあると他PCが移動しにくくなるという理由もあると思います。

状態を複数持つ

スコアが安定しないため、状態を複数更新していって、うまくいった状態に絞り込んでいくということを行っています。

一定時間最高スコア更新しないなら最高スコア時点の状態に戻す

スコア更新が見込めないような状態に陥っている可能性が高いため、最大スコアを出した時点の状態に戻します。

焼きなましの様子

seed=2

seed=7

コンテスト中に考えたこと

※覚えてないところをは若干の嘘があるかもしれません

1日目～2日目

移動と接続両方考えないといけない。

移動を確定させた時点で接続方法が定まるかどうか？簡単には定まらなそう。

移動と接続を同時に焼きなませる？接続された状態で移動させると切断される？
移動させるだけだとスコア変わらないから、移動～接続までを行う近傍を考えないといけないよね。

移動と接続どっちかを貪欲にできないか。

あーケーブルの交差って駄目なんだ。接続する順番も重要になってくるし焼きなまししにくくなってきた。

既に提出した人のスコアを見るに1ケース5000点は出ている。1種類のPCはほぼ全部繋げてるのかな。

分からんのでとりあえず実装してみる。

まずBFSで接続処理を実装。手動でPCを移動させてみる。少し移動させるだけで結構つながる。

接続はBFSでするものとして、移動と巻き戻しの2つの近傍で焼きなましてみよう。移動順によっては巻き戻しで不整合が起きる。各セルに履歴を持たせれば回避できる気がする。大丈夫そう。

とりあえず動くようになったし提出する。

252,421点（2位）

思ったより高得点出た。この方針で行けるのでは。

3～5日目

提出すると順位表気になっちゃうからあんまり提出しないでいこう（後で一気に高得点出してびっくりさせたろ）

毎回BFSするのは遅いけど後で差分計算とかできるでしょ。*4

状態の変更操作をいろいろ思いついたものを試す。PC移動時に他のPCをどかすのは良さそう。あとBFS時のPCの種類の順番も変えられた方が良さそう。
他いろいろ試したけどほとんど没。

違う種類のPCを経由してでもクラスターを大きくするのはやったほうが良さそう。実装大変だぞ。頑張って実装したけどスコア減った。

バグってただけだった。直したらわずかにスコア上がった。しかし処理速度1/10ぐらいまで落ちている。高速化したらスコアも上がってよくなった。

焼きなまし変更操作の集計を出してみる。操作に失敗して無駄にループが回っていることが多い。操作可能なPCリストを作っておけば回避できそう。ちょっと高速化になった。

やりたいことはやれたのでそろそろ提出しよう。

355,702点（2位）

届かなかった……

6～7日目

パラメータ調整する。Optuna君頑張ってね。

焼きなましの変更操作の「移動」と「巻き戻し」を1マスじゃなく複数マスにしたらスコア上がった。それはそうだよね。

優先度高いPCほど焼きなましの操作対象にしたほうが良いのでは→スコア上がらず。

スコアが低いケースの焼きなましの過程をビジュアライザで見てみると1種類のクラスターが邪魔で2種類目のクラスターが大きくなれない状態になっている。2種類のクラスターを同じぐらいの大きさで広げてくのが良いのでは？
クラスターの作る順序を工夫した。そして2種類つのクラスター以外はあまり重要じゃないから接続処理はスキップだ。

Optunaで調整したパラメータでテストしてみたらスコアが大幅に下がる。結果をグラフにしてみると、スコアのばらつきが大きすぎてうまく探索できてなさそう。

過去最高スコアと比べた70%ほどしか出ていないケースも多いし、このスコアが安定させるのが良さそう。

評価値工夫するも良くならず。状態を複数開始にするのと、一定期間スコア更新なしでロールバックするするのを入れた。これで多少ましに…?

後はパラメータ調整ぐらいしかできなさそうだし提出しておく。

387,912点（1位）

やっと届いたが、もう少し上げないとだめそう。

最終日

Optunaはまたも失敗。スコアやはり安定しない。

手動でパラメータを調整。高速化。焼きなまし操作も思いついたのを試す。

PCの移動量最大を16マス→3マスにしたらスコア上がった。そんなに動かさなくてよかったんだ。

焼きなましの操作で、「巻き戻してから移動させる」という操作を追加してみるとスコア上がった。山登りたいなら必要やつだよね。

終了が近づいてきたので提出。

404,444点（1位）

うおーー

2000ケースでテストしつつ高速化できたので最後の提出。あとはお祈り。

402,264点

 

感想

問題はシンプルだけど、どこから手を付けていいかわからないような難しめの問題だったと思います。seed=7とかははじめはスコアほぼ取れないと思っていたのに、最後には5000点ぐらい取れるようになってうまく調整されてたんだなあと。

焼きなましにうまく落とし込めたのは良かったです。評価値はもうちょっと頑張ったほうが良かったかな。
自己ベストスコアと比べると70%のスコアしか出てないケースも多いので、まだまだ改善の余地はある気がします。

おしまい

*1:PCの密度が高いケースでは2種類を大きくするより、1種類を大きくする方針の方が良いケースもありそうです。

*2:一般的なハブとは意味が違いますが

*3:高密度のケースでは考慮したほうが良かったかも。

*4:できませんでした……

CodinGameでバイナリデータを扱う

CodinGameでバイナリデータを扱いたい時ありますよね。ニューラルネットワークとか。

ソースコードで提出しないといけないので、バイナリデータを何らかの方法でテキスト形式に変換して埋め込んでおき、実行時にバイナリデータに戻すといった手順が必要になります。

バイナリデータをテキスト形式に変換する方法で有名なものにBase64がありますが、CodinGameにおいてはもっと良い方法があります。

Base64

まずBase64とは、バイナリデータを64種類の文字で表現する方法です。

手順

1. バイナリデータを先頭から6bit読み取る
2. この6bitを整数とみなすと0～63の値になる
3. 値に対応する1文字を出力（変換テーブルを用意しておく）
4. 1～3をバイナリデータなくなるまで繰り返す
   ※最後の6bitに満たないとこだけ特殊処理必要

という感じ（64進数に変換してるようなもの）

Base32768

CodinGameのコード長制限は恐らくUTF16で10万文字（2022/7/5 bowwowforeach調べ）

つまり'a'も1文字だし、'あ'も1文字だし、'犬'も1文字としてカウントされます。

使える文字を調べた結果55000文字ほどありました（サロゲートペアは良く分からんので除外）

このことからBase32768というのがデータ量効率、実装の手軽さで良さそうです。

手順

1. バイナリデータを先頭から15bit読み取る
2. この15bitを整数とみなすと0～32767の値になる
3. 値に対応する1文字を出力（変換テーブルを用意しておく）
4. 1～3をバイナリデータなくなるまで繰り返す
   ※最後の15bitに満たないとこだけ特殊処理必要

☆使える文字が55000あるので、55000進数変換すればもう少しデータ量効率は良くなるはず。処理時間や実装の手間と相談。

使える文字が連続している場所（文字コード）はこちら。（間違ってたらごめんなさい）

• 0x3220 ～ 0x4DB4
• 0x4DC0 ～ 0x9FEE
• 0xAC00 ～ 0xD7A2

これで39274文字あるので十分足ります。

UltimateTicTacToeでニューラルネットワークを埋め込んだらこんな感じ。

以上です。

CodinGame Green Circle参加記

CodinGame Green Circle に参加しました。

www.codingame.com

結果

優勝したぞー

 

ゲーム内容

tsukammoさんいつもありがとうございます。

tsukammo.hatenablog.com

やったこと

MCTS。不完全情報ゲームなのでちょっと工夫。

探索

MCTSベースの方法（ISMCTSというらしい？）

• ノードに状態は持たせない。
  MCTSの選択処理の時にノードをたどりながら状態を計算していく。
  不確定情報はランダムに決める⇒同じノードでも通るたびに状態が違う。
  次のノードはその時の状態で合法なものから選択する。

• プレイアウトは6ターン（MOVE～RELEASEまでを1ターンとして）で打ち切り、評価関数で判定。
  • ゲーム終了している時、勝ってるなら+1点、負けてるなら-1点。
  • ゲーム終了していない時、評価関数で少しでも勝ってるなら+0.5点、負けてるなら-0.5点、さらに評価値を-0.5～+0.5の範囲にして加算、みたいな感じ。

評価関数

• ゲーム内の実スコア
• スキルカードは多い方が良い
• CONTINUOUS_INTEGRATIONカードは多い方が良い
• 負債は少ない方が良い
• 永続化効果は多い方が良い
• アプリ評価
  • リーチ状態だと良い
    アプリリリースに必要なスキル8個分中4個分を自動化できている状態をリーチ状態とする。リーチ状態だと手札1枚＋移動後に1枚拾うことで負債0でリリースできる。
  • リリースに必要なカードがデッキ内に存在すると良い
• 最終リリース評価
  • アプリ4個リリース済みの時、リーチ状態のアプリをリリースするために必要なカードをドローする確率が高いほど良い。デッキに1枚もない場合は少し減点。
    
    

行動の枝刈り

• 最初の1手は CONTINUOUS_INTEGRATION か DAILY_ROUTINE のどちらか
  2手目以降は特に制限しない方が強かった。
• score=4の時は、RELEASEフェーズまで全探索して勝ち確定の手があれば必ずそれを選ぶようにする。
• リリースしたときに負債が5個以上のアプリはリリース禁止
  ただし自分のスコアが3以上または相手のスコアが4の時は制限なし
  • 自分のスコア3以上の時：負債の少ないアプリを5個目のリリースにとっておくために、4個目のリリースは負債が多くても良い
  • 相手のスコアが4の時：相手の最終リリースアプリを先にリリースして妨害するため負債を無視する
• 序盤はGIVEする場所への移動を禁止
• DAILY_ROUTINEは2回まで
• 同一基本スキルの自動化は2枚まで

その他

• 1ターン当たりのプレイアウト回数は8000回ぐらい
• 後手番の時、相手が CONTINUOUS_INTEGRATION にいると探索の結果初手 REFACTORING に行こうとするので DAILY_ROUTINE に矯正してた。自己対戦で勝率低いからやめさせてたけど提出したら勝率そんなに変わらなかった。理由がよく分からないから採用しなかったけど。
• カードの枚数を64bit整数で管理した。
  全種類のカードまとめて足し引きしたり、アプリリリースしたときの負債数の計算がビット演算で高速にできる。
  
• 相性そんなにないゲームかと思ってたけどパラメータによって大負けする相手が出てくる。最終的には平均的に勝てるような調整にした。

感想とか

• 不完全情報ゲームでMCTSは初めてだったのでうまくいってよかった。今後も使えそう。
• ゲームルールを理解するのに時間がかかった。勘違いしてることも多くて他の人のTweetで気づけて助かった。
• シミュレーション部分はRefereeコードを使わずに自前実装したけど、細かいルール勘違いしているところもあったので移植したほうが良かった。
• カード毎の有用度で評価値調整したかったけど難しくてできなかった。（CONTINUOUS_INTEGRATIONだけ0.6でそれ以外は全部0.1）
  評価値を機械学習的な奴で調整するの覚えたい。
• 次回も頑張る！

CodinGame Spring Challenge 2022 参加記

CodinGame Spring Challenge 2022 で優勝しました！

www.codingame.com

ゲーム内容

tsukammo さんが翻訳してくださってます。ありがとうございます！

https://tsukammo.hatenablog.com/entry/2022/04/22/010522

最終Bot内容

防衛2人 : ルールベース

攻撃1人 : chokudaiサーチ

防衛

ルールベースで頑張る

4つの役割と割り当て

1. 拠点を守る
   
   • 拠点内から半径5000に入ったモンスターを攻撃する。倒しきれないならできるだけ拠点に引き付けてからWINDする。できるだけ引き付けたほうがまとめて攻撃できるのでmana効率いいのではという理由。
2. 邪魔する
   • 相手ヒーロー1人を追い回す。もう一人が近づいてきたら自身にSHIELDや相手にWINDを放つ（ダブルWIND対策）
3. 自陣付近警備
   
   • 自陣付近(4000,4000)に来たモンスターを攻撃する。自陣からあまり離れない。
4. モンスター発生源付近警備
   • モンスター発生源付近に来たモンスターを攻撃する。発生源からあまり離れない。発生源は自陣に近い2か所。

上の役割の方が優先度が高く、相手ヒーローの位置とモンスターの位置によってどの役割が必要かを決める。

複数のヒーローそれぞれにどの役割を割り当てるかは、割り当てた際の目的地までの距離2乗が最小になるのを総当たりで求めた。

「拠点を守る」と「邪魔する」はそれぞれ1人まで割り当てる。相手に攻撃されているときはこの割り当てになる。

緊急行動

相手にこの行動をされたらまずいと判定し、役割に関係なく行動する。

• モンスターにWINDされることで拠点にダイレクトシュートされるならそのモンスターをWINDで飛ばす
• モンスターにSHIELDされることで拠点までに倒せなくなりそうならそのモンスターをWINDで飛ばす
  （これ欠陥があって、SHIELDの方がWINDより射程長いので間に合わないことが多い）

攻撃

15ターンのchokudaiサーチ

目的行動単位で分岐するようなゲーム木探索。目的の行動を達成するまでその行動を取り続けて分岐しないような感じ。なのでターン数のわりに分岐は少ない。

相手の行動は自分の防衛処理をそのまま適用する。

目的行動リスト

• 敵陣付近に移動する
• 敵陣側のモンスター発生源付近に移動する
• モンスターのところまで移動する
• モンスターにダメージを与えないギリギリの場所に移動する
• モンスターから半径1100の位置に移動してWINDする
• モンスターに近づいてWINDする
• モンスターに近づいてSHIELDする
• モンスターに近づいてCONTROLする
• 相手ヒーローをCONTROLする
• 相手ヒーローにWINDする
• 自身にSHIELDする

モンスターから半径1100の位置に移動するのは以下の図のようなWIND2連打狙い。

評価値

優先度順

1. ダメージを与えたターン数が早いほど良い
2. 相手に与えたダメージ量が多いほど良い
3. モンスターができるだけ相手拠点近くまで到達できるほど良い
   • モンスターのhpが0になるかWINDをかけられる場所を到達点とする
4. 自分のmanaは多く相手のmanaは少ないほど良い

評価値1,2はダメージ量よりも速さを重視するのでこの優先度順。ダメージ量を優先すると見えていない敵ヒーローに防がれることが多かった。

評価値3は最終的な行動を決めるときには無効にする。半端に攻撃してダメージを与えられないなら攻撃せずmana温存した方が良いでしょうという理由。

その他工夫

• mana50たまるまでは攻撃に呪文を使わない。
  ただし、前ターンでダメージを与える行動を見つけていれば制限しない。
• 入力で相手ヒーローの位置が来ない場合はその場から動かさないが、3ターンの間見えていないなら存在しないものとする。
• モンスターを1匹見たらそのIDからHPと出現ターン数が分かり、座標と移動方向から相手プレイヤーに妨害されてるかどうかも判断できる。妨害されてなければ対称の位置にモンスターを追加。
• 6ターンの間見えていないモンスターは存在不定状態とし、拠点に到達してもダメージを与えられないものとした。これをしないと既に倒されているモンスターが相手拠点に到達するのを期待して近くの敵ヒーローにCONTROLかけたりしちゃう。
  存在不定状態でもmanaは貰えて、mana目的で近づく行動により索敵っぽくなる。

だめだったこと

• 最初ビームサーチをしていたが、行動候補がなくなって時間いっぱい探索できなかったり、深さがほとんど探索できない場合があったりで安定しないため、chokudaiサーチに切り替えた。
• 見えていない敵ヒーローの位置をこちらの防衛コードで予測したり、相手の拠点側にいるものと仮定して探索していたが、それだとダメージが与えるのが難しくなるためか攻撃あまりしてくれない。
  いっそ存在しないことにしたほうが、とりあえず攻撃行動を取ってくれて、相手が見えたタイミングでそれを突破する行動を探索してくれるので良かった。
• 攻撃2人でWINDを打つ戦術が台頭してきて、これはまずいと思って攻撃2人でchokudaiサーチも試してみたが探索量が足りず良い動きをしてくれなかった。実装を大きく変える必要があるため攻撃2人の戦術は諦めた。

ツール類

ログ取得ボタン

画面上部に対戦結果のログをコピーするボタンを作った（Chromeプラグイン）

毎ターン入力情報をログに出しておいて、それをローカル環境で再現するために使用した。

ログの取得コードはjavascriptでこんなんでできた。

var elements = document.getElementsByClassName('stderr');
var content = "";
for (var i = 0; i < elements.length; ++i) {
  e = elements[i];
  content += e.innerText + "\n";
}

ビジュアライザ

細かく対戦結果を分析するために作成。

射程や移動先の場所等、ゲーム画面では確認できない情報を可視化できた。chokudaiサーチで予測された将来の状態も可視化できて良かった。

ローカル対戦環境

公開されている対戦サーバーのコードを使い、ローカルで大量に対戦する環境を作った。
相性ゲーなので勝率はあまり役に立たなかったが、存在しない相手にCONTROLしたとか、manaが足りないのに呪文打ったとかのログが出るのでバグチェックに使えた。

コード長削減

コドゲではコード長制限が厳しいため、コメントや空白を自動削除するツールを作ってある。#includeファイルを展開する機能、#if/#elseで無効になるコードの削除機能もある。（需要ありそうなので公開したいけど、使用上の制限が多いのを何とかしないと……）
これを使ったうえでコード長制限に引っかかってた。あとやれるとしたらシンボル名を短いのに書き換えるとかかな。

感想

防衛のルールベース部分を考えるのがつらくて、最終日まで雑な実装になっていた。
さすがに勝てなくなってたので急いで実装しなおしでバグりまくった。作業優先度が良くなかったなあ。

過去に似ているゲームを実装していた。
SoulSnatchers（旧CodeBusters）
https://www.codingame.com/multiplayer/bot-programming/soul-snatchers

マップサイズ16001x9001で霧があって複数エージェントと類似点が多い。このときやってたビームサーチの考えとかベクトルの計算処理を流用できた。
（このゲームもルールベース色が強くて実装辛かった記憶）

Nanaedaさんとの対戦成績が極端に悪くて勝率21%しかない。3人防衛による長期戦&後半SHIELD連打で手も足も出なかった。最終日に気づいたけど対策できなかった。防衛3人だとさすがに攻撃1人じゃ崩せそうにないので攻撃人数増やすとか、長期戦用の動き考えるかかな。

戦術相性とか特定の相手への対策が重要なゲームなので後だしが有利で、最終日に有給とってギリギリまで調整できたのが良かったと思う。（あといろいろ試すために提出を何度もしていて潜伏みたいになってた。どうなのかとは思うけど……）

ログ取得ボタンは今回初めて実装して世界が変わった。
今まではターンをまたいだログ情報の取得の仕方が分からず、最終ターンにまとめてゲーム開始時からのログを出すようにしていて、1ターンのログ長制限に引っかからないように情報の圧縮に苦労していた。javascriptならこんな簡単にできるんだ。

過去のゲーム経験が活かせたこと、ツール類の充実で有利取れた感じかな。

モノグサ プログラミングコンテスト2022（AtCoder Heuristic Contest 009）参加記

モノグサ プログラミングコンテスト2022（AtCoder Heuristic Contest 009）に参加しました。

結果は39位でした。

問題

atcoder.jp

やったこと

移動を少しづつ変える焼きなまし

初期解

• 氷上滑り（壁にぶつかるまで進む）を繰り返してゴールまでたどりつく経路
  • ゴール側からダイクストラみたいな計算をして、曲がる回数が少ない経路を求め、200回の移動になるように移動をだぶらせた。
• 上記でゴールできないケースでは、存在確率最大の場所からゴールに進む、を繰り返して経路を決めた

近傍

• 移動を1個削除
• 移動を1個ランダムな方向で追加
• 移動を1個選んで2回移動したことにする

ビジュアライザ

seed 0 ：氷上滑りでゴールできる

seed 2 ：氷上滑りでゴールできるが物忘れ激しい

seed 8 ：氷上滑りでゴールできない

コンテスト中考えたこと

コンテスト前は焼きなましのライブラリを整備してて、焼きなまし問題どんとこい！だった。

問題を読んでこれは焼きなましではないなと思った。（移動経路の自由度が高いから？）

ビジュアライザで手動操作してみると、壁に何度も進むことで1か所に確率を集められる。氷の上をすべってゴールまで進むみたいなパズルを解いて、壁に何度か進むようにしたらいいんじゃないかなあ。

それでゴールに到達できないケースあるかな？テストケース生成方法見たらわかるかもと思って壁の生成方法を見たけど変な記号いっぱいでてきて理解できない。

大体ゴールできるでしょと思って実装～提出。100ケース中33ケースでゴールに到達できない。この時点で100分経過。残り140分（絶望）

あかんこれじゃ全然だめだ。ゴールに到達できないケースをどうにかしないといけない。ゴールに到達できるケースも壁に何回進むかの部分を調整する必要があるので、時間あまりかけられないか。

ぱっと思いついたのが、その時点で存在確率が最大の場所からゴール方向に移動するを繰り返す。これを実装してローカルで実行したら悲しいくらい点数が出ない。とりあえず提出。

4,076,306,178点　残り80分　183位

氷上滑りでゴールにたどり着けないケースのスコアがあまりにも低すぎるので何とかしないといけないが、残り時間そんなにないしこの時点で解法決まってないのやばいよね。もうダメだあ。

新しい解法はたぶん思いついても実装する時間無さそうなので、焼きなましを入れて少しでもスコアを上げよう。あでもスコア計算ってどうやるんだろう？問題文を見ても理解できないし、いろいろ試したけどスコアが全然一致しない。うわーん。

公式テスターのコードをみて何とかスコアを計算できるようになった。しかしもう残り30分しかない。

移動経路を1個削除するという近傍だけで焼きなましをやってみた。スコアかなり上がるじゃん。

6,007,009,650点　残り25分　135位

移動経路追加と移動経路をだぶらせる近傍を追加して提出

6,972,408,352点　残り20分　39位

えーなんでこんなにスコアあがるの？考察してる時間もないし、あとは高速化とパラメータ調整ぐらいしかできなさそう。

コンテスト終了

最終スコア　7,016,045,541点　39位

ぐぬぬ

反省・感想

氷上滑りで大体ゴールできるでしょ思って実装して確認するとこに時間かかりすぎて良くなかった。

スコア計算方法理解するのに時間をかけすぎた。問題文見てもわからないならテスターのコード見たほうが早いね。

焼きなましでスコア上がるのがまだ理解できてないから考察しないと。ビームサーチ系も良いらしいけど評価値どうするんだろう。

氷上滑りできないケースはほぼ探索任せになってる。貪欲でもスコア取れるようにならないといけないなあ。

焼きなましはライブラリ整備してたおかげで実装早くできたのは良かった。

第8回 Asprova プログラミングコンテスト 参加記

第8回 Asprova プログラミングコンテストに参加したぞー

結果はなんと1位！

解法を紹介します。

問題

atcoder.jp

解法

スコア計算に使用するパラメータa,bがテストケースごとに与えられます。

• a＝ハンガー付外しコスト
• b=空きフックコスト
• a+b=100

まずa,bが極端な例を考えてみると

a=99, b=1 のとき

1度置いたハンガーは外さない。使用するハンガー数をできるだけ少なくする。製品の完成はちょっと遅くても大丈夫。

a=1, b=99 のとき

ハンガー付外しは何度行ってもいい。とにかく隙間を開けずに製造し早く完成させる。

というように真逆の解法が必要そうだったので、aの値によって解法を切り替えました。

解法①：aが大きいとき(a>=19)

1. ハンガー形状順と製造する色の順序を決める
2. ハンガーの配置を決める
3. シミュレーションしてスコアを算出
4. ハンガー配置と色順をちょっとずつ変える焼きなまし

1. ハンガー形状順と製造する色の順序を決める

形状順は、形状切り替えにかかる時間の総和が最小になるような順番にする。bitDPで最適解を出せる。

色順も同様に、色切り替えにかかる時間の総和が最小になるような順番をbitDPで算出。

2. ハンガーの配置を決める

ハンガーの配置を「ハンガー数」「右スペース数」という2つの情報で表現する。

ハンガー数の決め方

1. 全形状、ハンガー数1で初期化
2. ハンガー数から各形状の製造完了までの周回数を算出。周回数が一番多い形状のハンガーを1個増やす
3. これを一定のハンガー数になるまで繰り返す

こうすると全形状の周回数が大体同じになる。

右スペースの決め方

1. 全形状、次の形状への切り替え時間分のフック数で右スペース数を初期化
2. 一番右スペース数が少ない形状の右スペースを1増やす
3. これをハンガー数と右スペース数合わせて250になるまで繰り返す

3. シミュレーションしてスコアを算出

決めたハンガーの配置と色順通りに作業をシミュレーションする。

作業の遅れている形状の作業が進むように、途中で製造を止めたりして調整する。

作業の進捗が次の形状と同率の時、作業を譲るかどうかは製品ごとに「譲るかフラグ」を持たせてそれで判断する。このフラグは焼きなまし中に変えていく。

4. ハンガー配置と色順をちょっとずつ変える焼きなまし

変え方（焼きなまし近傍）

• 形状の順番を2点入れ替え（選択率7%）
• 色の順番を2点入れ替え（選択率7%）
• 2つの形状のハンガー数と右スペース数を1～3個書き換え （選択率17%）
• 2つの形状のハンガー数を1個書き換え（選択率12%）
• 2つの形状の右スペース数を1～2個書き換え（選択率29%）
• 1製品の作業を譲るかフラグを切り替え（選択率29%）

選択率はOptunaを使用して調整。

出力例

解法②：aが小さい時(a<19)

製品セットという単位に分ける

1000テストケースでこの分け方を試したところ、製品セット数は22～195個だった。手頃な個数かも。

これで製品セットをどの順で製造するかという問題になった。

この問題を2段階の焼きなましで解く

• 製品セットの大まかな並び順を決める焼きなまし（540ms）
• 細かい調整をする焼きなまし（1350ms）

1段階目の焼きなまし

• 貪欲法により製品セットの製造順を決める
  • 候補の製品セットの製造を全部試し評価値を算出。一番評価値の高い製品セットを次に製造するものとして確定。これを繰り返して全部の製品セットの順番を決める。
  • 評価値
    • (A)時間当たりの製造数
      　　同じ時間で沢山製造できていた方が良い
    • (B)「形状毎の進捗率」の分散
      　　全ての形状の作業進捗が同じぐらいが好ましい
    • (C)ハンガー付け外し回数
      　　付け外し少ないほうが良い
  • 順番が決まればその通りにシミュレーションしてスコアを計算できる

• 貪欲法の評価値(B)(C)に重みパラメータをつける。このパラメータをちょっとずつ変える焼きなましを行う。
  一番スコアが高かった製品セットの順番が2段階目の焼きなましの初期値となる

2段階目の焼きなまし

変え方（焼きなまし近傍）

• ランダムな範囲の作る順番を逆転させる（選択率33%）
• 2つの製品セットの順番を入れ替え（選択率33%）
• 連続している3つの製品セットの順番入れ替え（選択率8%）
• 1つの製品セットの順番を変える（選択率6%）
• 同じ製品の製品セット同士で作る個数を変更（選択率11%）
• 同じ製品の製品セット同士で作る個数を変更、を2製品同時にやる（選択率9%）

製品セットの順番を変える近傍と製造数を変える近傍がある

順番を変える近傍

製造数を変える近傍

出力例

その他工夫

• 焼きなましの近傍選択率をOptunaで調整するというのをやってみた。スコア更新頻度の大きい近傍の選択率が高くなるのかと思っていたが、全然違う結果になったのが意外だった。

おしまい