第34回高専プロコンの競技部門への参加記です。あまりにも楽しむことができたので記憶が新しいうちに記録に残そうと思いました。
ルールは募集要項をご覧ください。
結果から書きますと、私達のチームは準々決勝で敗退しましたが特別賞と企業賞を獲得することができました。🙌
競技部門に企業賞は非常に少ないという話を耳にしており、まさか私達が選ばれるとは夢にも思っていませんでした。実際に競技部門に企業賞が贈られたのは私が調べたところ 2017 年以降 6 年ぶりのようす。
戦略
パンフレットに私たちのチームは以下のようなことを書いています。
ここに書いてあることは結局本番に使うことはできませんでした。
まず機械学習ですが、盤面や職人数が少しでも多くなると途端に悲鳴をあげてしまいます。結局 B11 でしかまともに動かないという状況になり、さらにビジュアライザで Python を動かすことができないというバグも発生しこの方針で突き進むのは無理があるという結論になりました。
また、木探索も最終的に諦めることになりました。本番一日目の深夜までずっと後輩に木探索のプログラムを書いてもらっていましたが、後述するルールベースのプログラムに全く勝てずに本番では使わないことになりました。
私達はルールベースのプログラム、つまり私が考えた強そうなことを愚直に実行するプログラムで勝負に挑むことにしました。例えば、何もないところを囲むと30点ですが城を囲むと100点なので明らかに城を優先的に囲んだ方が良いです。しかし、かといって城のみを囲い続けては無駄な動きが多いです。こういったことをひたすらに考え実装し、デバッグするということを繰り返しました。私ははじめ後輩の木探索のコードで本番に臨むことを想定しており、本当に強いか実証するために盤面を大きく囲うプログラムやひたすら妨害しに行くプログラムなど極端なプログラムを作成し続けていました。しかし、あまり木探索が予想していたほど強くないことが発覚したため本番の一週間前からルールベースの実装を私が始めることにしました。
大体の戦略としては以下の通りです：
- 各職人はそれぞれ独立に城を囲む。ただし、それぞれの職人が囲おうとする城は全て異なるものになるようにする。
- 城をとにかく囲む。しかし、相手が近くにいない場合や残りターン数に余裕がある場合などは隣接するマスなども一緒に大きく囲う。
これだけです。非常にシンプルな作戦で突撃しましたが、私達は細かいところに非常に力を入れました。
例えば、職人が目指す城の決め方です。一日目は最も近くにある城を目指すようにしており、実際それでかなり強いプログラムになっていました。しかし、一日目の夜に更に周りに城がどれだけ繋がっているかの情報も一緒に入れて決めることにしました。要は孤立した城の優先度を下げ、周りに城が多くあるような城を優先的に囲むようにしたということです。一見意味のない改善のようで、実際配布されたフィールドのうち B,C から始まる盤面では特に強くなっていないです。しかし、 A から始まるフィールドでは目に見えて強くなりました。こういったあまり影響がなさそうな細かい部分をひたすらに修正していきました。盆栽っぽいなと思いました。
こだわり部分として、とにかく無駄な動きを避けることに尽力しました。職人が隣り合っている時などに行動の競合が起こりがちです。これを避けるために他の多くの高専では職人をいい感じに分散させるように設計していたようで、実際私達も木探索のプログラムではそのように設計していました。しかし、ここは黄色コーダーの意地を見せて気合を入れて実装することで競合をほぼ 0 にまで減らすことができました。これは、例えば城が真ん中に集中しているような盤面で他の高専と比べてアドバンテージとなると考えています。
ヒューリスティックや機械学習などは一切使っていないので爆速で職人の行動を決めることができます。最も大きい盤面でも 10ms 程度で行動を決定することが可能です。
大会当日
一日目の午前に実際のサーバと通信した際に職人の挙動がおかしいことに気付きました。フィールドの外にずっと壁を建てようとしてるのです。私達が先攻の時は正しく動いているのに後攻の際にバグっているので様々な予測をしました。この際は先攻の時は後輩の新しいパソコンで動かしていたが後攻の時は高専の処理がとんでもなく遅いパソコンで通信していたことが原因だと結論付け、本番では後輩のパソコンでのみ動かすことにしました。
ファーストステージ前半戦は仙台(広瀬)とでした。私達が後攻で第一戦を行いましたが、なんと初手でプログラムが落ちました。チームメンバー全員 10 秒ほど硬直し、それからうろたえ続けていました。高専のパソコンを起動させなんとか途中から参加できないか試しましたが、とんでもない手を出力するのみです。第二戦で取り返し結果は 1690 - 1350 で勝利しましたが、勝利に対し誰も喜びませんでした。生きた心地がしませんでした。異様に長い待ち時間の間にチームメンバーが私達のチームが後攻の時のみに発生するバグを発見し修正した時には安心しました。このバグの発見と修正がなければ大変なことになっていたと思うので本当に助かりました。
ファーストステージ後半戦は有明とでした。バグは修正され、ビジュアライザは正しく動作し想定通りの動きをしてくれました。しかし、サーバとの通信がだんだん遅れ、最後の方では想定より7秒ほど遅れてしまっていました。これは半ば Dos 攻撃レベルでサーバとの通信をしてしまっていたのが原因で、これも先ほどと同じチームメンバーが修正してくれました。本当に感謝しかないです。この試合も 3380 - 460 で勝つことができました。
競技が終わった後はバグの修正と他高専との交流をしました。特に仲良くしてくださった大分の方々ありがとうございます。
一日目の終わりには私のホテルの部屋に集まり深夜 2 時頃までバグの修正や新機能の実装をしていました。全ては覚えていませんが、私がこの時に修正した部分で効果的だと感じたのは以下の三つです：
- 残りターン数に間に合わないような城に向かわずに、相手の妨害や城ではないところの包囲などを行うように修正した。 (この修正が都立(品川)との対戦に非常に効きました)
- 囲む城を決める際にその城が他の城とどれだけ繋がっているかの情報も使うように修正した。
- 城を囲む際どれだけ大きく囲むかを決定する際に相手の職人との距離の情報も使うように修正した。
人が競技中一切手を加えない分細かいところを気にする必要がありました。
上記の修正をして自分のプログラム同士で対戦をさせていましたが、四方に池がある城を大きく囲おうとした際に池にも無駄に壁を建ててしまうバグに気付きました。しかし 30 分ほどデバッグしたところで時間は既に 2 時を回っており、逆に城を二重に囲むことで相手からの妨害に強くなっていると考えると致命的ではないと考えデバッグを諦めました。
以下の画像は上で一つ目に挙げた修正点です。深夜なのでパラメータ調整を適当にやっている上になかなか酷いコードを書いていますが、そこそこ良い感じになりました。 rand_12 : rand_4 : rand_1 の比率で結構囲む、そこそこ囲む、城のみ囲む、を選択するようにしています。
二日目の試合前は手の震えと動悸が止まりませんでした。自分の書いたプログラムを信じてはいますが、ここまで頑張ったなら…という気持ちが強かったです。
ファイナルステージ初戦は津山とでした。直前の修正も効いたのか、 9530 - 230 と快勝しました。ビジュアライザも正しく動作してウキウキでした。一勝できたせいか、負けることに対する恐怖はなく、できるだけ楽しみたいという気持ちの方が強くなりました。
第二回戦は都立(品川)とでした。勝負としては一番印象に残っています。第一回戦で都立(品川)は私達よりも高い点数で勝利しており、どのような試合展開になるのか全く予想できませんでした。こちらより高い点数で勝利しているということは大きく囲んでいる場所が多いということだから妨害も積極的に行う私達のチームは有利に試合を進められるとは考えていましたが、それでも不安は残りました。
こちらのサイトで各勝負の戦況の推移が確認できますが、第一戦も第二戦も非常に均衡しています。青が私達のチームです。
どちらも残りおよそ 10 ターンの際に追いつかれるか逆転されています。ビジュアライザに表示される点数が急に迫ってきたり逆転されたりと心が休まる瞬間が一切なかったので本当に緊迫した試合でした。私達のチームの強い部分をしっかりと出して勝つことができたのはこの試合だけなので、本当に楽しかったです。点数は 5140 - 3870 でした。
余談ですが、隣で都立(品川)の人たちが「C危ないかも」「Aちょっと手薄」などと指示を出している横でパソコンに全てを任せているのは気が気でなかったです。
第三戦はハノイ工科大とでした。ここで私達のチームの致命的な弱点が出てしまいました。相手は盤面を研究し、私達の職人の動きを封じに来ていました。そのような行動は完全に想定外であり、私達の職人の一人の身動きが封じられてしまいました。それから職人三人対職人四人の戦いとなってしまいますが、更に悪いことにこちらと向こうの職人二人同士が完全に膠着状態となってしまいました。そうなると自由に動ける職人はこちらが一人に対し向こうが二人です。早いうちに詰まされてしまい、どうしようもないままに 2000 点以上の点差をつけられてしまいました。ここで私達は負けを悟りました。
私達が内側の第二戦はまだ善戦していましたが、相手はこの盤面をかなり研究してきており、非常に洗練された動きをしていました。 50 点程度私達のチームがリードしましたが、全体で見れば 3950 - 6270 となってしまい敗戦してしまいました。勝負中に人が関与できない弱点がここで出てきてしまいました。
この後はずっと観戦していました。豊田が予選で非常に厳しい戦いを強いられていたこともありずっと応援していました。結果三位になったようで良かったです。三位決定戦はとんでもないほどに僅差で見ていて楽しかったです。
閉会式ではまず特別賞で名前が呼ばれました。賞状と盾を貰うことができ、非常に嬉しかったです。しかしこの盾は私達が卒業した後も学校に飾られるらしく、私物にならないのが少し残念でした。
また、なんと企業賞でも名前が呼ばれました。競技部門は滅多に呼ばれないと聞いていた上に私達より良い成績を取っているチームも多くある中で呼ばれるとは全く考えていませんでした。企業名と高専名を流し聞きしながら都立(品川)やハノイ工科大との試合を思い出していたので、私達の高専名が呼ばれた時に慌てて膝の上に置いていた荷物を全て床に落としてしまった記憶があります。さらに集中して聞いていなかったため壇上で盾と商品を受け取るまでどの企業から賞をいただいたのかも把握できていませんでした。競技中に人の指示が入らない部分やサーバとの通信の実装を高く評価されたのが企業賞を贈られた要因らしいです。本番前はどの高専も競技中に人の指示が入らないようなプログラムを書いてくると思っていましたが、実際ベスト 8 に上がってきたチームの中では私達だけだったようです。それだけ人が強かったわけですが、その中でまともに戦うことができたのは技術力が高かったからだと思っています。今までやってきた競技プログラミングが初めて他の場所で生きたと感じました。単純な実装力もそうですが、ダイクストラ法や行動の優先順位の決定方法などは競技プログラミングで培った力です。 Union-Find を使ったチームは私達のチームの他にはいないと思います。今まであまり自分の技術力が高いとは考えたことがなかったのですが、今回の高専プロコンでかなり自信がつきました。
私達が競技中に人が介さないようなプログラムにした理由は人が介したいような状況にそれぞれ対応するようなプログラムが作成できたからです。ハノイ工科大にこそ負けてしまいましたが、よっぽどのイレギュラー以外には対応できるようにしていました。そのようなプログラムで人が介入しようとすると逆に弱くなると考え、全てをプログラムに任せることにしました。ハノイ工科大にあのような負け方をしてしまった今となっては緊急用に実装しても良かったなとも思いますが、それは結果論なので仕方がないと考えています。
ところで DMM さんから DMM プレミアム 3 年分のポイントと一人あたり 30 万円のパソコンを頂けることになっているのですが、金額のスケールおかしくないですかね…？商品が読み上げられる前までは DMM のストラップでも貰えるのかな〜なんて考えていたのですが、 90 万円という文字を見てあまりの額に頭が真っ白になっていました。なんとか意識を保って yanoshi さんの言葉を一言一句聞き逃さないようにしていたのですが、後からアーカイブを見返すと記憶が結構飛んでることに気付きました。まだ企業賞の実感が全然ないです。
ちなみに壇上で頂いたあの大きなボードは持って帰ってきました。これを持って京都駅で爆速乗り換えをするのはつらかったです。
チームメンバー
この 3 人でしか成し遂げられなかった特別賞と企業賞だと思っているので、ここにチームメンバーの偉業について書いておきたいと思います。
- チームメンバー 1
ビジュアライザの作成と通信関係をやってもらいました。非常に視覚的に見やすいビジュアライザを作り、更に "お行儀の良い" サーバとの通信を実装してもらいました。通信部分をうまく実装しているところは企業賞の受賞理由の一つでもあります。
あと、審査員特権で裏方の人たちにもお話を聞いていましたが、競技システムとやり取りをする部分についても、ちゃんとお行儀の良い実装がなされていたと聞いています。UIも作り込まれてたし。技術力しっかりしてるなーって。#procon34 (9/13)
— yanoshi (@yanoshi) 2023年10月15日
一日目の終わりにビジュアライザ部分だけでなくアルゴリズム部分もやってみたかったと言っていたので、また機会があればアルゴリズム部分はみんなで一緒に考えていきたいな〜なんて考えています。
- チームメンバー2
今回のゲームで必要な職人や盤面の情報や点数計算などを全てやってくれるクラスを作成してもらいました。これのおかげで非常に楽にルールベースのプログラムを作成することができました。
また、木探索や機械学習などの様々な手法も検討してもらいました。どれも実際にコードを作成して対戦させて比較することができたのは非常に参考になりました。
私達のチームのもう一つの強みとして、仕事分担が上手くいき、作業が効率よくできたこともあると考えています。みんなしっかり働きました。特に後輩 (チームメンバー2) とは初対面だったのですが情報共有がしっかりできたのは良かった点です。
それとチームで実装する際の実装のマナーについて後輩からめちゃくちゃ怒られました。競プロをやる感覚で変数名を付けてはいけないということは聞いていたので分かりやすいようにと kakomi_kaisu (城を囲もうとしたターン数、これが多いと膠着していることなので一旦城を囲うのを諦める) や kakomitai_2d (既に職人が囲もうとしているフィールドを二次元配列で持つ、ここが true な場所は新しく囲まないようにする) などといった変数名を付けていたら、英語にしましょうと言われました。また、 assert の中に副作用のある関数呼び出しをしていたのは特に怒られました。 rep マクロもそこそこ怒られました。正しい方法やマナーを色々教えてもらい参考になりました。
まとめ
高専プロコンがこんなにも楽しいものだとは思っていませんでした。今までチームで協力して何か一つの作品を作ることの経験はなかったので、本当に大きな経験となりました。私達は他のチームとしっかり戦えるチームだということがわかったので、来年も編入が忙しくなければ出場したいと考えています。高専プロコンに出るために専攻科に進学することも考えているレベルです。
また、高専卒業後は絶対進学すると決めていたのですが、就職でも良いかなという気持ちも芽生えました。元々私は高専生を欲しい企業が多いのは大卒と比べて安い賃金で同じような仕事をさせられてしまうからだという思想を持っており、自分を安売りしないためにも大学やさらにその上には絶対に行こうと考えていました。しかし、様々な企業の方の言葉を聞いているとそうではなく高専生のスキルを正当に評価してくださる企業も多く存在することが分かり、進学の気持ちは揺らいでいます。時期的にもう編入に絞ると思いますが、それでも非常に刺激になるような体験をいくつもさせていただきました。もっと若いうちから高専プロコンに参加できていればと後悔しています。
喜怒哀楽全てを強烈に感じた二日間でした。恐らく一生記憶に残るであろう体験ができました。
このような場を設けてくださった方々にお礼を申し上げます。本当にありがとうございました。
