inani_waonの日記

コンテスト覚書

コドゲ常設コンペ(BOTプログラミング)紹介

前書き

コドゲは最近だと半年に1回程度のペースで新規コンテストを行っていますが、それとは別にいつでも挑めるコンペが開催されています。*1 常設コンペのうちコンテストと同形式である対戦型のものは、コドゲのトップページから[COMPETE→GAMES→BOT PROGRAMMING→VIEW ALL]で全て表示することができます。 以降、BOT PROGRAMMINGのものを指して常設コンペと呼びます。*2

 

常設コンペは執筆現在50種類以上のゲームがありますが、どれがどういう性質を持つゲームなのか分からなくなりがちなので、記録がてら紹介記事にしてみました。精進したり、沼るゲームを探すのにご利用ください。

 

目次

解説基準

基本的には二人零和有限確定完全情報ゲームであればシミュレートがしやすく、AIが作りやすいゲームです。そうでないゲームはシミュレートしにくかったり、意思決定時の選択肢が増えて難しくなります。

 

目安として、コドゲの公式タグと独断で付けた遊びやすさを書いてみます。

用語は適当です。

タグ

コドゲ公式がゲームに付けたタグです。攻略法であり、学びの目標にもなります。

単純度

ルール自体がシンプルか。ルールがシンプルでないものは実装が重くなりがちです。

初心者向けかの指標と言えるかもしれないけど主観は強め。

確定度

二人零和有限確定完全情報ゲームは星5、要素が欠けるごとに星を減らします。

ゲーム木探索の書きやすさと言えるかもしれない。

確定度が低い場合は、一部の情報を切り捨てて探索した方が良いこともあります。

明瞭度

ルールを読むだけでシミュレータを作れる場合は星5、情報が欠けると星を減らします。*3

コドゲのルールの不親切度(あるいはGoogle翻訳の原文破壊度)かもしれない。

想定ルート

Wood~で使用する技術→Silver~Legendで使用する技術(偏見強め)

ルールベースや貪欲法はいつでも使えるので、明記していないこともあります。

私のランク

これが高いほど解説が適切である可能性が高いです。

Silver以下のゲームはよく理解出来ていない可能性が高いです。

 

ゲーム紹介

Tron Battle

www.codingame.com

公式タグ:Flood fill, Pathfinding, Minimax 

単純度:★★★★★

確定度:★★★★☆

明瞭度:★★★★★

想定ルート:BFS(DFS)→ゲーム木探索

私のランク:Legend

何かとコドゲ入門で扱われがちなヘビゲーム。

4人ゲームで損得勘定や探索深度管理がややこしい点だけが厄介だが、ゲームルールは非常にシンプル。*4

 

Hypersonic

www.codingame.com

公式タグ:BFS, DFS, Simulation

単純度:★★★☆☆

確定度:★★★☆☆

明瞭度:★★★★★

想定ルート:貪欲法→BFS(DFS)→ゲーム木探索(ビームサーチ)

私のランク:Legend

ボンバーマン

4人同時着手なので、全員の動きを考慮するなら探索部分は苦労しそうだが、実際は自分の動き(+一部の特例)を探索すれば充分。

シミュレータがそこそこ重実装で、ルールに同時処理に絡む補足が多いので注意。

 

 

Coders Strike Back

www.codingame.com

公式タグ:Optimization, Multi-agent, Neural network, Distances Trigonometry 

単純度:★★★★★

確定度:★★★☆☆

明瞭度:★☆☆☆☆

想定ルート:ルールベース→不明(ルールベース???前評価???)

私のランク:Bronze

レースゲーム(?)

あらゆる条件や計算式がルールに明記されていない代物。解析ゲーなのか雰囲気実装ゲーなのか、ニューラルネットワークに丸投げゲーなのか…?Gold(複数機操作)まで全ルールは解禁されないっぽい。

突き詰めようとすると難しそうだが、Bronze到達までに自分で書くコードは10行程度なので入門としてやるのはあり。

 

Great escape

www.codingame.com

公式タグ:Pathfinding, Minimax

単純性:★★★☆☆

確定度:★★★★☆

明瞭度:★★★★★

想定ルート:BFS(DFS)→ゲーム木探索

私のランク:Gold

コリドールというボードゲームが元ネタの迷路作成&脱出ゲーム。相手がゴールしないよう妨害しつつ自分はゴールを目指す。

最大 3人ゲームなので損得勘定や探索深度管理は若干面倒だが、妨害する相手のセオリーはある様子? 現状1手読みまでしか作っていないが、144ヵ所の壁の有無が切り替わるのでゲーム木探索が本格化すれば計算量ゲーかもしれない。

 

Ultimate Tic-Tac-Toe

www.codingame.com

公式タグ:Monte Carlo tree search, Minimax 

単純度:★★★★☆

確定度:★★★★★

明瞭度:★★★★★

想定ルート:ゲーム木探索→ゲーム木探索(MCTS

私のランク:Legend

〇×ゲーム(3目並べ)の中に更に〇×ゲームが入っているゲーム。

ルールさえ理解すれば素直で計算量も多くない、二人零和有限確定完全情報ゲーム。

実装は重いというより、任意で高速化のテクニックが問われる感じ。

最終的には速度勝負な部分もあるので、高速言語への移植の練習にも。

 

Legends of Code & Magic

www.codingame.com

公式タグ:Card game

単純度:★★☆☆☆

確定度:★☆☆☆☆

明瞭度:★★★★☆

想定ルート:ルールベース?→ゲーム木探索?事前評価?

私のランク:Silver

マジック:ザ・ギャザリングトレーディングカードゲーム)のようなカードゲーム。*5

デッキに入れるカードをドラフトして、ドラフトしたデッキで戦う。

もちろん山札や相手の手札は見えない。使用可能な呪文の組み合わせ、クリーチャーの行動の組み合わせなど、組み合わせの最適解を探すゲームに見える。見えない情報が多いが、実際には見える情報の処理で手一杯な感じもする。

キーワード能力の組み合わせに対して説明が不足気味に見えたので、明瞭度は星1つだけ下げた。(接死トランプルの挙動は原作通りなんですかね…?)

 

Ocean of Code

www.codingame.com

公式タグ:なし(!?) 個人的にはPathfinding, 2D arrayあたり。

単純度:★★☆☆☆

確定度:★★★★☆

明瞭度:★★★★★

想定ルート:BFS(DFS)→パターン絞り込み→ルールベース?ゲーム木探索?

私のランク:Gold

海戦ゲーム。不完全情報を推理して敵の居場所を特定したり、逆に特定されないように立ち回ったりする。

初歩的な実装から始めて継ぎ足し強化がしやすく、他のゲームとは使用テクニックが違うこともあり、意外と万人向けな印象。逆に言うと競プロerでも詰まるときは詰まる。(相手のSILENCEへの対応が山場)

 

Spring Challenge 2020

www.codingame.com

公式タグ:Pathfinding, Multi-agent, Distances, 2D array

単純度:★★☆☆☆

確定度:★★☆☆☆

明瞭度:★★★★★

想定ルート:貪欲法→DFS(BFS)+焼き鈍し法or任意の探索法

私のランク:Legend

競争型パックマン

1プレイヤーあたり2~5体の同時操作かつ2プレイヤーの同時着手、衝突による移動の取り消しor殺害があり、さらに点アイテムも大半は視界外にある不完全情報っぷり。

 

Fall Challenge 2020

www.codingame.com

公式タグ:Monte Carlo tree search, BFS graph, traversal 

単純度:★★★☆☆

確定度:★★★☆☆

明瞭度:★★★★☆

私のランク:Legend

想定ルート:ルールベース→ビームサーチ?ダイクストラMCTS?(何も分からん)

センチュリー:スパイスロードというボードゲームのほぼクローンゲーム。

2人同時着手、山札(伏せカード)の存在があり想定が難しい。

どちらかというと相手を気にせずに1人で最適解を探すゲーム。公式タグが多様な通り、比較的好きなアプローチで挑める。実際にはビームサーチをメインに使う人が多い様子。

同じIDのBREWコマンドが再登場しないという点や、先読み税の前払い辺りが読み取りにくいので明瞭度を星1下げた。

 

有名デジタルゲーシリーズ

  • Code a la Mode(Overcooked)

私はやってないので、おそらく元ゲームと同じ性質としか言えない。

Code a la Modeは珍しい純協力ゲーム。

 

古典ボードゲームシリーズ

  • Checkers

単純度:★★★★☆

確定度:★★★★☆

明瞭度:★★★★★

 

ルールは元のボードゲームそのままなので、ルールで詰まることは無いのが安心。チェッカーは手数が有限か怪しいが、それ以外は二人零和有限確定完全情報ゲーム。*6

Woodリーグしかなく、登録人数は少なめ。

 

あまり向かなかったもの

Blocking

公式タグ:Monte Carlo tree search, Minimax

単純度:★★★☆☆

確定度:★★★★☆

明瞭度:★★☆☆☆

Blokusというボードゲームをインスパイアしたタイル敷き詰め(?)ゲーム。2人~4人の完全情報ゲーム。

入出力ルールの説明不足感があり、最低限のプレイがおぼつかなかった。多人数完全情報ゲーム+ビット管理してAndやOrを取るゲームとして見ると、他のゲームと被っている部分が多い。そのため解析に苦労してまでやりたいかと言われると微妙。せめて説明が充分なら…。

 

書いてないもの

他にもいっぱいあります。

やり次第書いていきます。(何年かかるやら)

 

目的別おススメゲーム

ゲームAIが初めて

Coders Strike Back。Bronze到達まではif文を書いたりパラメータを弄るだけ。クエストマップの対象でもあるので、おそらくはコドゲもここからの入門を推奨している。

BFS(幅優先探索)を使うならTron Battle。競プロから参入する人はこちらの方が馴染みやすそう。

ゲーム木探索を覚えたい

対戦相手を考慮せず自分の盤だけ考えたい → Fall Challenge 2020、Hypersonic*7

二人零和有限確定完全情報ゲームをしたい → Ultimate Tic-Tac-ToeOthello

3人以上のゲームに挑戦したい → Tron Battle(軽実装) > Great escape

MCTSを覚えたい → Ultimate Tic-Tac-ToeOthello

同時着手MCTSを覚えたい → Fall Challenge 2020

 

こうして見ると、ゲーム木探索関連は割とバランス良く参加できている気がしますね。

シミュレーションゲームやパズルゲーム、非グリッド座標ゲーム辺りの参加が足りていない気がします。

*1:コンテストという呼び方とは区別している模様。

*2:他にもコードゴルフ部門と最適化部門がありますが、ここでは割愛します。

*3:正確なシミュレータの作成に、サーバのソース解析等が必要になります。

*4:実は順位の損得勘定をしなくてもそこまで問題ない。

*5:ハースストーンの方が似ているらしい?

*6:チェッカーもコドゲのシステム上は上限ターンはありそう。

*7:情報を切り捨てて自分の盤だけ考えるくらいなら、最初から1人で完結する最適化部門(Optimization)をやった方がいいのでは…?