ヴァルのゲームAI開発記

ヴァルの開発記

コンテスト参加記など

CodinGame 最適化ゲームの紹介

この記事はCodinGameの一人用最適化ゲームの紹介記事です。

CodinGameといえば対戦ゲームが定番ですが、一人でやる最適化ゲームも実はけっこう充実しています。このたび全ての最適化ゲームをプレイし終えたので、それらの紹介記事を書いてみることにしました。

Optimizationカテゴリ

CodinGameにはOptimizationというカテゴリがあり、最適化ゲームはそこに分類されています。このカテゴリのゲームは一人でプレイし、ハイスコアを競います。

f:id:ValGrowth:20201202002618p:plain

Optimization ゲーム一覧

この記事で使う指標

・公式評価

  CodinGameユーザーによる投票の5段階評価の平均点(2021年3月14日 現在)

・私の評価

  私が好きかどうか

  ★1~★5(好きでない~好き)の5段階で評価

・問題の単純さ

  問題の内容が分かりやすいか

  ★1~★5(分かりにくい~分かりやすい)の5段階で評価

・クリア難易度

  問題の制約を満たす最低限の解を実装する難易度(最適化の難易度ではない)

  制約を満たすサンプルコードがあるときは難易度0とする。

  それ以外の場合は1~5(簡単)~(難しい)の5段階で表現。

 

本記事ではネタバレ防止のため解法や使用するアルゴリズムを紹介しないので、全体的にふんわりした内容になります。

ゲーム紹介

画像クリックでゲームのページに飛びます

A* Craft

f:id:ValGrowth:20201202003605p:plain

  公式評価:4.6

  私の評価:★★★★★

問題の単純さ:★★★★★

クリア難易度:0

【概要】

自動で前進する複数のロボットを、地面に矢印を置いて誘導する。できるだけ長いターン数、ロボットを地面から落とさずにいられたら高得点。

【評価】

見た目がかっこいいので眺めてるだけでも楽しい。ロボットくんが賢い動きをしてくれるようになるとさらに楽しくなる。TopCoderラソンマッチとかが好きな人に特にオススメ。過去にコンテストとして開催されたため、フォーラムに情報が充実しており、勉強に適している。

【難易度】

初期コードをそのまま提出すればScore100%が得られる。

ロボットの動きが単純なのでシミュレーションを書くのも簡単。

 

2048

f:id:ValGrowth:20201202005217p:plain

  公式評価:4.6

  私の評価:★★★★★

問題の単純さ:★★★★☆

クリア難易度:2

【概要】

全てのパネルを同時に上下左右に動かし、同じ数字をくっつけることで得点を得る。わりと流行ったゲームなのでスマホアプリとかで探せば無料のやつが見つかる。CodinGame上の2048では乱数Seedが与えられるため、次に出現する2や4のパネルの位置は計算できる。

【評価】

Seedが与えられるため運要素が無いのがとても良い。高速化の練習にも向いている。

自分が手動でやるときの動きをコンピュータにやらせるにはどうすればよいか、というのを考える良い題材なので初心者にもオススメ。

【難易度】

何も起こらない行動をするとInvalid Moveだと怒られてしまうため、意味のある行動を出力しないとダメ。

シミュレーションする場合は、次に出現するパネル位置の計算方法を知るためにゲームのソースコードを読む必要があるため少したいへん。

 

Mars Lander

f:id:ValGrowth:20201202010634p:plain

  公式評価:4.6

  私の評価:★★★★★

問題の単純さ:★★☆☆☆

クリア難易度:4

【概要】

火星着陸ゲーム。機体の角度と推進力を制御して水平な地面に着陸させることでゲームクリア。ただし着陸させる際は機体を水平にし、かつ速度が低い状態でなければならない。最適化要素は、使用する燃料を最小化すること。

【評価】

詰めていくと美しい動きをするので見た目が楽しい。人それぞれいろんなやり方でクリアできるのも良い点。

【難易度】

着陸の条件がけっこう厳しめだが、わりと雑なやり方でもゴリ押せてしまえるので楽しい。ルール理解のために先にMARS LANDER - EPISODE 1をやるのがオススメ。

 

Code of the Rings

f:id:ValGrowth:20201202012604p:plain

  公式評価:4.6

  私の評価:★★★★☆

問題の単純さ:★★★☆☆

クリア難易度:3

【概要】

自キャラ(ビルボくん)に魔法の文字列を作らせて森から脱出させてあげるゲーム。ビルボくんは左右移動と、頭上の石を叩くことができる。石を叩くことで[空白→A→B→C→...→Z→空白]と1文字ずつ進めることができる(Z→Y→X→...と逆順に進めることも可能)。指定された文字列を石で作ることでゲームクリア。

最適化要素はビルボくんの行動回数を少なくすることだが、複数回の行動を括弧で囲うことでループ行動をさせることができ、ループ2周目以降は行動回数としてカウントされないのでビルボくんを上手くループさせることで高得点が得られる。叩いた石が空白ならループから脱出する。

【評価】

最適化問題のよくある定石を実装して終わり、ということにはならない(と思う)のでいろいろ考えるのが楽しい。細かい改善の積み重ねでけっこう良くなるので微改善を積み重ねるのが好きな人に向いている。

【難易度】

ループを使わない解を実装するまでは初心者にもオススメできる程度の難易度。ループ命令を使おうとすると一気に難易度が上がる。

 

Search Race

f:id:ValGrowth:20201202015112p:plain

  公式評価:4.7

  私の評価:★★★★☆

問題の単純さ:★★☆☆☆

クリア難易度:3

【概要】

車を操作してコースを3周するとクリア。Bot ProgrammingにあるCoders Strike Backから対戦要素を除外したもの。

【評価】

ゲームのコードが公開されておりシミュレーションの実装に困らないのが良い。

【難易度】

シミュレーションしなくても、速度と位置の関係から目的地に行くために与える加速度を考えてやるとかでもいい感じに走るようになる。シミュレーションを実装するのはやや大変。

 

SameGame

f:id:ValGrowth:20201205143432p:plain

  公式評価:4.7

  私の評価:★★★★☆

問題の単純さ:★★★☆☆

クリア難易度:2

【概要】

さめがめ。4近傍に2つ以上連結しているブロックの集まりを消すことができる。消したブロック数に応じて指数関数的に増えるスコアがもらえる。ブロックを消すと上にあるブロックが下に落ち、1列ぜんぶ空になると左に詰められる。2つ以上連結しているブロックが無くなった時点で終了。全てのブロックを消すとボーナス点がもらえる。

【評価】

ポップなデザインがかわいい。ブロックが横にも移動するので先を予測するのがけっこう難しい。

【難易度】

最適化を無視してValidな解を書くだけなら簡単。

シミュレーションをする場合は4近傍の繋がりを計算したりブロックが落ちるとか左に詰めるとかのシミュレーションを書く必要があり少しだけ大変。

全消しを狙ってとるのはとても難しい(私には無理だった)。

 

Code vs Zombies

f:id:ValGrowth:20201205145659p:plain

  公式評価:4.7

  私の評価:★★★☆☆

問題の単純さ:★★★☆☆

クリア難易度:3

【概要】

アッシュおじさんを操作してゾンビを倒す。マップ上にいる人間(アッシュを除く)が1人でも生き残った状態でゾンビを全員倒すとクリア。人間が全員やられたら負け。アッシュは最強なので死なない。ゾンビを倒すと点数が得られる。その時点で生き残っている人間の数が多いほどスコアがたくさんもらえ、またゾンビを1ターンにたくさん倒すとフィボナッチ数列に従って増える高得点がもらえる。

【評価】

人間を守りつつゾンビを倒すのを狙うのか、1人以外の人間を捨ててゾンビを1ターンにたくさん倒すのを狙うのか、トレードオフの関係があり考えるのが楽しい。テストケースごとに立ち回りを変えるのもアリ。

【難易度】

単純な解法を考えるのもけっこう難しい。テストケースが凝って作られていて、雑に書いた解法はけっこう落とされてしまう。

 

Bender - Episode 4

f:id:ValGrowth:20201205152720p:plain

  公式評価:4.8

  私の評価:★★★☆☆

問題の単純さ:★★☆☆☆

クリア難易度:5

【概要】

Benderくんを友人Fryのもとへ誘導してあげるゲーム。マップ上には磁場が形成されている場所がありBenderくんは触れると死んでしまう。それぞれの磁場には同じ色のスイッチがマップ上に存在していて、それを踏むことで磁場をON/OFFできる。またマップ上にはゴミのボールが置いてあり押してどかすことが出来るが、押した先にFryがいたら圧死してしまう。

Benderくんの行動を記述した文字列を出力し、その長さがスコアになる。短いほど良い。一連の連続した行動を定義したファンクションを9つ登録することができ、ファンクション呼び出しを行うことで文字列を短くすることができる。

【評価】

最適化を考えずにただFryのところへ誘導するだけでもけっこう難しい。ゴミボールをどかして移動を最適化するところまで考えられる人はかなり少ないだろう。

行動は1ターンでまとめて出力しないといけなく、ターンごとの入力は与えられないのでシミュレーションの実装が必須になるのもつらい。

実力がある人にとっては良問だと思う。

【難易度】

解くためにアルゴリズムの知識が必要なので初心者には厳しそう。

 

Bulls and Cows 2

f:id:ValGrowth:20201205151257p:plain

  公式評価:4.4

  私の評価:★★☆☆☆

問題の単純さ:★★★☆☆

クリア難易度:4

【概要】

マスターマインドに似たゲーム。隠されたn桁(1≦n≦10)の数列を言い当てると勝ち。異なる桁で同じ数字が使われることはない。数を宣言すると、桁の位置と数字がともに合っている数(Bull)と、桁の位置が間違っているが数字は合っている数(Cow)が返ってくる。正解を言い当てるのにかかったターン数の最小化が目的。

【評価】

この数列でBullがいくつだからこうして…みたいなのを考えるのが楽しい。しかし10桁しかないので、力技な解法でもある程度得点が取れてしまうのはやや残念。

【難易度】

ターン数制限が300ターンであり、総当りでは全く間に合わないので何かしら方法を考える必要がある。論理的思考力を問われる。力技で解決もできる。

 

CGFunge Prime

f:id:ValGrowth:20201205154718p:plain

  公式評価:4.7

  私の評価:★★☆☆☆

問題の単純さ:★☆☆☆☆

クリア難易度:4

【概要】

CGFungeというプログラミング言語が登場する。『CGFungeのスタックに積まれた数が素数かどうか』を出力するCGFungeのプログラムを実装する。

最適化要素はCGFungeプログラムの実行ステップ数を短くすること。

【評価】

CGFungeに慣れるのにけっこう時間がかかってたいへん。実装の途中で空きスペースが足りなくなると悲しい気持ちになる。

【難易度】

素数の判定方法さえ分かれば、あとは一つ一つ確実に実装していけば解くことはそれほど難しくはない。サンプルコードがすでにある程度実装してくれているのが優しい。

 

Number Shifting

f:id:ValGrowth:20210315111509p:plain

  公式評価:4.8

  私の評価:★★☆☆☆

問題の単純さ:★★★★☆

クリア難易度:1

【概要】

グリッド上に数字が書かれたパネルがいくつか置いてあり、上下左右のいずれかの方向へ数字の数だけ動かすことができる。例えば3と書かれたパネルは上に3、左に3、下に3、右に3のいずれかの移動が可能。グリッド外への移動や、移動先にパネルが無い場所への移動はできない。

移動先のパネルと足し算するか引き算するかを選べる。引き算した場合にマイナスの値にはならず、絶対値の値になる。数字が0になったパネルは消える。グリッド上の全てのパネルを消したらクリア。何問クリアできるかを競う。

 

この問題では本番テストケースを事前に知ることができる。

最初はLevel1のテストケースだけが与えられており、それに正解することでLevel2のテストケースが与えられる、という感じ。そのためローカルで1問ずつゆっくり解いて答えだけ提出すればよく、CodinGame上の実行時間を気にしなくて良いので無限の計算時間が使える。

『現在のLevelをローカルで解いて、解けたら次のLevelのテストケースをCodinGameからダウンロードする』というのを自動化してくれるPythonスクリプトが用意されている。

 【評価】

シンプルな問題でありながら、解くことは難しく奥が深い。最初の何問かは手動や全探索でなんとかなるが、いくつか解いたところで無理になる。雑なヒューリスティックでやるとすぐに詰み状態になってしまう、手強いパズル。

Forumを読んでみたら、高レベルの問題を解くには"ある数学の知識"があるとよいらしい。数学弱い私には何も理解できなかった。

↑これなにかの勘違いでした。消しておきます。

【難易度】

1問目の簡単なパズルが解ければ正のスコアがもらえる。最初の数問は手動でなんとかなるが、難問か解いたところで手がつけられなくなる。

 

CodinGame Sponsored Contest

f:id:ValGrowth:20210314190256p:plain

  公式評価:4.1

  私の評価:★☆☆☆☆

問題の単純さ:★☆☆☆☆

クリア難易度:1

【概要】

全てが不明。ビジュアライザなし。いくつかの数字と文字が入力として与えられるため、それに対してA,B,C,D,Eのいずれかを出力するれば、次の入力がくるので、またA,B,C,D,Eのいずれかを出力する。それを繰り返す。そのうち入力が来なくなり、スコアが表示される。

【評価】

根気強く取り組めば何をやっているのかが徐々に見えてはくる。しかしスコアの計算方法まで完全に理解するのは難しい。問題を完全に解き明かすまで最適化どうこうという話ができない。謎解きとしては面白いけれど、最適化問題として面白いかと言われるとやや疑問。謎解きが好きな人には向いてそう。

【難易度】

A,B,C,D,Eのいずれかを出力するプログラムが書ければ正のスコアはもらえる。

 

総評

対戦ゲームとも共通する点として、CodinGameはビジュアライザがかっこいいのが大きな魅力です。最適化をうまくできたときには、自分のボットが美しい動きをするので永遠にビジュアライザを眺めて楽しめます。

最適化ゲームは対戦ゲームと比べて実装が軽いものが多く、より気軽に取り組めることも大きなメリットだと思います。

これを機に、あなたも最適化ゲームに挑戦してみませんか? OptimizationのLeaderboardsでみなさんをお待ちしています!