2026-03-25

CodinGame Winter Challenge 2026: SNAKEBYTE

CodinGameの2週間ゲームAIコンテストの参加記。題材は重力下にあるスネークゲームです。

ゲームの様子：https://www.codingame.com/replay/881180397

結果は、世界22位/2382人・日本2位/105人でした。

解法概要

ヘビを塊ごとに分けてグループ毎にchokudaiサーチをしました。

で、今回は手で書いたのは最初の入出力くらいで、残りはAIがコードを書いています。改善に関しても7割くらいはAIが勝手にやった改善です。

ローカル対戦環境

AIでの自己改善に必須だったローカル対戦環境は2日目くらいに作りました。作るのに1時間もかからなかったと思います。 Tauriで作っていてGUI版とCUI版があります。最新のコードvsアーカイブされた昔のコードが対戦出来るようになってます。 100戦こなすのが40秒くらいで3000戦位しないと勝率は収束しなかったです。

タイムアウトについて

今回、謎のタイムアウトが発生してちょいちょい負けてたんですが、他の人も発生してたらしいので完全解決は諦めました。

アルゴリズム詳細

AIに解説してもらいましょう。

ゲーム概要

「Snake Bot」は、グリッド上でヘビ型ロボットのチームを操作し、エサ（パワーソース）を食べて成長させる対戦ゲームである。重力があり、ヘビは支えがなければ落下する。頭が壁や他のヘビの体に衝突すると頭が破壊され（体長3以下なら即死）、最終的に全ヘビの合計体長で勝敗が決まる。制限時間は1ターン50ms。

アルゴリズムの概要

Chokudaiサーチを用いた先読み探索AIである。処理の流れは以下の通り。

毎ターン、全エサからの壁考慮最短距離をBFSで事前計算する
盤面上のヘビを近さに応じてグループに分ける
グループごとにChokudaiサーチで先読みし、最善手を決定する

核となる設計思想:

シンプルな高速計算を重い精密計算より優先する（45msの制約下では探索回数が正義）
評価の各軸を独立に保ち、辞書式に比較する（混ぜるとスケールが崩壊する）
枝刈りは安全側で行う（確実に悪い手だけを除外し、グレーゾーンは残す）
重い計算はターン開始時に事前計算し、探索中には持ち込まない

アルゴリズムの詳細

1. エサまでの距離の事前計算

毎ターン開始時に、全エサの位置からBFS（幅優先探索）を実行し、壁を迂回した各マスへの最短距離をテーブルとして事前計算する。この距離テーブルは評価関数の複数箇所で参照される。

探索中（シミュレーション内）にBFSを毎回走らせる方式は4回試したが、計算が重すぎて探索回数が激減し全て壊滅的に退化した。ターン開始時に1回だけ計算するのがコストと精度のバランスとして最適だった。

2. ヘビのグループ化

全ヘビ（味方・敵問わず）をマンハッタン距離6以下でグルーピングする。遠くの無関係なヘビを同時に探索すると組み合わせ爆発が起きるため、近くにいるヘビだけを1つのグループとして扱い、グループごとに独立に探索する。

グループ内の味方ヘビは全方向の組み合わせを探索対象にする。グループ内の敵やグループ外の味方は、最寄りのエサに貪欲に向かうBFS予測で行動を決め打ちする。グループ外の敵は静止扱いとする（遠方なので影響が小さい）。

3. Chokudaiサーチ

グループごとにChokudaiサーチで先読みする。探索深さはグループ内の味方ヘビ数に応じて動的に決まる。味方1匹なら17手先、2匹なら9手先、3匹以上なら7手先まで読む。味方が少ないほど分岐が少ないため深く読める。

時間配分は「残り時間をグループ内の味方数に比例して按分」する方式で、制限45msの中でグループ間に公平に配分する。

4. 評価関数

評価は3つの軸を持ち、辞書式に比較する。つまり第1軸で差があればそれだけで決まり、第1軸が同じなら第2軸、それも同じなら第3軸で比較する。この3軸を重み付きで合算する方式は何度も試したが、毎回壊滅的に退化した（勝率9%〜34%）。軸を独立に保つことが極めて重要だった。

第1軸: 体長と生存の相対評価（最重要）

味方と敵の体長差を基本とし、生存・死亡に関するボーナス/ペナルティを加減する。

味方の体長: そのまま加算
敵の体長: 減算（敵が伸びるのは不利）
味方の死亡: -80の大ペナルティ（死亡回避が最優先）
体長4以上ボーナス: +30（衝突しても即死しない安全域に達したことへの報酬）
敵を倒したボーナス: +30/匹
行き止まりペナルティ: 頭の周囲4マスに空きがなければ-40、1マスだけなら-10

死亡ペナルティ(-80)がサイズボーナス(+30)より遥かに大きいため、「死なないこと」が最優先の評価体系になっている。

終盤の特殊処理: エサが全てなくなるとゲーム終了するため、その時点での体長比較で勝ち/負け/引き分けを判定し、大きなボーナス/ペナルティを加える。

第2軸: なわばり（ボロノイ的エサ制御度）

各エサについて、味方と敵のどちらが先に到達できるかを壁考慮の距離で比較し、「どれだけのエサが自分の勢力圏にあるか」を数値化する。単純なカウントではなく、距離差が大きいほど確実な制御として高い重みが付くスムーズな連続値を使う。

第1軸が同点の場合のタイブレーカーとして機能し、「体長が同じならエサが多い勢力圏にいる方が有利」という判断を可能にする。

終盤攻撃モード: 残りエサが3個以下で体長負けしている場合、この軸を「敵の頭への近さ」に切り替える。負けている状況でエサのなわばりを争っても意味がないため、敵に接近して衝突（相打ちによる敵体長の削減）を狙う行動を誘導する。

第3軸: エサへの接近度

各味方ヘビの頭から、最も近い3つのエサまでの壁考慮距離の合計。小さいほど良い。

最寄り1つだけだと目先のエサに突進する短絡行動になり、5つだと広すぎて焦点がぼける。3つが最適で、エサが密集しているエリアへ自然に向かう誘導効果がある（top-1/2/4/5は全て退化を確認済み）。

終盤切替: 残りエサ3個以下で体長負けの場合、エサへの距離の代わりに最寄りの敵の頭への距離に切り替える。

5. 枝刈り（移動方向の段階的フィルタ）

味方ヘビの移動候補を4段階で絞り込む。各段階で全候補が消えてしまった場合は、前の段階の結果にフォールバックする安全弁を設けている。

逆方向の除外: ゲームルール上、現在の進行方向と逆には進めないため除外（4方向→3方向）
壁・ヘビ体への衝突除外: 移動先が壁またはヘビの体（次ターンに移動する尻尾を除く）なら除外
首刎ねリスクの回避: 移動先が敵の頭の隣で、かつ敵の方が自分より大きい場合に除外。同サイズ以下の敵との相打ちは許容する
行き止まり回避: 移動先から2手先まで見て脱出不能な方向を除外。3手以上先まで見ると過保守になり退化した

6. 敵の行動予測

敵ヘビの行動をBFSベースの貪欲予測で推定する。「最寄りのエサに最短経路で向かう」と仮定し、1手目の方向を返す。

いくつかの工夫を加えている:

行き止まりに突っ込む方向は除外した上でBFSを開始する
BFS開始方向で敵の頭の近くに飛び込むリスクのある方向を避ける
どのエサにも到達不能な場合は、周囲の空きマスが最も多い方向に進む

敵予測の精度向上はこのゲームで最も一貫して効果のあった改善カテゴリだった。

7. 高速化の工夫

ビットセットによる占有判定: 壁・エサ・ヘビ体の位置管理にビットセットを使い、OR演算で高速に合成
固定長配列の活用: 探索の内側ループで動的メモリ確保（ヒープ割り当て）が発生しないよう、可変長配列を固定長配列に置き換え。これが唯一大きな効果のあった高速化で+3.8%
必要最小限のコピー: ヘビの体の配列コピーを実際の体長分だけに限定

バージョン進化の概要

段階	主な改善	効果
初期	体長合計のみの評価、固定深さ7	-
評価多面化	死亡ペナルティ・差分評価・動的深さ・敵撃破ボーナス	大
エサ距離改善	上位3エサの距離合計・なわばり評価の導入	大
枝刈り強化	壁衝突除外・ヘビ体衝突除外	大
安全性向上	行き止まり回避・首刎ねリスク回避	大
距離精度向上	BFS事前計算・なわばりの壁考慮化・スムーズ化	中
脱出判定改善	敵の尻尾は次ターンに空くとみなす・同サイズ相打ち許容	小
探索深化	探索深さ12→17・敵予測改善・内側ループ高速化	中
終盤対応	ゲーム終了検知・終盤攻撃モード	大

感想

時代は変わってしまった

2024-06-26

CodinGame Summer Challenge 2024 with Fiverr - Olymbits

CodinGameの2週間ゲームAIコンテストの参加記。題材は4つのゲームを1つのコントローラーで操作する謎ゲームです。

ルール：https://tsukammo.hatenablog.com/entry/2024/06/12/000614

ゲームの様子：https://www.codingame.com/replay/792769882

結果は、世界34位/18147人・日本6位/370人でした。

アルゴリズム概要

DUCTを使いました。以上。

DUCTについてはterryさんの記事や
https://www.terry-u16.net/entry/decoupled-uct

記事中にもあるThunder本が分かり易いと思います。

ゲームで学ぶ探索アルゴリズム実践入門～木探索とメタヒューリスティクス

作者:青木栄太
技術評論社

Amazon

評価値について

プレイアウトは今やってる競技が全部終わるまでor100ターン経過するまでをやります。

評価値はプレイアウト後にスコアの変動がなければ0.0で全部金メダルを取ったと仮定したスコアを1.0として計算します。

例えば現状のメダルスコアが

ハードル	3点（金1個）
アーチェリー	1点（銀1個）
スケート	3点（金1個）
ダイビング	4点（金1個・銀1個）

であれば、プレイアウト後に36点なら0.0で1008点なら1.0で300点なら0.271みたいな感じです。

ただメダルスコアが

ハードル	3点
アーチェリー	0点
スケート	0点
ダイビング	4点

みたいな状態なだとプレイアウト前は0点だしプレイアウト後も0点であることがザラにあるので、メダルスコアが0点の場合は無償の銀メダルを1個与えて1点持ってる状態にして計算しました。

それに加えて、最終的な順位での評価値も↓のようにつけて

1位	1.0
2位	0.5
3位	0.0

lerp(スコアでの評価値, 順位での評価値, 現在のターン数/100)で最終的な評価値を出してました。

最初はスコアでの評価値のみで評価値出してたんですけど、順位での評価値を加味すると成績が結構上がったので効果あったんじゃないかと思います。

プレイアウト時の手の進め方

まずそれぞれの競技のLRUDそれぞれについて-1.0～1.0で評価値をつけます。

ハードル	1歩進むと0.3333点、ハードルに引っかかると-1.0点
アーチェリー	`操作後の中心からの距離-操作前の中心からの距離`を-1.0～1.0に正規化する
スケート	常に0.0（1手目以外は予測できないので）
ダイビング	一致した矢印だと1.0点、不一致の場合`-現在のコンボ数/15`点（コンボが繋がってたらなるべく続けたい気持ち）

で、この評価値を元にして比重をつけてからランダムで次の手を選択します。

余計なことせずに単純にランダムに手を選ぶと大体10000～15000回くらいループできてたんですが、ここに書いたような工夫をした手の進め方にすると4000～7000回くらいになっちゃいました。

ただ、ループ回数は減ったんですが、成績は上がったんでループ回数を犠牲にしてでもプレイアウトの手の進め方を工夫するのは有りだったっぽいです。

木の選択＆展開

木の選択は深く考えずUCB1を使いました。

Cは0.2で7回選ばれたら木を展開するようにしました。この辺は人力パラメータ調整です。

ローカル環境

cg-brutaltesterを使ってました。

今のコードvs直前提出のコードvsちょっと古いコードで対決して検証してました。

実はpsyleagueを使ってみようと思ってたんですが上手く環境構築できなくて諦めました。

感想

・DUCT組んだのは初めてだったけど、雑にDUCT組んで提出したら二桁順位になってこりゃつえーってなった。

・対戦画面を眺めても何も分からんので、今回はメタを張るとかなくて完全に自分との戦いって感じだった。

・上位のDUCT使いました勢とレート差がだいぶ開いてるので自分のモンテカルロ力はまだまだ低いんだろうな・・

2020-05-19

SPRING CHALLENGE 2020

CodinGameの10日間コンテスト。じゃんけんパックマンゲーム。

f:id:y_kwn:20200518230416p:plain

リプレイ : https://www.codingame.com/replay/467340361

世界25位/4976人、日本5位/228人でした。個人的にはあまりぱっとしない成績。

ルール

同時に2～5体のパックマンを操作しペレットを集めるゲーム。
過半数のペレットを集めたほうが勝ち。
じゃんけんで勝っている敵のパックマンを食べることができる。
アビリティとして「加速」と「グーチョキパーどれかに変身」が使える。

アルゴリズム概要

10手読み幅200のビームサーチで各パックマンの動きを決定。
パックマン毎に200パターンの動きが求まるので、どれを組み合わせるかを山登りで決定。（この辺のパラメータ調整は甘い）

最初は相手の動きに合わせて如何に動くかが肝心と思って「すわっこれはMCTSか！？」と思ったんですけど、敵と絡むことはそんなにないので敵の動きはある程度無視して自分の動きを最適化するのがベストだと思い直しました。
さらに味方同士もそんなに絡むことはないから、パックマン毎にサーチして後でマージするって方式にしました。

ビームサーチ部

10手読み幅200でサーチ。
多様性確保のために最初の2手の動きが異なる物はビーム内に必ず入るようにした。
あいこか負ける敵は行き止まりとして扱ってサーチした。（これ勝つ相手も行き止まりにしてよかったかも）
来た道を戻るような動きにはペナルティをかけた。

山登り部

各パックマンが10ターン分の動きを200パターン持ってるから、各パックマンはその中から動きを１つチョイスする。選んだ動きを元に10ターン分シミュレーションして評価する。シミュレーション中敵は動かさない。
その後どれか１つのパックマンの動きを変更するという遷移で山登りする。

評価関数

小ペレットを取った数 * 10
大ペレットを取った数 * 100
なくなってるかもしれないペレットを取った数 * 1
近くの小ペレットまでの距離 * -0.1
近くの大ペレットまでの距離 * -5.0
殺される相手の移動圏内にいると -10000

小手先テクニック

敵の動きの予測

各ターンの最初に、見えない敵は1手分動きを予測して予想位置を決定した。動き方はこれ↓

アビリティを使える状態なら加速を撃つ
なるべく大ペレットに近づく
ペレットに接していたらペレットを食べる

見えない敵を再び見かけたときは、その地点にワープさせた。（適当）

通路

f:id:y_kwn:20200518230020p:plain

通路（画像の黄色い部分）の入り口をチェックして、入り口にペレットがあったら通路内のペレットはまだ存在すると仮定した。逆にペレットがなかったら存在しないものとして仮定した。

とられたかもしれないペレット

ペレットは、小ペレット・大ペレット・とられたかもしれないペレットの3つの状態を持つようにした。

かちあい時の動き

f:id:y_kwn:20200518230027p:plain

かちあいが発生したら、加速と相手に突っ込むのを禁止した。
（加速したらその瞬間に取られるし、変身した相手に突っ込んだら死ぬので）

殺し

アビリティを使えない敵が袋小路に追い込まれていた場合は殺すようにした。逆に自分が袋小路に追い込まれていた場合は勝てる相手に変身するようにした。

反省

敵の動きの予測をもっと作り込むべきだったかなあ。

戦術をもっと真面目に考えるべきだった。

諸々検証不足でフィーリングで進めがちだった気がする。

山登りより優先度順にビームサーチの方が強そう。

2019-05-21

CODE VS Reborn

2019/4/15～2019/5/10にあったゲームAIコンテスト。ぷよぷよみたいな落ち物パズルゲー。

f:id:y_kwn:20190521201613p:plain

決勝の様子(が見れる予定)：https://live.nicovideo.jp/gate/lv320076507

予選3位/112人・決勝◯位でした。
参加人数は少ないですが参加面子を考えると日本最高峰のゲームAIコンテストだったでしょう。

ルール（適当説明）

基本ぷよぷよですが、4つ揃えるんじゃなくて数字の和を10に揃えたらブロックが消えるみたいなルールです。連鎖すると敵の盤面にお邪魔ブロックを降らせます。相殺もぷよぷよと同じ仕様です。ぷよぷよと大きく違うのはスキルがある点です。ブロックを消すとスキルゲージが溜まって、溜まると数字の5を爆発させて連鎖したときと同じように攻撃ができます。

アルゴリズム概要

目標連鎖数を決めてchokudaiサーチで探索して、発火が近くなったら色々考える感じです。

全体フローチャート

f:id:y_kwn:20190521201912p:plain

連鎖数決定

基本12連鎖を狙います。

敵がスキル型だったら15連鎖を狙います。敵が6連鎖以上組めてなかったらスキル型と判定してます。

敵を殺せそうだったら殺せるぐらいの連鎖を狙います。例えば敵が3行のお邪魔で死ぬなら大体11連鎖(お邪魔33個)を狙う感じです。

探索

心臓部です。

探索の重要性

単純な探索では絶対に負けないようにしました。敵が先に12連鎖撃ってきてるリプレイを発見したら、最低でも同じ速度で撃てるように徹底的に改良しました。探索で負けていてもカウンター等の戦略で勝つことはできますが、それはじゃんけんに例えると「パーを出せないからグーとチョキと戦略で勝つ」みたいな発想です。上位層で戦うにはグーチョキパーすべてと戦略を組み合わせないと話にならないと思ったので、妥協は絶対にしないようにしました。

探索の概要

10秒間のchokudaiサーチで探索しました。初手だけ18秒です。

MAX15ターンですが予定の連鎖数が見つかったら探索を打ち切ってるので15ターンまで読むことはほぼ無いです。（言い変えると15ターン以内に連鎖が見つかるように調整した）

こういうサーチ系を強くするのに重要なのは

評価関数改良
高速化
探索の質を高める

ですが、評価関数はほぼ弄ってないので残り２つ中心の改良が中心でした。（評価関数を弄らないで正解だったかは不明）

評価関数

連鎖数 * 100
+ ブロック数 * 0.1
- 消えたブロックの数/連鎖数
- 15行積み上げていたらペナルティ
- 2ターン前から連鎖数が伸びてなかったら超ペナルティ

連鎖数は1ブロックを仮で落としてみての連鎖数です。

ブロックの落とし方ですが、最初は左端から右端まで落としてチェックしますが、1度連鎖を発見したら以降は発見ポイントから前後1マスだけ落とすように縛ってます。

高速化

多分皆やってたと思うんですが、1マスに4bitを割り当てて盤面をlong long[WIDTH]で表現して、ひたすらbit演算しました。

ざっくりすぎるのでいつもやってる高速化の手法を紹介します。これはどんなコンテストでも使える汎用的な方法です。

1. visual studioでパフォーマンスプロファイラーを起動します。

2. ボトルネックを見つけます

3. ボトルネックをカスカスになるまで高速化します。

f:id:y_kwn:20190521203149p:plain — ボトルネック

よくある話ですがボトルネック以外は高速化してもほぼ意味がないです。

実際にどう高速化するかはtomerunさんの高速化の記事を読みましょう。 https://topcoder.g.hatena.ne.jp/tomerun/20171216

探索の質を高める

基本は「無駄な探索を排除する」です。

まずはこんなツールを作ります。

f:id:y_kwn:20190521203405p:plain

これはchokudaiサーチの中身をダンプしたものを表示するツールです。これとにらめっこして改良していきました。

主にやったこと

１．ブロックを落とす場所を連鎖群に隣接する範囲に絞る

この縛りを入れないと、離れたとこにポツンと落とすパターンが生まれるので潰しました。

f:id:y_kwn:20190521203706p:plain

２．１ターン目は落とす場所を真ん中に固定する

この縛りを入れないと、形が横にずれただけみたいなパターンが生まれがちなので縛りました。 f:id:y_kwn:20190521211126p:plain

３．重複盤面除去

ダンプした結果を見ると重複盤面がそこそこあったので排除しました。

発火間際の諸々

発火１・２手前になると諸々考えて、前倒しで発火するか普通に発火するかさらに連鎖伸ばすかを判断します。

以下が入れた処理です。カッコ内は判定タイミングです。

・カウンター警戒（連鎖発動ターン）

カウンター戦術使ってくる人が多かったので入れました。

敵にお邪魔ブロックを降らしてみた上で敵の盤面を７手読みchokudaiサーチします。で、こっちがかました連鎖数以上のカウンターが飛んでくるようだったら、連鎖を撃っても意味ないので連鎖さらに伸ばします（目標連鎖数はそのカウンターの連鎖数）。

・目標連鎖数に達していたら発火（連鎖発動ターン）

変にバグって発火しなかったら困るのでこの処理入れました。

・対ボマー対策１（連鎖発動2手前以内）

敵があと2手でスキルゲージが溜まる状態かつ、こちらが2手以内に12連鎖以上発動できる場合は発火します。

・対ボマー対策２（連鎖発動3手以上前）

敵があと3手でスキルゲージが溜まる状態かつ、こちらが3手以内に連鎖を発動しない場合3連鎖を狙います。

・連鎖潰され対策（連鎖発動１手前）

敵が連鎖を発動させたと仮定して自分の盤面にお邪魔ブロックを降らせます。で、次のターンの自分の連鎖数が激減する場合は前倒しで連鎖を発動します。

・まだ舞える（連鎖発動ターン）

敵の盤面を2手全探索してもしょぼい連鎖(11連鎖以下)しか見つからない場合、自分の盤面を2手全探索します。で、連鎖が伸ばせるなら自分の連鎖を伸ばします。

・敵の連鎖つぶし（毎ターン）

敵が次のターンに12連鎖以上発動させることが出来る場合、ためしに自分の連鎖を発火させてみます。で、お邪魔ブロックを降らした結果、敵が2手かけても5連鎖以下しかつくれない状態になるなら連鎖を発動します。

小ネタ

死亡間際のボマームーブ

基本は足掻いてもそのまま死ぬんですが、たまーに刺さるのでやり得でした。雑に３手呼んで、スキル攻撃力を上げつつゲージ溜め優先といった感じです。

並列化はやってない

最後２日くらいでやろうと思ったんですが、やろうと思ったときには上位キープしてたし、決勝も1スレッドだろうからまあいいかなって感じでした。

反省点

余裕で決勝で行けたのでまあ満足です。

2019-03-19

CODE A LA MODE

CodinGameの10日間コンテスト。味方と協力して料理を作るゲーム。

f:id:y_kwn:20190319070610p:plain

リプレイ : https://www.codingame.com/replay/377758737

世界7位/1543人、日本2位/53人でした。もう日本2位は嫌なんじゃ・・。

ルール

一言で言うとovercookedです。2人で料理を作って配膳するとスコアが入るゲームです。
いつものと違って対戦相手と協力プレイをするってのが面白いです。

料理の作り方はそれぞれ↓みたいな感じです。

料理	作り方
アイス	そのまま
ブルーベリー	そのまま
イチゴ	イチゴ→まな板→完成
クロワッサン	パン生地→オーブン→完成
タルト	パン生地→まな板→ブルーベリー→オーブン→完成

順位の付け方は、3人がマッチングしてA+B・B+C・A+Cで協力プレイをして、合計スコアが高い順で順位が付きます。例を挙げると・・

A+B: 100点
A+C: 200点
B+C: 1000点

だったとすると

A: 300点
B: 1100点
C: 1200点

みたいなスコアがついて順位が付きます。こういう形式にすれば協力プレイでも順位がつくのでなるほどな～と思いました。

アルゴリズム

chokudaiサーチで7手読みでした。シミュレータは45msで100k～150kくらいの性能でした。
これ書いてて気付いたけど重複盤面除去やってねぇ。

サーチ部

枝刈り

1～3歩の移動かつ外周を移動中かつ周囲になにもない場合の移動は無視してます。
手に何か持ってる時、周囲に複数箇所置ける場所があっても置く場所は1箇所にとどめています。RAW_TARTならオーブンの近くに置くとかそんな感じで適当に決めてます。

相棒のシミュレーション

相棒の行動は以下のシミュレーションだけやって、それ以外は棒立ちです。

1手目の時点でオーブンにTARTかCROISSANTが入っていて、オーブンに隣接している場合取る
完成した料理を持っていたらwindowに近づいて配膳

評価関数

ゲームスコア  
+ (料理が揃っていたら)配膳する評価値  
+ タルト・クロワッサンの数（燃え尽き防止）  
+ 料理作る評価値

基本的に上に書いてある方が値が大きくなるようになってます。
「配膳する評価値」と「材料作る評価値」は3つのオーダーそれぞれで評価値を出して、1番評価値が高い値を採用しています。
結果的に配膳できるものをさっさと作ってさっさと配膳する感じの評価関数になってます。

配膳する評価値

料理が皿に乗ってたら加点  
+ 料理が皿に乗ってなかったらその料理までの距離  
+ 皿を持ってなかったら皿までの距離  
+ 余計なものが皿に混じってたら大減点

料理作る評価値

（必要な料理それぞれについて）  
既に料理ができていたら加点  
+ 料理の進捗度に応じて加点

例：TARTの進捗度得点

状態	得点
オーブンにRAW_TARTを入ってたら	4点
RAW_TARTを持っていたら	3点+オーブンまでの距離で微小点
CHOPPED_DOUGHを持っていたら	2点+BLUEBERRIESまでの距離で微小点
DOUGHを持っていたら	1点+まな板までの距離で微小点
何も持っていなかったら	DOUGHまでの距離で微小点

その他

bit表現

アイテムやらはこんな感じでbitで表現してました。

const int NONE                  = 0b000000000000000;
const int DISH                  = 0b000000000000001;
const int BLUEBERRIES           = 0b000000000000010;
const int ICE_CREAM             = 0b000000000000100;
const int STRAWBERRIES          = 0b000000000001000;
const int CHOPPED_STRAWBERRIES  = 0b000000000010000;
const int DOUGH                 = 0b000000000100000;
const int CROISSANT             = 0b000000001000000;
const int CHOPPED_DOUGH         = 0b000000010000000;
const int RAW_TART              = 0b000000100000000;
const int TART                  = 0b000001000000000;
const int MAP_EMPTY             = 0b000010000000000;
const int MAP_TABLE             = 0b000100000000000;
const int MAP_WINDOW            = 0b001000000000000;
const int MAP_CHOP              = 0b010000000000000;
const int MAP_OVEN              = 0b100000000000000;

メモリ使用量抑えたり、速度稼ぐためにやっとくかーって感じでしたが、普通に諸々の処理書くときに割と便利でした。

if(hand & DISH) //皿を持っているか
if(hand & (~order)) //オーダーにないものを持っているか
hand |= TART //タルトを拾う

みたいな

小ネタ

相棒が持っているものは基本無視しました。他人を信用しないスタンスです。

オーブンに入ってるRAW_TART・DOUGHはTART・CROISSANTとしてカウントしています。これで焼け上がるのをボーッと待ってるマンを防げました。

ローカルテスト環境

一応ローカルでもゲームを回せるようにしてました。プレイヤーは全員最新の自分で30戦くらい回して改善をチェックしてました。
ローカルテストでのスコアをベースで改善を進めるんじゃなくて、大きくスコアが下がってなければバグが仕込まれていないのでOKくらいなスタンスで運用していました。
ただまぁ、ローカルテストのスコアとsubmit後の順位は大体比例してた気もします。

反省点

やっぱりこれ書いているときにバグやら改善点を思いつくので、面倒臭がらずに終了1日前くらいにこれ書いた方がいいかも。
評価関数の数字の大小関係の調整が超シビアだったので、予め理論的に評価関数を設計すべきだったかも。
取れる行動の種類は多くても、シチュエーションの数は数えれる程なので(ホントか？)もっとヒューリスティックに寄せても良かったかも。
何か見ながら作業するのはやめた方が良い（さくゆいかわいい）

2018-12-17

Xmas Rush

CodinGameの10日間コンテスト。アイテムを集めるゲーム。

f:id:y_kwn:20181217212006p:plain

リプレイ： https://www.codingame.com/replay/360798673

世界29位/1229人、日本2位/40人でした。上位層に全然ついていけなかったので悔しい結果です。

ルール

大きく分けてPUSHターンとMOVEターンに別れていて、その2つのターンを繰り返します。

PUSHターン：いずれかの行列をPUSHして迷路をずらします。このときの行列の指定は敵味方同時に行います。敵味方で同じ行or列が指定されたら何も起きません。

MOVEターン：プレイヤーを20歩動かすことが出来ます。アイテムが3つ指定されるのでそのアイテムを回収するのが目的です。回収すると次のアイテムが指定されます。

最終的に12個のアイテムを回収したほうが勝利します。

アルゴリズム

minimaxっぽいことやりました。計算時間は余裕だったので枝刈りとかやってないです。

PUSHターン

自分のPUSH(max) → 敵のPUSH(min) → アイテム回収MOVE(一意に定まる) → 自分のMOVE(max)

という探索をやりました。2手読みとかやってみたんですけど性能落ちたので採用してないです。

MOVEターン

アイテム回収MOVE → 自分のMOVE(max) → 自分のPUSH(max) → 敵のPUSH(min) → アイテム回収MOVE → 自分のMOVE(max)

という探索をやりました。

評価関数

回収したアイテムの個数がベース
自分が端にいてNEXTに自分のアイテムがあったらそこそこプラス
自分が動ける範囲が広かったらちょっとプラス
指定アイテム周辺の道が繋がってたらほんのちょっとプラス
相手を邪魔するより自分の得点を稼ぐムーブをしたかったので、自分に関する評価値はちょっと増やした

小手先テクニック

行のPUSHが優先されるのでNEXTが自分のアイテムでかつ横端にいると100%アイテムを回収できる。
よく行列がかち合って数ターンロック状態になるけど、ロック状態のときは相手は自分と同じ行or列を指定しているはずなので、敵の動き予測が2パターンまで絞れる。
敵がアイテム回収を先行している場合、敵の指定アイテムを記録しておくことで自分の次の指定アイテムを予測できる。

反省

何も分からなかった
なかなかlegend行けなくて唸ってたらシミュレータに糞バグが仕込まれてて泣いた。（直したら余裕でlegend行けた）
smitsmaxというアルゴリズムが強いらしい。勉強しよ・・ https://www.codingame.com/playgrounds/36476/smitsimax