お気づきの点や感想要望などなんでもＯＫ！
塗り壁さん、こんばんは。deepgreenです。 お誘いありがとうございます。パズルの話題がでるようでしたら一度参加して みたいなあと思っています。過去の例をみると無いようです。(残念） 何か面白そうな話題がでるようでしたらおしえてください。
こんばんは、deepgreenです。 【斜軸変換】 高橋さんのご指摘のとおり、ＡとＡ’（斜軸変換後）とは等価ですから一方のみで よいはずです。今のＵＢｃｈｅｃｋは、Ａの評価のときにＡ’も評価し、逆に、Ａ’ の評価のときにＡ（＝Ａ''）を評価しているので大変無駄でした。 これですっきりします。とにかく、高速化の材料は大歓迎です。 【最長手数探索の時間見積り】 今の道具（Ｕｌｉｎｅ，ＵＢｃｈｅｃｋ，高橋さんのＳｏｌｖｅｒ）でどの位の 時間が必要かを見積もってみました。見積もりの方法は、４点（U=95,90,85,80)の サンプル探索のデータから全体の時間を推測しました。 Ｕｌｉｎｅの探索条件は、Ｕ＞＝８０、８０手以上を候補として残す （８０手の問題をすべて見つけるため,８０手の問題も残す） 候補は、高橋さんのSolverで、１問＝１分で解くという想定です。 Ｕの範囲 サンプル点 スキャン時間 Ｓｏｌｖｅｒ時間 ９９−９３ ９５ ２．０ ８５．１ ９２−８８ ９０ １９５．４ ２２，４８２ ８７−８３ ８５ １１８．４ １，１４２ ８２−８０ ８０ １３６．７ １２０．８ 合計 ４５３Ｈ ２３，８３２Ｈ （１９日） （９９３日） この計画の一番の問題は、Ｕ＝９０近傍で問題数を絞りきれない点にあります。 この部分を少し深い探索にすると、スキャン時間 ３４日、Ｓｏｌｖｅｒ時間 ３２２日となります。 Solver時間の基礎値（１問＝１分）は、厳しすぎで３０秒位が妥当かもしれません。 また、斜軸変換により問題数が２／３になることを考慮すると、１５０日位でできる と思われます。（まだ、現実的ではないが） なお、論文のように８１手以上の問題がないことを確認するだけなら８０手の問題を 対象外にできるのでＳｏｌｖｅｒの対象が大幅に（１桁以上）少なくなるのでかなり 現実味のある時間になるでしょう。
御無沙汰しております。塗り壁です。私はこの度、情報処理学会の中にある ゲーム情報学研究会に入会しました。パズルに関するプログラミングも 研究の対象です。高橋謙一郎さん、及び常連のdeepgreenさん。よろしければ 入会を検討してみたらどうでしょうか。 http://www.tanaka.ecc.u-tokyo.ac.jp/sig-gi/ p.s. 私は、情報処理学会の回し者ではありません。
報告 １５９Ｄ ２６ＡＥ ３７ＢＦ ４８Ｃ＊ に対してLowerBound=48となる距離を考案しました。 今のところ、評価時間が枝刈り効果に追いつかず、高速化はできませんでしたが… 詳しくは書きませんが、縦横一本ずつ区切りを入れて、シュミレーションをするものです。９種のテーブル（WDで使っているのと同じようなもの）を用いています。 最長手数という点では解けてしまいましたが、ソルバーの高速化は、もうすこしなんとかならないかな、といった感じです。 WD,IDが非常に優れているので、なかなかそれを越えるアイデアが出ません。
deepgreenさんの１７個の問題の中には「対称変換」すると同一面になるものが６つありました。 見た目は違っていても本質的に同じものですから実際にdeepgreenさんがUB>=84からしぼりこんだ 面は１１個ということになります。(少ないのはいいことですよね) 4: *c9dfbae87654321 //UB : 84 / 88 No.1 -> LB : 66 / 78moves 69sec 7: *cedfba937654821 //UB : 84 / 88 No.4 -> LB : 66 / 78moves 70sec 例えば、上の２つは本質的に同じものと言えます。当然結果も同じになります。ただしソルバー の実行時間は駒を上下左右に移動する暗黙の優先順位があるので実行時間だけは違いが出ます。 尚、「対称変換」とは以前書いた縦横変換(斜軸変換)のことです。 4:の問題面 斜軸変換後 数値変換後(7:の問題面と同形になる) * c 9 d * f 8 4 * c e d f b a e -------> c b 7 3 -------> f b a 9 8 7 6 5 斜軸変換 9 a 6 2 数値変換 3 7 6 5 4 3 2 1 d e 5 1 4 8 2 1 上の問題の 上の問題の 上の問題の 目標完成図 目標完成図 目標完成図 1 2 3 4 1 5 9 d 1 2 3 4 5 6 7 8 -------> 2 6 a e -------> 5 6 7 8 9 a b c 斜軸変換 3 7 b f 数値変換 9 a b c d e f * 4 8 c * d e f * いまさらと言った感じですが、一応報告だけしておきます。
えへへへへへへへ なかなか凄いモンですね。 初めて見させてもらいました。 うふふふふふふふふふふふふ（ハート）？ でもね、でもね。 ちっとだけぬけてるところがあるんべや。 ３５３５９６６９８８７５４６９９８５４６３２１０５０２３．．０１２２３６５４５６６９８２６４８９５１３５８５６４７１２０．．． このうえの奇妙な数字解読してみて（ハート）？ ヒント：．．．これがーーーーーーー だいひ・ん・と
こんばんは、deepgreenです。 高橋さん、ありがとございました。もう少し、８０手の問題が見つかると思っていましたが、 期待はずれでした。残りは、Ｕ＝８０，８２にあるということですか。 ところで、８０手の問題は、１３個で全てなのでしょうか？ あらさん、ありがとうございます。なんとなくわかりましたが、細かな点はよくわかりません。 （私の語学力の問題とやはり説明がすくないので） 並列マシンで約３日(シリアルマシンでは２３０日相当）とかいてありました。 やはり、そのくらいかかるのかな？ それとも、もっとかかるかもしれない
あらさん、ありがとうございます。 あらさんから教えて頂いた、最長手数=80を最初に発表した論文は、いやはやなんとも 並列コンピュータ処理の宣伝だけのようですね。(千手観音の上手な使い方の概要のみ) 学術論文でパズル問題を前面に押し出すのは日本だけでなく、どこの国でも何かしらの 体裁が必要なようです。 さて、deepgreenさんがしぼりこんだ１７個の候補群の探索結果ですが残り１４個の探索 はアッサリ終わってしまいました。(10時間くらいの覚悟だったのですが) そして、残念 ながら僅かな望みも絶たれました。以下、全１７個の候補群の探索結果です。 1: *cadfbe978624351 //UB : 84 / 92 No.1 -> LB : 66 / 80moves 2038sec 2: *f9dcbae37654821 //UB : 84 / 90 No.1 -> LB : 66 / 78moves 195sec 3: *c9dfbae37624851 //UB : 84 / 90 No.2 -> LB : 66 / 80moves 8516sec 4: *c9dfbae87654321 //UB : 84 / 88 No.1 -> LB : 66 / 78moves 69sec 5: *c9df8ae7b654321 //UB : 84 / 88 No.2 -> LB : 64 / 76moves 131sec 6: *cadfeb937654821 //UB : 84 / 88 No.3 -> LB : 64 / 76moves 24sec 7: *cedfba937654821 //UB : 84 / 88 No.4 -> LB : 66 / 78moves 70sec 8: *fadcbe987653421 //UB : 84 / 86 No.1 -> LB : 70 / 78moves 31sec 9: *cadfbe987654321 //UB : 84 / 86 No.2 -> LB : 68 / 78moves 24sec 10: *fedcba987654321 //UB : 84 / 86 No.3 -> LB : 70 / 78moves 8sec 11: *cadfbe978653421 //UB : 84 / 86 No.4 -> LB : 66 / 78moves 61sec 12: *ca9fbed78654321 //UB : 84 / 86 No.5 -> LB : 66 / 78moves 93sec 13: *fe9cbad78654321 //UB : 84 / 86 No.6 -> LB : 70 / 78moves 33sec 14: *fadcbe978654321 //UB : 84 / 86 No.7 -> LB : 70 / 78moves 28sec 15: *cedf8a9b7654321 //UB : 84 / 84 No.1 -> LB : 66 / 76moves 5sec 16: *cbdfea987654321 //UB : 84 / 84 No.2 -> LB : 66 / 76moves 7sec 17: *cedfba978654321 //UB : 84 / 84 No.3 -> LB : 68 / 78moves 24sec
あらです。 最長手数=80を立証した論文は ftp://ftp.ifor.math.ethz.ch/pub/fukuda/reports/zram970924.ps.gz にあります。
こんばんは､deepgreenです。 あらさん、貴重な情報をありがとうございます。最長手数が８０手というのは 最悪に近いシナリオで、ちょっとショックです。 高橋さん、Ｓｏｌｖｅｒでの解法ありがとうございます。８０手の問題が２問 ありましたか。 とりあえず、Ｕ＞＝８４の結果を以下にｕｐしました。 ＋＋＋で始まる行はコメントです。よろしくお願いします。 http://www2.tokai.or.jp/deepgreen/shortnotes/Uscan84.txt さて、このあとどうしようかと考えています。 現状の道具でＵ＞＝８０がどのくらいの時間が必要かを具体的に検討してみます。 もし、人海戦術で対応できる範囲ならやってみたい。 Ｕｌｉｎｅ，ＵＢｃｈｅｃｋの説明は、そのうちＨＰにＵＰしようと思います。