連珠プログラムを作ってみるブログ

趣味で製作中の連珠プログラムの開発ログです.
ひっそり,まったり,のんびりと開発中です.

まずは対局できるところまで!



テーマ:

連珠に関連するブログは連珠プログラムポータル(Quinstella.net)に移転しました。記事も順次写す予定です。

AD
いいね!した人  |  コメント(0)  |  リブログ(0)

テーマ:

限珠案solverの方は大体キリのいいところまでいけたので,ここ最近は四追い案(VCF問題)を解図するプログラムの開発に取り組んでいる.


例によって,「夢幻の構想」(龍鷹 編著)に収録されている問題を主に解図しているのだが,収録されている問題は非常に芸術性が高く解答を眺めるだけでも面白い.


今回は,反復深化法 [*1] で解図を行った結果について述べたいと思う.


解図を行ったのは「夢幻の構想」収録の問題番号1~336の計336問.

ただし,一部の問題は実用時間内に解けないので探索ノード数に上限(100万,1000万,1億)を設けて解図を行っている [*2]


問題の解図率だが,


上限 100万 233問 / 336問 (69.3%)

上限 1000万 303問 / 336問 (90.2%)

上限 1億 326問 / 336問 (97.0%)


となっている.現在はおよそ15万nps程度の探索速度なので古典的な反復深化法であっても1分程度で9割の問題を解図できることが分かる.


1億ノードかけても解図出来なかったのが次の十問で,dep(百万,千万,一億)というのは上限が来たときに探索済みの深さ(ここでは四追いの回数)である.


Title dep(百万) dep(千万) dep(一億)
057月面の足跡 9 17 27
097十年フィーバー 7 11 13
100シンジケート 18 27 34
110スーパーラック 6 9 10
113フリーダム 8 12 19
187星渦II 22 32 44
195星誕 6 7 9
196孤高星 6 9 12
270天地創造 41 46 52
271東高円寺村 11 26 30


反復深化法にとって難問であるのは「十年フィーバー」「スーパーラック[*3]」「星誕」「孤高星」であり,初形における着手可能点の多さがネックになっていると考えられる.もし,「星誕」で「探索ノード数10倍で探索深さ +2」という関係が続いたとすると解図を行うのにおよそ6×10^34秒!という天文学的な時間がかかることになる.


さすがに時間がかかり過ぎなので,「最短性」を捨てて[*4]高速に解図するアルゴリズムを設計し336問全問解くことに成功したので次回はそのアルゴリズムについて述べたい.




[*1] 深さを閾値とするIterative deepening depth-first search.最短解が得られることが保証される.

[*2] 解図を行ったマシンはCPU : Core 2 Duo E6420, Mem 2G, OS : Fedora 7 (with gcc 4.1.2)である.置換表は最大600MBほど確保している.

[*3] 正確には「スーパーラック」の"ラ"の上に「・」が付く.

[*4] 反復深化法でも探索途中の不詰の局面に対し出来るだけ早い段階で不詰であることを判定できれば十分高速化できると考えているが,判定が煩雑であることもあり現時点では実装していない.

AD
いいね!した人  |  コメント(3)  |  リブログ(0)

テーマ:

一月ほど前に見つけたのだが,連珠入門シリーズ に貴重な資料が数多く公開されている.


名月一間飛びの定石(おそらく過去の連珠世界の連載)や詰め連珠作品集などがあり,連珠関係の資料が極めて手に入りにくい現状のなかで非常に貴重な情報提供の場となっていると思う.まずはサイト管理者およびネット上での再掲載に許可を出された著作権者に感謝したい.


資料はPDF形式で配布されているのだが,なぜかPDFが一ページずつに分かれており,製本する際に一つずつPDFを開いて印刷する必要があり大変である.そこで,PDFを結合して印刷することにしたのでそのログ.


1.Irvine 等のダウンロードツールでPDFファイルをダウンロード.(このときフォルダ毎に分けるべき)

2.PDF結合ツール を使って結合.


  ○枚目外側(ファイル名だとxxxSy.pdf.xxxは講座名,yは通し番号)は昇順で一つのpdfファイルに結合.

  ○枚目内側(xxxUypdf)は降順で一つのファイルに結合.


  エクスプローラで表示->詳細にしてファイル名でソートすると楽に出来る.


3.結合した外側pdfを印刷.

4.印刷した紙を180度回転させて印刷用紙入れに入れて内側pdfを印刷.


最後の両面印刷するための手順はプリンタ依存で変わる可能性あり.

AD
いいね!した人  |  コメント(0)  |  リブログ(0)

AD

ブログをはじめる

たくさんの芸能人・有名人が
書いているAmebaブログを
無料で簡単にはじめることができます。

公式トップブロガーへ応募

多くの方にご紹介したいブログを
執筆する方を「公式トップブロガー」
として認定しております。

芸能人・有名人ブログを開設

Amebaブログでは、芸能人・有名人ブログを
ご希望される著名人の方/事務所様を
随時募集しております。