前書き
コドゲは最近だと半年に1回程度のペースで新規コンテストを行っていますが、それとは別にいつでも挑めるコンペが開催されています。*1 常設コンペのうちコンテストと同形式である対戦型のものは、コドゲのトップページから[COMPETE→GAMES→BOT PROGRAMMING→VIEW ALL]で全て表示することができます。 以降、BOT PROGRAMMINGのものを指して常設コンペと呼びます。*2
常設コンペは執筆現在50種類以上のゲームがありますが、どれがどういう性質を持つゲームなのか分からなくなりがちなので、記録がてら紹介記事にしてみました。精進したり、沼るゲームを探すのにご利用ください。
なお、最適化部門についてはValGrowthさんの紹介記事がありますので、興味のある方はこちらもどうぞ。
目次
解説基準
基本的には二人零和有限確定完全情報ゲームであればシミュレートがしやすく、AIが作りやすいゲームです。そうでないゲームはシミュレートしにくかったり、意思決定時の選択肢が増えて難しくなります。
目安として、コドゲの公式タグと独断で付けた遊びやすさを書いてみます。
用語は適当です。
タグ
コドゲ公式がゲームに付けたタグです。攻略法であり、学びの目標にもなります。
単純度
ルール自体がシンプルか。ルールがシンプルでないものは実装が重くなりがちです。
初心者向けかの指標と言えるかもしれないけど主観は強め。
確定度
二人零和有限確定完全情報ゲームは星５、要素が欠けるごとに星を減らします。
ゲーム木探索の書きやすさと言えるかもしれない。
確定度が低い場合は、一部の情報を切り捨てて探索した方が良いこともあります。
明瞭度
ルールを読むだけでシミュレータを作れる場合は星５、情報が欠けると星を減らします。*3
コドゲのルールの不親切度（あるいはGoogle翻訳の原文破壊度）かもしれない。
想定ルート
Wood～で使用する技術→Silver～Legendで使用する技術（偏見強め）
ルールベースや貪欲法はいつでも使えるので、明記していないこともあります。
私のランク
これが高いほど解説が適切である可能性が高いです。
Silver以下のゲームはよく理解出来ていない可能性が高いです。
ゲーム紹介
Line Racing(旧名:Tron Battle)
公式タグ：Flood fill, Pathfinding, Minimax
単純度：★★★★★
確定度：★★★★☆
明瞭度：★★★★★
想定ルート：BFS(DFS)→ゲーム木探索
私のランク：Legend
何かとコドゲ入門で扱われがちなヘビゲーム。
4人ゲームで損得勘定や探索深度管理がややこしい点だけが厄介だが、ゲームルールは非常にシンプル。*4
Hypersonic
公式タグ：BFS, DFS, Simulation
単純度：★★★☆☆
確定度：★★★☆☆
明瞭度：★★★★★
想定ルート：貪欲法→BFS(DFS)→ゲーム木探索（ビームサーチ）
私のランク：Legend
4人同時着手なので、全員の動きを考慮するなら探索部分は苦労しそうだが、実際は自分の動き（＋一部の特例）を探索すれば充分。
シミュレータがそこそこ重実装で、ルールに同時処理に絡む補足が多いので注意。
Mad Pod Racing(旧名:Coders Strike Back)
公式タグ：Optimization, Multi-agent, Neural network, Distances Trigonometry
単純度：★★★★★
確定度：★★★☆☆
明瞭度：★☆☆☆☆
想定ルート：ルールベース→不明（ルールベース？？？前評価？？？）
私のランク：Silver
レースゲーム（？）
あらゆる条件や計算式がルールに明記されていない代物。解析ゲーなのか雰囲気実装ゲーなのか、ニューラルネットワークに丸投げゲーなのか…？Gold(複数機操作)まで全ルールは解禁されないっぽい。
突き詰めようとすると難しそうだが、Bronze到達までに自分で書くコードは10行程度なので入門としてやるのはあり。
Great escape
公式タグ：Pathfinding, Minimax
単純性：★★★☆☆
確定度：★★★★☆
明瞭度：★★★★★
想定ルート：BFS(DFS)→ゲーム木探索
私のランク：Gold
コリドールというボードゲームが元ネタの迷路作成＆脱出ゲーム。相手がゴールしないよう妨害しつつ自分はゴールを目指す。
最大 3人ゲームなので損得勘定や探索深度管理は若干面倒だが、妨害する相手のセオリーはある様子？ 現状1手読みまでしか作っていないが、144ヵ所の壁の有無が切り替わるのでゲーム木探索が本格化すれば計算量ゲーかもしれない。
Ultimate Tic-Tac-Toe
公式タグ：Monte Carlo tree search, Minimax
単純度：★★★★☆
確定度：★★★★★
明瞭度：★★★★★
想定ルート：ゲーム木探索→ゲーム木探索（MCTS）
私のランク：Legend
〇×ゲーム（3目並べ）の中に更に〇×ゲームが入っているゲーム。
ルールさえ理解すれば素直で計算量も多くない、二人零和有限確定完全情報ゲーム。
実装は重いというより、任意で高速化のテクニックが問われる感じ。
最終的には速度勝負な部分もあるので、高速言語への移植の練習にも。
Legends of Code & Magic
公式タグ：Card game
単純度：★★☆☆☆
確定度：★☆☆☆☆
明瞭度：★★★★☆
想定ルート：ルールベース？→ゲーム木探索？事前評価？
私のランク：Silver
マジック：ザ・ギャザリング（トレーディングカードゲーム）のようなカードゲーム。*5
デッキに入れるカードをドラフトして、ドラフトしたデッキで戦う。
もちろん山札や相手の手札は見えない。使用可能な呪文の組み合わせ、クリーチャーの行動の組み合わせなど、組み合わせの最適解を探すゲームに見える。見えない情報が多いが、実際には見える情報の処理で手一杯な感じもする。
キーワード能力の組み合わせに対して説明が不足気味に見えたので、明瞭度は星１つだけ下げた。（接死トランプルの挙動は原作通りなんですかね…？）
Ocean of Code
日本語訳ルール：tsukammoの収穫記
公式タグ：なし（！？） 個人的にはPathfinding, 2D arrayあたり。
単純度：★★☆☆☆
確定度：★★★★☆
明瞭度：★★★★★
想定ルート：BFS(DFS)→パターン絞り込み→ルールベース？ゲーム木探索？
私のランク：Gold
海戦ゲーム。不完全情報を推理して敵の居場所を特定したり、逆に特定されないように立ち回ったりする。
初歩的な実装から始めて継ぎ足し強化がしやすく、他のゲームとは使用テクニックが違うこともあり、意外と万人向けな印象。逆に言うと競プロerでも詰まるときは詰まる。（相手のSILENCEへの対応が山場）
Spring Challenge 2020
日本語訳ルール：tsukammoの収穫記
公式タグ：Pathfinding, Multi-agent, Distances, 2D array
単純度：★★☆☆☆
確定度：★★☆☆☆
明瞭度：★★★★★
想定ルート：貪欲法→DFS(BFS)＋焼き鈍し法or任意の探索法
私のランク：Legend
競争型パックマン。
1プレイヤーあたり2～5体の同時操作かつ2プレイヤーの同時着手、衝突による移動の取り消しor殺害があり、さらに点アイテムも大半は視界外にある不完全情報っぷり。
Fall Challenge 2020
日本語訳ルール：tsukammoの収穫記
公式タグ：Monte Carlo tree search, BFS graph, traversal
単純度：★★★☆☆
確定度：★★★☆☆
明瞭度：★★★★☆
私のランク：Legend
想定ルート：ルールベース→ビームサーチ？ダイクストラ？MCTS？（何も分からん）
センチュリー：スパイスロードというボードゲームのほぼクローンゲーム。
2人同時着手、山札（伏せカード）の存在があり想定が難しい。
どちらかというと相手を気にせずに1人で最適解を探すゲーム。公式タグが多様な通り、比較的好きなアプローチで挑める。実際にはビームサーチをメインに使う人が多い様子。
同じIDのBREWコマンドが再登場しないという点や、先読み税の前払い辺りが読み取りにくいので明瞭度を星１下げた。
Spring Challenge 2021
日本語訳ルール：当ブログ
公式タグ：Minimax, Graphs
単純度：★★☆☆☆
確定度：★★★★☆
明瞭度：★★★★★
私のランク：Legend
想定ルート：ルールベース→（任意の評価関数による探索、もしくは同時着手MCTS）
Photosynthesisというボードゲームを元にしたゲーム。元ゲームとは結構違う。
2人同時着手ということ以外は考えやすいが、ゲーム空間が大きいうえに互いの手の影響が大きいので上手く読むのは大変。
公式タグは少ないが、貪欲法、ビームサーチ、MCTSなど、好きなアプローチでLegend到達が見込める。
説明はゲーム要素が多いうえに入り組んでいて読みづらい。日本語訳ルールもどうぞ。
Spider Attack(Spring Challenge 2022)
日本語訳ルール：tsukammoの収穫記
公式タグ：Multi-agent, Resource management
単純度：★☆☆☆☆
確定度：★★★☆☆
明瞭度：★★☆☆☆
私のランク：Legend
想定ルート：ルールベース→（三角関数、任意で何らかのゲーム木探索？）
RTS？MOBA？っぽい戦略ゲーム。コンテスト性はOceanOfCodeに近そう。
完璧な戦略を作りこむよりも雑に押し付ける戦略が強かったりで、AIそのものよりも開発者自身の戦略性を問われるゲーム。
時にはジャッジコードを解析したり、メタを分析して刺し合い（常設だと一方的に刺すだけかも）したりも必要。
自由度は高いので、「ぼくのかんがえたさいきょうのAI」を作りたい人にはお勧めかも？
有名デジタルゲーシリーズ
- Code a la Mode(Overcooked)
私はやってないので、おそらく元ゲームと同じ性質としか言えない。
Code a la Modeは珍しい純協力ゲーム。
古典ボードゲームシリーズ
-
Checkers
単純度：★★★★☆
確定度：★★★★☆
明瞭度：★★★★★
ルールは元のボードゲームそのままなので、ルールで詰まることは無いのが安心。チェッカーは手数が有限か怪しいが、それ以外は二人零和有限確定完全情報ゲーム。*6
Woodリーグしかなく、登録人数は少なめ。
あまり向かなかったもの
Blocking
公式タグ：Monte Carlo tree search, Minimax
単純度：★★★☆☆
確定度：★★★★☆
明瞭度：★★☆☆☆
Blokusというボードゲームをインスパイアしたタイル敷き詰め（？）ゲーム。2人～4人の完全情報ゲーム。
入出力ルールの説明不足感があり、最低限のプレイがおぼつかなかった。多人数完全情報ゲーム＋ビット管理してAndやOrを取るゲームとして見ると、他のゲームと被っている部分が多い。そのため解析に苦労してまでやりたいかと言われると微妙。せめて説明が充分なら…。
書いてないもの
他にもいっぱいあります。
やり次第書いていきます。（何年かかるやら）
目的別おススメゲーム
ゲームAIが初めて
Mad Pod Racing。Bronze到達まではif文を書いたりパラメータを弄るだけ。クエストマップの対象でもあるので、おそらくはコドゲ公式もここからの入門を推奨している。
BFS(幅優先探索)を使うならLine Racing。競プロから参入する人はこちらの方が馴染みやすそう。
ゲーム木探索を覚えたい
対戦相手を考慮せず自分の盤だけ考えたい → Fall Challenge 2020、Hypersonic*7
二人零和有限確定完全情報ゲームをしたい → Ultimate Tic-Tac-Toe、Othello
3人以上のゲームに挑戦したい → Line Racing(軽実装) ＞ Great escape
MCTSを覚えたい → Ultimate Tic-Tac-Toe、Othello
同時着手MCTSを覚えたい → Fall Challenge 2020、SpringChallenge 2021
こうして見ると、ゲーム木探索関連は割とバランス良く参加できている気がしますね。
シミュレーションゲームやパズルゲーム、非グリッド座標ゲーム辺りの参加が足りていない気がします。
