はじめまして、nezusともうします。
コンピュータと勝負できる自動回答１５パズルゲームを作成しました。
乱数で作成したパズルの回答を短時間で出す必要があるため最小手数回答にはなっていません。
人間思考形ともいえるアルゴリズムですが、最後に残る５パズルのところだけは最小手数回答になっています。
プログラムをVBScriptに移植し昨日（６／３０）アップロードしました。URL は次のとおりです。
ただしVBScriptですのでInternet Explorerでご覧下さい。Internet Explorer以外では機能しません。
http://www5e.biglobe.ne.jp/~nezus/

http://www5e.biglobe.ne.jp/~nezus

難しいです。符号理論を勉強してみましたが、ある程度は理解出来たものの
特に線形独立あたりが混乱してしまいます。この理論の応用として、あらさん
の見つけてきたマトリックスメソッドがあると思われるのですが、その辺の
絡みを追求すると益々混乱してしまい、なんだか力尽きてしまったみたいです。

こんばんは、deepgreenです。

高橋さんの鋭いコメントでネタバレですが、ちょっとだけ補足させてください。

【符号理論との接点】
　この問題（ｔｏｔｏのバラ買い）を符号理論（といっても初歩の線形符号）の考え方で
　アプローチした結果です。

　バラ買い：ＴｎＤ０の問題は、ｎ次元空間をＫ個の点で構成される部分空間ですきまなく
　　　　　　埋めるような配置を求める問題です。このとき、ｔ字違いをカバーするには
　　　　　　お互いの買い目の間の距離は（２ｔ＋１）以下であることが必要です。

　符号理論：長さｎの符号でｔ個の誤りを訂正する場合、Ｋ個の点で構成される部分空間が
　　　　　　ｎ次元空間のなかでお互いに重ならないように配置する問題です。このとき、
　　　　　　お互いの符号語の間の距離は（２ｔ＋１）以上であることが必要です。

　バラ買いではなるべくＫを小さく、符号理論ではなるべく大きなＫにしたいのは当然です。
　高橋さんの指摘のように、バラ買いで最も効率のよい買い方は、お互いの買い目の領域が重
　複しないものです。一方、符号理論で最もよい符号とは、ｎ次元空間を余すところなく使う
　ような符号です。（これを完全符号といいます）
　
　この両者の間には、
　
　　　　　｢バラ買いの理想的な買い方＝完全符号｣

　という接点があります。つまり、長さ１３以下の完全符号を見つければ、それはバラ買いの
　最適解となるのです。しかし、完全符号の存在は稀であり、バラ買いに使える長さ１３以下
　の３元符号は以下の３個のみです。

　　　（長さ４　，情報点２）の３元単一誤り訂正符号　＝＝＞　Ｔ４Ｄ０
　　　（長さ１３，情報点８）の３元単一誤り訂正符号　＝＝＞　Ｔ１３Ｄ０
　　　（長さ１１，情報点６）の３元２重誤り訂正符号　＝＝＞　Ｔ１１Ｄ０


【符号語（買い目）の求め方】
　符号語を求めるには、以下の性質をもつパリティ検査行列Ｈを求める必要がありますが、
　説明は難しいので割愛します。（興味のある方は符号理論の本を見てください）

　［パリティ検査行列Ｈ］
　　　符号長をｎ、情報点をｋ、検査点ｍ（＝ｎ−ｋ）の場合、ｑ（＝３）を法とするｍ行
　　　ｎ列の行列で、以下の条件がなりたつものです。
　　　行列Ｈを構成するｎ列のベクトルの中から任意の２ｔ個をとりだしたとき、これらが
　　　線形独立であること。ただし、ｔは誤り訂正可能な数とします。

　（長さ１３，情報点８）の３元単一誤り訂正符号のＨは、本にでていましたが、（長さ１１，
　情報点６）の３元２重誤り訂正符号のＨはなかったので、上記の条件で探索を行いました。
　（これが唯一苦労したところ）

　パリティ検査行列Ｈ（ｍ行ｎ列）、ｎ次元符号空間の要素ｖ（列ベクトル）　ただし、ｖは
　(0,0,...0)〜(2,2,...2) ［<--表記の都合で行ベクトル］ としたとき、

　　　　　　　ｅ　＝　Ｈｖ　（ただし、３を法とする演算）

　を求め、ｅが０ベクトルとなるｖの値をリストアップします。これが符号語です。


　例：（長さ４、情報点２）の単一誤り訂正符号の場合

　　　Ｈ　＝　｜１　０　１　２｜　　 　ｖ　＝　(0,0,0,0)〜(2,2,2,2)
　　　　　　　｜０　１　２　２｜　　　

　とします。これより、ｅ＝Ｈｖを計算し、０ベクトルとなる点をリストアップすると

       1   ...   0  0  0  0
       2   ...   2  1  1  0
       3   ...   1  2  2  0
       4   ...   1  1  0  1
       5   ...   0  2  1  1
       6   ...   2  0  2  1
       7   ...   2  2  0  2
       8   ...   1  0  1  2
       9   ...   0  1  2  2

　の９個（＝３＊＊２）が求まります。　上記のどの２つをとっても、距離は３以上となること
　を確認してください。

deepgreenさん、こんばんは。

　　Ｔ１３Ｄ０(２等保証)＝５９０４９
　　Ｔ１１Ｄ０(３等保証)＝７２９

　この結果は紛れも無く理論的最小値(ヒット数／マルチ数)と同値になっています。
なるほど、ヒット位置が重複しない理論的最小値の解が存在するパターンを探したの
ですね。制約的に厳しい探索になると予想されますのでとても見事なアプローチです。

こんな大きなパターンを調べてみようなんて誰も思わないでしょうから、これは素晴
らしい大発見だと思います。

こんばんは、deepgreenです。

ニューロは、難しくて遠い存在と思っていましたが、意外と近いところもある
ということですか。面白い結果ですね。

やはり、時節がら、ｔｏｔｏ（サッカーくじ）のｓｉｍｕｌａｔｉｏｎを検討
しています。（ＸＯＲＳｏｌｖｅｒの説明はサボって）

あらさんの表記でいうと、Ｔ１３Ｄ０の１字違い、Ｔ１１Ｄ０の２字違いの
最適解（それぞれ、５９０４９、７２９になる）を求めました。
特に、Ｔ１１Ｄ０の結果は注目（２試合の予想が正しければ、３等は確実にと
れる）です。しかし、投資に見合ったリターンでなければ意味がありません。

ということで、これからは、投資とリターンに着目したｓｉｍｕｌａｔｉｏｎに
フォーカスしてみます。

garumaさんは学校で人工知能の勉強をしているんでしょうか。
そういうことを学校で勉強出来るのは楽しいでしょうね。

今月のＣマガジン(2002年/6月号)が人工知能を特集していて、
説明がとても判り易かったので、今現在、夢中になっています。
それでも理解するには大変です。ところが理論は難解でも
プログラムは単純なので、こんなのでいいの？ってな感じ...。

さらに理解を深めようとして、たまたま下のURLを見つけました。
ニューラルネットワークの解説をしてるこのURLも、ものすごく
理解し易かったです。ＣマガとこのURLの説明を基にして、以前に
あらさんから教えていただいた「サッカーくじ」の組合せ問題
をニューラルネットワークを使って再挑戦してました。

なんと、マルチ５００以内程度なら最適解を見つけてくれました。
アッサリ書いた単純なプログラムなのに....面白いですねぇ。

「ノイズの振幅」(温度)を少しずつ小さくして行くと最適解に
収束しやすくなるという、それだけの「魔法」を初歩的に体験
しただけですが「相互結合型ネットワーク」はパズル問題の
解法にはかなり有効だと実感しました。

http://mars.elcom.nitech.ac.jp/java-cai/neuro/menu.html

これは感動しました．

はじめまして．
反復深化A＊アルゴリズムを検索しているとこのサイトに当たりました．
自分は人工知能の分野において「探索」という問題について研究しています．
なにかいい題材がありましたらかきこんでください．
よろしくお願いします．

こんにちは、deepgreenです。

ＸＯＲの法則｢歩数制限の幅を４刻みにしてよい｣をとりこんでみました。
あまり期待はしていなかったのですが、意外な効果になりました。

　　　　　　　　　前回　　　　　　　　　今回の改善版
　　＃３０９　　３７６．７秒　−−−＞　１６６．６秒
　　＃３３４　　２３４．１秒　−−−＞　　９２．４秒
　　＃４０６　　１０３．５秒　−−−＞　　３８．２秒
　　＃７１９　　４２３．２秒　−−−＞　１５７．７秒
　　＃７７９　　１２７．５秒　−−−＞　　６４．６秒

一部には全く改善されない面もありましたが、２−３倍と大きく改善され
るケースもかなりありました。なによりも、上記の苦手の面に大ききな効
果があったのは嬉しいです。

deepgreen さん、全面クリアおめでとうございます。

７１９面目で探索時間が最大になったということは、
正しい本格的な作りになっている証拠なのでしょう。
Ｓｏｌｖｅｒの解説が楽しみです。