2019/3に開かれたCodingameのコンテストに参加しました。
色々あって目標だった20位以内に入れなかったので、反省も込めて参戦記を書きます。
ちなみに今回のコンテストで数万円を無駄にしてしまったので、課金額で言ったら1位なんじゃないかと思ってます。
ゲーム概要
キッチンにある食材を調理して、料理を作って客に出すゲームです。
現在でもこのゲームで遊べるので、ルール詳細が気になる方は↓から見れます。
https://www.codingame.com/ide/puzzle/code-a-la-mode
このゲームの難しい所は、自分が作ったものではないAIと二人同時にプレイする所です。
当然相手と協力した方が良い点数を取れるのですが、メッセージを送るなど相手と直接コミュニケーションを取ることは出来ません。
なので空気を読んで相手と協力する必要があります。
立てた方針
このゲームでは、食材の準備や食材の提供に何個かの手順を踏む必要があります。
そこで現在達成したい小目標を設定し、それを達成するためにルールベースのAIを書きました。
どの小目標を選択するかは、
{小目標の達成価値} / {小目標の達成に必要なターン数}
を評価値として最も高いものを毎回選択する方針としました。
小目標の達成価値は、盤面の特定のパラメータ(例えばオーダーにあるタルトの数など)に重みをかけて算出します。
このパラメータは探索が難しいので、初期値は直感で設定して、遺伝的アルゴリズムを用いた自己対戦で探索することにしました。後から思うとこれが失敗だった...
小目標の設定
以下のような小目標を設定しました。
- 料理の素材を準備する
- イチゴを刻む
- クロワッサンを焼く
- タルトを焼く
- オーブンに入っているものを取り出す
- 料理1,2,3を作る
- 皿や素材を取りやすいように配る
- 皿、イチゴ、ブルーベリー、アイス、生地
それぞれの動作はルールベースで書いています。
ルールベースの部分には細かい工夫を多数盛り込んでます。
例: 料理を作る部分は一番早い順を幅優先探索で求める、素材を机に置く際は中央のテーブルに置くようにする
小目標の評価値の算出式はそれぞれ別に設定しました。
例: イチゴを刻む評価値 = 定数値 + オーダーに含まれるイチゴの数 * 重み1 + すでにキッチンにあるイチゴの数 * 重み2
最初は重みを直感で設定して実装していました。
今思うと重みを直感で実装していた時が一番順位が高かった...
↓パラメータ探索に取り掛かる直前くらいの順位表
パラメータ探索
人間が直感で設定したパラメータで5位(一瞬2位まで行ったらしい)になっていたし、パラメータ探索すればもっと上にいけるじゃん！と取り掛かり始めは思っていましたが...
ひとまずGithubで公開されているゲームシステムのコードを持ってきて、ローカルで自己対戦できるよう改造しました。
pythonで簡単に自己対戦&結果集計をするプログラムを書き、1000試合ほどした後に結果を集計してスコアに従って次の世代のパラメータを作成を繰り返しました。
しばらく回しましたが...
全然自分が直感で設定したパラメータのAIを超えられない!!!
1日くらい探索すると、完全ランダムのパラメータからスタートして自分が設定したパラメータと同じくらいの強さにはなりましたが、大して変わらないスコアになってしまいます。
しかも自分のAIを超えるスコアを取る個体が現れたのに、次の世代ではいなくなってたりします...
結局パラメータ探索は成果が出せず、後半4日間くらいを完全にドブに捨ててしまったためズルズルと順位を下げてしまいました...
遺伝的アルゴリズムによるパラメータ探索がダメだった理由
ちゃんと検証は出来ていませんが、以下のような理由があったと考えられます。
- 1世代の試合数が少なく、運のブレで弱いパラメータが生き残ったりしてしまっていた
- 各AI1000試合こなすくらいの試合数は行ったのですが、まだ足りなかったのかもしれません。
- 各試合の乱数のシード値を固定していなかったため、配置による不公平が起きてしまう可能性も排除できていませんでした
- 1世代の個体数が少なすぎた
- 自己対戦を3人の総当たりでやっていたため、試合数が多くなりすぎないように1世代の個体数を10程度にしていたのですが、少なすぎたかもしれません。
- しかし増やすと試合数が多すぎて終わらないので、悩ましいところです...
- パラメータの数が少なすぎた(20~30ほど)
- この程度の数のパラメータだと、探索しても実現できる評価値の式の形はたかが知れています。より多様な動きをさせるために、より多くのパラメータを用いて評価を出すべきだったかも知れません。
- 直感による初期値が実は最適解だった
- この可能性もあります。
パラメータ探索させるなら、パラメータ次第で様々な行動を取れるように設計しておきたかったです。
強化学習とヒューリスティックのいいとこ取りをしようとして今回は爆死してしまいましたが、次回はもう少し強化学習寄りに方針を傾けて取り組んで見たいですね。
ぶっちゃけ今回は最後までヒューリスティックAIに時間を使えばTシャツ行けてたと思うので悔しい...
余談
今回自己対戦をするために、AWSで高いマシンを借りていたのですがなんとコンテスト終了後に切るのを忘れていました。
恐る恐る請求を見てみると...
なんて事だ...
皆さんもインスタンスの落とし忘れにはくれぐれも注意してくださいね！