Marathon Match 129 ChickenRun
問題
方針
- 農家を 2人 1グループにまとめる。奇数の場合は 1つだけ3人のグループになる。
- 農家を移動させる
- 移動後の盤面を評価して一番良い配置を決定する
農家のグループ分け
鶏の確保には最低でも 2人必要なので 2人組のグループを作成します。（1人でも確保出来るパターンは存在しますがそんなに多くありません）
奇数の場合は 1つだけ 3人のグループが出来ます。 各グループごとに追いかける鶏を決定し、その鶏を追いかけるようにします。
農家の移動
農家の移動ですが、各農家の移動先の候補は 上, 下, 右, 左, 待機 の 5つの候補が存在しており、各農家の移動の組み合わせを試そうとした場合 5 ** 農家の人数 のパターンが発生します。この膨大なパターンの中から最適な配置を見つけるために農家の移動方向を配列としてその移動方向を焼き鈍すことで最適な配置を求めました。
遷移は任意の1箇所を選んで方向を変更するです
これで農家が増えてもある程度有効なパターンを探索しやすくなります。
盤面の評価
盤面の評価は以下の項目を中心に確認を行いました。
- 鶏の確保
- 鶏が確保できるパターンかどうかの確認
- 捕獲対象の鶏に接近できているかどうか
- 捕獲対象の鶏の移動可能範囲を狭めているかどうか
鶏の確保に繋がる可能性が高いほどより高い評価になるようにしています。
鶏の確保
鶏と同じマスに到達した場合はスコアが増えるので評価としては一番高いです。場合によってはあえて捕まえないほうが良くなる場合もありますが、そこまで評価出来ませんでした。
捕まえないほうが良くなるケース
二羽同時に捕まえられるようにするのがここでは最適解となります。
確保できるパターン
鶏が確保できる状態というのは 鶏が移動不可 + 鶏の隣接マスに農家が存在する ことを指します。各鶏についてこの状態になっているかどうかを調べ、そのパターンに一致した場合は評価を高くします。主なパターンとしては以下のようなものがあります。
確定パターンへの誘導
確保出来るパターンについては事前の状態として 鶏の移動候補が 1つ + 移動先に柵または農家が存在している という状態になっているので、この状態についても評価を行います。
確率で確保出来るパターン
鶏の行動は行動する順番も方向もランダムに決定されるので、鶏の移動順や移動方向によっては確定パターンにつながる可能性があります。それらのパターンについても評価を行います。
鶏の移動順によっては確保が可能になるパターン。
鶏の移動先によっては確保が可能になるパターン。
対象の鶏に接近する
対象の鶏に対して接近します。接近する際には対象の鶏より先に到達出来るマスの数を多くするように移動します。（鶏のボロノイ領域が小さくなるように移動する）
まとめ
鶏を確保するための評価関数の中身が複雑になって意図しない挙動も出てしまったので評価関数の設計で失敗してしまった感じ。農家の移動に関しては全体をまとめてやるより特定の領域とかで絞ったほうがもっと効率的に配置を調べられた気もするけど実装する時間がなかったので諦めた。鶏の移動についてランダム性が高いのでちょっと後回しにしてたけど、もうちょっと細かく調査して評価に組み込めば良かったなと思う。
