Code A La Mode 参加記
問題概要
CodinGameのCode a la Modeというコンテストに参加しました。
ゲームの雰囲気は以下のリンク参照↓
シェフを操作し、味方プレイヤーのシェフと協力して、お客さんに注文された料理をいかに効率よく調理して提供するかというゲームです。
結果
世界４位（日本１位）
最終提出プログラムの内容
１．戦略
まず客に注文された料理を調理してマップ上に置いていき、マップ上に全ての料理が揃ったら最後に皿に乗せて集める、だいたいそんな流れで行動するようにしました。
このゲームはお互いに協力したほうが良さそうなので、自分と味方を比較して味方のほうが良い位置にいるなら積極的に協力するようにしました。逆に、自分のほうが味方よりも良い位置にいる場合、味方は協力してくれるものとして行動するようにしました。
味方と協力している例として、例えば以下のリプレイでは味方にアイスを渡してあげるところとか見れます。優しい。
https://www.codingame.com/replay/377756278?f=206
２．アルゴリズム
Chokudaiサーチ７手読み（自分→味方→自分→味方→自分→味方→自分）
１ターンに評価できる盤面が約１万局面で、７手先の盤面は２０００局面ぐらい見れていました。３手先ぐらいまではだいたい全探索できてて、４手先以降でChokudaiサーチの最良優先が効いてた感じです。
３．評価関数の設計思想
（以下、Player1を自分、Player2を味方とします）
ChokudaiサーチでPlayer1→Player2→Player1…と評価するのとの相性を考えた結果、２人のプレイヤーを同じ重みで扱い「２人が協力すると仮定した場合の盤面の良さ」を評価するようにしました。
もしPlayer2を無視してPlayer1だけに対する評価にするとPlayer2が全力でPlayer1のために働いてくれるという評価なり、現実味がなくなるので明らかにダメです。（実際は味方は私だけのために働いてはくれないので）
もしターンプレイヤーだけに対する評価にすると、Player1を評価→Player2を評価→Player1を評価、と最後のターンは結局Player1に対する評価になるので、やっぱりPlayer2の評価が蔑ろにされがちになります。例えば３ターン全探索できたとして、３ターン後にPlayer1の評価が最も良くなる行動を選択するので、２ターン目にとるPlayer2の行動も結局はPlayer1にとって評価が最も良いものが採用されてしまうことになってしまい、現実味の無いシミュレーションになってしまいます。
それらも踏まえると、どちらのターンも２人を同等に扱って評価したほうが良い結果が得られそうなことが分かります。
４．評価関数
評価関数は以下のことを計算します。
①ゲームのスコア
②回収評価（注文の料理がフィールド上に揃っている場合、それを皿に乗せて提供するまでの評価）
③調理評価（フィールド上に揃っていない食材を調理する評価）
優先度は①＞②＞③で、①が同じなら②で比較、②も同じなら③で比較、といった感じです。
具体的な計算手順
(1) 客の並び替え
まず３人の客に優先順位をつけます。
① フィールド上に注文の料理が全て揃っている客を優先する
② ①が同じ場合は、Awardの高い客を優先する
優先順位の高い客から順に料理を提供していくことを考えます。
(2) プレイヤーを客に割り当て（回収評価）
(1)で並び替えた客のうち、フィールド上に注文の料理が全て揃っている客について、２人のプレイヤーのうちどちらがその客の注文を先に完成させられそうか評価します。評価が良い方のプレイヤーをその客の担当として採用し、評価が悪いほうのプレイヤーは次の客にまわします。このとき、客の担当になったプレイヤーがその客に使った料理は以降の評価から除外します。
これによって、自分が揃えたほうが良い注文は自分がやり、味方が揃えたほうが良い注文は味方に任せる（あるいは味方に協力する）という動きをするようになりました。
客の注文に対するプレイヤーの評価は、良い状態から順に
①注文が完成した皿を持っていたらWindowに近いほうが良い
②注文の料理が皿にたくさん乗っている方が良い
③皿を持っている方が良い
④皿を持っていたら、必要な料理への距離が近いほうが良い
⑤料理を持っていたら、皿に近いほうがよい
⑥何も持っていなければ、必要な料理か皿への距離が近いほうが良い
という基準で評価しました。（このへんコードが複雑になってしまったので、書いてることと少し違ってるかも）
(3) 余ったプレイヤーは余った客の料理を調理する（調理評価）
(2)でどの客にも割り当てられなかったプレイヤーは、残った客の料理を調理します。
①注文の料理が皿に多く乗っているほど良い
②注文の料理がフィールド上に多く揃っているほど良い
③各料理の調理工程（切る、混ぜる、焼く）が進んでいるほうが良い
④調理工程に必要なアイテム（オーブン、まな板など）への距離が近いほうが良い
⑤未調理の食材への距離が近いほうが良い
調理評価はあくまで回収評価が等しい時の比較に使用するだけなので、味方の回収評価を改善できるならば自分の調理をほっぽりだして味方を補助します。
ただ、これに関してはリプレイを見てて『ちょっとやりすぎかな？』って思う場面もありました（切った生地を机に放置して味方にアイスを届けに行ったりとか）。『自分の工程をどのぐらい犠牲にして、味方の工程をどれぐらい短縮できるか』を考慮するなど、改善の余地があったようにも思います。
５．その他やったこと
・距離[自分の位置][味方の位置][目的位置]を１ターン目にあらかじめ計算しておけば、各マス間の距離は毎ターン計算しなくても良い
・『オーブンに全力で向かったときに中のアイテムが焦げる前に取れるか』はシミュレーションしなくてもO(1)で計算可能。焼け焦げが確定になった時点で評価値にペナルティを入れた
・オーブンに入ってるものが生タルトや生地の場合、オーブンへの距離は考慮しないようにした。そしたら焼いてる途中も他の調理を進めるようになった
感想
『２人を同等に扱って評価値を計算する』というのが実装できたのが最終日の午前２時ごろで、ぎりぎり滑り込みセーフって感じで危なかった。
味方と協力するというゲームが分からなさすぎて途中３日ぐらい迷走していたのが良くなかった（そういえばCode of Kutuluのときも迷走してたし俺って仲間と協力できないタイプの人間なのか？）
最終的にはなんとかなってよかった。
