Entries

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/53-53f88ebe

トラックバック

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

Challeruns;Gate 再帰検索とビットシフト

※以下、某作品とは全く関係のない話になります。

○概要
 あなたは、「ペーパーチャレラン」と呼ばれる学習ゲーム教材を知っていますか。
 教育家の伊藤亮介氏が1990年に公表して以降、のべ140万人を超える子供達が取り組んできました。
 詳細なルールは公式サイトを見てもらうとして、その中でも「インターネットペーパーチャレラン」と呼ばれるものについて、コンピュータで解いてみようと思います。
 ちなみに、公式的には「※コンピューターのプログラミングをおこなっての応募はできません。」と書かれています。が、過去の大会結果を見る限り、同一最高得点が横並びになっていることが多いという時点で有名無実ですよね?


○方針
 このゲーム教材(と言うかパズル)のルールは、要約すると次の通りです。

  ・格子状の道を縦横に進み、スタート地点からゴール地点へと向かう。
  ・道の交差点と交差点の間には、「+1」や「-2」などの演算が記されている。
   その上を通る度に、持ち点に対して演算を行わなけばならない(普通の電卓と同じルール)。
  ・最初の持ち点は1点で、ゴール地点に付いた時の持ち点(得点)の高さを競う。

 最初は幅優先探索すればOKかと思ったのですが、どうせ全経路試さなければならないので、より実装が容易な深さ優先探索でプログラムを書くことにしました。と言うか、幅優先で組むとメモリ確保で遅い&メモリが足りなくなったんだよ察してくれ……。

 ただ、ちょっと試してみれば分かるのですが、この問題、1つ横幅or縦幅が増えただけで全経路数が極端に増えます。
 例えば左上から右下に抜けた場合において、具体的に表にすると次の通り。
[横][縦]ノード数
222
234
248
2516
2632
2764
3316
3472
35335
361562
377273
44800
459754
46121130
471508919
55323632
5611171466
57389866263
661086297184
([横][縦]は、縦横の筋の数。大阪人はそれぞれ「通」「筋」と脳内変換してください)
 なんでここまで多いのか、なんとなく察せられる人もいたかと思います。そう、インターネットチャレランでは、「同じ道を二度通ってはならないが同じ交差点は二度通っていい」からです!
 かつてネット界隈を騒がせ、「公式が病気」という賛辞惨事を招いたあの「フカシギの数え方」ですら、上の例で言えば「同じ交差点を二度通ってはならない」に相当するものなのです(つまりチャレラン>フカシギ)。向こうの一部分を表にすると、
[一辺]ノード数
11
22
312
4184
58512
61262816
となります。ここで[一辺]=6の部分に注目してください。ここは、チャレランでは6x6の問題に相当します。では比べてみましょう。
 「フカシギ」では1262816通り、チャレランでは1086297184通り。
 1262816対1086297184。
 比率にすると1:860。

 ……なんなのこのインフレ。DBか何かですか?


○DFS(深さ優先探索)でゴリ押しした結果wwwww
 爆死したンゴ……と言うほどではないのですが、結構苦労しました。
 最初に組んだプログラムの場合、

・盤面データは上下左右方向に対する演算を記録したint型+bool型(vector二段重ね)
・DFSで探索(一歩移動する度に演算を適用させる)
・一歩移動する際には毎回移動位置を計算

といった代物だったので、5x5を計算させるのに30秒は掛かっていました(6x6で3日、7x7で10世紀掛かる計算)。
 ただ、それから幾重にも改良を重ね、

・盤面データは上下左右方向に対する移動位置と演算を記録したint型(ビットシフトで処理)
・DFSで探索(ゴールに着いた時にまとめて演算する)
・移動位置は配列参照(for文で回していたものも展開した)

としたことにより、5x5で0.2秒、6x6で18分という記録を叩きだすことに成功。でも、7x7にはまだ2.6年掛かる見込みですorz

 前述の「フカシギ」では、「ZDD」を利用した高速算法(クヌース先生が発案)により、大きく高速化を果たしました。ただ、「フカシギ」と「チャレラン」とでは条件が異なるので、そのまま当てはめられるかはよく分かりません。仮にできたとしても、ものすごい量の経路一つ一つ(7x7では約2.9×10^13≒29兆通り)に対して得点を計算して最大値を求めるという作業が残っているのですが。
 ちなみに、前に紹介したOpenMPを用いて、経路計算を高速化することも試してみました。その結果、経路計算自体は高速化するけど、演算とセットで運用(部分問題を各コアに割り当て)すると逆に遅くなるという怪奇現象が起きたでござるwww俺涙目wwwwww


:::::::::::.: .:. . ∧_∧ . . . .: ::::::::
:::::::: :.: . . /彡ミ゛ヽ;)ヽ、. ::: : ::   並列化効かないのだけは
::::::: :.: . . / :::/:: ヽ、ヽ、i . .:: :.: :::  マジ意味わかんねえ……
 ̄ ̄ ̄(_,ノ  ̄ ̄ヽ、_ノ ̄



○私は皆に「考えることの素晴らしさ」を教えたいの!止めないで!
 このコードを書く過程で、色々なことが学べました。幅優先探索の書き方とか、ビット演算で変数一つに詰め込む技法とか、OpenMPとか、ループアンループとか、小さいことの積み上げでプログラムが高速化していくのは実に素晴らしいことです。
 個人的な事情により私が書いたコードは晒せませんが、これを読んだあなたも自分で書いてみては?

 ん、「インターネットチャレランサイトの問題って2002~2005年(Pentium M~Pentium D、Opteron~Athlon 64 X2)だろ、問題発表期間が各一ヶ月ぐらいなのにそれじゃ厳しくね」って? アーアーキコエナイキコエナーイ。
関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/53-53f88ebe

トラックバック

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

Appendix

プロフィール

YSR

Author:YSR
「YSR」「YSRKEN」「◆YSRKENkO6Y(~2013/08/25)」「◆YSRKEN.ceVZZ(2013/08/26~)」として活動しています。
プログラミングと艦これが趣味です。
プロフ画像はCrystalDiskInfoの水晶雫ちゃんです。
主な創作物についてはhttp://ysrken.blog.fc2.com/blog-entry-76.htmlをご覧ください。

カレンダー(月別)

06 ≪│2017/07│≫ 08
- - - - - - 1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31 - - - - -

全記事表示リンク

全ての記事を表示する

QRコード

QR

総アクセス数

アクセス数

現在の閲覧者数:
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。