お気づきの点や感想要望などなんでもＯＫ！
１５パズルを普通のパソコンを使用して幅優先で解くことは不可能だと判っているので、 どうしても解くつもりなら反復深化で解くことになるでしょう。この時、常套手段として どんな枝刈りを仕込むかというと、 [現在までの手数]＋[以後絶対必要な手数]＞[既に得られた解の最小値] という条件が成立すれば枝刈り出来ます。この式の中にある[以後絶対必要な手数]とは、 例えばある駒が現在の位置からgoal局面の位置に達するまでの単純な距離(縦座標の差＋ 横座標の差)を[１]から[15]までの駒について計算した値の合計値が使えます。 (もしかしたらＭＤ/Manhattan distanceとはこのことなのかな...???) しかし、この枝刈りが有効に働く為には、[既に得られた解の最小値]がないと使い物に なりません。つまり、何んでもいいからとにかく早く解がひとつ欲しいことになります。 その時期が早いほど枝刈り効果は有効に働くし、最小値が更新されればなおさらです。 「何んでもいいからとにかく早く解がひとつ欲しい」という要求を満たし、アワ良くば、 それが最適解かもしれない、悪くてもそれが最適解に限りなく近いはずだとなるととても 美味しい枝刈りになります。そう言うロジックなのだろう(推測)ということですね。 作者本人の真意のほどは不明ですが、とにかくそう言うことであれば納得できますね。 ところで、作者の作ったsubgoalのＤＢは「充分条件のＤＢ」であり、本当に欲しいのは ＭＤの精度を高めた「必要条件のＤＢ」を作るべきだと思います。ＭＤの精度を高める ロジックの発掘が１５パズルの最適解を得るには一番重要なポイントだと思うのですが、 それはさて置き、今回もまたとても勉強になりました。ありがとうございます。
密かに、この質問がでないようにと祈っていたのですが、やはりバレてしまい ましたね。論文には､何ら説明がありませんので､以下の話は私(deepgreen）の 推測です（大うそかも？？） 高橋さんがご指摘のとおり、最初に見つかった解が最適解とはかぎりません。 従って、深さ優先で最短手数を求めるのと同じ考えが必要と思います。 −−−＞ Ｃ2 ＜＝＝ ／ ＼ 初期局面 □−−−−> Ｃ1 ＜＝＝＝＝ □ Ｇｏａｌ ＼ ／ −−−−−＞ Ｃ3 ＜＝ 最初にＣ１（＝Ａ１＋Ｂ１）という解が見つかったとすると、それ以降はＣ１ 未満の手をサーチする。次にＣ２（＝Ａ２＋Ｂ２）という解が得られたとき Ｃ２＜Ｃ１であれば、こんどはＣ２未満の手を探すという手順を繰り返して いくのではないでしょうか？ 最終的には （ｈ＋ＭＤ） ＜ Ｃn ｈ ：ＩＤＡ＊サーチの深さ ＭＤ：Manhattan distance（現在からｇｏａｌまでの距離） （この説明は別の論文にあるようだがどこかは不明） の範囲をすべてサーチしたところで終了となり、Ｃnが最短解となる。
deepgreenさん、面白い情報をありがとうございます。 しかし、ちょっと気になることがあるのでそれを書いてみます。 ある初期局面からあるsubgoalに達するのに最短でA手かかったとす る。そのsubgoalからgoalまではB手であることが逆解き結果のＤＢ を参照して得られる。従ってその初期局面からの最適解は(A+B)手で ある。と言うことなのでしょうか。 (0手目)初期局面 ↓ (４×４探索/反復深化) ↓ (A手目)subgoal(B手目) ↑ (３×３探索/幅優先探索) ↑ goal局面(0手目) しかしここで気になるのはsubgoalのＤＢはgoal局面から逆Ｌ字型 の部分を固定して左上３×３の世界だけで全探索を行って得られた 結果である。４×４の世界をフルに利用すればもっと少ない手数で subgoalとgoalの間をつなぐことが出来る可能性はないのだろうか。 その可能性は無いことを理論的証明しておかないと実験結果の範囲 からだけでは最適解を得る正しいソルバーとは言えない気がします。 それとも、私のとんでもない勘違いなのでしょうか。
すこし前（昨年の１０月末頃）に１５パズルの最適解の話題がありました。 その時は､関連する論文のタイトルまでしか解りませんでしたが、年明けから 倉庫番Ｓｏｌｖｅｒ関連の情報を探していて偶然にも１５パズルの最適化に 関する以下の論文（９６年に書かれた）を見つけました。 論文名：Searching with Pattern Database 著者名：Joseph C. Culberson and Jonathan Schaeffer Department of Computer Science, University of Alberta ＵＲＬ：www.cs.ualberta.ca/~joe/selected.html （論文の概略） (1)subgoalを設定し、 (2)subgoalからgoalまでの最短パスをＤＢ化 (Pattern Database）しておき、 (3)初期局面からsubgoalまでを反復深化（ＩＤＡ＊）で探索する というものです。 (初期局面） （subgoal) (ｇｏａｌ） ＊４８ｃ x ｘｘ３ ＊１２３ １５９ｄ ＝＝＞ ｘｘｘ７ ＜＝＝ ４５６７ ２６ａｅ (3) ｘｘｘｂ (2) ８９ａｂ ３７ｂｆ ｃｄｅｆ ｃｄｅｆ subgoalのｘは、1,2,4,5,6,8,9,a が入る （subgoalからgoalを求めるのは８パズルの問題になっている） Pattern Databaseの作成はgoalからの逆探索を行う Lawrence Livermore National LaboratoryのTC2000(128CPU,1GBmemory） を使用した実験結果では、subgoalなしの探索に比べて１／１０００のノー ド数となった。 Pattern Databaseの作成が１時間弱とありましたので相当な探索時間が 必要とおもわれます。 面白い話ですので興味のある方は原文を読まれることお薦めします。http://www.cs.ualberta.ca/~joe/selected.html
発売元のソフトバンクパブリッシングから連絡があり、見本誌をいただきました。 それにしても当ホームページが１年半も更新が止まっている中、「WATTA」はだいぶ前のもの。 久しぶりに自分で遊んでみたら、たら、たら、、、自分で解けなくなってる。これはヤバイと 必死で挑戦しました。やっとの思いでどうにか解けましたが、Special版とFerak版は悪魔の ように難しかったです。(まるで他人事のようですが本当です)今思うに、解くよりも作るほう が易しかったような気がします。
発売中のPC Computingをみると、高橋さんのパズル(WATTA)が紹介されてました。 2年以上たった今でも人気があるんですねー。驚きました。
一人遊びを総称してそう呼ぶのですか。うーん。 トランプの数ある一人ゲームも皆ソリティア…。 どうもウインドウズのアレが目立ちすぎていて困りモンです(笑)。 回答、ありがとうございました！
麹味噌さん、こんにちは。 「ソリティア」という言葉の意味は分からないのですが、一人遊びのパズルゲーム等を広く ソリティアと呼んでいるようです。ご指摘のゲームは一般に「ペグ・ソリテア」と呼ばれて いますが、やはり単に「ソリテア」と呼ぶ人もいるようです。盤面の形状は色々なタイプが あり一番有名なものがご指摘の「３３穴英国盤」というタイプのようです。 参考文献：Ｃマガジン1996/2号「特集コンピュータパズルへの招待」
パズルというよりも卓上ゲームと言った方がいいのかも知れませんが、 どなたかタイトルを御存知でしたら教えてください。 盤面：７Ｘ７マスの正方形の四隅から２Ｘ２ずつ切り取った十字形（３３マス） コマ：ビー玉等３２個 最初に３２個のコマを並べておいて（中心部１マス空き）、コマでコマを飛び越しながら （隣接したもの同士）、飛び越された方のコマを除いていき、最後に１つだけコマが残る ようにする、というもの。 …なんですが、私の不確かな記憶では「ソリティア」だったと思いますが、各所のＨＰで ソリティアと言うとカードのソリティアばかりで、自信が無くなってます。 元々はヨーロッパあたりの遊び道具だったかと思います。 突然の質問で済みません。
いやーぁ、Ｎ＝１７が存在したのは驚きですね。 最小問題はあきらめて、Ｎ＝１８の問題を探そうかと考えていたところです。 こうなったら、Ｎ＝１７の探索に変更して、年末までがんばります。 (年明けから本業？のSokobanにもどる予定） それにしても凄いことですね。本当にどこまでいけるのでしょうか？