高専プロコン26競技部門
第26回全国高等専門学校プログラミングコンテスト 競技部門、
同時開催されたNAPROCK7thに産技高専(品川)から参加し準優勝をいただきました。
メンバーは以下の通りです。
@_hokekyo1210(3年)、@Mahito6(3年)、@destiny3141592(3年)
僕は高専プロコンの参加は2回目で、準決勝敗退という苦い経験をしています。その時の悔しさから目標を決勝進出と掲げていたので、今回このような素晴らしい賞を頂けてとても嬉しいです。
また、サレジオ高専さんと合同で実戦同様のシステムを用いた練習も行っていました。この場をお借りしてサレジオ高専さんには感謝を申し上げます。
以下は用意したプログラムや、やったことの解説です。
※文中に出てくるquestXXは全て非公式練習場の問題番号です。
開発環境
メンバー間のデータの共有にはDropboxの共有フォルダを利用していました。
OS:Windows 7,Windows 8.1,MacOSX 10.9.5
言語:Java,C++
エディタ:Eclipse4.4.1,Sublime Text 3
開発した物
総コード量はコード全体の行数であってコミットした全てのコード量ではありません。
問題の簡単化
8行8列のグリッドで構成される石は、左上詰めにしておくことで様々な場面で楽が出来るのでまずそれをしておく(このことをRefineと呼ぶ)。
ノードに過去の設置情報を保持しておく必要はなく、盤面に石番号を格納しておけばあとから解は復元可能なのでそれを利用した。
大まかな段取り
1,ビジュアライザで問題を取得
↓
2,GCCRunnerでパラメータを選択
↓
3,ビームサーチで解を探索し出力
↓
4,Shakerで解答を書き換え、より良いスコアを目指す。
↓
5, 2に戻る
実際の試合ではShakerがほとんど使えず、ビームサーチ勝負になってしまった(インタビューで苦手な傾向の問題と言っていたのはこのため)。
ビームサーチの詳細
ノードの評価値
以下の全ての評価値を足し合わせたものに、親ノードの評価値を足し合わせた値をそのノードの評価値とした。
親ノードの評価値を足し合わせる事により、前の盤面の状態も評価に加えることが出来る。
・ZKスコア
現在埋まっているマスの数に応じて点数を与えた、前半は高く、後半は低くなるようなバイアスが掛けられている。
・盤面複雑度
盤面の入り組んでいたり複雑であったりする部分を前計算し、どれだけ複雑な部分が埋まっているかを計算し点数を与えた。
複雑度の計算はあるマスについて、10.0/(障害物からのマンハッタン距離)^2の総和により求めた。
また盤面の直径を求め、もしその直径が閾値を越えていた場合丁度中点となる部分の複雑度も同様に高めた。これによりquest3や、quest14といった問題において効率の悪い場所から石を置き始めることが無くなった。
・領域分割
盤面全体の分割されている部分(ツイッターでは閉領域と呼ばれていた？)に応じて負の点数を与えた。
基本的に盤面は分割されていないことが望ましいのでこれはかなり重要な評価値だったように思われる。
・接地面積
石を設置する時、既に盤面に存在する障害物やZKへの接地面積がより大きい方が良いので点数を与えた。
石の先読み
基本的に石を設置して閉領域が出来ることは避けたい、しかし今回の課題の場合完全に閉領域の発生を回避することは相当難しい(というより不可能？)であるように思われた。
そこで僕たちはこの問題を解決するため、閉領域が出来た際、その閉領域にピッタリハマる石があった場合その石を予め設置しておくという手法を使った(これをbookingと呼んでいた)。
閉領域の判定にオーダーがかかるがある石がピッタリハマるかどうかは閉領域の一番左上の座標をピンポイントに石と合わせると１回のチェックで判定が出来る。
bookingは障害物の多い問題においては特に効力を発揮し、決勝の問題においても20回前後bookingによる設置が発生していました。
上図のような場合、Blankに12の石を設置する
スキップ
場合により石はスキップした方が良い場合が多くある。そこで、石を置かずに次のノードに遷移するというスキップノードを１ノードにつき１つ、必ず生成した。具体的な遷移の様子は下の図に示す。
この手法により解の幅が増え、より良い解を期待することが出来るようになりました。
最終的にこれら全てを実装し、ビーム幅100~200程度でquest1やquest4といった問題を安定してスコア0で解くことが出来るようになりました。また乱数を使わないことで解の再現性が保たれ、デバッグは比較的容易でした。
ビームサーチの高速化
設置判定のbit演算化
盤面は固定長で32行32列なので、1行の情報をintに収めることが出来る。そこで32要素のint配列を作り、石(これもまた8要素のint配列からなる)のbit情報で&を取ることで障害物との衝突判定を行った。
また、衝突していないことさえ分かっていればあとは石と隣接していれば良いので、隣接が起こるマスを管理したbitboardを先ほどと同様に作り石のbit情報と&を取り高速化を行った。
優先度付きキューのメモリ削減
基本的にビームサーチでは評価をつけた上位N個のノードさえ保持していれば良いので、それ以外のノードをキューに入れるのはオーダー的にもメモリ的にも無駄が多い。しかしこの問題は優先度付きキューを昇順、つまり一番評価値の低いノードをtopに持っていくことで簡単に解決できる。
もしキューの要素数がNより多ければ、Nになるまでpopを行うことで簡単にメモリの削減が出来る。
またこれによりキュー内で最も評価の低いノードはtopを見れば分かるので、キューにpushする前にtopと評価値を比較することでpushする必要があるかどうかも同様に分かる。
これらのメモリ(オーダー)削減は非常に強力で、動作を50倍程度速める事が出来ました。
定数倍の高速化
stlのコンテナをできる限り使わず、使い回せるキューを自作するなどして定数倍の高速化を図った。それ以外にも、出来る限り関数を呼ばない、配列のアクセスにはポインタを用いるなどの細かい高速化を行った。
パラメータの最適化
今回の課題は問題の傾向が複数あり、それぞれによって使うパラメータがかなり変わってくる。具体的に問題の傾向は以下のように分類した。
・広大系(quest1,2,4,13)
・先輩系(quest9,14)
・ぴったり系(quest8)
それぞれについて最適なパラメータを複数見つけることが重要で、本番までに15個程最適化したパラメータを用意しました。この部分の調整は全て@Mahito6がやってくれました。
並列動作
ビームサーチソルバーは1スレッド1プロセスで動作するので、8コアPCを3台用意し8プロセスを同時に実行することで短時間でより多くの解を生成出来るようにした。
並列動作には専用のGUIを用意することで、パラメータの変更を視覚的に行えるようにした。
石個数の削減(おまけ)
解を書き換えて石個数を削減することを目指すソルバーも用意していました。ほとんどおまけ的部分なのでここは読み飛ばしてもいいです。(ぼくたちのチームは本番ではスコア0が狙える問題が出ると踏んで、ここを2ヶ月近く調整し続けていた)
要石の存在
まず今回の問題の性質上、解を書き換えることは比較的容易であり実際に、既に完成した盤面から石を取り外し、他の石を設置し直すということが可能でした。
そこで注意しなければいけないのが、全ての石が取り外せる訳では無いということです。
実際に解の書き換えを試みると、簡単に隣接判定に引っかかってしまいます。つまり、石を外したあとの盤面が、石の隣接ルールに従っている必要があります。
これを深く調べて行くと、外せない石というもののルールが分かってきます。具体的には「ある石(番号はN)について、隣接している石の中で番号がN+1以上であるものを子と呼び、番号がN-1以下であるものを親と呼ぶ。ある石について、隣接している子の中で、親が1つしか無いものがあれば、その石は取り外せない。」となる。このような石のことを以降要石と呼ぶ。
要石の例として、黄緑色が取り外せない石である。
実際に石個数を減らす工夫
2個の石を取り外して出来た閉領域があるとする。これを1個の石で埋め直すことが出来れば、実質石個数を減らす事に成功したことになる。
現実的にこれを全探索で試すのは時間がかかりすぎるので、ここでは5個の石を取り外し、4個で埋めるという作業を高速に行うことを考える。
少し考察すると分かる事実として、「N個で埋められるかどうかは、N-2個の埋め方を全探索して、残りの領域をbookingすることで判定できる。」というものがある。実際にこれは強力で、4個で埋めたいなら2個で埋めるパターンを全探索し、空いた領域をbookingにより埋めればよい。基本的には深さ2のDFSで済むのでこれはかなり高速に動作するし、石番号が昇順に並ぶというメリットがある。
ある石から外し始めて外せる石の数を最大化するという問題もDFSにより求めることが出来る。これにより効率の良い外し方を探し、前述したDFSで効率の良い埋め方を行うことが出来る。
これらを全て実装したものがAIというソルバーで、quest2などの比較的スコア0が出やすく石も減らしやすい問題で平均して20個近くの石を30秒程度で減らせるようになっていました。(非公式練習場や公式練習場にあげている石個数の少ない解は全てこのAIによるもの)
本番での実績
これらは当然ながらスコア0が出ているという前提でのみ動くソルバで、本番で出題されたピッタリ系にはまったく効力を発揮出来ませんでした。
しかし裏番組として行われていたOB戦の第一問において、優勝した八戸高専さんに(石個数では)圧倒的な大差で勝利できたので、得意な問題が来ていれば勝ちの目もあったかな、と感じました。(完全に問題のプロファイリングミスなのでクソザコ)
反省点
・気付けていないビームサーチの評価値があった
・問題の分析を怠った
・１回戦の問題の傾向を見て、ソルバーを鍛え直すという発想に至らなかった
・非公式練習場に気を取られすぎて、今回の競技の本質に気付けなかった
・ビームサーチが弱い
・石が減らせない
・壇上で緊張しすぎ
