読者です 読者をやめる 読者になる 読者になる

高専プロコン第27回の競技部門に参加した

高専プロコン C++ プログラミング
第27回高専プロコン競技部門に木更津高専から出ました。

方針

枠とピースを取り込みしながら、取り込みが終わったピースは人力で埋めていく。
パソコンでいい感じの組み合わせが出てきたらそれを反映する。
ブースに持ち込んだもの、人がなるべく休みなく稼働するようにしました。

開発環境

OS: Windows 10
IDE: Visual Studio 2015 Community
言語: C++
ライブラリ:
  OpenCV(画像処理),
  Boost.Geometry(幾何ライブラリ),
  SFML(グラフィック),
  Thor(SFMLの補助ライブラリ、凹角形の描画用)

データ取得

枠はA4のスキャナ(GT-S650)に乗り切らないので、分割して合成する方法で行きました。枠に適当にペンで模様をつけて、0度と180度回転でスキャンして、Microsoft Image Composite Editorで1枚にします。

ピースは普通に何回か分けて取り込みしました。

多角形検出
OpenCVを使って、RGBのRだけ抜き出し => 輪郭強調(Canny) => 2値化 => 確率的Hough変換 => 出てきた線をいい感じにまとめる => 交点を頂点として多角形検出 という感じである程度は自動で取れるようにしました。
Hough変換は細かい線が大量に出てくるのがどうしても改善できなかったので、それらの線をまとめる処理が必要になりました。
その他細かい部分は人が修正するようになっています。紫の線が修正が必要な線です。(左上のピース)


解の探索

枠とピースを多角形で表現して、枠からピースの多角形を引くことで「置く」動作にしました。取ってきたデータに誤差が乗っているので、ある程度重なりを許す必要が出てきます。
とりあえずそれっぽい解を探すためのバックトラックと、出てきた解が確実なものになるように置いたピースと枠の重なり面積を重みとしてダイクストラっぽいことをするやつを書いていきました。
全部の頂点にピースを置いていたらクソ重いので、初期状態の枠から1つ選んだ頂点に一番近い頂点のみ試すようにしています(その頂点から置いていくことになる)。例外的に、谷になっている部分があれば、その谷を構成する頂点を試します。

バックトラックは枠の頂点の角とピースの角が近いもの、辺の長さが近いもの、重なりが少ない置き方を優先的に選んでいます。また、人間が見ながらそれ以上先に解がなさそうなら適当なキーを押して、一番最初のピースを変えたり別の置き方をさせるようにしました。
ダイクストラっぽいやつは結局重すぎて使えなかったので作っただけで終わりました。

どちらの方法も、最終的に枠の面積が0になれば解けたことになります。実装にはBoost.Geometryを使いました。ピースと枠の頂点と辺を合わせて引くときに、なぜか落ちることがあったので、合わせたピースを若干膨張させてから引くようにしました。(なぜ落ちるのかと、これで解決できたのかはよくわからない)
引くピースによっては引いたあとの枠に極端に小さい角度とか短い線などのゴミが出てきます。そのため、それぞれのゴミを削除する操作を掛けながら探索しました。

どう考えてもこれだけで完全解にたどり着ける気がしなかったので、人のサポート程度になればいいなという感じでした。
下の画像は競技が終わった後に試してみた画像です。すべてバックトラックのやつです。
10/11/10:30追記.
画像を拡大してもらえるとわかりますが、結構実際には置けない組み合わせもあります。あと、これ以上先の解は出せていないです。あくまで最初のほうの置き方がわかるかな?程度のサポート力です。
予行 - 右上の頂点から
1回戦第5試合 - 右下の頂点の1つ左の頂点から
1回戦第5試合 - 左上の頂点から


当日の結果など

予行練習
5分しかなくスキャンが終わらなかった。思ったより枠とピースが大きい。

1回戦 - 最下位
8分ごろに取り込みが終わったが、修正前のソルバーの方を起動してしまいパニックになって人力解。そもそも2分しかないので正しく動かせてても無駄だった気がする。

敗者復活戦 - 5位(敗退)
最大のピースを抜けば1分あれば-1解が作れる問題。枠の合成に失敗して人力解。

上でプログラムについて解説したわけですが、結局1回も使えなかったわけです。

感想など

問題発表の時点で-1人力最強では?と思いましたが、逆に完全解が出せればほぼ間違いなく勝てるとも思いました。7月中旬までは編入試験、8月初めまでは定期試験で忙しく、本格的に取り組み始めたのは8月中旬の夏休みに入ってからです。
昨年度は練習場があり、モチベーションが保てましたが、今年度はそういったものがなくて、他高専がどこまでできているのかわからず疑心暗鬼でコードを書いていました。結局夏休みのほとんどをプロコンに当てました。
当日の1試合の時間は想定以上に短かったです。1回戦、敗者復活戦が10分、準決勝、決勝が20分でした。私は決勝が20分、それ以外は15分でくるかと勝手に予想していました。
結局、プログラムが影響した解を1度も出せず本当に残念でした。これは練習不足と準備不足が原因。
解の評価方法はもう少し何とかならなかったのかと思います。例えば、空白部分の多角形の頂点の数とか面積を使うようにするとか。この評価方法もピースが自由な位置を取れるので相当難しい気もしますが、さすがにあの評価方法はひどいのではないでしょうか。会場に電源がなかったり、重要な情報が募集要項に書かれていなかったり当日の問題にもレギュレーション違反があったりと、今年は競技の運営にやる気がなかったのですかね。
ソースコードはスペルミスとか直して適当にコメントをつけたら公開したいと思います。
(1日目の夜、津山高専の方々に旅館でツイッターバードの自作問題を貸してもらいました。ありがとうございました!)