GDD2011 DevQuiz のスライドパズル晒し祭りをまとめてみた

プログラミング まとめ

基本的に自分用メモです．主に以下のtogetterまたは#gdd11jpのハッシュタグから情報を集めました．一応言語順にしてあります．
http://togetter.com/li/187147
（勝手にリスト化してほしくないという場合はご連絡ください！）

追記：エントリーポスト時は9名分．9月12日18時で16名分に増加．22時に28名分，9月13日10時現在43名分です．大雑把な分類でJava:14名，C++:8名，C:6名，C#:1名，Python:6名，Perl:3名，Ruby:1名，Haskell:1名，PHP:1名，Go:1名，OCaml:1名

．

@ さん

「A*アルゴリズム」と「双方向探索」による実装．Core i5-2520M/Z21，8GB Memory の 64 bit PC で4600 問以上を1.5時間程度で解答するそうです．

@ さん

@ryosmsさんは3182問解答されたそうです．

@ さん

@ さん

「ものすごく素直に組んだIDDFS+下限値枝刈りのみ」です．

@ さん

「特徴：Java、並列処理対応、深さ優先、探索空間を縮小していく戦略、可読性が（わりと）高いと思われる。実績３日稼動で3300問弱。」

@ さん

「実際はこれのパラメータをいくつか変更して枝刈り無しでの最速手探索と枝刈り厳しめの探索深さ確保をちょいちょいやりました。」とのこと．

@ さん

「自己流遺伝的アルゴリズムで解いた。一応4500問以上は解けるけど、ハイスペックPCでないと死ぬ。簡単に解説すると、大量に個体を発生させてランダムに移動させる。で、移動するたびに解答との適応度を計算して、適当度の高い個体を一定数エリート選択。さらに高確率で欠失系の突然変異を起こさせて個体の多様性を保った。あとは最優秀の個体が解答と一致したら収束で終わり。」とのこと．

@ さん

「スライドパズルは壁無視マンハッタン距離＋始点からの経路長で優先度つきキューに入れるだけの適当実装。」とのことで4378問．

@ さん

「反復深化深さ優先探索，下限値枝刈り法，幅優先探索，フィーリングカップルアルゴリズム」など．4902問．

@ さん

「実行速度特化型で、需要ないと思いますが晒してみます('A`)5000問解くのにかかった時間は203分、言語はJava、正答率は・・・ｗ」とのことですが，2〜3分で1015問解くというのもすごい気が…．

@ さん

「提出したコードを公開してみる。評価関数は自分が読んでも分かりにくいのでコメントを追加した。 -Xmx1g で実行すれば全問解答できるはず。」とのこと．

@ さん

「Javaで実装。BFS, IDDFS, A*, スレッド化, SQLite化, 出力問題選択」とのこと．

@ さん

「状態は盤面がlong[4]と履歴がBitSet. あとはおまけ」とのこと．

@ さん

@ さん

各ピースの元の位置と現在の位置の間の距離の和をヒューリスティックにした、反復深化A*だそうです．

@ さん

「幅優先だとメモリつらそうだなと思ったので，基本は深さ優先で．反復深化深さ優先探索？して，それでだめそうなら，途中結果で良さそうだったところから，再度同じアルゴリズムで繰り返す．」

@ さん

@ さん

「一応２日かけて4600問までは行きました。メモリはそんなに必要ないですよ。」だそうです．

@ さん

「アルゴリズムは双方向A*+マンハッタン距離の組み合わせ。」4748問．

@ さん

「dfs，wfs」など様々試されたようです．3397問．

@ さん

本人による解説：http://topcoder.g.hatena.ne.jp/firewood/20110912/1315840772
「スタートとゴールからBFSで全探索。評価値はマンハッタン距離ではなく、x^2+y^2としたのが良かったようだ。」とのこと．その発想はなかった．あとでちょっとやってみよう．

@ さん

全問正解の方！参考になります．

@ さん

@ さん

この方も満点！すごいなー．「IDA*，双方向探索，端優先，ステップ実行，半自動シミュレーション」というアルゴリズムです．

@ さん

「アルゴリズムの方針としては、反復深化深さ優先を基本としてます。加えて終了局面を起点として幅優先で正解局面を展開してハッシュに溜めて、深さ優先の終了チェックに使用します。終了局面との距離には普通のマンハッタン距離を使用してます。それだけです。」とのことです．4427問．

@ さん

「総当り。 0 の位置から上下左右で移動出来るところ全てを移動させて最終的なゲームクリアの盤面になっているかをチェック，完全に幅優先で作成」とのこと．

@ さん

「反復深化深さ優先探索をCでゴリゴリ書き、マシンパワーに任せて解きました。」とのこと．5プロセス同時実行で3742点だそうです．

@ さん

「深さ優先探索でgame_sというオブジェクにスタート、ゴール、訪れた盤面の管理をしてもらいつつ、可能な手を試していってもらいます。 訪れられる盤面がなくなるまでこれを繰り返す」とのこと．

@ さん

「最後の「スライドパズル」は、本来、プログラムに解かせるのが狙いなんでしょうが、一般的な解法もわからないまま、いきなりプログラムは組めません。とりあえず、手動で解くプログラムを書いて、解いているうちに、一般的な解法が閃くのではないか、ということで、アプリケーションを作ってみました。 」とのことです．おもしろそう．

@ さん

5000問全て解答されている．基本はA*で4980問，手動で19問，反復深化で1問．

@ さん

  • 言語：Python
  • コード置き場兼本人による解説：http://水嶋.jp/2011/09/12/devquiz11slidepuzzle/

「計算速度はそんなに早くなくて，先代MacBookAirで1週間計算させ続けて解答できたのは4000問でした」だそうです．

@ さん

5000問解いた@methaneさん．読んで参考にしたいです．

@ さん

言語：Python
コード置き場：https://gist.github.com/1210841#file_slidepuzzle.py
本人による解説：http://d.hatena.ne.jp/mohayonao/20110912/1315817662
「幅優先探索でちょっとやってみたら全然解けなかったので、適当に優先順位つけるようにしたら、思ったよりは回答してた」とのことです．

@ さん

「作戦は「空」つまり0を上下左右に動かして結果を記録して1手、次に1手で記録した盤面を全て上下左右を調べて記録、これで2手。pythonのmapを使い、インデックスを盤面とした。」とのことです．

@ さん

「Pythonで素直なA*アルゴリズムの実装です．」とのこと．

@ さん

正統派の解き方の解説から一風変わった解き方の解説まであり，とても勉強になります．また，@kaoriyaさんご指摘ありがとうございました．

@ さん

「ベースとなるアルゴリズムは双方向 A*，コストはいわゆるマンハッタン距離と手数」だそうです．

@ さん

「LRやUDなど移動元に戻るなんて動きは当然除外，マップの状態をテーブルにストックして同一局面になったものは除外，各局面で次ループに残す局面はマンハッタン距離でソート」という方針だそうです．

@ さん

「普通に幅優先探索してる．マシンは途中までMacBook Core2Duo 2GHz, 途中からCore2Quad 2.4GHzで前者は2プロセス並列，後者は5プロセス並列で実行していました．」とのことで227問です．

@ さん

「まずは幅優先の総当り（大きいパズルでは全然）．ゴールへの近さを定義して、近いものから優先して解く．ハッシュを計算して盤の比較」とのこと．1335問．

@ さん

「3x4をBFS、3x4をIDDFS、それ以上をごくベーシックなマンハッタン距離のA*をPHPで。SplDoublyLinkedListクラス利用。」とのこと．3750問．

@ さん

「どれもはじめて触ったGoで書きました。とても楽しかったです」とのこと．Goでやるとは…．

@ さん

「普通のA*，今気付いたんだけどもしかしてこれ劣化双方向探索だった？」とのこと．3723問．


まだまだ増えそうですが，現時点でtogetterにまとまってたのを言語別にまとめ直してみました．できれば時間を見つけて他の人が書かれたコードを読んで自分なりに整理したいと思います．で，お前は何点なんだと言われそうですが，Pythonで1238/5000なのでまだまだですね．A*使えばいいことは気付いたんですが，アルゴリズムの実装が適当なのと壁があるケースをきちんと扱えていないので，全然解けていませんｗもっとアルゴリズムのお勉強とプログラミング能力を高める必要があるという反省．楽しかったのでいいけど．