CodinGame を知っていますか？
私はよく知りませんでした *1 。
ちょうど TL で少し流行っていた Line Racing というのが初心者向けと聞いてやってみました。
1～2 週間ほどやりましたが、一旦やりたいことはだいたいできたので *2 感想を書いておきます *3 。
CodinGame って何？
- 対戦ゲームをプレイするプログラムを作って、強いプログラムを作った方が勝ち
Line Racing って何？
いわゆる常設コンテストという部類らしく、期間無制限で遊べるらしい。
ルールはこんな感じ。
- 2～4人対戦で、 20×30 のグリッド内でリボンを上下左右に伸ばしていって、伸ばせなくなった人が負け
- 3人以上の場合、負けたプレイヤーのリボンは丸ごと消えるので注意
- 制限時間は一手100ms（Python だと結構きつい）
どういう戦略？
おそらくこういうゲームでは探索アルゴリズム（ビームサーチとか minimax とか？）で何手先まで読むかみたいな勝負になりがちな気がしました。
そっちを勉強しながらやってみる手もあったかもですが、今回は評価関数のみでやってみました。
理由はいくつかありますがこのあたりです
- Python でやると C++ などの言語にスピードで負けるため、何手先まで読めるかみたいな勝負をしても勝てる気がしないため *4
- 評価関数で実装する方が簡単な気がしたため
- ゲームが単純かつ盤面がそこそこ広いので、数手先まで読むより大局的に評価する方が有効な気がしたため
結果的には
という感じになりました。
結果は？
順位は常に変動しますが、最終的に 30 位台ぐらい *7 （Legend の上位 6% 程度）までいけました。
最初は正直どこまでいけるかは分からなかったですが、初めてにしては十分かなという気はします。
Line Racing 34 位（国内 4 位）
— きり (@kiri8128) January 8, 2022
だいぶ疲れてきたので一旦ここらでアルゴの世界に戻るかな pic.twitter.com/8Ys7L1nMlG
具体的なアルゴリズムは？
基本的には「自分が一番近いマスの個数」をベースに作った評価関数が一番高くなるマスに移動します。
詳細なアルゴリズムはここには書きませんが、ツイートにいくつか心の声が漏れていたので、参考に。
3 人以上対戦の評価関数、得点（評価）差のシグモイド関数の合計みたいにすると良くなった気がしてるけどこれ一般的なのかな？
— きり (@kiri8128) December 21, 2021
よく考えたら正規分布の累積分布関数とかでも良かったかもです。プロットしたら似てたのでまあ良しということで。
あと例えば自分と相手がどっちも Closed になったら逆転が難しくなるので評価を極端にするなどもしました。
二重頂点連結成分分解ライブラリ、何を返すのが良いかな
— きり (@kiri8128) December 20, 2021
関節点があると行った後戻って来れないんですよね。実装大変だった。
先に死にそうな相手がいる場合に、どの連結成分からなら何ターン後に行けるかみたいな判定も大変です。細かいところは正確性を多少犠牲にして実装をサボりました。
競プロ（アルゴ・マラソン）のコンテスト・精進との違い
コードの書き方
長期戦になりがちなので、コードの書き方がかなり変わりました。
変数名もちゃんと分かりやすい名前にしたり *8 class も一から作ったり *9 。
そう言えば今日の G では変数名を分かりやすく stack_max / stack_min とかにしました（えらい！）。こどげで気を付けていた効果かも。
— きり (@kiri8128) January 8, 2022
今までなら X / Y とか（良くて sma / smi とか）になってた気がします
作業の進め方
Last Battles をたくさん見て、一つずつ確認していく作業になりました。提出コードから毎ターン標準エラーに状態を吐き出すことで、手元でデバッグできるようにしてからだいぶラクになりました。
- アイデアを考える
- ロジックを決める
- 設計を考える
- 実装する
- 大丈夫そうなら Submission する
- Last Battles をたくさん見る
- 意図していない挙動があれば手元でデバッグする
- 考慮できていない理由で負けていたらどういう判定にすればよいかアイデアを考える
改善したつもりでも順位が下がったりすることもあって、どれが良くてどれが悪いのかの判断がとても難しかった気がします *10 。
レアケースだけど、そのケースにおいては必ず得になるみたいなのもいくつか思い付いたけど、結局コスパを考えてあんまり入れませんでした。「2 人かつ初期配置が対称的かつ自分が後手」の場合は対称戦略で勝てるというのだけは、実装も簡単なので入れました。
Line Racing いろいろアップグレードしたつもりがするたびに順位下がってなんでだーってなってる
— きり (@kiri8128) January 4, 2022
感想
ちょうど AtCoder の Rated がない時期だったのと年末年始休暇も使えたので、ゆっくり取り組めました。
アルゴのコンテストとは違う面白さがありますね。
自分が提出したとき、自分のプログラムが戦っているのを見るのはテンション上がりますね。寝るときもずっと Last Battles TV を見続けてしまってました。
自分が提出したとき以外にも勝手に戦っているようで、気付いたら順位が上下しているのも常に参加している感じで良いですね。
頑張って実装したのに順位が上がらないのはつらいですが。
あと同時期にやっていたメンバーがいたのはモチベーションになりましたね。さんだーさんがちょうど狙えそうな位置にいたのも良かったです。
アドバイスくれたさんだーさん、同時期にやっていたかえでさん、ゆうさんろんどん、クルトンさん（？）には感謝です。
*1:実は前回のやつに参加していたみたいですが、ルールとかを理解する前にやめてしまってました
*2:疲れたので
*3:期間無制限なので、何か書くとかしないとやめどきが難しいんですよね
*4:こどげは PyPy も使えないようで、 C++ などに比べると数十倍遅くなる可能性があります
*5:「敵プレイヤーが一手進めた状態」などを計算しない
*6:定数倍はそこそこ重い。これでも TLE でたまに落ちてた（！）
*7:本記事執筆時点で 34 位
*8:Global のは X とかもあったけど
*9:アルゴではライブラリになってるもの以外 class はほとんど使わないので
*10:同じコードでも Legend の 30～60位ぐらいまで変動することもあったり
