予習は大切、どうもかわしんです。
「天下一 Game Battle Contest 2023」に参加しました。4位でした。
去年このコンテストの存在をちょうど終了した時に知ってやりたいなと思い、Twitter アカウントをフォローして1年待ってました。今回の大会は去年の大会がベースになっているということで事前に予習してから挑みました。
ルールは以下を参照してください。
tenka1-2023/problem.md at master · KLab/tenka1-2023 · GitHub
言語の選択
個人的には Rust か Python がなれているのですが、Go で参加することにしました。
- Rust
- 所有権とか、mutable/immutable の制限を気にしながら書くのがめんどくさい。素早く書けない。
- 複数スレッドでの処理もめんどくさい
- Python
- 素早く書けるけど、シングルスレッドになる
- Go
4 方向への予測をマルチスレッドで並列に処理できたら有利だなと思ったので Go でやりました。が、結局僕のロジックはシングルスレッドで全部計算しても 10 ms もかからず、500ms の制約を十分クリアできたのでマルチスレッドの必要はなかったです。
Go は愚直に書かないといけないのでシンプルにめんどくさかったです。ぶっちゃけ Rust で書いた方が実装速度が速かったような気もします。
細かい小技
スタートダッシュ
2023 のコンテストは 2022 のコンテストと同様に複数リーグの構成になっていて、それぞれのリーグの上位数名と下位数名が上下のリーグに移動しながら4時間かけて順位が決まっていくルールになっています。
決勝に進める 1 ~ 8 位もそもそも最上位のクラス 1 のリーグにいないとなれません。リーグ自体は参加した時点で一番下のリーグに組み込まれるので、素早く試合に参加することでスタート地点を有利にすることができます。
予習してたので、ルールが公開されて大体のルールが同じことを確認してから、すぐにサンプルコードで試合を開始して無事クラス 1 のリーグからスタートすることができました。
バージョン管理
運営から提供される gorunner はそれぞれの試合ごとに登録されたコマンド (go run main.go) を実行して試合に参加させます。
Go のサンプルコードは tenka1-2023/go/main.go にありますが、これを開発しながら並行して試合に参加するとコマンド実行のタイミングによっては main.go がコンパイルに失敗したり中途半端なロジックの状態で参加することになってしまいます。そのため、main.go で開発して実装の区切りがついたら以下のコマンドを実行してバージョン管理をしてました。
cp main.go v0001.go go build v0001.go
実装したロジック
大枠としては、2つのエージェントそれぞれについて４方向に進んだ時にどういう感じに有利かを判定して比べながら一番いいものを選択するという方式でやりました。４方向はそれぞれ Prediction 型で表すことにしました。
戦術的優先度
ShortTermPrediction で表しているのが、1 手先のどのマスが有利なのかです。1 手先のマスの状態によって ShortTermPredictionValue で優先度をつけます。空白が一番優先度が高いです。
const ( EmptySteal ShortTermPredictionValue = iota EmptyMayStolen Empty EmptyMayConflict SelfHalfMayConflict EnemyHalf EnemyHalfMayConflict SelfHalfRecover EnemyFullCanSteal EnemyFull SelfHalf EnemyFullMayConflict EnemyHalfMayStolen // TODO EnemyHalfMayConflictEnemy SelfFullMayConflict EnemyFullMayRecovered SelfFull Others Dont )
また、進む先のマスの 1 マス先、2 マス先をそれぞれ見て、敵のエージェントがいないかどうかを確かめます。もしいる場合は、相手が被る方向に移動してきた時に有利になるかどうかで優先順位が変わります。例えば敵の半壊のマスはEnemyHalf* の派生で優先順位が決まります。
if state[1] == 1 { priority = EnemyHalf if len(enemies0) > 0 { priority = Dont } else if slices.Contains(enemies1, state[0]) { priority = EnemyHalfMayConflictEnemy damageTarget = slices.Contains(enemies1, target) } else if len(enemies1) > 0 { priority = EnemyHalfMayConflict damageTarget = slices.Contains(enemies1, target) } else if len(enemies2) > 0 { priority = EnemyHalfMayStolen damageTarget = slices.Contains(enemies2, target) }
一番ムカつくのが自分が全壊にしたマスを敵に取られることなので、それが起きないように Dont を指定しています。
ターゲット指定
以下の記事で紹介されていた通り、順位が最終的なポイントに直結するので、1 位の時は 2 位の敵を、1 位でない時は一つ上の順位の敵を優先して攻撃するようにしました。EstimateRanking() で順位を予測しています。
天下一 Game Battle Contest 2022 参加記 - matsu7874のブログ
戦略的優先度
例えば周りが全部自分のマスに囲まれた時1手先の優先度だけでは効率的に動けません。
そのため、4 方向へのそれぞれの最短で到達できるエリアに存在するマスの状態によって potential を計算し (CalcPotential())、もし potential が低い方向（つまり自分のマスが多く意味の薄い方向）に移動しようとした場合は、第 2 優先の方向へ移動するようにしました。
if idx_0 == 0 {
minPotential := predictions0[0].potential
minPotentialIdx := 0
maxPotential := 0
for i, p := range predictions0 {
if p.potential <= minPotential {
minPotential = p.potential
minPotentialIdx = i
}
if p.potential >= maxPotential {
maxPotential = p.potential
}
}
if predictions0[0].shortTermPrediction.priority > SelfHalfMayConflict && minPotentialIdx == 0 && maxPotential-minPotential > 700 {
log.Println("potential 0")
idx_0 = 1
}
}
不利なマスの乗り越え
1 マス先だけを見ているとあるマスを隔てて空白マスが広がっていた時にそちら側に移動することができません。壁になってるマスを乗り越えて空白マスを取りに行くと有利になります。
2 マス先の考慮を Length2Prediction で行うことにしました。ただし、わざわざ不利なマスを乗り越えていった直後に敵にそのマスを取られるのは悔しいので空白マスの周囲に敵がいるかどうかを検証して、マスの乗り越えをするかを判断します。
周期的な動きの抑制
一番優先順位の高いマスを選びランダムな要素はないので、似たようなユーザーと鉢合わせた時に同じ2マスを交互に移動し続けたり、周期的な挙動をする可能性があります。その場合自分の得点が変わらないまま周期的な動きをしていないユーザーだけが動き続けて不利になってしまいます。そのため、2ターン周期と4ターン周期で同じマスに同じ状態で移動していないかを確認して、無限に周期的な動きをしてターンを浪費することを防ぎます。
// pendulum 2
if len(agentLog) > 2 {
previousPos := agentLog[len(agentLog)-1][0]
pos := predictions0[0].pos
if IsSamePos(pos, previousPos) && IsSameState(move.Field[pos[0]][pos[1]][pos[2]], fieldLog[len(fieldLog)-2][pos[0]][pos[1]][pos[2]]) {
log.Println("pendulum 0 for 2")
idx_0 = 1
}
}
// pendulum 4
if len(agentLog) > 4 && idx_0 == 0 {
previousPos := agentLog[len(agentLog)-3][0]
pos := predictions0[0].pos
if IsSamePos(pos, previousPos) && IsSameState(move.Field[pos[0]][pos[1]][pos[2]], fieldLog[len(fieldLog)-4][pos[0]][pos[1]][pos[2]]) {
log.Println("pendulum 0 for 4")
idx_0 = 1
}
}
特殊移動
今回の大会では特殊移動が新しい要素として加わりました。4 方向のどれかに 5 マス移動して強制上書きするか、任意の場所にジャンプして周囲の 5 マスを強制上書きすることができる機能でエージェントにつき 1 回まで実行できます。
ぶっちゃけ上の部分で時間を使ってしまったので特殊移動は十分に考えることができなかったです。
任意ジャンプした場合は周囲 4 マスが塗りつぶされ、その次の移動は必ず自分のマスになるため、1 ターン無駄になります。そのため、縦に強制上書きするものだけ選択するようにしました。(NewSpecialPredictionStraight())
前半で特殊移動しても点数に加算されないので後半になったタイミングで実行するようにしました。また2つのエージェントが同時に特殊移動してマスが被ったら無駄なので違うタイミングで特殊移動するようにしました。（被るかどうかは予測可能なので余裕があれば改善できた）
感想
最初の方はスタートダッシュがうまくいって 1 位をキープできていたのですが、途中から抜かされてしまいました。考慮できる点はもっとあったし、もっと無駄な移動を省けていたはずなのでその差だと思います。4時間はあっという間でした。
楽しかったです。
