#procon29 競技部門のおはなし

はじめに

第29回高専プロコンで取った戦術のはなしをします 戦術以外のはなしもします 参加記と混ぜたりすると怒られが発生しそうだったので、わけてかいています

対戦結果

対戦相手 得点 対戦結果
予行演習 茨城 おぼえてない… 負け
予選1試合目 モンゴル科学技術 81-73 勝ち
予選2試合目 有明 86-66 勝ち
予選3試合目 国際 93-90 勝ち
決勝トーナメント1回戦 徳山 141-117 勝ち
決勝トーナメント2回戦 北九州 168-155 勝ち
準々決勝 佐世保 280-275 勝ち
準決勝 福井 319-205 勝ち
決勝 仙台(名取) 190-469 負け

開発環境,操作環境

GitHubでプライベートリポジトリ作って8人のチームで開発しました。(実際たくさんコード書いた人は3人ぐらい)
基本的にはC++とQtを用いて開発、QRコードの読み取りにはZbarを使いました。 それ以外のライブラリは使ってないです
うちの部員にArch使いがたくさんいたので、環境をArchで統一していました いいね
本番では自分のThinkPad X270(いいぞ)に持ってきたwebキャメラを使って操作をしていました

アルゴリズムについて

†人間の力†なので当然人間の力を考慮したアルゴリズム設計をします。いくつかポイントがあって、それさえできていればだいたいどんな実装でもいける木が生えます。
ぼくたちの アルゴリズムの ポイントは
・相手の駒を考慮しないで実装する
・自分の2つの駒を独立に考える
・領域ポイントは無視する
です。これは北九州高専さんのパンフレット原稿にある内容とほとんど同じらしいです(ほぼ同じ方針の立て方をしていました)
この上で5手から10手分ぐらいの利得が最大になるように探索を行い、アルゴリズムに都合が悪い場面を人間でカバーします(要するに人力)

この辺りは競技プログラマ向けの話になってしまうのですが、ぼくたちの部門では探索に動的計画法(DP)を採用しました。(なくても普通に探索できます DPするとネタになっていいよね、以外の理由はないです)
dp[i][j][k]:i手先まで探索して(j,k)のマスに到着する時の最高利得 みたいに決めて、同じマスを踏まない所だけ気をつければなんかいい感じに計算ができます。
この方法だと経路復元とかいろいろの都合で絶対に最適な経路が出せるとは限らない(はず)なのですが、なんかだいたいいい感じに動いたので多分いい感じなんでしょう。

値の最適化のためにたくさんプレイアウトをしてデータを取って、重回帰分析やいい感じのグラフ化(?)、散布図目grep(!?)などを用いて調整をしました。
たぶん調整しなくても本番での結果はあまり変わらないです(本質ではない部分の改善に時間を取られすぎた)

ちなみにボツになったアルゴリズムやアイデアがたくさんあります。だいたい弱かったです。
モンテカルロ木探索、BeamSearch(これは普通によかった)、DFS(ギリギリ戦えるレベル)、両エージェント考慮のDP(これはまぁまぁ)、強化学習、敵の行動を予測した上でのナッシュ均衡を用いたほげ、領域考慮BeamSearchやDP、貪欲ベースに遺伝的アルゴリズムでパラメータ調整したやつ、†機械学習†でパラメータ調節するやつ(これは自分の実力不足な気がします)、焼きなましてパラメータ調べるやつ、ミニマックス法(方針が固まっていない段階のものなので弱い)、最後10ターン程度を想定した領域考慮探索(結局未完成、人力の方が強かった)、最後数手の全探索(これも人間で十分)…みたいなのを全部実装しました(えらいね)

ゲーム進行管理について

複数個のアルゴリズム同士で対戦をさせて強さをはかる、アルゴリズムと人間で戦わせて強さをはかる みたいな事は当然やらないといけないので、
・複数のアルゴリズム同士で試合をさせる事ができる
・人力で盤面入力ができる
・全部のエージェントの動きを与えるとシミュレーションしてくれる
辺りができるものを書かないといけません 書きます 書きました
あとはcsvでの盤面出力、バイナリでの盤面出力、QRコードでの読み取り(それはそう)とかも実装しました

設計

AlgorithmWrapperを継承してアルゴリズムを設計、GameManager内でアルゴリズムを呼び出して手を受け取ってシミュレーションしてFIeldの盤面を更新、更新した盤面をVisualizerに反映 みたいな設計でやりました。個人的にはかなりわかりやすい設計になっていると思っています(自画自賛)

ビジュアライザ

前述の通りVisualizerはQtで実装しています。競技内容の告知から1週間ぐらいで適当に書いた骨組みをベースに各種機能を追加していきました。
キー入力時やマウスクリック時にQtのconnectを使ってGameManager側に情報を伝達します 割と見た目がマシで操作性もよいのでかなりいいです UI担当ありがとう(だれ?)
エージェントクリック→タイルクリックで移動、タイルクリック→数字入力で盤面の変更、Rキーで移動先と得点の再計算、矢印キーで盤面の回転や反転 のような操作ができて、うれしいです
実は4人分のエージェントの入力が終了した時点で自動で行動が行われるモードを用意していて、予選第二試合が終わる辺りまではそのモードで動かしていました。しかしその方法は柔軟性に欠けている事が(予選の最初を通して)わかったので、他チームの試合中に急いでコードを書き直しました。

暗号について

暗号、伝わればなんでもいいしセキュアな方法を考えるのも無駄じゃないですか?ぼくはそうおもいます
そのためできる限り平易で分かりやすいものを考えて、それを使う事にしました。実は予行演習の時と比べると暗号の仕様がいろいろ変わっているのですが、ここでは最終版について説明する事にします。

まずは各エージェントごとにトランプを一枚ずつ割り当てます。赤と黒みたいに色分けされてるとうれしいです。
前後左右の4方向に対して指示をする際は、エージェントに対応するトランプの向きで指示をします。トランプが前を向いていたら(司令塔側からフィールドを見て)前方向への移動、右側にトランプの表面を向けていたら右に移動…みたいな感じです
斜め方向に指示をしたい時はまずトランプの向きを4方向で決めて(右前方なら右か前に表面が来るようにする)、その上でトランプを倒し、トランプの動かし方によって細かい方向の指示をします。(トランプを90度倒して右に表を向けた状態で前方向にトランプを動かす、みたいになります)

戦術について

最後まで完璧にできていたのは3試合程度(トーナメント1,2回戦と準決勝)なのですが、とりあえず自分たちが想定していた戦術について書きます

基本的に自分の領域点はほとんど無視してタイルポイント差で勝利を狙い、相手が大きな領域点を狙っていそうな場合はそれを防ぎにいく戦略を取りました。
タイルポイントを取りに行くアルゴリズムはそこそこ優秀(なはず)で、序盤は完全にアルゴリズム通りに動かす事で得点差で有利な状況を作ることができます。
都合上、相手が大きな領域点を取りに行こうとするケースに対する(アルゴリズム側での)対策はしていません。そのため、相手の領域確保を妨害する操作は基本的に†人間の力†で行うことになります。
人間は優秀なので、GUIにしっかり盤面入力ができていれば基本的に相手に大きく囲まれたまま試合を終えてしまうような状態にはならないと考えています。

封筒に入っている紙からQRコードを読み込んで盤面の向きを揃える所までは10秒程度で済ませる事ができるので、そこで時間が足りなくなるような事はなかったです。
問題は盤面の変化(エージェントの移動)をプログラムに反映する部分で、そこについてはかなり失敗してしまう事がありました。(特にフィールドが大きくなった場合などは入力が難しく、準々決勝などでは最後の10ターンぐらいで入力を諦めていました)

おわりに

GitHubリポジトリを近い内に公開するはずです。1300commitsぐらい生えていて10000行ぐらいは書いたので(実際に使っているのは2-3割程度?)ぜひみてみてください。もう開発はやめたのでぷるりくとかいしゅー投げられても対応はできません。