SamurAI Coding 2020-21 参加記 - ヴァルの開発記

f:id:ValGrowth:20210319151122p:plain — 画像引用元：SamurAI Dig Here 2020 ゲームルール

第９回情報処理学会国際人工知能プログラミングコンテスト [ SamurAI Coding 2020-21 ]に参加しました。

コンテストの内容が昨年と似ているため、本記事では昨年の内容から変わった点のみを記載します。本記事を読む前に昨年の記事を読むことを推奨します。

結果

３位／２２チーム

昨年からのルール変更点

ルール変更内容

・侍が１ターン立ち止まることで、次のターンに斜め移動を出来るようになりました。侍の斜め移動と犬の斜め移動が交差する場合、犬の移動をキャンセルして侍だけが移動できます。

・無効なプレイプランを利用した侍と犬の情報伝達が出来なくなりました。

それ以外は去年と同じです。

ルール変更に対する所感

侍がやや強くなっています。それにより犬で侍の移動を妨害する戦略がやや弱体化されはしましたが、それでも依然として強い印象です。犬の行動をキャンセルして侍だけが移動できるのは移動が交差したときのみであり、移動先が同じ場所になった場合は両方移動キャンセルになるので、特に侍が有利というわけでもない感じです。

昨年からのプログラム変更

１．侍の斜め移動に対応

侍の斜め移動が追加されたことで、評価関数で埋蔵金回収経路を計算するときの移動経路パターンが大きく増えました。それにより去年のやり方（幅優先探索＋雑な枝刈り）では計算時間が爆発したり、充分な探索の深さが出なくなったりして安定しませんでした。

今年はこの部分をChokudaiSearchに書き直して、安定した時間で評価値を計算できるようにしました。未知の地面を掘っていくときの経路計算も同様です。

２．犬に妨害されても諦めないように評価関数を調整

去年は犬が侍を完封することができましたが、今年は斜め移動が使えるようになり完封は出来なくなりました。犬は現在地と移動先の２マスをブロック出来ますが、それ以外の方向へは侍の移動を許してしまいます。

例えば、自犬が敵侍の上から敵侍の右へ移動するとき、去年なら敵侍は左か下へしか移動出来ませんでした。しかし今年のルールでは、侍の斜め移動が優先されるため敵侍は右上へ移動できます。敵侍が右上へ移動するのを防ぐためには、自犬は敵侍の上から敵侍の右上へ移動しなければいけませんが、そうすると敵侍が左上や右へ移動するのを許すことになります。侍が去年よりかなり移動しやすくなっていることがわかります。

これをふまえて評価関数を調整しました。去年は敵犬が近くにいるときは埋蔵金を取りに行くのを完全に諦めるようにしていましたが、今年は諦めずに埋蔵金を掘りに行くようにしました。

ただし、マップ上に既知の埋蔵金が１つしかなくて敵犬が先に到達出来る場合は諦めるようにしました。敵犬がその上に乗ると永遠に掘れないためです。