問題
久々の参加
方針
- 拠点と資源（クリスタル・卵）を頂点として最小全域木を作る
- 木の上にビーコンを配置し、ビーコンの強さを焼きなましで決定
- どの資源を狙うかについてはターン毎にルールベースによって決定する
最小全域木の作成
資源を効率よく回収するために拠点と資源を頂点とした最小全域木を作成しました。
各頂点間のコスト計算時に「資源マスを通るようにする」「アリのいるマスを優先的に使用する」となるように距離以外のコストを含めた経路探索になっています。
例) 拠点とクリスタル資源を頂点とした最小全域木を作った場合
ビーコンの配置 & 強さの決定
先程作成した木の上にビーコンを配置し初期の強さを 10に設定します。そのあとに木の上のタイルをランダムに選びそのタイルのビーコンの強さをランダムに変化させ、その後アリの動きをシミュレートしアリの配置の評価を行います。
基本的な評価基準としては「目的の資源をどれだけ集められたか」をベースにその他諸々を評価します。
ターン毎に狙う資源を決定
アリの数が多ければ多いほどゲームを有利に進められるようになるので序盤は基本的には卵を優先して取得するようにします。 アリの数がある程度確保出来たらクリスタルを回収します。優先度としては敵陣と自陣の中間にある資源を優先的に獲得するようにしています。
今回のゲームの勝利条件では以下のようになっています
- 初期のクリスタル総数の半分以上を集める
- 100ターン経過後に相手より多くのクリスタルを所持する
そのため、クリスタルの位置を「相手陣側」「自陣側」「中立地点」と分けた場合
- 相手陣側のクリスタルを 1個以上取る （中間地点が存在しない場合）
- 中立地点のクリスタルの過半数を取得
自陣のクリスタルをすべて集めた上でどちらかの条件を満たせば負けはなくなるので基本的に中間地点に近い資源の優先度が高くなります。 また、相手陣から遠い資源についてはそもそも chain attack の仕様上集めるのが非常に困難なのでほっといても特に問題になりません。
これらの条件を考えつつ毎ターンごとに狙う資源をルールベースによって決定していました。
感想
とにかく卵とクリスタルの回収タイミングがゲームの盤面ごとに異なってその判断がうまく評価値に落とせないままコンテストが終了しました。早く取りすぎるとあとから相手に奪われたり、遅すぎると相手に回収されてしまったりと、毎回異なる盤面ごとに難しい判断が要求されました。こういった評価が難しいケースは強化学習とか強いイメージあるんですけどどうなんですかね。
