第34回高専プロコン 参加記
2023/10/14~15に開催された高専プロコン競技の参加記です
目次
開発環境
OS: Windows10,11, WSL
使用言語: C++(mingw,gcc, OpenSiv3D)、JavaScript(Nodejsで簡単な対戦サーバを作成)
使用ライブラリ: OpenSiv3D
開発期間: 4~8月でゆっくりいろいろ試して、9月後半から本格的に開発を始める
競技ルール
募集要項(https://www.procon.gr.jp/wp-content/uploads//2023/04/4d890277c1072170185a2709f89342d4.pdf)に概要が書かれてます
1対1の対戦で、職人がそれぞれ何人かいて、移動や壁の建築などを繰り返して壁で領域を囲んでいく感じの問題です
領域内にある城の数と、領域の大きさ、建てた壁の数でなるべく敵チームとのスコア差を大きくするように対戦をする感じです
敵の城壁を解体したりして、領域ができないように妨害したり、領域を奪ったりすることもできます
最終的な解法
人間側が建てたい壁の場所を伝えるビジュアライザと、それを入力として味方の職人の行動を決定するソルバーを作成しました
ソルバーのアルゴリズム
ソルバーは建てる壁の座標が複数与えられるので、その情報から、職人を動かしてなるべく最小ターン数ですべて建築をしてください。
といった問題を解きます
複数人の巡回セールスマン問題み(TSP)たいな感じです
移動にかかる距離(コスト)は、何もない場所へ移動を1、敵の壁がある場所へ移動を2(破壊の行動が含まれるため)として、最短経路を求めました
初めに、貪欲法で職人が建築を担当する壁を決めます。 貪欲法では、選択された壁それぞれについて、最も距離が近い職人にその壁の建築を担当してもらいます
その後、各職人が担当する壁でTSPを解き、担当する壁をすべて建築する順番のうち、最短となるものを求めす
その後、焼きなまし法を使って、職人全体の移動・建築コストを下げていきます
(これは上の問題を解く良い解法が特に思いつかなかくて焼きなましを使ったので、もっと正確に求められる解法はあると思います)
先ほど貪欲的に決めた職人が担当する壁とその順番を入れ替えたり、担当する壁を変えたりする近傍を探すことでより良い建て方はないか探します
評価値は各職人が担当する壁をすべて建てるまでにかかる最大ターン数としています
評価値の計算は以下の動的計画法を用いて毎計算 で処理をしました:
:
個目までの壁を建て終えて、現在
の方向に職人がいるときの最小コスト
差分だけスコアの更新をすることで、指定された城壁が30個くらいだと、ほどの処理をすることができました
これだけだと、各職人について行動を求めているだけなので、たまに職人同士で衝突してしまうときがあります。 その場合は焼きなましで解を求めた後に、動けない職人のうちどちらかを行動るようにしました
また、大会当日に、壁を建てない職人が出てきて(与えられた建設予定の場所が少ないや、遠すぎるなどが原因)、何も行動しない職人がいた場合は、とりあえず4方向に壁を建てる行動をするようにしました
この解法にする前に考えてたこと
7月くらいまでは、職人全体の行動を探索するようなmctsやαβ法などを実装して城壁を建ててくれるか試したりしましたが、思うように動いてくれない&&パターンが多すぎて探索ができないといったことがあり、この解法はあきらめました(城壁を建てる場所を探索すれば良くなったかもしれない)
あとは、職人1人の行動をあらかじめ探索して、探索した行動の中から一つ決めて全体の盤面の評価値を上げていく焼きなまし法を使った実装も思いついて試してみましたが、これもうまくいきませんでした
自分が実装できそうな方法は何かないかなと思っていたところ、いい感じの場所に城壁を建ててくれないなら、指定した場所に城壁を建てるようにするのはできるかもしれないと考え、上で紹介した最終的な解法を実装しました
ビジュアライザの機能
今回作成したビジュアライザはこんな感じです:
大会で使用した主な機能としては、
建てたい城壁を指定する
- クリックやカーソルで城壁を建てたいマスをクリック
ターン数や得点、得点の差などの情報の表示
職人や壁、池、領域、城などがすべて識別できるような盤面の表示
- 職人は円、壁や池は四角、領域は背景の色を変え、城は星型になっている
行動していない職人の表示
- 何も行動しないターンがあった職人はその時に表示されている番号が薄くなる
初めの対戦データの取得や、データの送受信
- ターンの更新情報の取得は0.1秒に1回サーバーへ問い合わせて変更を検知
- OpenSiv3Dのライブラリを使ってすべて実装
ソルバーへの職人の行動や壁のデータの送信と、ソルバーからの職人の行動の受信
- ChildProcessでソルバーのプログラムをはじめに呼び出し、標準入出力を使って職人の行動データをやり取りする
といったものがあります
自分が初めに想像していた量の2倍以上あり、さらに通信プログラムで大会近くまでバグを修正していたりなどいろいろと大変でした
バグ探し
大会2,3日前くらいにソルバーとのデータのやり取りができていないことがありました
必死になって探した結果、原因はPOSTリクエストが正常に送信できておらず、同期がとれなくなっていることがわかりました
送信する時間を制限時間の700[ms]前ほどにするとこの時は正常に動作しました
今年の大会の目標とか 大会までの話
今回の大会の目標は、ファイナルステージ進出して1回勝つ、ほどでした(解法に自信がないということや、チーム内で対戦練習がほとんどできていなかったりしたので)
今年は上位に行くよりも、福井と高専プロコンを楽しもうという感じで出場しようと思っていました
大会の話
大会情報
実際の試合はここから見れます
1日目(ファーストステージ、セカンドステージ)
2日目(敗者復活戦、ファイナルステージ)
対戦履歴
大会前日
ビジュアライザの壁の指定をやりやすくする(指定したマスの4方向を建設予定にする)
ソルバーは敵の城壁の破壊をしないバグを修正したりする
1日目
予行練習
正常に動いてるかどうかで戦略AI(敗者復活戦で戦う戦略AIとは別)との対戦をする
めっちゃ強いかと思ったけど、いざ対戦してみると戦略AIはランダムに動いてるっぽかった(敗者復活戦で使われた戦略AIは普通に強かった)
ひとまず正常に通信ができて、ソルバーが止まらずに動いてることに一安心
ファーストステージ
始めはグループ内での対戦をしました
第一試合は、新モンゴル高専と対戦しました
試合開始後、数ターンほど相手が行動しなかったため、通信かプログラムがうまくいっていないのかなと思い、始めは攻めるだけ攻めました
先行後攻が反転した後は、大きく逆転されないように守りにてっして、勝つことができました
結果はぼろ負けでした...
全体的な戦略がほとんど決まっていないまま対戦したのですぐに陣地が取られてしまいました
対戦チームは横一列に並んで対戦をするのですが、隣から声が聞こえてくると、その数ターン後に大きめの陣地が取られてしまい、これは負けるなと思ってました
ファーストステージで2位だったため、セカンドステージに出場します
セカンドステージ
セカンドステージは米子高専との対戦でした
試合が始まるまでに、この対戦で使用される盤面を事前に見ておき、戦略を3人で考えました
第1対戦では、職人の初期配置が外側だったので、外側に入らないように城壁を建てたあと、周りの城壁を囲みつつ相手の様子をうかがうという感じでいきました
相手が最初の数ターンうまく動いていなかったので、近くの城壁を囲んだ後、中心に入り、相手に陣地が取られないようにしました
第2対戦では、内側の城壁を先に囲み、その後内側に入られないように城壁を建てるという戦略で行きました
セカンドステージは勝つことができ、ファイナルステージに出場できました
1日目夜
ビジュアライザに城壁を立てる命令を送り切れておらず、何も行動しない職人が発生していたため、何もしない職人は周りで建築or解体がないか調べて行動するという処理を追加し、職人が動かないことがないようにしてみました
実装自体は2日目のファイナルステージ前くらいに終わりました
ごはんを食べたらちょうど9時だったので、ABCに参加しました
2日目
ファイナルステージに進出しているチームはちゃんと戦っていたので、勝てるか少し不安でした
次の試合の競技フィールドと対戦相手の戦略をだけをできるだけ読み取ってそれぞれの試合をしていきます
ファイナルステージ第1試合
ファイナルステージ第1試合は鳥羽高専と試合をしました
相手はファーストステージでは城の周りから少しずつ領域を作っていく感じだったので、自陣への侵入を防ぎつつ、自陣内で領域を確保して得点を稼ぐという戦略を立てました
第1対戦は相手があまり行動できていなかったので、戦略を変更し、相手の陣地へ入り大きめに領域をとる方針にしました
プログラムもうまく動いてくれたおかげでかなりの点差で1試合目は勝つことができました
第2対戦では、試合の途中でソルバーでエラーが出て止まってしまいました...
原因は前日から追加で実装していたところのバグが原因です
ソルバーの仕様上、初期状態しか盤面の同期をしないため、半ば無理やりビジュアライザをもう一度起動させます
職人の位置や盤面がずれまくってるのでとにかく何か行動してくれと願って、大量に壁を指定しまくりました
試合後のビジュアライザはこんな感じになってます:
相手もうまく動いていなかったのと、第1対戦で大きく点差をつけることができたのがあり、勝つことができました
ファイナルステージ第2試合
第2試合は松江高専と試合をしました
相手は市松模様をベースに陣地を少し大きめに確保している感じだったので、先に内側の城を取りに行く戦略を立てました
第1対戦は、初めに中心に集中しすぎて上のほうで大きめの領域を取られてしまいました...
その後もずっと優位に立たれていたので、何とか取り返そうと陣地を大きく囲める場所を頑張って探してました
105ターンあたりで真ん中の城を囲んだ領域を囲めそうなのに気づいたので城壁の場所を指定します
116ターン目で大きく陣地を取り返すことができ、何とか逆転できました(スコア遷移を見ると一気に逆転しているのがわかります)
第2対戦は、戦略を少し変えて、大きめの陣地を取られないように、敵の動きを妨害するように試合をしてみました
上のほうでは領域を作られるのを事前に防ぎ、ほかの職人が建築/解体を繰り返す状態に持ち込んだり城を囲んだりしながら耐えてました
取り返した城の周りからちょうど陣地を作れそうなところがあり、城壁を建てるよう指定し、117ターン目で何とか逆転し、最終的に勝つことができました
この試合は対戦が終わるまで勝てるかわからず、ずっと緊張と不安がありました
スコアを見ると途中まで接戦でした
(去年の悔しい思いを払拭できた気もします)
ファイナルステージ準々決勝(第3試合)
準々決勝は香港VTCと試合をしました
過去の対戦を見ると、外側の領域を取りに行く感じがしたので、相手の行動を妨害していく戦略を立てました
第1対戦は、中心からスタートだったので真ん中の城を取った後、入れないように周りを塞いでから内側から陣地を少しずつ取りつつ、相手の職人の妨害をしました
第2対戦は、外側の城を囲みつつ、領域がとられないように相手の職人の妨害をしました
相手が次に何をしようとしているのか考えながら指示を与えていたので、めちゃくちゃ頭が疲れました
これも何とか勝つことができました
ファイナルステージ準決勝(第4試合)
準決勝(第4試合)は福井高専と試合をしました
1,2対戦とも、あと少しで領域が囲めそうという場面がいくつかあったのですが、どうやって囲めばいいのかわからず、点差が開いたまま終わりました
試合前に戦略を考えていたのですが、ここまで進めるとは思っておらず、あまり対策してきていないのでなかなか思うようにいきませんでした
福井強い...
ファイナルステージ3位決定戦
準決勝の試合で、大きい盤面の場合は城をたくさん囲みに行くのが良いということが分かったので、なるべく城を囲みつつ、相手に領域を作らせないといった戦略にしました
第1対戦では、内側に職人がいたので、内側の城を優先的に建てていきました
なるべく相手の妨害をしつつ城を取っていこうとしたのですが、職人が同じ個所に集まったり、意図した場所に移動しなかったりなどがあり、陣地が少し多めに取られてしまいました
スコア差は120点とかなり抑えたほうかなと思います
第2対戦は、第1対戦の相手の行動を少しまねしつつ、城を取りに行きました
初めは城をどんどん建てていき有利な状況だったのですが、途中で城と領域を取られてしまい、その後逆転されてしまいました
このまま、また4位かなと思っていたのですが、199ターン目で左上の職人が敵の城壁を解体して逆転したそうです(スコア遷移を見るとすごいことになってます)
自分でも盤面を把握しきれておらず、どういう状況なのかあまり理解してませんでした
2試合目で270点差をつけ、合計で150点差でギリギリ勝てました
最終結果は全体で3位でした！
去年悔しい思いで4位だったので、1つ順位を上げることができて嬉しいです
改善できそうなこと
個人的にほかの高専の戦略などを見て改善できそうだと思ったことは、
ビジュアライザに味方/敵だけの城壁などの状態を表示する機能をつける
近くに相手の職人がいないときは陣地がたくさん取れるような行動をするようにする
現在指定されている建設予定の城壁を建てるのにかかるコストの概算を高速に計算して表示する
特定の職人を指定した場所に強制的に移動する
です
メインで開発していた期間がかなり短かったのと、案が思いつかなかったというのもあり、ここまで取り掛かれなかったです
感想
去年より良い順位を出せて、去年目標にしてた3位は達成できました(去年は4位だった)
今年の目標はファイナルステージ進出程度だったので、思った以上に進めることができてめっちゃ嬉しいです
来年も出れたら出たいけど、後輩への競技部門の引き継ぎを優先しようかなと思ってます
