SuperCon 2011の問題作成のお話とか

SuperCon 2011の本選課題作題委員をやっていました。課題(なくろん)決定までの流れを話せる範囲で記録しておこうと思います。あと、結果についても簡単に触れておきます。

何で自分が課題作成委員なのか

スーパーコン実行委員長であるサイバーメディアセンター菊池誠教授の研究室と自分の所属している研究室の間に普段から交流があって(同じフロアに研究室がある)、自分がプログラミングコンテストによく参加しているということで声をかけていただきました。

問題の候補

課題となる問題の候補は複数ありました。候補が一つだけだと何かが原因で使えなくなったときに詰みかねないので安全側に振って4題ほどの候補が出ました。今年はSX8Rを使うので、ベクトル化が効くことが大前提で、その次に解法にバリエーションがあった方がいいとか、新機軸を試したいとかが選出の基準となっていました。

なくろんの原型

実際に本選で使われた課題(なくろん)は最後に出てきました。一番最初は3次元格子内の迷路でボールに対して離散的に加速度を与えて最短時間でゴールを目指す、というのが原型でした(個人的にはこの問題には今でも興味があります)。これから、ボールを増やしたらどうなるかとか、ゴールを増やしたらどうなるとか言いながら、加速度の要素が消えてなくろんの形に近づいて来ました。可視化しやすい方がよいし、次元を落としても十分難しさは保たれるだろうということで2次元に落ちました。また、初期のなくろんのコードネームは「玉」でした。実は、玉が多いときはベクトル計算で速度を稼いで玉の数が少なくなったらスカラー計算に切り替えるとか色々妄想していたのですが、実際にはそんなことにはならなかったようです。

なくろんに決定するまでの流れ

候補を出し切った段階では玉は第2候補でした。ところが、第1候補の問題にちょっとした欠陥があったのと、hasi君が玉をhtmlで遊べる形に実装したものが予想以上に面白かったので玉優勢の流れになって来ました。やっぱり実際に遊べるものがあるのはいいですね。

なくろんの性質を調べる

次の作業は実際になくろんを解く簡単なプログラムを書いて性質を調べることでした。この時点でベクトル化率99%が達成できていたことを確認しました。最大の前提条件が満たされていたので一安心です。この時点で既に、ランダム解とgreedy解(キーは得点そのまま)があまりスコアは変わらないことは分かっていました(理由も含めて)。評価関数(greedyのキー)を色々変えて試してみたりして、一応差はつく問題であろうことは確信していました。というか、流石に最適解を出す効率的なアルゴリズムは存在しないだろうから、適切な評価関数＋枝刈り探索が重要になるだろうことは簡単に予想できていました。そしてそのタイプの問題は実力差が結構はっきり出るので、問題としては悪くなかろうということになりました。

コンテストとしての出題形式を決める

ベクトル化の恩恵を受けるために、問題のサイズが250以上になることは最初期に決定されました。最終的な順位決定にスコアの総和をそのまま使うのは流石にまずいので、順位点を利用することになりました。壁密度が高い方が実力をより反映すると考えていたので、問題によって順位点を変える案もあったのですが、それだと理不尽なクイズ番組みたいになってしまうので、1位にボーナスを与えるだけ、という出題形式になりました。

サンプルプログラムなどの準備、具体的な仕様の策定

出題形式などが決まったら後は実際に参加者に渡すヘッダファイルやサンプルプログラムなどを書きはじめます。ヘッダファイルや問題生成器、ビジュアライザ、解答チェッカの仕様は比較的すんなり決まったのですが、サンプルプログラムをどうするかは結構悩みました。greedyとrandomなソルバを用意することはすぐに確定したのですが、盤面の遷移関数をどうするか、というのは重要な問題です。結局、解答チェッカをソースコードで渡すので、解答チェッカで実際に利用するO(SIZE^2)の遷移関数をサンプルとして与えることになりました。結果的には、参加者がいじる余地が少なくなってしまったかもしれません。解答チェッカをO(SIZE^3)にして、サンプルプログラムもO(SIZE^3)を渡す方がよかったかも。
このあたりの作業はhasi君の貢献度が最も高かったように思います。html版なくろんの機能追加の合間にチェッカを書いたりサンプルプログラムやヘッダファイルの修正、テストという面倒な作業を率先してやってくれました。

トラブル

コンテスト開催数日前に自分自身でサンプルソルバを書いてみて試してみたら、SXでベクトル化率99%を達成できているにもかかわらずローカルで実行した場合と2倍以下しか速度差が出なかったのでなんじゃこりゃ、となりました。原因は、サイズ250程度だとキャッシュヒット率が上がって高速に動作することのようでした。実際、サイズを2倍3倍にするとSX8Rとの速度差は大きくなります。これが前日のことでなかったらサイズを変更することも考えられたのですが、残念ながら時間が足りずにサイズは250のままということになりました。

コンテストの結果

評価関数は (得た得点/落ちた玉の数) としているチームが多かったようです。それ以外の評価関数もあって、例えば自分は穴の色のばらつきによって各色に重み付けるようなものも考えていたんですが、結局得点率よりは良くなりませんでした。シンプルなものが強い，というのはよくあることですが。
2~5位の方針は非常によく似ていました。おおまかに言うと、現在の局面から深さ5~7程度までの手を読み、もっとも高い評価値を得る状態に遷移するというものです。その中でも工夫の多いチームが高い順位を得ていたようです。この辺りの結果は驚くほど妥当でした。
1位のチームは幅優先+枝刈りというのが基本戦略だったようです(初めて知ったのですが、こういうのを遺伝アルゴリズムと呼ぶ人たちもいるようです)。多分その方針だけでも1位をとれていたとは思うのですが、さらに評価関数の計算を高速化したり、スコアに大きく影響する序盤を重視するなどの工夫がダメ押しでした。ベクトル化率99%、メモリ使用量28GBというSX8Rの性能を生かした完成度の高いプログラムでした。文句なしの完全優勝です。
あと、探索途中の盤面を保存しているチームが複数あったんですが、正直それが必須かどうかはよく分かっていません。まあ、保存して困ることは無いし、微妙に(1~2%?)は高速化されるでしょうけど。
今回の問題は結構高速化するのが大変で、色々工夫しても実行速度が大して稼げなかったような印象があります。
探索の工夫として、上下上という遷移は下上という遷移と一緒なので、上下上という遷移は考えなくても良いことが分かります。それによる枝刈りはそれなりに高速化に寄与します。depth=8で1792と2916。それでも2倍以下の違いしか出ませんが。
(追記)greedyでやってるチームは、探索木の葉の中だけで最大値をとっていたようだけど、別にそうする理由は特段無くて、探索木の根以外の全てのノードで最大値をとるノードに遷移すればいいんじゃないかと思った。評価関数を初手からの得点率に修正してやる必要があるけど。また、タイムスケジュールがやりにくくなるという欠点はあると思う。それに、実際は探索木の深い所ほど得点率が高いので、あまり変わらない気もする。