「最強最速」を見せつけた浪速の高専生：高専プロコンリポート

高専生にとっての大イベント、「高専プロコン」の季節がまたやってきた。競技部門では、大人をもうならせる良問に、優れたアルゴリズムを携えてしのぎを削る学生たちの姿があった。

[西尾泰三，ITmedia]

　秋晴れに包まれた10月17日、18日にかけて、千葉県木更津市にある「かずさアカデミアホール」にて、「全国高等専門学校 第20回プログラミングコンテスト」（高専プロコン）が開催された。

　高等専門学校の学生を対象とした情報処理技術系コンテストといえば「高専ロボコン」が特に有名だが、1990年にはじまった高専プロコンも歴史を重ね、いまでは高専ロボコンとの二枚看板の様相を呈している。

　大きな節目となる20回目を迎えた今回の高専プロコンのテーマは「集まれ手作りの未来たち――海を越え！翔けろ！橋になれ！――」。課題、自由、競技と3部門が設けられている同大会だが、競技部門はほかの部門と比べてエンターテインメント性を強く押し出し、メディアへの露出も増えている。昨年の第19回大会では、システムの不具合から競技部門が不完全燃焼のまま終了する事態が発生し（高専プロコンを襲った魔物の正体とは参照）、続けての失態をさらすわけにはいかないという事情もあり、ホスト校である木更津工業高等専門学校は入念な打ち合わせを重ねながら開催の準備を進めてきた。一説には、これまでにはなかったような開催のための仕様書を書くほどのものであったという。以下では、競技部門についてリポートする。

良質なアルゴリズム問題が用意された競技部門

フィールドの例

　今回の競技部門は題して「何色？　サッと見　発見伝」。数色のパネルが配置されたマス目状に区切られたフィールド上で、その一部の正方形の領域を回転しながら、同色のセルが上下左右の1か所以上で接続された連続するセルの領域（クラスタと呼ぶ）を可能な限り最大化するパズルゲームである。

　1回の回転（ステップ）では、n×nの領域を、その領域の中心に対して点対称に90度単位で90〜270度回転させることができる。これを繰り返し、各色が1つのクラスタにまとまった配置をいかに少ないステップで完成させるかが今回の問題である。問題の数は3問で、各問題のフィールドは1辺が5から20の大きさの正方形で、色数は最大で8色。これを10分という短い時間で回答する。

　今回の問題について、「最強最速アルゴリズマー養成講座」でおなじみの高橋直大氏は、以下のように実装方針を解説してくれた。

今回の問題は非常に簡単に説明すると、ひたすら探索を行って良い解を探していくだけの問題です。しかし、今回の問題では、

• 盤面全体が良いものになっているかを簡単に評価しづらい
• 可能な手の数が膨大であり、最大ケースで工夫なしだと2手先を読むのも苦しい

といった具合に、安易な方法を取るのが難しくなっています。

とはいえ、これ以外の方法を思いつくのはなかなか難しいため、

• 端の方からパネルを確定していくことで、回転する範囲を狭める
• 盤面を分割し、それぞれ狭い範囲に置いて効率のよくなる解を探し、組み合わせる
• 同じ色を切断してしまう数が少ない回転のみを調べ、探索範囲を狭める

といったさまざまな工夫で対応していく必要があります。いかにそういったアイデアを生み出し、実装していくかを競い合える、非常によい問題だと思います。

　クラスタの条件さえ満たせばよいので、完成状態の配置は多数存在することになる。実装としては、全幅探索を用いて最善手を見つけるのがセオリーだが、10分間で3問という時間制限があるため、まともにやっていては時間が足りなくなる。このため、評価関数を組み合わせた枝刈りの手法を用いることで探索範囲を削減することが求められる。運による揺らぎも少なく、実装のできがそのまま勝敗につながる奥の深い問題となった。

完全制覇を狙う浪速のトラ

ステージ上で競技部門を競う各高専の代表たち

　実装方針はさまざまな方法が考えられ、そこが各校の味となって現れることになった。遺伝的アルゴリズムを用いるチームもあれば、複数のアルゴリズムを連鎖適用し、アルゴリズムごとの得意な部分を生かすようにしたチーム、独自の評価関数を用いて最良優先探索を行いながら、最善解に近似する解を求めようとするチームとさまざまだった。また、沼津高専や鈴鹿高専のように、GPGPUを用いた並列演算を行うチームもあった。

　勝敗の判定は、まず各問題ごとの順位を決め、3問を集計して試合全体の順位が決定されるというもの。複数の同色のクラスタが存在する場合は、クラスタに含まれるセルの数（クラスタのサイズ）が最大のもの1つのみが勝敗判定に使われるが、ほどんどのケースでは、規定ステップ以内に、最大クラスタサイズの合計がフィールド中の全セル数に等しくなる状態にまで完成しており、レベルの高さが際立っていた。

　そんな激戦をくぐり抜けて決勝まで勝ち進んだのは、津山、熊本（八代）、一関、久留米、大阪府立、釧路の各高専のほか、ハノイ、大連の8校。今回の大会は、昨年設立されたNPO法人である「高専プロコン交流育成協会（NAPROCK）」主催による「NAPROCK第1回国際プログラミングコンテスト」も兼ねており、中国、ベトナム、台湾、モンゴルからのチームともしのぎを削る大会となったが、そうした海外の強豪2校も決勝に駒を進める国際色豊かな決勝となった。

決勝の問題

　会場を沸かせたのは大阪府立工業高専（府立高専）。もともと府立高専は、大会前に有志が作成した「高専プロコン2009競技練習場」でもその名前が散見される実力を備えていたが、圧倒的ともいえる少ないステップ数で最大クラスタサイズの合計がフィールド中の全セル数に等しくなる状態にまで仕上げ、会場からはどよめきが起こっていた。その大阪府立高専に一関高専、久留米高専が肉薄するといった様相で、特に大阪府立高専と一関高専の2校が前評判どおりの実力をみせていた。

　3問の結果を合わせた総合順位で優勝を手に入れたのはやはり府立高専。セル数が最大のマップ（マップC）では一関高専に4ステップの差をつけられ2位となったが、ほかの2つのマップでからくも逃げ切り、その実力を見せつけた。なお、総合順位で2位は一関高専、3位は釧路高専となった。屈指のアルゴリズマーと呼んでも差し支えないであろう府立高専の浜田悠樹氏は試合後、「（一関高専が167ステップで完了したマップCを）もう一度試したら159ステップで完了した」と完全優勝とならなかったことに無念さをにじませていた。

マップCの結果（左）と大会の総合結果（右）。左図から、各校がまったく違った戦略で臨んでいることがうかがえる。なお、過去の大会で“鬼才”井上恭輔氏を輩出した津山高専は、試合中にノートPCのバッテリーが切れてしまい、半棄権状態となってしまった

　試合後、府立高専の3人（藏内亮氏、浜田悠樹氏、岩見宏明氏）は、「5カ月もの間、さまざまな人の力を借りながらアルゴリズムの精度を高めていった。回転させるn×nの領域について、5から20の範囲でそれぞれ最適な評価関数を用意して臨んだ。コードとしては、再帰ではなく、動的計画法によるただのループに落としこんだことが効いたと思う」と勝因を語った。

競技部門を制した大阪府立工業高専の3人（左から岩見宏明氏、浜田悠樹氏、藏内亮氏）。ほほに張り付いているのはIntelのステッカー。「Intelコンパイラがあればもっといい結果が出たかもしれない。Intelコンパイラほしいですね」と話す

---

　本記事では競技部門のみをリポートしたが（課題、自由部門は別記事で紹介予定）、今年の高専プロコンは非常に質が高く、20回目にふさわしいできであったことを改めて付け加えておきたい。運営側の努力の跡がいたるところでみられ、学生にとってもよい思い出となったのではないだろうか。今後、プロコンやロボコン、デザコンのような“チームでの取り組み”を重視した課目などを用意することで、こうしたコンテストに興味を持つ学生が増えることを願いたい。