tsukammoの収穫記

上下左右の更地にアルゴリズムを

codingame:GREEN CIRCLE ルール要約

これはなに?

お題のゲームを解くプログラムを各自が作成、サイト上に提出して順位を競い合うゲームAIコンテストCodinGame「GREEN CIRCLE」について、ルール要約を紹介します。
※記載内容の保証はし兼ねるので、自己責任で読んでください。
コンテストページ:https://www.codingame.com/ide/challenge/green-circle
コンテスト期間:6月16日~6月27日

本ゲームは、スキルカードを揃えて相手より早く5つのアプリケーションをリリースした方が勝ちです。
元となるボードゲームはこちらのようです。 https://okaluda.fr/samsara-le-jeu/

ルール説明

あなたはハッカソン参加しました。アプリケーション開発における各種作業を適切に行い、相手チームよりも効率的に5 つのアプリケーションをリリースして下さい。

ゲームでは8つの作業場所が存在し、プレイヤーは各作業場所を周りながら成果(スキルカード)を収集、収集したスキルカードを使用することでアプリケーションをリリースする。 各作業場所は以下の名称で、括弧内はゲーム内ID。

  • TRAINING (0)
  • CODING (1)
  • DAILY_ROUTINE (2)
  • TASK_PRIORITIZATION (3)
  • ARCHITECTURE_STUDY (4)
  • CONTINUOUS_INTEGRATION (5)
  • CODE_REVIEW (6)
  • REFACTORING (7)

右から順に時計回りに作業場所が置かれている。

収集したスキルカードはデッキに格納される。

手札とデッキと墓地

所持しているスキルカードは自由に使えるわけではなく、手札・デッキ・墓地の3つの場所があり、手札にあるスキルカードのみ扱える。 各プレイヤーは自身のターン終了時に手札を全て捨て、デッキから所定の枚数(標準4枚)を引く。 カードを引く際に山札が無かった場合、墓地のカードをデッキに戻し、シャッフルした上で引く。

スキルカード

スキルカードは10種類存在する。 各8つの作業場所に対応する8種類の基本カードの他、ボーナスカードと負債カードがある。 各スキルカードが手札にある場合、アプリケーションのリリースに必要な作業スキルを生み出すことができる。 基本スキルカードはそれぞれの作業に応じた優良スキルを2つ、オールマイティな粗悪スキルを2つ生み出す。※スキルの優良/粗悪については後述
ボーナスカードはオールマイティな優良スキル1つ、粗悪スキルを1つ生み出す。 負債カードはスキルを生み出さない。

  • TRAINING のカードが1枚手札にあった場合は、TRAINING(優良) x 2、オールマイティ(粗悪) x 2 のスキルが使用できる。
  • CODING のカードが2枚手札にあった場合は、CODING(優良) x 4、オールマイティ(粗悪) x 4 のスキルが使用できる。
  • ボーナスカードが1枚手札にあった場合は、オールマイティ(優良) x 1、オールマイティ(粗悪) x 1 のスキルが使用できる。

アプリケーション

ゲーム開始時に12種類のアプリケーションが指定される。アプリケーションは以後追加されない。 各アプリケーションには8つの作業に応じた要求スキルが設定されている。 手札のカードから生み出せるスキルが要求スキルを満たしている場合、そのアプリケーションをリリースできる。 アプリケーションのリリースは自身のターンで1度のみである。

アプリケーショのリリース

アプリケーションをリリースする際、優良なスキルと粗悪なスキルをそれぞれ使用できるが、粗悪なスキルを使用する場合はデメリットが発生する。 アプリケーションのリリースにおけるスキル消費は以下のように処理される。

  1. 要求スキルに対し優良スキルから優先的に割り当てる。
  2. 優良スキルが足りない場合、粗悪なスキルが割り当てられる。
  3. 割当られた粗悪なスキルの数だけ、リリース後に負債カードが墓地に送られる。

また、最後の5つ目のアプリケーションは、粗悪なスキルを用いてリリースはできない。

スキルの使用(上位のリーグのみ)

基本のスキルカードが手札にある場合、1枚だけスキルを使用し、特別な効果を得ることができる。

  • TRAINING (0):デッキから2枚のカードを引き、さらに1枚追加で使用することができる。
  • CODING (1):デッキから1枚のカードを引き、さらに2枚追加で使用することができる。
  • DAILY_ROUTINE (2):次にアプリケーションをリリースするまで、このカードを除外し移動後の作業場所に隣接する作業場所のスキルカードを手に入れることができる。使用した枚数に応じて、より遠くの作業場所のカードを取得できる。リリース後に墓地に戻る。
  • TASK_PRIORITIZATION (3):手札からスキルカードを1枚取り出してボードに戻し、枚数の残っているスキルカードを1枚指定し取得できる。
  • ARCHITECTURE_STUDY (4):次にアプリケーションをリリースするまで、このカードを除外し標準の手札枚数が+1枚される。使用した枚数に応じて枚数が加算される。リリース後に墓地に戻る。
  • CONTINUOUS_INTEGRATION (5):手札から指定したスキルカードを除外し、アプリケーションをリリースのためにいつでも利用可能にする。(自動化)
  • CODE_REVIEW (6):ボーナススキルカード2枚を墓地に置く。
  • REFACTORING (7):手札から負債カードを1枚取り除く。

移動(MOVE)

各プレイヤーは作業場所を移動しながらスキルカードを集める。 自身のターンの初めに必ず移動しなければいけません。また、相手プレイヤーの作業場所、もしくはその隣接した作業場所に移動した場合、負債以外のカードを1枚相手プレイヤーに渡さなければいけない(コロナの迷惑料という設定)。手札に負債カードしかなく、迷惑料を支払えない場合負債カードを2枚取得する。 移動に際し、作業場所IDが小さくなる移動をした場合、手札にある負債以外のカードを2枚除外しなければいけない。除外できなかった場合、その数に応じて負債カードを取得する。

REFACTORING (7) → TRAINING (0) の移動
※つまり時計回りに作業場所を周り、1週したら通行税を払う必要がある。

リーグ毎の特徴やルール開放

  • bronze:全てのスキルが使用できる。通行税を支払う必要がある。
  • wood1:「TRAINING 」「ARCHITECTURE_STUDY 」「CODE_REVIEW 」「REFACTORING 」のスキルが使用できる。迷惑料を支払う必要がある。
  • wood2:スキルは使えません。迷惑料や通行税は存在しません。

各ターンの行動順

各プレイヤーは交互にプレイする。

  • 移動(MOVE)を行う。その際に迷惑料や通行税が必要なら支払う。
  • 手札に基本スキルカードがある場合、そのスキルを使用できる。
  • リリース可能なアプリケーションがある場合、指定したアプリケーションをリリースできる。

その他細かい仕様※順次update

  • 基本スキルカードは5枚、ボーナスカードは36枚、負債カードは100枚しか存在しない。
  • 基本スキルカードが5枚全て所持されている場合、対応する作業場所からはボーナスカードを取得できる。
  • 先手が5つ目のアプリケーションをリリースしても後手のターンが終わるまでゲームは続けられる。
  • アプリケーションリリース数が同じ場合、負債カードの獲得数が少ないプレイヤーが勝者となる。

アプリケーションの生成

アプリケーションは大きく2種類存在する。

  • 各スキルを2つずつ、3種類求めるアプリ小。
  • 各スキルを4つずつ、2種類求めるアプリ大。

大小のアプリに必要なスキルは予め決められた組み合わせがあり、IDはゲームが異なっても共通の番号が振られる。ブロンズリーグ以降は大アプリのみとなる。

  • 0: 小 { 0, 0, 0, 2, 2, 0, 2, 0 }, 大 { 4, 4, 0, 0, 0, 0, 0, 0 }
  • 1: 小 { 0, 2, 0, 0, 2, 0, 0, 2 }, 大 { 4, 0, 4, 0, 0, 0, 0, 0 }
  • 2: 小 { 0, 0, 2, 0, 0, 0, 2, 2 }, 大 { 4, 0, 0, 4, 0, 0, 0, 0 }
  • 3: 小 { 0, 2, 2, 2, 0, 0, 0, 0 }, 大 { 4, 0, 0, 0, 4, 0, 0, 0 }
  • 4: 小 { 0, 2, 0, 2, 0, 0, 0, 2 }, 大 { 4, 0, 0, 0, 0, 4, 0, 0 }
  • 5: 小 { 0, 0, 2, 2, 0, 2, 0, 0 }, 大 { 4, 0, 0, 0, 0, 0, 4, 0 }
  • 6: 小 { 0, 0, 2, 0, 0, 2, 2, 0 }, 大 { 4, 0, 0, 0, 0, 0, 0, 4 }
  • 7: 小 { 2, 0, 0, 2, 0, 2, 0, 0 }, 大 { 0, 4, 4, 0, 0, 0, 0, 0 }
  • 8: 小 { 2, 0, 0, 0, 2, 2, 0, 0 }, 大 { 0, 4, 0, 4, 0, 0, 0, 0 }
  • 9: 小 { 2, 0, 2, 0, 0, 0, 2, 0 }, 大 { 0, 4, 0, 0, 4, 0, 0, 0 }
  • 10: 小 { 2, 0, 0, 0, 0, 0, 2, 2 }, 大 { 0, 4, 0, 0, 0, 4, 0, 0 }
  • 11: 小 { 0, 0, 2, 2, 2, 0, 0, 0 }, 大 { 0, 4, 0, 0, 0, 0, 4, 0 }
  • 12: 小 { 0, 0, 0, 0, 2, 2, 0, 2 }, 大 { 0, 4, 0, 0, 0, 0, 0, 4 }
  • 13: 小 { 0, 0, 0, 0, 2, 0, 2, 2 }, 大 { 0, 0, 4, 4, 0, 0, 0, 0 }
  • 14: 小 { 2, 2, 0, 2, 0, 0, 0, 0 }, 大 { 0, 0, 4, 0, 4, 0, 0, 0 }
  • 15: 小 { 2, 2, 0, 0, 0, 0, 0, 2 }, 大 { 0, 0, 4, 0, 0, 4, 0, 0 }
  • 16: 小 { 2, 0, 0, 0, 0, 2, 2, 0 }, 大 { 0, 0, 4, 0, 0, 0, 4, 0 }
  • 17: 小 { 2, 2, 0, 0, 0, 2, 0, 0 }, 大 { 0, 0, 4, 0, 0, 0, 0, 4 }
  • 18: 小 { 0, 0, 2, 0, 2, 0, 2, 0 }, 大 { 0, 0, 0, 4, 4, 0, 0, 0 }
  • 19: 小 { 0, 2, 2, 0, 0, 0, 0, 2 }, 大 { 0, 0, 0, 4, 0, 4, 0, 0 }
  • 20: 小 { 0, 0, 0, 2, 0, 0, 2, 2 }, 大 { 0, 0, 0, 4, 0, 0, 4, 0 }
  • 21: 小 { 0, 2, 2, 0, 0, 2, 0, 0 }, 大 { 0, 0, 0, 4, 0, 0, 0, 4 }
  • 22: 小 { 0, 2, 0, 2, 0, 0, 2, 0 }, 大 { 0, 0, 0, 0, 4, 4, 0, 0 }
  • 23: 小 { 2, 0, 0, 2, 0, 0, 0, 2 }, 大 { 0, 0, 0, 0, 4, 0, 4, 0 }
  • 24: 小 { 0, 0, 0, 2, 0, 2, 2, 0 }, 大 { 0, 0, 0, 0, 4, 0, 0, 4 }
  • 25: 小 { 2, 2, 0, 0, 2, 0, 0, 0 }, 大 { 0, 0, 0, 0, 0, 4, 4, 0 }
  • 26: 小 { 2, 0, 2, 0, 2, 0, 0, 0 }, 大 { 0, 0, 0, 0, 0, 4, 0, 4 }
  • 27: 小 { 0, 0, 2, 0, 2, 2, 0, 0 }, 大 { 0, 0, 0, 0, 0, 0, 4, 4 }

現在の不具合※2022/06/20

2022/06/21 既知のバグが修正されました。TRAINING/CODING の追加スキル使用が正常化。DAILY_ROUTINE 使用時の無移動が不可に。通行税を払う際、同種2枚のスキルカードを保持していると1枚の支払いとなっていた不具合が解消。
また、visualizerのツールチップ情報として、アプリケーショ一覧が見えるようになりました。 https://www.codingame.com/forum/t/contest-green-circle/196455/77

2022/06/18 一度使用したスキルカードは脇に置かれ、ターン終了まで墓地に送られないようになりました。 これにより、一部スキルの無限ループは解消されます。 https://www.codingame.com/forum/t/contest-green-circle/196455/39

2022/06/17 各種処理の発生が不安定だったり、一部のスキルを無限に使用できるなど、ゲームの不具合が見つかっています。 以下のフォーラムにて参加者からFBがなされているので、順次対応される見込みです。 www.codingame.com

codingame:Spring Challenge 2022 ルール要約&モンスター生成ロジック

これはなに?

お題のゲームを解くプログラムを各自が作成、サイト上に提出して順位を競い合うゲームAIコンテストCodinGame「Spring Challenge 2022」について、ルール要約と予め設定されている内部パターンについて紹介します。
※記載内容の保証はし兼ねるので、自己責任で読んでください。
コンテストページ:https://www.codingame.com/contests/spring-challenge-2022
コンテスト期間:4月21日~5月2日

本ゲームは、拠点を守りつつマップ上に現れるモンスターになるべく多くのダメージを与えた方が勝ちです。

ルール説明

各プレイヤーは3体のヒーローを操作し、マップ端から出現するモンスターを倒して下さい。モンスターが自分の拠点に到達するとダメージ1回受けます。自分の拠点が3回ダメージを受けると負けとなります。 相手プレイヤーが先に3回ダメージを受けるか、220ターン経過時に相手より受けたダメージが少ない場合、あなたが勝利します。 なお、受けたダメージが同じ場合、各プレイヤーは拠点外でモンスターに与えたダメージ量の多いほうが勝者となります。

マップ

X=0、Y=0を左上、X=17630、Y=9000を右下のピクセルとする長方形のマップ上でゲームを行います。 wood2ランクまでは、マップ全域の視界を得ていますが、wood1以降は自分のヒーローから2200ユニット以内、または自分の拠点から6000ユニット以内の視界のみとなります。

エンティティ

各エンティティ(ヒーロー、モンスター)は、衝突せず、同じ座標に存在することができます。

ヒーローとアクション

毎ターン、あなたは各ヒーロー毎のコマンドを出力して下さい。ヒーローは以下のコマンドのいずれかを実行することができます。

  • MOVE:指定されたマップの座標に向かって最大800ユニット分前進します。
  • SPELL:(wood1以降)定められた呪文を使用します。
  • WAIT:その場に留まります。

互いのヒーローにはダメージを与えられません。 ヒーローの移動後、800ユニット以内にいるモンスターに2ポイントのダメージを与えます。

モンスター

モンスターは、プレイヤーの拠点以外のマップ端から点対称にランダムで出現します。出現時にランダムで定められた移動方向に毎ターン400ユニットの速度で一直線に進みます。点対称の対になるモンスター同士は、移動方向も点対称となります。全てのモンスターには一定のHPが定められており、ヒーローからのダメージでHPが0になったモンスターは消滅します。

ターン終了時に拠点から5000ユニット以内にモンスターがいた場合、その拠点を目的地として移動方向を変更します。ターン終了時にHPが0でないモンスターが拠点から300ユニット以内にいると、そのモンスターは消滅し、拠点に1ポイントのダメージを与えます。
なお、WINDコマンドでターゲットされた拠点の半径外に押し出された場合、再度ランダムに定めた移動方向に移動し始めます。

ゲームのターンが進むにつれ、モンスターの初期体力はわずかに多くなることがあります。

マナと呪文

あなたのヒーローがモンスターにダメージを与えるごとに1ポイントのマナを獲得する。HPが0のモンスターからでも獲得する。
獲得したマナ10ポイントを消費することで、あなたのヒーローは1つの呪文を唱えられる。

  • WIND :1280ユニット以内にいる自軍のヒーロー以外のエンティティは、呪文を唱えたヒーローから x, y の方向に2200ユニット移動させられる。
  • SHIELD :2200ユニット以内の指定したエンティティは、12ターンの間スペルの対象にならない。
  • CONTROL :2200ユニット以内の指定したエンティティは、次のアクションを指定された座標へ強制的にMOVEさせられる。

リーグ毎の特徴やルール開放

  • bronze:「SHIELD」「CONTROL」の呪文が解放されます。
  • wood1:「WIND」の呪文が解放されます。マップ上の視界が制限されます。
  • wood2:呪文は使えません。マップ全域の視界が得られます。

行動順

  • CONTROLの呪文が対象に適用される。
  • SHIELDの呪文が対象に適用される。SHIELDは次のターンから有効になる。
  • すべてのヒーローが移動する。
  • ヒーローは範囲内のモンスターに攻撃し、マナを生成する。※モンスターは移動前であることに注意
  • WINDの呪文が範囲内のエンティティに適用される。
  • すべてのモンスターは速度に応じて移動する。ただし、WINDを受けたモンスターは移動しない。
  • SHIELDの残りターンが減少する。
  • 新しいモンスターを出現させる. 死んだモンスターが取り除かれる.

モンスター生成ロジック

ゲーム中のモンスターは下図赤丸の4点から発生します。実際の発生地点はy軸方向に799マップ外に進んだ点となります。

各点から初期体力10のモンスターが1匹/5ターンの速度で発生し、10ターン毎に初期体力が+1されます。
200ターン経過後、サドンデスモードとなり、発生するモンスターは各プレイヤーの拠点をより狙うようになります。

呪文周りの細かい仕様

  • 複数からCONTROLを受けた場合、各移動先の平均に向かいます。
  • 複数からWINDを受けた場合、各移動量の合計に飛ばされます。
  • SHIELD中は、新たなSHIELDも弾きます。
  • SHIELDは次ターンから有効になります。同じターンの呪文は作用します。
  • WINDなどでモンスターはマップ外に飛ばされます。ただし、拠点半径内の場合は境界線を超えません。
  • WINDを受けたモンスターはそのターン移動しません。
  • ターン終了時にマップから800ユニット離れたモンスターは消滅します。(マップ外でもモンスターは存在。)
  • マップ外のモンスターは視認できません。
  • マップ外からモンスターが拠点エリア内に侵入することはできません。

カーブ時にペナルティが発生する経路探索アルゴリズム~AHC003を添えて~

これはなに?

一般的に最短経路を求める場合はダイクストラ法が用いられます。ダイクストラ法は元来たルートを意識しないことで高速に計算できる反面、現実世界において進行方向を変える場合に発生するコスト(減速や車線変更、信号待ち等)が考慮できません。今回、AtCoderヒューリスティックコンテスト「AHC003」を題材に、カーブ時のペナルティを考慮できる経路探索アルゴリズムを考えてみたので紹介します。
コンテストページ:https://atcoder.jp/contests/ahc003

提出プログラム

こちらです。https://atcoder.jp/contests/ahc003/submissions/23029917
当該処理を行っているのは fn solve() の部分です。

ダイクストラ法を用いたカーブ考慮の問題

一般的なダイクストラ法では、下図の場合に問題が発生します。
f:id:tsukammo:20210530212808p:plain

1マス進むとコスト1かかるとして、コスト0のスタート地点から上右と来た場合と、右上と来た場合に、どちらかの進行しか保持できず、"↑"と"→"のマスのコスト値が実行順序によって大きく異なってしまいます。※移動コストが等価であれば計算を進めることで正しい値が得られますが、コストが等価で無い場合は正しくない結果になる場合があります。

今回行った工夫

今回は、下図のように直進できる所までやりきってしまい、更新可能な場合どこから進んできたかを別のgridに保存します。
f:id:tsukammo:20210530213620p:plain

移動コストが等価の場合だと有り難みがわかり難いですが、それぞれ異なる移動コストの場合、あるマスは上移動で来るのが最短だが、すぐ隣の別のマスは右移動で来るのが最短、というのをそれぞれ保持できて嬉しいです。

おわりに

AHC003では、理論値を100%とした際、一般的なダイクストラ法にカーブ時ペナルティを加えたもので93%、上記工夫を行うことで96%と、3%スコアアップしました。もちろん、そもそもの盤面推定の方が重要な問題ですが、雑な盤面推定でもそこそこのスコアが取れたので、学びを得ました。

codingame:Spring Challenge 2021 問題予想

これはなに?

お題のゲームを解くプログラムを各自が作成、サイト上に提出して順位を競い合うゲームAIコンテストCodinGame「Spring Challenge 2021」について、公開されている情報から問題を予想しようという遊びです。
コンテストページ:https://www.codingame.com/contests/spring-challenge-2021
コンテスト期間:5月6日~5月17日 f:id:tsukammo:20210403052500p:plain

なお、コンテストが始まっていないので、この記事を読んで得られる情報は特にありません。

おことわり

本記事はコンテスト開催が待ち切れない沼先案内人の妄想を書き起こしたものです。筆者は本コンテスト関係者と一切の関わりを持ちません。また、CodinGameではコンテスト内容や自身のアイディアに関する言及が許されており、本記事が万が一当たってたとしても問題は無いという考えの元、公開しております。 もし本記事によりコンテスト開催に支障が生じる場合、すみやかに削除いたします。

それでは早速はじめましょう。

手掛かり

コンテストのtopページを見るに、ルールはいつも通り11日間、コンテスト名も記号的な「Spring Challenge」のため、top画像が唯一の手掛かりです。 この画像から、モチーフがスタジオジブリ制作の映画「となりのトトロ」であることがわかります。
CodinGameはゲームAIコンテストサイトなので、過去にぷよぷよボンバーマンなどがコンテスト化されましたが、トトロはそもそも映画なのでそのままコンテストにはなり得ません。そこで、"トトロ ゲーム"で検索をかけるとこんな商品がヒットしました。

item.rakuten.co.jp

2~4人用のボードゲームのようです。奇しくもCodinGameのプラットフォームの仕様と同じです。ボードゲームといえば、前回のコンテストのFall Challenge 2020では、下記のボードゲームがモチーフとなっていました。

item.rakuten.co.jp

センチュリースパイスロードの日本販売元は株式会社アークライトで、トトロのどんどこゲームのゲームデザイン会社と同じなのですが、センチュリースパイスロード自体はカナダの Plan B Games という会社が開発したものなのであまり関係は無さそうです。 とはいえ他に選択肢が無いので、このボードゲームがモチーフになると仮定して問題を予想します。

コンピュータゲームに変換する

トトロのどんどこゲームのルールはこちらにインストが公開されていました。以下は、トトロのどんどこゲームのルールをご理解いただいているという前提で進めます。

プログラムはサイコロを振らない

人間がプレイするボードゲームでは、ゲーム性を高めるために確率的な事象の発生、つまりサイコロを振るという操作がなされます。トトロのどんどこゲームでは、所謂"すごろくゲー"と呼ばれるサイコロの出目で駒を進めるゲームデザインとなっています。ところが、明確に優劣を付けたいゲームAIコンテストにおいて、不公平な確率の介在はいたずらに必要な試行回数が増すだけです。私の記憶にある限り、過去のCodinGameにおいてアイテムやマップ生成など、互いのプレイヤーに公平に影響する要素に確率が介在することはあれど、提出された各botの出力内容自体に確率が介在するようなゲームデザインはありませんでした。

このような場合に、過去のコンテストでは同時着手ゲームにアレンジされることが多かったです。同時着手ゲームの場合、互いのプレイヤーの行動に差異が生まれるよう、じゃんけんの要素を入れる必要があります。前々回のコンテストでは、パックマンをモチーフとし、文字通りじゃんけんのグーチョキパーの属性に変わる行動が可能でした。これによりプレイヤー間の読み合いが発生し、ゲーム性が生まれます。
しかし、モチーフ上トトロにはそのようなじゃんけん要素が存在しません。小トトロ達がじゃれ合うのは微笑ましいですが、足を引っ張り合うのは見たくないものです。どうしたらよいでしょうか。

人類は愚か

人間は忘れる生き物です。トトロのどんどこゲームでも、得点となるどんぐりをたくさん得るため、相手プレイヤーの手札から神経衰弱のように目当ての探し物カードをめくる操作があり、記憶力が問われます。一方、プログラムはメモリの許す限り覚えておけるため、記憶力を問うても優劣は付かないでしょう。

さらに、トトロのどんどこゲームでは一度公開された探し物カードは全プレイヤーが利用可能です。そのため、もっともどんぐりの獲得数が多い探し物が決まってしまい、各プレイヤーは勝つためにそれしか選択しない状況が生まれます。探し物のひとつであるトウモロコシは、いくら劇中で物語のクライマックスに繋がる重要なアイテムとはいえ、ルール上高得点だからとそればかり選ばれてしまうと、もうひとつの探し物である傘を届けてもらえなかったお父さんは、雨の中一人寂しくずぶ濡れで帰ることになってしまいます。どうしたらよいでしょうか。

踊らにゃ損損

トトロのどんどこゲームは、あるプレイヤーがどんどこ踊り行ってクスノキを7段登るとゲーム終了となります。サイコロによる確率的な事象であればよいのですが、自由にマス目が選べる状況ではどんどこ踊りは踊り得となってしまい、ゲーム性を失ってしまいます。かといって、どんどこ踊りよりどんぐりの獲得数が多い行動とのトレードオフとなるようなデザインにしてしまうと、どんぐりの多さで勝敗が決まるというルール上、どんぐり集めに傾倒しクスノキを一切登らない無敗戦略が生じてしまいます。

前回のコンテストでは、モチーフとして素材を集めて完成品を作るゲームとなっており、スコアを稼ぐにはポーションを作成する必要がありますが、同時に6本目のポーションが完成した時点でゲーム終了となります。そのため、勝敗条件とスコア獲得が連動しており、スコアの低くて簡単に作れるポーションを作るか、簡単には作れないがスコアが高いポーション作るかのトレードオフが発生しました。どんぐりを集めつつ、クスノキを登ることを避けられないようにするには、どうしたらよいでしょうか。

item.rakuten.co.jp

歩こう歩こう東海道

これまでの考察から、トトロのどんどこゲームはゲームAIコンテストにするには根本的なゲームデザインが不向きであることがわかりました。正直とても困りました。しかし、遊びとはいえここで投げ出すわけにはいきません。モチーフを尊重しつつ、ゲーム性が生まれるデザインにするため、他のボードゲームについて頑張って調べました。すると、サイコロを振らない"すごろくゲー"を見つけました。

store.steampowered.com

Tokaidoというこのゲームは、各プレイヤーが自駒を任意のマスに進めることができます。ゲーム性を生むため、以下のような工夫がなされています。

  • 最大マス数が決まっており、ゴールに着いたらそれ以上駒を進めることができない。
  • 全プレイヤーがゴールに着いた時点でスコアが高いプレイヤーが勝利する。
  • スコアを上げるためなるべく多くのマスに止まりたいが、各マス毎に決められた数しか駒が止まれない。
  • ターン制ではなく、現在最もゴールから遠いプレイヤーから駒を動かす。(後ろにいると有利)
  • 特定のマスに連続で止まると獲得スコアが増えていく。(空きマスを飛ばしてでも狙ったマスに飛ばしたい)

このルールをトトロのどんどこゲームに当てはめてみると、モチーフを活かしたまま、ゲーム性を生むことができます。

  • ゴール地点がクスノキのてっぺんと見なせる。
  • 探し物カードの種類が、Tokaidoのマスの種類と同じものと見なせる。
  • 得点の高い探し物マスは奪い合いになり、得点の低い探し物マスを独占する選択とトレードオフが生じる。

やったぜ。

ゲームサイズ

コンピュータゲームは、人間によるプレイに比べて非常に高速に行動の処理を行えます。 そのため、元のゲームでは12マス・6種類の探し物・7段のクスノキ・中トトロ1匹でしたが、特にゲーム盤のマス目や中トトロの数に関しては拡大の余地が大きいと考えます。また、事前にすべてのマスが公開されてしまうとゲーム性が薄れるため、一定マス以上は公開されず、近付くことでマスの種類がわかるようなデザインも可能です。

完成したゲームルール

以上より、Spring Challenge 2021 の問題を以下のように予想します。

小トトロを操作しなるべく多くのどんぐりを集める4人ゲームです。各プレイヤーは、自分のターンに小トトロをいくつ進めるか出力して下さい。ただし、止まる先のマスに定められた定員を超えてしまう場合はエラーとなります。 勝利条件は、すべての小トトロがゴールに到達した時点でゲーム終了となり、最も多くのどんぐりを持っているプレイヤーが勝者となります。

マスについて

マスの種類は先頭の小トトロから5マス先まで確認することができ、全部で6種類のマスが存在します。小トトロがそのマスに止まった際、そのプレイヤーは予め定められた探し物カードを入手し、すでに獲得した同種のカードに記載された獲得どんぐり数との合計値だけどんぐりを入手します。
各マスには種類の他に、同時に止まれる定員が定められています。定員を超えてそのマスに止まることはできません。

ターンについて

ゴールに対し最も遠いプレイヤーが操作を行えます。操作後もゴールに対して最も遠い場合、連続して操作を行います。同一マスに複数のプレイヤーがいる場合、そのマスに訪れたターンが遅いプレイヤーから先に操作を行います。ゲーム開始時の順番はランダムに定められます。

リーグ毎の特徴やルール開放

  • bronze:4人ゲームです。
  • wood1:2人ゲームです。マスの種類が6つになります。
  • wood2:2人ゲームです。マスの種類は1つしかありません。

おわりに

ゲームAIコンテストが大好きで、過去色々なコンテストに参加してきましたが、実際に競技性のあるゲームを考えるとなると非常に難しいことがよくわかりました。毎回コンテストの題材を準備していただいているCodinGameと作成者の方に改めて感謝を。

今回考えたゲームについて、まだまだ要素が少なくプレイするには少々物足りないと感じています。とはいえ、モチーフをあまりに逸脱したゲームデザインを考えるのは本来の趣旨から逸脱するため、実際のコンテスト内容がどのようになるのか、ますます期待が高まりました。

それではまた、コンテストでお会いしましょう。

codingame:Fall Challenge 2020 ルール要約&内部パターン紹介

これはなに?

お題のゲームを解くプログラムを各自が作成、サイト上に提出して順位を競い合うゲームAIコンテストCodinGame「Fall Challenge 2020」について、ルール要約と予め設定されている内部パターンについて紹介します。 ※記載内容の保証はし兼ねるので、自己責任で読んでください。
コンテストページ:https://www.codingame.com/contests/fall-challenge-2020
コンテスト期間:11月13日~11月24日 f:id:tsukammo:20201113023607p:plain

(本ゲームは、素材を集めて注文された商品を作成していく「お店経営シミュレーション」がモチーフです。)
(類似のボードゲームがあるそうです。https://bodoge.hoobby.net/market/items/239)
ゲーム終了時に相手よりも多くのルピーを稼いでいれば勝ちです。

ルール説明

各プレイヤーは魔女を操作し、自分の手持ちのポーション素材と学習した呪文を駆使してルピーを稼いで下さい。各呪文は、素材の入手に活用することができます。 注文は常に5つ表示され、素材を消費して注文通りのポーションを作ることで、指定のルピーを稼ぐことができます。 各プレイヤーは、ターン毎に同時に1つのアクションを実行します。

素材

ポーション素材は全部で4種類あり、基本的に上位の素材を作成するために下位の素材を消費します。 より高価なポーションの作成には、よりレベルの高い素材が要求されます。 各魔女は最大10個まで素材をためておくことができます。

アクション

毎ターン、以下のいずれかのアクションを行うことができます。

  • LEARN:魔法の書庫から新しい呪文を学ぶ。
  • CAST:学習した呪文を1つ使う。※一度仕様した呪文は休息を取るまで使用不可となります。
  • REST:休息をとって、以前に唱えた呪文をすべてリフレッシュする。
  • BREWポーションを生成してルピーを稼ぐ。
  • WAIT:何もせず、ターンをスキップする。

あるターンにそれぞれの魔女が同じアクションをしたとき、双方のアクションが実行されます。

CAST:呪文を唱える

各呪文には4つの数字があり、使用時の各素材毎の増減を表します。

  • 正の数字は使用時に増える素材の量です。
  • 負の数字は使用時に消費される素材の量です。

例えば、-1,1,0,0と書かれた呪文は、レベル0の素材を消費して、レベル1の素材を産み出すことを意味します。

ゲーム中に何度でも呪文を使用できますが、一度唱えた呪文は休息を取るまで使用することができなくなります。 呪文の中には一度に連続使用可能なものがあります。

なお、ゲーム開始時には常に同じ4つの基本呪文が使用可能です。

LEARN:呪文の学習

魔法の書庫は常に6つの呪文が用意されています。どちらかの魔女が呪文を覚えた場合、その呪文は書庫から消失し、もう片方の魔女は覚えることができなくなります。

各魔女が呪文を覚える際、書庫の利用には制限がかかります。

  • どちらかの魔女が書庫を利用するまで、全ての呪文は自由に学ぶことができる。
  • 書庫の最初の呪文(下から1番目)は自由に学習できる。それ以上の呪文を覚えるには、「先読み税」を支払う必要がある。

例えば、下から4番目の呪文を覚える場合、手待ちレベル0素材から1番目、2番目、3番目の呪文に1つずつ素材を支払います。税が支払えない場合、学習に失敗します。 税が支払われた呪文を覚えるたびに、その呪文の素材も獲得し、次のターンに使えるようになります。もし、魔女の素材が溢れる場合、余った分は捨てられます。

呪文は規定の種類がありますが、書庫に現れる順番はランダムです。

REST:休息

休息することで一度使用した呪文をリキャストできるようになります。

BREWポーション作成

注文されたポーションに必要な素材を消費して、ルピーを獲得します。 消費量はマイナスの数字で表され、正の値になることはありません。 例えば、Delta = -2, -1, 0, 0の注文は、ポーションを作るために2つのレベル0の素材と1つのレベル1の素材を消費しなければならないことを意味します。

どの注文のポーションでも作成できますが、緊急度の高い左側の注文は、緊急ボーナスを得ることができます。ボーナスの仕組みは以下の通りです。

  • 1番左の注文のポーションを作成すると+3ルピーのボーナスが与えられます。これはゲーム中に4回しか発生しません。
  • 左から2番目の注文おnポーションを作ると+1 ルピーのボーナスが与えられます。これもゲーム中に4回しか発生しません。
  • ただし、1番左に与えられる+3ボーナスを全て使い切った場合、+1のボーナスは2番目の注文ではなく1番目の注文に与えられます。

なお、同時にポーションを作成した場合、ボーナスは2回発生したとみなされます。最後の1回の場合、どちらもボーナスを取得します。

注文は規定の種類がありますが、現れる順番はランダムです。

勝利条件

少なくとも1人の魔女が6つのポーションを作成するか、100ターン経過でゲーム終了です。 ゲーム終了時、各魔女は手持ちのレベル1以上の素材1つにつき、1ルピーを得ます。 最も多くのルピーを持っているプレイヤーが勝者となります。

リーグ毎の特徴やルール開放

  • bronze:呪文の学習ができます。以降、6つの注文に応えた時点でゲームが終了します。
  • wood1:呪文が使用できます。3つの注文に応えた時点でゲームが終了します。
  • wood2:予め素材が与えられた状態で始まり呪文は使えません。2つの注文に応えた時点でゲームが終了します。

呪文と注文のパターン一覧

シミュレータにて予め定められた呪文と注文を紹介します。
※11/14にレベル1と2の値が訂正されました。
※11/17に19番目の呪文(id18)が更新されました。

呪文

左から各レベルの素材の増減です。素材消費のある呪文は全て連続使用可能です。

-3 0 0 1
3 -1 0 0
1 1 0 0
0 0 1 0
3 0 0 0
2 3 -2 0
2 1 -2 1
3 0 1 -1
3 -2 1 0
2 -3 2 0
2 2 0 -1
-4 0 2 0
2 1 0 0
4 0 0 0
0 0 0 1
0 2 0 0
1 0 1 0
-2 0 1 0
-1 -1 0 1
0 2 -1 0
2 -2 0 1
-3 1 1 0
0 2 -2 1
1 -3 1 1
0 3 0 -1
0 -3 0 2
1 1 1 -1
1 2 -1 0
4 1 -1 0
-5 0 0 2
-4 0 1 1
0 3 2 -2
1 1 3 -2
-5 0 3 0
-2 0 -1 2
0 0 -3 3
0 -3 3 0
-3 3 0 0
-2 2 0 0
0 0 -2 2
0 -2 2 0
0 0 2 -1

注文

左から各レベルの素材の消費量と、達成時の獲得ルピーです。

2 2 0 0: 6
3 2 0 0: 7
0 4 0 0: 8
2 0 2 0: 8
2 3 0 0: 8
3 0 2 0: 9
0 2 2 0: 10
0 5 0 0: 10
2 0 0 2: 10
2 0 3 0: 11
3 0 0 2: 11
0 0 4 0: 12
0 2 0 2: 12
0 3 2 0: 12
0 2 3 0: 13
0 0 2 2: 14
0 3 0 2: 14
2 0 0 3: 14
0 0 5 0: 15
0 0 0 4: 16
0 2 0 3: 16
0 0 3 2: 17
0 0 2 3: 18
0 0 0 5: 20
2 1 0 1: 9
0 2 1 1: 12
1 0 2 1: 12
2 2 2 0: 13
2 2 0 2: 15
2 0 2 2: 17
0 2 2 2: 19
1 1 1 1: 12
3 1 1 1: 14
1 3 1 1: 16
1 1 3 1: 18
1 1 1 3: 20

codingame:Spring Challenge 2020 ルール要約&マップ生成ロジック説明

これはなに?

お題のゲームを解くプログラムを各自が作成、サイト上に提出して順位を競い合うゲームAIコンテストCodinGame「Spring Challenge 2020」について、ルール要約とマップ生成ロジックを説明します。 ※記載内容の保証はし兼ねるので、自己責任で読んでください。
コンテストページ:https://www.codingame.com/contests/spring-challenge-2020/
コンテスト期間:5月8日~5月18日

f:id:tsukammo:20200508062252p:plain

(本ゲームは、コンピュータゲーム「パックマン」がモチーフです。)
相手よりも多くのペレットを食べ、マップ上の過半数のポイントを取るか、200ターン経過した場合にポイントの多ければ勝ちです。
パックマンの残数は影響しません。

ルール説明

ゲーム開始時に与えらる壁と床で構成されるグリッド上で、各プレイヤーはグリッドに沿って移動できるパックマンを操作します。 マップはランダムに生成され、幅と高さも変化します。マップの各セルは次のいずれかです。

  • 壁 ("#"で表される)
  • 床 (" "(スペース文字)で表される )

マップは常に中心の縦軸を挟んで対称的に配置されます。 多くのマップでは左右端を壁で区切っていない箇所(トンネル)があり、パックマンがトンネルを通るとマップ反対側に移動できます。

ゲーム開始時、マップはペレット or スーパーペレットで埋め尽くされます。 同じセルにパックマンが移動するとすると取得することができ、ペレットは1ポイント。スーパーペレットは10ポイントのスコアを得て、ペレットは取り除かれます。

f:id:tsukammo:20200508062537p:plain
ペレットとスーパーペレット

各プレイヤーは最大5つのパックマンを同数コントロールします。各ターン毎に、あなたのパックマンとスーパーペレットの位置に加え、視界内にあるパックマンとペレットに関する情報が与えられます。 視界は、あなたのパックマンを起点とし、上下左右の直線上に壁に遮られるまで続きます。
※初期のwood2リーグでは、最大1つのパックマンを操作し、全ての視界を持っています。

f:id:tsukammo:20200508062639p:plain
視界と壁

パックマンはじゃんけんと同様の3つのタイプを持ちます。 各タイプは移動とパックマン同士の対決に影響します。

f:id:tsukammo:20200508062706p:plain
タイプ(ROCK・PAPER・SCISSORS)

パックマンは2つのスキル(SWITCHとSPEED)を使用でき、共通のクールダウンは10ターンです。スキルはゲーム開始時から使用可能です。

アクション

あなたのパックマンに対し、ターン毎に以下の操作のいずれか1つの操作をすることができます。

MOVE

パックマンに目標の位置を与えると、その位置までの最短ルートを見つけて最初のステップを移動します。 パックマンはルートを選ぶときにペレットや他のパックマンの存在を考慮せず、後述する衝突処理が発生することがあります。

SWITCH

パックマンのタイプを指定したタイプに変更することができます。

SPEED

次の5ターンの間スピードが上がり、MOVE時に2step移動します。つまり2倍の距離を移動できることを意味します。

衝突

他のパックマンと移動が交差したり同じセルに移動した場合、「衝突」が起こります。衝突発生時の解決順序は下記の通りです。

  1. 移動しているすべてのパックマンはSPEEDに関係なく 1 ステップ移動します。
  2. 同じタイプのパックマンや同じプレイヤーのパックマンがいる場合、各パックマンの移動はキャンセルされ元のセルに戻ります。 異なるプレイヤーかつ異なるタイプのパックマンの場合、同じセルに移動可能ですが、じゃんけん関係において自身より強いパックマンを横切る場合、同様に移動がキャンセルされます。
  3. 2.によって新たな衝突が発生する可能性があります。このため、新しい衝突が発生しなくなるまで前のステップが繰り返されます。
  4. 同じセルにいるパックマンのうち、じゃんけん関係において弱いパックマンはゲームから除外されます。
    ※ROCKはSCISSORSを、SCISSORSはPAPERを、PAPERはROCKに対して強いです。
  5. SPEED能力が発動しているパックマンは、もういちど1.から処理されます。

リーグ毎の開放

  • silver:自他共に(視界外でも)倒されたパックマンが入力で与えられる
  • bronze:スキル(SWITCH・SPEED)、視界の制約
  • wood1:一度に複数のパックマンを操作

※simulator上、4人同時対戦も想定されています。

マップ生成と初期位置

マップ

幅:28~3329~35、高:10~1517の範囲(ルール変更が入った模様)で一様ランダムで決定します。 2人対戦の場合は、横方向に折りたたむ線対称となり、4人対戦の場合は縦横4つ折りの線対称となります。 マップ左上から順に、下記の決められた通路の形状からランダムに選択し、当てはめていきます。 最後に、生成したマップの外周を壁で多います。その際、マップ端の床の上下が壁の場合、トンネルとして床を残します。

f:id:tsukammo:20200508063000p:plain
通路形状(■が床)※上限左右反転したものも対象

初期配置

各プレイヤーの操作するパックマンの数を2~5の範囲で一様ランダムに決定します。 生成したマップの床をランダムに選択し、線対称にパックマンを配置します。 さらに床をランダムに選択し、線対称にスーパーペレットを合計4つ配置します。

codingame:Ocean of Code ルール要約&マップ生成ロジック説明

これはなに?

お題のゲームを解くプログラムを各自が作成、サイト上に提出して順位を競い合うゲームAIコンテストCodinGame「Ocean of Code 」について、ルール要約とマップ生成ロジックを説明します。 ※記載内容の保証はし兼ねるので、自己責任で読んでください。
コンテストページ:https://www.codingame.com/contests/ocean-of-code
コンテスト期間:3月20日~4月20日

f:id:tsukammo:20200329073257p:plain

このゲームは、2人対戦ゲーム(≠play人数)である、ボードゲーム「キャプテンソナー」を元にしています。 互いに潜水艦を操縦し、先に相手のHPを0するか、300ターン経過時にHPが多い方が勝ちです。

ルール説明

潜水艦は海と島で構成される15×15マスの地図上を移動します。潜水艦は海上のみ動くことができ、潜水艦や機雷と同じセルを共有できます。 プレイヤーは互いに最初の地点を指定しゲームをスタートします。互いの開始位置は相手には知らされません。 マップは9セクターに分割され、1つ5x5マス、左上のセクター1から順番に番号が振られ右下のセクターが9です。

f:id:tsukammo:20200329073441p:plain
図:マップとセクター

各プレイヤーがターン毎に交互に行動します。あなたは対戦相手が何をしたかについて知ることができます。(例:北に移動した) 相手の位置を特定するためにこの貴重な情報を上手く活用しましょう。

アクション

ターン毎にあなたは必ず1つ以上のアクションを実行する必要があり、各アクションについて説明します。 パイプ"|"を使用してチェーンすることで、複数のアクションを同時に実行できます。ただし、各アクションは1ターンに1度しか使用できません。

移動(MOVE)

潜水艦を1マスだけ特定の方向(北、東、南、西)に移動します。 移動と同時に、他のアクション(魚雷、索敵、潜航、地雷)のパワーを充電することができます。島や移動済のマスに移動することはできません。

浮上(SURFACE)

移動済みのマスがリセットされ、以前に移動したマスに再度移動可能になります。 しかし、あなたの潜水艦のあるセクター番号が対戦相手に通知され、1HPを失います。

魚雷(TORPEDO):必要パワー3

魚雷を道のり4マス以内の任意の地点に発射します。島を迂回できますが通過はできません。 発射地点にいる潜水艦に2ダメージ、すべての隣接マス(対角線を含む)に1ダメージを与えます。 自分自身にもダメージが入ります。

f:id:tsukammo:20200329073545p:plain
図:魚雷の発射可能地点

索敵(SONAR):必要パワー4

指定したセクター内に敵潜水艦が存在するかどうかを確認します。 結果は次の自分のターンに得られますが、対戦相手が動いた後ではなくアクション実行時の位置です。

潜航(SILENCE):必要パワー6

上下左右の任意の方向に0~4マス直線移動します。通常の移動と同じく、島や移動済みのマスには移動できません。 対戦相手にはあなたが潜航したことしか通知されず、どの方向にどれだけ移動したかを知られずに移動できます。

機雷(MINE):必要パワー3

上下左右の隣接マスに機雷を設置します。同じマスに2つの地雷を設置することはできません。 ただし、対戦相手の潜水艦や地雷のあるマスに設置することは可能です。 地雷は、起爆アクションを使用する場合にのみ爆発し、設置マスを通過しても爆発しません。。

f:id:tsukammo:20200329073600p:plain
図:機雷

起爆(TRIGGER)

自身が設置した地雷を起爆します。ダメージは魚雷同様に、地雷の位置に2ダメージ、全ての隣接マス(対角線を含む)に1ダメージを与えます。 同じターンに複数の地雷を起爆することはできません。そのターンに設置した地雷を起爆することはできません。 自分自身にもダメージが入ります。

リーグ毎の開放

各アクションはリーグに応じて順次解法されていきます。

  • wood2:移動(MOVE)・浮上(SURFACE)・魚雷(TORPEDO)のみ
  • wood1:索敵(SONAR)と潜水(SILENCE)が追加
  • bronze:機雷(MINE)と起爆(TRIGGER)が追加

入出力

具体的な入出力内容について説明します。

開始時

島の位置("x")を示すマップ情報(15x15)を受け取ります。 互いのプレイヤーは、潜水艦の初期位置(x、y)を出力します。

各ターンの入力

3行の情報を受け取ります。

1行目:8つの整数値です。

  • x,y:自身の潜水艦の現在位置
  • myLife:自身のHP
  • oppLife:相手のHP
  • torpedoCooldown,sonarCooldown,silenceCooldown,mineCooldown:各アクションに必要な充電回数。 0で使用可能、-1はそのリーグでは使用不可。

2行目:索敵(SONAR)の結果を示す文字列です。

  • NA:索敵未使用時
  • Y:指定したセクターに敵艦が存在
  • N:指定したセクターには敵艦がいない

3行目:対戦相手がそのターン中に行ったアクションを示す文字列です。複数の場合、"|"で区切られます。
例:MOVE N | TORPEDO 3 5
この例は、対戦相手が上に移動してから、魚雷を地点(3,5)に発射したことを意味します。 対戦相手がまだ何もしていない場合はNAとなります。

各ターンの出力

あなたは"|"で区切られた1つ以上のアクションを出力します。アクションは先頭から順次処理されます。
例:MOVE N TORPEDO | TORPEDO 3 5
このコマンドは、潜水艦を上に移動した後、地点(3,5)に魚雷を発射します。

マップ生成

マップは下記のロジックで生成されます。

  • 一様ランダムにマップ上のマスを1つ選び、島を生成します。これを同じく一様ランダムに5~30回繰り返します。同じ地点を複数指定することもあります。
  • 島のあるマスに対して、右上方向に島を拡張します。そのため、基本的には最低4マスの島が形成されます。

f:id:tsukammo:20200329073615p:plain
図:島の拡張処理