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日前くらいにこれ書いた方がいいかも。
  • 評価関数の数字の大小関係の調整が超シビアだったので、予め理論的に評価関数を設計すべきだったかも。
  • 取れる行動の種類は多くても、シチュエーションの数は数えれる程なので(ホントか?)もっとヒューリスティックに寄せても良かったかも。
  • 何か見ながら作業するのはやめた方が良い(さく ゆい かわいい)