全国高等専門学校第21回プログラミングコンテストに参加
16日、17日の2日間にわたって行われた全国高等専門学校第21回プログラミングコンテストの競技部門に参加してきました。
うちの高専は準決勝でかなり悔しい負け方をしてしまいました。そんな結果だったので閉会式をスルーしてとっとと帰ってしまったのですが、どうやら特別賞をいただけたようで、ちょっと惜しいことをしてしまったなぁという感じです。
というわけで、今回作成したプログラムのソースコードを置いておきます。直前でかなりいじっていて見せられた物ではないので、簡単に戦略も書いておきます。 MizuGame-semi-final.zip
戦略
私ひとりの強いこだわりで、すべて自動で処理するようになっています。人間と連携した方がうまくいく場面があるというのは理解できますし、実際に結果もそうなったわけですが。
経路探索
A*アルゴリズムを用いた経路探索をさまざまな場面で活用しています。地形による影響はもちろん、相手チームが所有するセルからの吸い取り動作についてもコストとして扱うようにしています。
重要拠点
その場所に配水すれば大きなエリアを作ることができる点を重要拠点とし、マップ上の重要拠点への対応をそれぞれ一番近くにいるロボットに担当させています。
重要拠点の算出方法は、自分が配水したセルを始点として何方向かに対して直線を伸ばし、始点と繋がっている自分が配水したセルに到達できた場合はエリアを作ることができると判断できます。エリアを作れることが分かった場合、どれだけ得点が増加するか計算し、それを重要度としています。
行動決定
各ロボットはチャージと配水の2つの状態間を遷移しながら動作しています。また、各ロボットが連動して動作するような処理は組み込まれておらず、それぞれが独立して判断を行います。ただ、重要拠点をあらかじめ各ロボットに振り分けておくことで、干渉を防ぐとともに連携しているような動きを実現しています。
チャージの動作
- 現在位置がチャージ可能でない場合、近くにあるチャージ可能なセルへ移動する
- ロボットの積載している水量が一定値に達するまでチャージする
- 配水状態へ移行する
配水の動作
- ロボットの積載している水量が一定値を下回った場合、チャージ状態へ移行する
- ロボットの積載している水量が最も近いチャージ可能セルへの距離以下になった場合、配水しつつチャージ可能セルへ移動し、チャージ状態へ移行する
- 担当しているすべての重要拠点について
- 「そのセルに配水することで得られるエリアの大きさ / ロボットから重要拠点までの距離」を計算し、最大値を求める
- 最大値が1を超える場合、最大値を取るセルへ移動し、配水を行った後、配水状態へ移行する
- 前方のある程度離れたセルへの経路探索を行う
- 「そのセルまでの直線距離 / そのセルまでの総移動コスト」を計算し、最小値を求める
- 最小値を取る方向の経路に沿って配水しつつ移動し、配水状態へ移行する
サーバ部分だけは対戦練習に使えるかもしれないので触れておきます。
MizuGameServer --port=ポート番号 --tokens=トークン定義ファイル マップ定義ファイルトークン定義ファイルには、各チームのトークンを改行区切りで記述しておきます。マップ定義ファイルはsystem/map で返ってくるフォーマットのXMLです。
感想
過去3年間まったく賞とは無縁だったので、特別賞をいただけてとてもうれしかったです。ただ、他の学校がチームで協力してプログラムを組み上げているのに対して、うちは私ひとりだけという状況は組織としてかなりまずいのではないかと感じました。実際には去年あたりからそのように感じてはじめて、なんとか後輩にも少しずつプログラムを書いてもらおうと考えたのですが、結局私の力不足でそこまでの余裕を持たせて開発を行うことができませんでした。私が入部する前からそんな状態だったので、すぐに改善できるものではないのかもしれませんが、悩ましい問題です。
あと、Twitterで応援してくださる方がいらっしゃったのがとても印象的でした。学校内ではほとんど注目されていないので、余計にうれしかったです。