GDD DevQuiz
満点までの道のり

田中伸明
@tomerun

自己紹介

徳島からきました

普段はWindowsプログラマです

そればかりでは将来が不安なのと
アルゴリズム的な話が好物なのとで、
DevQuizに飛びつきました

こんな形で話をするのは大学での卒業研究発表会（6年前）以来だ

アジェンダ

DevQuiz概要
スライドパズルの戦略
答えのない問題へのチャレンジについて
EXP-hackathonの様子

DevQuiz概要

GDDなどのGoogleの開発者向けイベントで、参加者を選抜するプログラミングクイズ。良い結果を出した人から順にイベントの招待状が送られる

できるだけやる気や能力が高い人に参加してもらうための仕掛け

公式のコメント(GDD2010)：

DevQuiz とは、従来のような先着順や単純な抽選式ではなく、
以下の 3 点を重視した開発者向けのクイズを出題させていただき、
その合計得点を評価させていただくものです。
- より多くの開発者に参加していただく
- より公平な方式を実現する
- イベント開催前から開発者の方に楽しんで頂く
https://groups.google.com/forum/#!msg/codesitejp/HYhD5nOECGM/hxIsyKTsqEwJ

GDD2011のDevQuiz

ウォームアップクイズ: Googleの技術に関するトリビア。3択問題が5問。
ググれば一発
分野別クイズ: Googleの各種技術について、コードを書いて簡単なタスクを実際にやる。
それぞれ、その技術を知ってれば数十分、初めて触るのなら数時間〜1日くらいでクリア可能
5問中2問やればOK…完全制覇？
チャレンジクイズ（スライドパズル）: 簡単に満点が取れない難しいアルゴリズムの課題
通過だけなら数時間、満点取る気なら20〜∞時間

GDD2011のDevQuiz

参加者：約3000人
通過者：約1000人
満点獲得者：30人
通過ボーダー：100.56点/150.00点

スライドパズルで単純な探索をするコードをバグ無く書ければ突破できた、程度

GDD2011のDevQuiz

問題作成チームからのコメント

100点ちょうどをボーダーにしたかった。スライドパズルはオマケのつもりだったのに手を付ける人がこんなに多いとは。みんな頑張りすぎ
30人も満点が出るとは思っていなかった。日本の開発者を舐めていた
実は出題者のGooglerたちは満点取ってません

スライドパズルの問題

いわゆる15パズル（1〜15までの数字のパネルが4×4にばらばらに配置されていて、空きマスを動かして数字のパネルを左上から順に並べるアレ）の亜種

スライドパズルの問題

・サイズが3×3〜6×6に拡張されている

・パネルを移動させることのできない位置（壁）がある

問題例：

40=       // =は壁、0が空きマス
215
=86

回答例:

DLURDRD   // D:↓　L:←　U:↑　R:→

スライドパズルの問題

・全部で5000問。1問0.01点で50点満点

・それぞれぐちゃぐちゃに並んだ状態が与えられるので、パネルを揃えるには空きマスをどう動かせば良いかを回答する

・5000問合計で、上下左右への移動をそれぞれ何回まで使えるかの制限がある

移動方向	回数
L	72187
R	81749
U	72303
D	81778

最初に考えること

・答えは1つではない!!

・とはいえ移動数の制限があるのでそれなりに短い経路を見つけないといけない

・最短経路を見つけるのはどのくらい大変？

最短経路を探す

定石：幅優先探索

1手後の状態、2手後の状態、…を順に生成してゴールの状態になったかを調べる

書いてみると 191問/5000問正解　まだまだ全然

注：GDDの招待状をもらうだけならこれで十分です

最短経路を探す

定石その2：双方向探索

スタートとゴールの両方から幅優先探索する

たとえば20手の解を見つけるのに要する計算回数は
幅優先探索：約3^20回 VS. 双方向探索：約2*3^10回

計算量が平方根程度！になる

けどそんなに解けない

最短経路を探す…のは無理

同じ状態を何度も探索しないように調査済みの状態を保持しておくが、そのメモリが足りない

3×4の盤面の場合あり得る盤面の状態は 12! / 2 ≒ 2億通り

盤面1つに最低20Byteくらいは必要なので4GB。普通のパソコンではこれ以上は厳しい

→確実に最短経路を出すのは諦めて、てきとーに良さげな状態だけ選んで調べる

良さげな状態

盤面の状態に対して、どれだけゴールに近づいた状態かを判定する評価関数を設定する

パネルそれぞれに対して、目標位置から何マス離れているかをペナルティにして、全パネルについて足し上げる

この合計が小さい方が良い状態

評価関数で枝刈り

評価関数の値が悪い状態は無視することによって、ゴールに近づいている変化のみを調べられるようにする

基本は幅優先探索で、1手進めるごとに評価関数が良い方から一定個数だけ残す

→844問/5000問正解

評価関数に一工夫

この評価関数だと、
「先に盤面の真ん中あたりを揃えてしまうけど、左上を揃えに行くときにせっかく揃えた真ん中の領域が乱されるから意味が無い！」
みたいなことになる

人間がこのパズルをどう解くか考えてみると、ゴールから遠い左上から順に埋めていくはず

パネルごとに、評価関数にどれだけ影響を与えるかの重みを付ける。最終的に左上に来るべきパネルは重く、右下に来るパネルは軽く

→2135問/5000問正解

涙ぐましい最適化

実行してる様子を見ると、やっぱりメモリ食いすぎのようだったので省メモリ化する

int使っていた箇所は変えられるなら全部int8_tにする
経路を1手1byteで持ってたのを、1手2bitに押し込める

あと、パラメータ変えて何度か実行

→4947問/5000問正解まで到達

ここからが本当の戦いだった…

難しいケース

どんな問題で解けていないのかを見てみる

壁のせいで通路みたいになっているところがある場合が答えられていない

パネルごとの評価関数だと、いったん通路の一部だけそろっている部分を敢えてずらしてから揃えなおさないといけない場合に、その方向へ行けない

難しいケース

盤面の中で通路みたいになっている箇所を検出

その領域では、パネル1枚ごとではなく通路全体がそろっていないと評価関数にプラスにならないようにする

→4966問/5000問正解

もっと難しいケース

通路のせいで盤面が2つの部屋に分かれているようなケースがまだ解けてない

通路部分を揃えても、部屋同士でパネルが1つずつ入れ替わっていたり、両方の部屋でパリティが逆になっていたりするとお手上げ

そのへんも考慮した評価関数を作ると解けるのだろうが…

…

すいません手動で解きました<(_ _)>

→5000問/5000問正解！

手動でも鬼畜問はだいぶ鬼畜だった

結果

・手数は12426手余った

・最長経路は303手

LLUURRDDLLUURRDDDDRRUULULULLDDRRURDLUULLDDRRUULLDDRRRRDDLLUURRDDLLUURRDDLLUURUURRDDDDLUULLDDRRRUUUULLDDLDDRRUULLDDRRRUUUULLDDRRDLULUURRDDDLURUULLLDRDRRUULLDDRRUULLDDLURDLUURRRDDLLLUURRRDDLLULURRRDDLLLURDLURURRDDLLLURUULDRULDULDRURDLLURRDLURRDLDLURDLUURDLDRULURDDDLUURDLDRUULDRDRDRDUUUULLURDLURDLURDRDDDD

・思考・コーディング時間は計40時間くらい？

・計算時間は計40時間くらい？

・最後の34問手動で解くのにかかった時間は、GUIソルバ作成も含めると10時間くらい

実装上の細々したこと

言語はC++を選択

5000問も計算させないといけなくて処理速度が重要
もちろん言語差よりアルゴリズムの賢さの方が大事だけど
寝るときに計算回し始めたら…
起きたときには終わっている VS 丸一日経たないと終わらない

C++11便利です

サイズを指定できる整数型（int8_t など）
拡張for
型推論のauto
ラムダ式

実装上の細々したこと

盤面サイズをテンプレートパラメータ化したら実行速度がかなり（1.5倍くらい）速くなって驚いた

      if (h == 3) {
	if (w == 3) answer = solve<3,3>(data);
	else if (w == 4) answer = solve<3,4>(data);
	else if (w == 5) answer = solve<3,5>(data);
	else if (w == 6) answer = solve<3,6>(data);
      } else if(h == 4){
	if (w == 3) answer = solve<4,3>(data);
	else if (w == 4) answer = solve<4,4>(data);
	else if (w == 5) answer = solve<4,5>(data);
	else if (w == 6) answer = solve<4,6>(data);
      } else if(h == 5){
	if (w == 3) answer = solve<5,3>(data);
	else if (w == 4) answer = solve<5,4>(data);
	else if (w == 5) answer = solve<5,5>(data);
	else if (w == 6) answer = solve<5,6>(data);
      } else if(h == 6){
	if (w == 3) answer = solve<6,3>(data);
	else if (w == 4) answer = solve<6,4>(data);
	else if (w == 5) answer = solve<6,5>(data);
	else if (w == 6) answer = solve<6,6>(data);
      }

ただしコンパイル時間は16倍だけどな！　地獄のようだった…

他の人の回答

GDD2011 DevQuiz のスライドパズル晒し祭りをまとめてみた
http://d.hatena.ne.jp/harapon1012/20110912/1315805381

「Java:14名，C++:8名，C:6名，C#:1名，Python:6名，Perl:3名，Ruby:1名，Haskell:1名，PHP:1名，Go:1名，OCaml:1名」（上記URLより引用）

アルゴリズム的には、反復深化深さ優先探索やA*探索を使っている人が多い

戦略によっては、手数が足りなくなって困っていた人もちらほら見かけました

近似解出そうイベントを布教するよ

このスライドパズルのような、ある程度の時間をかけてプログラムを改善していくというイベントにはよく参加しているので、それについて紹介します

TopCoder Marathon Match
Samurai Coding
Code VS
Google AI Challenge

TopCoder Marathon Match

http://community.topcoder.com/tc

参加していると個人にレーティングが付いて励みになる（a.k.a. ネトゲ）

月1回〜2ヶ月に1回開催。ときどきスポンサーが付いて賞金が出る

Samurai Coding

http://www.washi.cs.waseda.ac.jp/samurai_coding/

早稲田大学とGREEが主催

AIを作るらしい（12/16開始）

チーム組んでの参加もOK

CodeVS

http://codevs.jp/

KLab、pixiv、mixiなどが協賛

一昨日開始。なんか賑わってる。非学生は予選までしか参加できませんが…

Google AI Challenge

http://aichallenge.org/

GoogleがスポンサーになってるAIコンテスト。年2回くらいやってる

けっこう正体不明

近似解を求めるプログラムの重要性

「アルゴリズムイントロダクション」第1章練習問題より

"最適解しか意味を持たないような現実社会の問題をあげよ。"

世の中で解いて価値がある問題というのは、最適解が簡単に出せないような問題

実用になっています

NASA-TopCoder Challenge

NASAがスポンサーになって、宇宙探査のための物資輸送効率化に関するコンテストを開催

上位に入った人のコードを元にしてアルゴリズムを開発、実運用されているという噂

コンテスト形式でアルゴリズム考えてもらうのいいね！　ということで、その方法論を研究するための組織まで設立してしまった

もっと増えるかも

このNASAコンテストの商品、賞金総額25000ドル+参加者全員に記念Tシャツ

・主催者にとって：数百万円程度の投資で世界中のアルゴリズム好きが寄ってたかって良い解法を考えてくれる

・参加者にとって：コンテストに参加してるだけで、賞金もらえるかもだし実運用されるとなったら名誉にもなる

というWin-Win

TopCoderの中の人曰く、こういった形での賞金付きコンテストを増やしていく予定とのこと

身につく能力

実装の難しさと効果を天秤にかける感覚: 「このアイディアは実装可能な程度の複雑さか？」
ボトルネック以外を最適化する無意味さ: 本当に面白いくらいに意味が無い。けどつい作業しやすいことをやってしまうという人間の性
コードを綺麗に保つことの大事さ: ごちゃごちゃしたコードを書いていると、後で違う方針を試そうと思っても改造が難しくて泣きそうになる
作業管理: 「一番良い結果出したのはいつのコードだっけ？」←適切にバージョン管理しましょう

参加してみませんか

こういったのに参加して鍛えておくと、

来年はあなたがDevQuizで満点を取って話す番かも!?

…とまでいかなくても、好きな時間に取り組めるものが多いので、"役にも立つコンピューターゲーム"みたいな感じで遊んで貰えると良いなーと思います。

EXP-hackathon

GDDの2日後に、六本木のGoogleにてEXP-hackathonというシークレットイベント（？）が行われました

参加者

DevQuiz満点獲得者
Google API Expertの方々
GDDボランティアの方々
デザイナーの方々
Google社員（海外からも何人も）

お題を出し合って、チームに分かれてハッカソン

EXP-hackathon

写真：https://plus.google.com/photos/106159982274124243155/albums/5670637093193526305

自分のチームは「新しめの技術てんこ盛り君」ということで、WebIntentsやGITKitを使ってみた簡易画像ピッカーを作成していました。

クライアントをDartで書こうという話もありましたがさすがに断念

日程の都合で途中までしか居れなかったので最終的にどうなったかは知らないんですが…

EXP-hackathon

ほかのチームがやってたテーマ

自動飲み会幹事システム
Hangoutsを自分のガジェットに埋め込む的なもの
GWTで2Dゲームを作ってAndroidでどれくらいパフォーマンスが出るか見てみる

感想

周囲の人がみなハイレベルな開発者なので話がどんどん進む

慣れないWeb開発でアタフタしたまま時間が終わってしまいました＞＜

せっかくの豪華イベントなのに満喫できなかった感が…

次回があればもっとスキル付けてリベンジをせねば

おわり

このスライドはhtml5slidesで作成されました。
http://code.google.com/p/html5slides/

GDD DevQuiz満点までの道のり

自己紹介

アジェンダ

DevQuiz概要

DevQuiz概要

GDD2011のDevQuiz

GDD2011のDevQuiz

GDD2011のDevQuiz

GDD2011のDevQuiz

GDD2011のDevQuiz

スライドパズル

スライドパズルの問題

スライドパズルの問題

スライドパズルの問題

最初に考えること

最短経路を探す

最短経路を探す

最短経路を探す…のは無理

良さげな状態

評価関数で枝刈り

評価関数に一工夫

涙ぐましい最適化

難しいケース

難しいケース

もっと難しいケース

結果

実装上の細々したこと

実装上の細々したこと

他の人の回答

答えのない問題へのチャレンジ

近似解出そうイベントを布教するよ

TopCoder Marathon Match

Samurai Coding

CodeVS

Google AI Challenge

近似解を求めるプログラムの重要性

実用になっています

もっと増えるかも

身につく能力

参加してみませんか

EXP-hackathon

EXP-hackathon

EXP-hackathon

EXP-hackathon

感想

おわり

GDD DevQuiz
満点までの道のり