AHC033 参加記
AHC033
トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033）お疲れさまでした。
プレテストが49,558,778,478点で暫定2位でした。
5x5の盤面上で5台のクレーンを同時に操作して、左列の5つの搬入口から右列の5つの搬出口へ荷物を指定された順番で運ぶ問題でした。
荷物は5種類x5つの数字があり、各種類が各搬出口に対応していて、それぞれ数字が小さい順に運ぶ必要があります。
中央の3列は、荷物を一時的に退避するスペースとして使用することができます。
詳しくは公式の問題文を参考にしてください。
https://atcoder.jp/contests/ahc033/tasks/ahc033_a
おおまかな方針: ビームサーチ
クレーン1体の行動を1手とし、搬出完了までに必要な手数の下限をベースとした評価を行うビームサーチを行います。*1
ビーム幅は7000です。*2
行動
クレーン1体の行動を1手とし、番号が小さいクレーンから順に決めていきます。
本来は同時に行動するところを1クレーンずつ行動するため、
- 自分より番号が大きいクレーンの居る位置への移動を許容
- 他のクレーンと重なっているクレーンは、そのクレーンが来た方向とは別方向への移動を強制
とします。
爆破コマンド’B’は使用しませんでした。 必要になる場面はごく限られているのに対し、 評価関数の設計・状態遷移の実装が複雑になるのを嫌ったためです。*3
評価関数
評価関数は「搬出完了までに必要な手数の下限」とします。
極論、この評価関数が常に0を返したとしてもそれは「下限」ですが、それでは評価関数としては役に立ちません。
この「下限」は大きければ大きいほど真の残り手数との差分が小さくなり、評価関数として優れているといえます。
そのため、「互いに排反な」「将来確実に必要な手数」をなるべく多く足し合わせていくことで、下限を高めていくことが重要です。
搬出完了に必要な手は以下に分類されます。
- 荷物を持っているクレーンが搬出口に近づく
- 荷物を持っていないクレーンが次の荷物に近づく
- 搬出可能な荷物を掴む、荷物を搬出口に置く
- 退避が必要な荷物を搬入口から掴む、中央列に置く
上記は同時に1つまでしか実行できない、すなわち排反です。そのため、それぞれの必要回数を計算し、それらを足し合わせたものも下限となります。
荷物を持っているクレーンが搬出口に近づく
すべての荷物の搬出口までのマンハッタン距離の総和が下限となります。
クレーンが次の荷物に近づく
現在のクレーンから荷物までの距離のみではなく、各搬出口に将来発生するクレーンから荷物までの距離についても考慮したほうが良いです。
各搬出口に将来発生するクレーン数は、その搬出口の未搬出数となります。
例えば、以下のような状況の場合、
各搬出口に上から順に4,4,3,4,5回ずつ搬出することになります。
さて、「すべての荷物」に対して「現在/将来のクレーン」を最適に割り当てた時の、そのマンハッタン距離の総和が下限となります。
しかし、これを高速に求める方法は思いつきませんでした。
そのため、以下の2つの緩和をします。
- X方向の距離だけ考えて、Y方向の距離は無視する
- 全ての荷物を搬出後、全てのクレーンは左端まで移動することとする
- すなわち、X=0に疑似荷物を5つ追加する
先ほどの図の状況の場合は以下のようになります。
この緩和の下で、全クレーンに対して左または同列の荷物を割り当てることができるならば、Xの距離の和は最小となります。*4
実際、現在のクレーン5つ(X≥0)には搬入口の疑似荷物5つ(X=0)を割り当て、将来のクレーン(X=N-1)には実在の荷物(X≤N-1)を必ず割り当てることができます。
その総和は、クレーンのX座標の総和 - 荷物のX座標の総和 で求められるため、差分更新も容易です。
ここでは、2つの緩和をしました。
1つ目の緩和はできればしたくないですが、高速な方法が思いつかなかったので仕方ありません。*5
2つ目の緩和については、緩和前の問題における最適解において、搬出完了後に左に動き続けるようにした解が緩和後の最適解になり、その逆も言えます。(多分)*6
搬出可能な荷物を掴む、荷物を搬出口に置く
未搬入の荷物の個数 * 2 + 置かれている荷物の個数 * 2 + 搬出準備済み*7の荷物を持っているクレーン数 * 1 + 搬出未準備の荷物を持っているクレーン数 * 3
を下限とします。
「未搬入の荷物」「置かれている荷物」は、最低でも掴むと置くの2手が必要です。
「搬出準備済みの荷物を持っているクレーン」は、最低でも搬出口に対する置くの1手が必要です。
「搬出未準備の荷物を持っているクレーン」は、退避の置くを行った後で、搬出準備ができてから掴むと置くの計3手が必要です。
退避が必要な荷物を搬入口から掴む、中央列に置く
「必要な退避の最小回数 * 2」を下限に加えます。
必要な退避とは、簡単な例だと「ある搬入口にに同じ種類の荷物が2つ存在し、数字が大きい → 小さい順に搬入される場合の、大きい荷物の退避」があります。
より複雑な例だと、2つの搬入口が絡む場合もあります。
7を搬出するためには6の搬出必要で、6の搬入には2の搬入が必要で、2の搬出には1の搬出が必要で、1の搬入には7の搬入が必要で…と実行順序の依存関係のループができてしまっています。*8
これは「各搬入口から荷物を回収した回数」による65通りの状態に対して、「最小退避回数」をDPで求めておけばよいです。
まとめ
以上をまとめると、評価関数は以下の総和になります。
- 荷物
- ゴールまでのマンハッタン距離 - X座標 + 掴む離すの必要回数
- 掴む離すの必要回数は、
- 置いてあるなら2
- 掴まれていて、搬出準備済みなら1
- 掴まれていて、搬出未準備なら3
- クレーン
- X座標
- 搬入の状態
- 最小退避回数 * 2
- 搬出の状態
- 未搬出の荷物数 * (N-1)
- 将来出現するクレーンのX座標に対応
- 未搬出の荷物数 * (N-1)
多様性確保
状態のハッシュ化にはZobristHashを使用しています。 その際、厳密には違う状態であっても、 似た状態はあえて区別しないことで、 状態の多様性を確保しています。
各状態について、以下の要素が一致する状態には同一のハッシュが割り当てられます
- 各行ごとの(大クレーンの個数, 小クレーンの個数)
- 各搬入口ごとの搬入した個数*9
- 各搬出口ごとの搬出した個数
- 中央列(0列目と4列目以外)の置かれた荷物の有無
以下は考慮・区別していないことに注意してください。
- IDの異なる2つの小クレーン
- クレーンのX座標
- 0列目に置かれた荷物の有無
- 各位置に置かれた荷物のID
「各搬入口ごとの掴んだ個数」「中央列(0列目と4列目以外)の置かれた荷物の有無」の良さが評価値に反映されるまでには遅れがあるため、ビーム幅の多様性はなるべくこれらに当てたいです。
*1:正確には下界でしょうか。
*2:幅8000でもACしていたんですが、提出ごとの分散が激しく、1位とも点差が開いていて逆転が難しそうだったため、日和ました。
*3:要するに面倒だったということです。ここまで僅差ならやったほうが良かったんだろうか。
*4:証明略
*5:例えば横方向と縦方向を独立に考えて、縦方向も貪欲な割り当てをやろうとすると、「荷物が左上と右下にある」「クレーンが右上と左下にある」というケースが評価値良くなって困りました。
*6:例外あったら教えてください。もちろん、適宜上下に移動する前提です。
*7:同じ種類の自分より小さい荷物がすべて搬出された荷物のこと
*8:「運んでいるうちに追いつく」というケースもありますが、考慮してないです。
*9:盤面に出現したうえで、クレーンが掴んだら、搬入したとみなしています
codingame 2023春 ローカル環境構築(自分用メモ)
やったこと
ボンドさんの真似
Codingameのローカル対戦環境をdockerでポンする - 接着剤の精進日記
jiro:~/work$ git clone https://github.com/EmulsionBondo/CodingameLocalBattle.git
jiro:~/work$ git clone git@github.com:CodinGame/SpringChallenge2023.git
jiro:~/work$ curl -OL https://github.com/dreignier/cg-brutaltester/releases/download/1.0.0/cg-brutaltester-1.0.0.jar
jiro:~/work$ ls CodingameLocalBattle SpringChallenge2023 cg-brutaltester-1.0.0.jar
2023春をcg-brutaltesterに対応
https://github.com/dreignier/cg-brutaltester#all-steps
Modify the pom.xml file.
2022春のpom.xmlを参考にして、SpringChallenge2023/pom.xmlを以下で置き換え
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>com.codingame.game</groupId>
<artifactId>spring-2023-ants</artifactId>
<version>1.0-SNAPSHOT</version>
<properties>
<gamengine.version>4.4.2</gamengine.version>
<maven.compiler.source>1.8</maven.compiler.source>
<maven.compiler.target>1.8</maven.compiler.target>
</properties>
<dependencies>
<dependency>
<groupId>com.codingame.gameengine</groupId>
<artifactId>core</artifactId>
<version>${gamengine.version}</version>
</dependency>
<dependency>
<groupId>com.codingame.gameengine</groupId>
<artifactId>module-endscreen</artifactId>
<version>${gamengine.version}</version>
</dependency>
<dependency>
<groupId>com.codingame.gameengine</groupId>
<artifactId>runner</artifactId>
<version>${gamengine.version}</version>
</dependency>
<dependency>
<groupId>commons-cli</groupId>
<artifactId>commons-cli</artifactId>
<version>1.3.1</version>
</dependency>
</dependencies>
<build>
<plugins>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-compiler-plugin</artifactId>
<version>3.3</version>
<configuration>
<source>1.8</source>
<target>1.8</target>
</configuration>
</plugin>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-jar-plugin</artifactId>
<version>3.1.0</version>
<configuration>
<archive>
<manifest>
<addClasspath>true</addClasspath>
<mainClass>com.codingame.gameengine.runner.CommandLineInterface</mainClass>
</manifest>
</archive>
</configuration>
</plugin>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-shade-plugin</artifactId>
<version>2.4.2</version>
<executions>
<execution>
<phase>package</phase>
<goals>
<goal>shade</goal>
</goals>
<configuration>
<transformers>
<transformer
implementation="org.apache.maven.plugins.shade.resource.ManifestResourceTransformer">
<mainClass>com.codingame.gameengine.runner.CommandLineInterface</mainClass>
</transformer>
</transformers>
</configuration>
</execution>
</executions>
</plugin>
</plugins>
</build>
</project>
Add the CommandLineInterface class in the package com.codingame.gameengine.runner
SpringChallenge2023/src/main/java/com/codingame/にgameengine/runner/ディレクトリを作成して、その中に
2022春のCommandLineInterface .javaをそのまま突っ込む
追記：2023/06/01
src/main/java/com/codingame/game/Config.javaの SCORES_IN_IO が false になってるので、trueに直す
ボンドさんの続き
jiro:~/work$ docker run -it --rm --name my-maven-project -v $PWD/SpringChallenge2023/:/usr/src/mymaven -w /usr/src/mymaven maven:3.3-jdk-8 mvn clean install package ... (たくさんのログ) ... [INFO] ------------------------------------------------------------------------ [INFO] BUILD SUCCESS [INFO] ------------------------------------------------------------------------ [INFO] Total time: 14.670 s [INFO] Finished at: 2023-05-25T17:21:22+00:00 [INFO] Final Memory: 56M/655M [INFO] ------------------------------------------------------------------------
jiro:~/work$ cp SpringChallenge2023/target/spring-2023-ants-1.0-SNAPSHOT.jar ./ jiro:~/work$ ls CodingameLocalBattle SpringChallenge2023 cg-brutaltester-1.0.0.jar spring-2023-ants-1.0-SNAPSHOT.jar
jiro:~/work$ docker build -t local_battle ./CodingameLocalBattle/ jiro:~/work$ docker run -it -d --name local_battle -v $PWD:/work local_battle
結果
./mainは適切に自分のプログラムに置き換えてください
jiro:~/work$ docker exec local_battle java -jar cg-brutaltester-1.0.0.jar -r "java -jar spring-2023-ants-1.0-SNAPSHOT.jar" -p1 "./main" -p2 "./main" -n 10 02:31:36,775 INFO [com.magusgeek.brutaltester.Main] Referee command line: java -jar spring-2023-ants-1.0-SNAPSHOT.jar 02:31:36,775 INFO [com.magusgeek.brutaltester.Main] Player 1 command line: ./main 02:31:36,775 INFO [com.magusgeek.brutaltester.Main] Player 2 command line: ./main 02:31:36,775 INFO [com.magusgeek.brutaltester.Main] Number of games to play: 10 02:31:36,776 INFO [com.magusgeek.brutaltester.Main] Number of threads to spawn: 1 02:31:37,368 INFO [com.magusgeek.brutaltester.GameThread] End of game 1 0.00% 0.00% 02:31:38,312 INFO [com.magusgeek.brutaltester.GameThread] End of game 2 50.00% 0.00% 02:31:39,214 INFO [com.magusgeek.brutaltester.GameThread] End of game 3 33.33% 33.33% 02:31:39,995 INFO [com.magusgeek.brutaltester.GameThread] End of game 4 25.00% 50.00% 02:31:40,888 INFO [com.magusgeek.brutaltester.GameThread] End of game 5 20.00% 60.00% 02:31:41,502 INFO [com.magusgeek.brutaltester.GameThread] End of game 6 16.67% 66.67% 02:31:42,181 INFO [com.magusgeek.brutaltester.GameThread] End of game 7 14.29% 71.43% 02:31:42,981 INFO [com.magusgeek.brutaltester.GameThread] End of game 8 12.50% 75.00% 02:31:43,599 INFO [com.magusgeek.brutaltester.GameThread] End of game 9 11.11% 77.78% 02:31:44,232 INFO [com.magusgeek.brutaltester.GameThread] End of game 10 20.00% 70.00% 02:31:44,233 INFO [com.magusgeek.brutaltester.Main] *** End of games *** +----------+----------+----------+ | Results | Player 1 | Player 2 | +----------+----------+----------+ | Player 1 | | 20.00% | +----------+----------+----------+ | Player 2 | 70.00% | | +----------+----------+----------+
参考
AtCoder Heuristic Contest 001
アルゴリズムの流れ
- 解(=各企業の領域)を初期化する
- いくつかの企業の領域を変更する(突然変異)
- 全ての企業をある方向に寄せる(引力発生)
その際、評価値が低い企業は引き伸ばす
3. は方向を変えて4回繰り返す - 2.3.の操作を近傍とみなして焼き鈍し
- 最後に、最良解について、微調整を行う
初期化
すべての企業の領域を、その基準点を囲う面積1の正方形とする
突然変異
ターゲット指定/範囲指定/ランダム の3種類から1つを行う
採用確率は
序盤から中盤 : 80%/14%/6%
終盤 : 20%/56%/24%
ターゲット指定
- 面積がr * max_per_r * 0.95より小さい企業からランダムにターゲット企業を選ぶ
※ max_per_r は時間経過につれて大きく - ターゲット企業の新しい端点y1 y2 x1 x2を、
世界の端(0または10000)と基準点の間からそれぞれ一様ランダムに選ぶ - ターゲット企業の評価値が大きく悪化していたら2からやり直し
- 他の企業の基準点を内包していたら2からやり直し
※ 累積和でO(1)で判定 - ターゲット企業と接触している企業の領域を適切に縮小する
※ すべての企業について愚直に確認 O(n)
※ y1 y2 x1 x2のうち1つを変更することで縮小
範囲指定
- ある大きさの正方形を一様ランダムに配置
※ 1辺の長さは時間経過とともに短く - 正方形と接触しているすべての企業の面積を1にする
ランダム
- すべての企業について、ある確率に基づいて面積を1にする
※ 確率は時間経過とともに小さく
引力発生
- 引力方向を決める
- 評価値を改善するターゲットとして「評価値の低い企業 + ランダムにいくつか」を選択
- 基準点が引力方向に近い企業から順に、引力をかける
・ターゲット→引力方向に、衝突するギリギリまで引き伸ばす。ただし、面積がr * max_per_r を超えないように調整
・非ターゲット→引力方向に、衝突するギリギリ/基準点が飛び出さないギリギリ まで平行移動
※ 区間をsetで管理する or 遅延セグ木を使う → 全体でO(nlogn)
※ 実際は区間をvectorで管理したほうが早かったのでそうした
1~3を方向を変えて4回繰り返します。
微調整
- 企業と企業の境界線を1マスずらしてみて、評価値が改善されるなら採用
- 引力発生(ただし平行移動のみ)
これらをたくさんやる
何をしたら伸びた？
最初期は引力のみ
突然変異を導入
← それまでは領域の縮小が無かったので、当然伸びる
引力発生の3において max_per_rを導入
← 想像以上に伸びてびっくりした
スペースに余裕のある企業は後でどうにでもなるので、
評価値の低い企業にスペースを譲るのが大事？
突然変異にターゲット指定を追加
← これも結構伸びた
ターゲット指定においてターゲットと接触した企業の対処を、
面積を1にする にしていたが 適切に縮小する に変更
↓
1回の突然変異に対して引力発生を30回行っていたが、
4回に減らしても改善解が発見されるようになった
← 近傍探索を行える回数が増えたので伸びた
微調整を導入
← 結構伸びる
(焼き鈍しフェイズがざっくりしているから というのは要因としてありそう)
定数倍高速化は行う度に大きく伸びた
山登りと焼き鈍しはあまり変化が無かった気がする...?
困ったこと
点数の分散が大きく(同じコードをsubmitしても49599~49624のブレ)、
コードの変更が改良なのか改悪なのか判断できなくて困った。
どうすればいいのでしょうか。
次回の長期マラソンではやりたいこと
- 解が改善されていく様子を確認するためのビジュアライザの作成
- パラメータチューニング
- 何をしたら何点伸びたのかメモしておく
