高専プロコン第34回 参加記

競技部門での参加です。優勝しました！

exeはここにあります

github.com

簡単なルール

・壁を建てて囲むと中が陣地になって点数があがる。城を陣地にすると更に点数があがる。

・エージェント一人が1手で動けるパターン数は大体16パターン

・最大で25*25盤面の6人エージェント

 

最初に考えたこと

普通に全探索すると2手が限界、しかも陣地を毎ターン更新する必要がある。
明らかに全探索は無理

->職人一人ずつ独立に探索してみる

大きく囲むのは不可能+連携ができない 人がプレイしたほうが強い

 

次に考えたこと

探索中毎ターン陣地更新して評価は無駄

あらかじめ建築、破壊したほうが良い場所(以下目標とする)を決めてから独立に探索させる。
->目標決めるのめちゃくちゃ難しい。ヒューリスティックな観点を利用して4マスまで壁を補完して大きく囲むのには成功、ただし敵の妨害を反映させるのが難しい(例:敵が建築に専念してたなら妨害はあまり考えなくてよいなど) 補完を敵目線でおこなえば破壊目標も決めることが出来る

しかもこの処理2秒ちょいかかる 遅すぎ
->これ人力の方が精度良いのでは？ A.良かった しかも敵の動きを反映させやすい

 

完全AIか人力を混ぜるか悩んでいたところで発見してしまう

めちゃくちゃ似たルールで人力混ぜたチームが優勝してるじゃん！！！

 

最終的な基本方針

1.人力で建築と破壊箇所を決定

2.Dijkstra法+決定順序を順列全探索で連携力を高め行動を決定


ビームサーチしないのはなぜ？<-人間が動きを予測しやすくするため+連携をビムサには組み込みづらい+探索に時間がかかった+なんかPOST失敗する(マジでなんでだ)

この方法なら最大でも300msくらいでかなり速い(実際は最短の目標を見つけた段階でDijkstraを打ち切るのでもっと短い(50msくらい？))

 

アルゴリズムの説明

今回のゲームは最短経路を考える過程で敵の壁破壊が最短経路上に存在することがある。そのため、BFSでは最短経路を求められない。

縦横の近傍を探索する時、cost(壁を破壊+そのマスへの移動)=1.875としてDijkstraを適用することで到達済み配列を汚染せず最短経路が求まる。(2未満にすると優先的に壁を壊しながら移動するので)

ある職人で最短となった目標は、以降に決定する職人の目標にならないよう、目標のリストから削除する。

順列全探索の役目

行動の競合を減らします。

例:以下のような時に職人1,2の順番で行動を決定すると1が右のマスに建築し、ターン全体で壁が一つしか建築されない無駄が生じることがあります。(+マークは建築したいマス)

この時、順列全探索で1,2と2,1のそれぞれの順序でdijkstraを行い、評価値のmaxを取れば必ず壁が2つ建築されるはずです。

ちなみに城周りで千日手が起きているときや混戦のときにめちゃくちゃ効果を発揮します。

順列全探索中の評価関数は以下です これを最大化します

目標の達成数*100-Σ(最短目標への距離)-(行動無しの職人数)*10000

 

GUIを凝る

上の内容ですが夏休み前にはほぼ出来ていた(パンフの方針からDijkstraを復元に切り替えただけ)のでテストサーバが出てからはひたすらGUIいじってました。人力を混ぜるのにも限界があるので何をやるのかは人が決めて、出来るだけ自動化させました。

 

城の周りを自動で目標に追加する機能

敵、味方片方の情報だけ表示する機能

破壊すると自陣になる壁を目標に追加する機能(GG)

網目状に目標を追加して陣地ポイントを雑に稼ぐ機能

1ターンで敵壁を味方壁に直接塗り替えるための機能

職人の移動先を強制的に決める機能(妨害の時めちゃくちゃ役に立った)

たぶんこれで全部です。

gui

 

なんで勝ったんですか？

人力を上手く組み込めた<-100%のAIを使っていたチームには申し訳なく感じますが間違いなく一番優勝に寄与した部分でした。ただ、今年は人力が勝敗の全てを分けたわけでもないので割といいバランスだったと思います。もし意見が通るなら10試合並列とかやってほとんど人力を出来なくしてほしい(戦略の切り替えくらいは人ができるくらい)と思いました。

 

競プロをやっていた<-DijkstraもDFSもDSUも順列全探索も競プロをやってなければ知りませんでした。あと計算量を見積もるスキルで無駄な実装を避けることが出来ました。

 

OpenSiv3Dの採用<-GUIをC++で作るならまじでこれ一択なんじゃないだろうか おすすめです。通信とかファイル操作とかのC++だとめんどくさい部分が簡単に出来るようになってます。

 

チーム内でめちゃくちゃ模擬戦した<-GUIの機能の提案+定石の考察

 

並行試合が結局なかった<-1対戦につき1人で練習していたがまさかの並行試合無し。もともとそれなりに自動で戦えるものを作ったため残り2人に暇が出来てしまい試合中は触らなくても動くのにGUI触りまくってました。 なんで？

 

千日手を作ると圧倒的有利<-人力を組み込むと千日手が起きた時カバーに行かせることが可能でした。僕らのチームの城取得数が多いのは多分これが要因

 

追記

大きく囲むための目標の決め方が難しいという話を書きましたが、大会後に別の手法を思いつきました

 

いい感じの点Aをなんらかの評価関数で決め、そこからすべてのマスに対して

(Aからの距離,敵からの最短距離,味方からの最短距離、敵壁の個数,付近の城の個数) を加味した0~1を出力する関数fを考え、

A点からfを使用して確率的にBFSを行い、BFSの終了時点で

(BFSの端にすでに存在する味方壁の個数,BFSが広がった面積)でその広がり(=囲み方)を評価し、

時間が許す限り、このシミュレーションを繰り返し、いい感じの囲み方を見つける
というのを思いつきました 実装してないのでなんとも言えませんが割と良さそうじゃないですか？