2024-04-21

いま、ここにしかない、出会い。(AtCoder 第一回マスターズ選手権 -決勝- で五位入賞しました。)

下記の日時に開かれた競技プログラミングコンテスト、AtCoder「第一回マスターズ選手権」の備忘録です。

予選：2024/03/03(日) 13:00 ~ 19:00 (360分)
本戦：2024/04/21(土) 11:10 ~ 17:10 (360分)

結果

予選：41/182位、本戦：5/56位でした。※有効回答者のみカウント。
初のオンサイト出場 & 入賞ができ、たくさんの方と出会えた記念に参加記を書きます。

2023-05-26

codingame:SPRING CHALLENGE 2023 ルール要約

これはなに？

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

ルール説明

勝敗

あなたはロボットアリを上手く誘導し、相手より多くクリスタルを集めて下さい。
ロボットアリは直接操作できず、設置するビーコンに反応して移動します。
フィールド上の全クリスタルの過半数を取得、もしくは100ターン経過時点でより多くのクリスタルを所持しているプレイヤーが勝利します。

行動

あなたは毎ターン以下のアクションを取ることができます。アクションは出力した順に実行され、実行不可のものは無視されます。 1ターンの間にセルにおけるビーコンはひとつまでです。

WAIT(待機)：何もしません。
BEACON(ビーコンを設置)：指定したセルに任意の強度でビーコンを設置します。ターン中何回でも実行可能です。
LINE(2点間にビーコンを設置)：指定した2つのセルとそれを結ぶ自動算出された最短路上のセルに、任意の強度でビーコンを設置します。ターン中何回でも実行可能です。

フィールド

フィールドは、六角形のセルで形成され(ヘキサグリッド)、中央を起点として点対称に生成されます。フィールドの大きさは、中央からの横幅が4～7、高さは横幅の60%未満となります。
フィールドのうち、10～20%の確率でセルが消去されます。消去されたセルには移動不可となります。

図. 最小のフィールド(上)と最大のフィールド(下)

セルの種類とオブジェクト

各セルは3種類(type)に分類されます。戦闘の数字はゲーム開始時に各セル与えられる区分値です。

0：何も資源を持たないセルです。
1：ロボットアリの卵を持つセルです。※Wood1から開放
2：クリスタルを持つセルです。

また、type=0のセルのいずれかに各プレイヤーの拠点が設置されます。
拠点は1つ、もしくはBronze以降は33%の確率で2つ設置されます。

ビーコンの設置とロボットアリの誘導

両プレイヤーは、自分の拠点に数匹のロボットアリが配置された状態でスタートし、ビーコンを設置しロボットアリを誘導することができます。
プレイヤーは1ターンに何個でもビーコンを置くことができますが、1つのセルに1個ずつしか置くことができません。
設置するビーコンに任意の強度を与えられ、それぞれのビーコンの強度に応じて誘導するロボットアリの割合を決められます
例：全ビーコン強度が1だと、各セルに均等になるようロボットアリが移動します。

ビーコンに対するロボットアリの移動は以下のロジックで決まります。

自身のロボットアリの総量を設置したビーコンの強度の総和で割り、強度1に対するロボットアリの数を算出します。
各セルのビーコンの強度に対して、比率との差が最も小さくなるよう実際に割当るロボットアリの数を決めます。
各ロボットアリが割当られたセルに対して最小経路で移動します。 ※2023/05/26　18時時点、最後の最小経路選択が一意に定まらず同じ条件でも移動先が変化するっぽい？

ロボットアリの連なりと資源の取得

資源を取得するには、資源のあるセルと自分の拠点との間に、自身のロボットアリが存在するセルが途切れることなく連鎖している必要があります。
1ターンに取得できる資源の量は、その連鎖の中でロボットアリが最も少ないセルのロボットアリの数と同じになります。

図. この連鎖はクリスタルを4取得する

資源の取得量は、クリスタルでも卵でも同じ処理です。
卵を取得した場合、取得した数と同じ数のロボットアリが次のターンの開始時にそのプレイヤーの拠点に産まれます。
プレイヤーごとに複数の拠点があるゲームでは、収穫チェーンに存在する拠点に関係なく、追加のアリはそれぞれの拠点に生まれます。
取得量は資源ごとに別々に処理され、複数の経路が考えられる場合はジャッジ側で取得量が最大になる連鎖が自動的に選ばれます。

資源取得妨害(Attack Chain)

※Bronzeから開放されます。
※2023/05/26 18時現在、以前まで動作していなかった本仕様が修正されました。
プレイヤーの資源取得は、相手のロボットアリによって妨害されることがあります。
資源取得を処理する時に両プレイヤーが資源取得可能な状態の場合、取得可能量(つまり連鎖経路のうちの最小アリ数)を計算し、低い方のプレイヤーは資源取得ができなくなります。
※取得可能量が同数の場合、両プレイヤーが資源を取得できます。なお、十分な量の資源がなくとも取得可能量そのままの値を受け取ることになります。

各ターンの処理順序

LINEアクションが処理されます。
BEACONアクションが処理されます。
ロボットアリがビーコンに誘導され移動します。
クリスタルが取得され、得点になります。
卵が取得され、新しいロボットアリが産まれます。

その他ジャッジコードから読み取れる内容

シルバーリーグから、入力に現在スコアが追加されるようです。
ロボットアリ同士が戦う処理が存在します。同じセル上に両プレイヤーのアリが存在する時、1ターンに最大3匹消失するようになるかもしれません。

2022-12-13

codingame:FALL CHALLENGE 2022 ルール要約

これはなに？

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

ルール説明

勝敗

あなたはロボットを操作し、相手より資材が残る陣地を広げて下さい。
ロボットは資材の残るマスでしか生存できず、新たなロボットを生産するには資材が必要です。

行動

あなたは毎ターン以下のアクションを好きなだけ取ることができます。アクションは出力した順に実行され、実行不可のものは無視されます。

移動(MOVE)：あなたの陣地のうち、指定したあるマスから別のマスへ、好きな数のロボットを移動させます。
建設(BUILD)：あなたの陣地のうち、ロボットのいないマスにリサイクル施設を建設します。建設には10の資材を消費します。
生産(SPAWN)：あなたの陣地のうち、指定したマスに好きな数のロボットを出現させます。ロボットは1体毎に10の資材を消費します。

陣地

フィールドは、幅12～24、高さ6～12のマスからなり、各マスには0～10の資材が設定されています。
各マスは初期状態はどちらの陣地にもなっていないニュートラルな状態であり、最後に通ったロボットの所有プレイヤーの陣地となります。各ロボットの移動処理は同時に行われ、同じマスに異なるプレイヤーのロボットが移動した場合、存在するロボットの数分だけ相殺されます。

リサイクル施設

建設(BUILD)コマンドによって、あなたの陣地のうち、ロボットのいないマスにリサイクル施設を建設します。リサイクル施設は自身と上下左右の合計5マスから、毎ターン1ずつ資材を回収します。資材の無くなったマスは通行不可となり、リサイクル施設のあるマスが資材0となった場合、リサイクル施設は消滅します。

ロボット

ロボットは初期に4体与えられ、1体につき資材10を消費して好きな陣地に生産することが可能です。ロボットは各ターン毎に1マスずつ移動することができますが、生産されたターンは移動ができません。移動先は資材が残っているマスのみとなり、リサイクル施設によりロボットのいるマスの資材が無くなった場合、ロボットは消滅します。

ゲームの処理順

建設(BUILD)アクションの実行
移動(MOVE)アクションと生産(SPAWN)アクションの実行
同じマスのロボットの相殺処理の実行
残ったロボットによる陣地の更新
リサイクル施設による資源回収
資源0のマスのリサイクル施設とロボットの除外
各プレイヤーは基本資材10とリサイクル施設が回収した資源を取得

以下の状態となった時、ゲームが終了し多く陣地を保有しているプレイヤーが勝利します。

あるプレイヤーの陣地が全て失われた
20ターン各マスの資材や陣地の変更が無かった
200ターンが経過

今後の発展性

2022/12/13 3:00時点で、ブロンズリーグでルール開放がされませんでした。
2022/12/20 0:00時点で、シルバーリーグでルール開放がされませんでした。
2022/12/24 0:00時点で、ゴールドリーグでルール開放がされませんでした。よってルールはそのままの可能性が高いです。
~~現状のルールはあまりにシンプルでコンテストとして成立しておらず、今後のルール追加の可能性があります。~~
例えば、ジャッジコードに複数人の実行可能性が記載されており、3人以上のプレイヤーによる同時バトルの可能性があります。~~また、コストを支払って任意のマスにワープするアクションが存在していることが確認できています。~~ワープ機能は今後も使われないと公式から連絡がありました。

2022-06-17

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度のみである。

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

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

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

また、最後の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

2022-04-22

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ユニット離れたモンスターは消滅します。(マップ外でもモンスターは存在。)
マップ外のモンスターは視認できません。
マップ外からモンスターが拠点エリア内に侵入することはできません。

2021-05-30

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

これはなに？

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

提出プログラム

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

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

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

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

今回行った工夫

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

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

おわりに

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

2021-04-03

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ではコンテスト内容や自身のアイディアに関する言及が許されており、本記事が万が一当たってたとしても問題は無いという考えの元、公開しております。もし本記事によりコンテスト開催に支障が生じる場合、すみやかに削除いたします。

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

「楽しいよ」 https://t.co/4Nh0TUYsF6
— ツカモ (@tsukammo) 2021年3月25日

手掛かり

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

item.rakuten.co.jp

２～４人用のボードゲームのようです。奇しくも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と作成者の方に改めて感謝を。

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

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