お気づきの点や感想要望などなんでもOK!
はじめまして、nezusともうします。 コンピュータと勝負できる自動回答15パズルゲームを作成しました。 乱数で作成したパズルの回答を短時間で出す必要があるため最小手数回答にはなっていません。 人間思考形ともいえるアルゴリズムですが、最後に残る5パズルのところだけは最小手数回答になっています。 プログラムをVBScriptに移植し昨日(6/30)アップロードしました。URL は次のとおりです。 ただしVBScriptですのでInternet Explorerでご覧下さい。Internet Explorer以外では機能しません。 http://www5e.biglobe.ne.jp/~nezus/http://www5e.biglobe.ne.jp/~nezus
難しいです。符号理論を勉強してみましたが、ある程度は理解出来たものの 特に線形独立あたりが混乱してしまいます。この理論の応用として、あらさん の見つけてきたマトリックスメソッドがあると思われるのですが、その辺の 絡みを追求すると益々混乱してしまい、なんだか力尽きてしまったみたいです。
こんばんは、deepgreenです。 高橋さんの鋭いコメントでネタバレですが、ちょっとだけ補足させてください。 【符号理論との接点】 この問題(totoのバラ買い)を符号理論(といっても初歩の線形符号)の考え方で アプローチした結果です。 バラ買い:TnD0の問題は、n次元空間をK個の点で構成される部分空間ですきまなく 埋めるような配置を求める問題です。このとき、t字違いをカバーするには お互いの買い目の間の距離は(2t+1)以下であることが必要です。 符号理論:長さnの符号でt個の誤りを訂正する場合、K個の点で構成される部分空間が n次元空間のなかでお互いに重ならないように配置する問題です。このとき、 お互いの符号語の間の距離は(2t+1)以上であることが必要です。 バラ買いではなるべくKを小さく、符号理論ではなるべく大きなKにしたいのは当然です。 高橋さんの指摘のように、バラ買いで最も効率のよい買い方は、お互いの買い目の領域が重 複しないものです。一方、符号理論で最もよい符号とは、n次元空間を余すところなく使う ような符号です。(これを完全符号といいます) この両者の間には、 「バラ買いの理想的な買い方=完全符号」 という接点があります。つまり、長さ13以下の完全符号を見つければ、それはバラ買いの 最適解となるのです。しかし、完全符号の存在は稀であり、バラ買いに使える長さ13以下 の3元符号は以下の3個のみです。 (長さ4 ,情報点2)の3元単一誤り訂正符号 ==> T4D0 (長さ13,情報点8)の3元単一誤り訂正符号 ==> T13D0 (長さ11,情報点6)の3元2重誤り訂正符号 ==> T11D0 【符号語(買い目)の求め方】 符号語を求めるには、以下の性質をもつパリティ検査行列Hを求める必要がありますが、 説明は難しいので割愛します。(興味のある方は符号理論の本を見てください) [パリティ検査行列H] 符号長をn、情報点をk、検査点m(=n−k)の場合、q(=3)を法とするm行 n列の行列で、以下の条件がなりたつものです。 行列Hを構成するn列のベクトルの中から任意の2t個をとりだしたとき、これらが 線形独立であること。ただし、tは誤り訂正可能な数とします。 (長さ13,情報点8)の3元単一誤り訂正符号のHは、本にでていましたが、(長さ11, 情報点6)の3元2重誤り訂正符号のHはなかったので、上記の条件で探索を行いました。 (これが唯一苦労したところ) パリティ検査行列H(m行n列)、n次元符号空間の要素v(列ベクトル) ただし、vは (0,0,...0)〜(2,2,...2) [<--表記の都合で行ベクトル] としたとき、 e = Hv (ただし、3を法とする演算) を求め、eが0ベクトルとなるvの値をリストアップします。これが符号語です。 例:(長さ4、情報点2)の単一誤り訂正符号の場合 H = |1 0 1 2| v = (0,0,0,0)〜(2,2,2,2) |0 1 2 2| とします。これより、e=Hvを計算し、0ベクトルとなる点をリストアップすると 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 の9個(=3**2)が求まります。 上記のどの2つをとっても、距離は3以上となること を確認してください。
deepgreenさん、こんばんは。 T13D0(2等保証)=59049 T11D0(3等保証)=729 この結果は紛れも無く理論的最小値(ヒット数/マルチ数)と同値になっています。 なるほど、ヒット位置が重複しない理論的最小値の解が存在するパターンを探したの ですね。制約的に厳しい探索になると予想されますのでとても見事なアプローチです。 こんな大きなパターンを調べてみようなんて誰も思わないでしょうから、これは素晴 らしい大発見だと思います。
こんばんは、deepgreenです。 ニューロは、難しくて遠い存在と思っていましたが、意外と近いところもある ということですか。面白い結果ですね。 やはり、時節がら、toto(サッカーくじ)のsimulationを検討 しています。(XORSolverの説明はサボって) あらさんの表記でいうと、T13D0の1字違い、T11D0の2字違いの 最適解(それぞれ、59049、729になる)を求めました。 特に、T11D0の結果は注目(2試合の予想が正しければ、3等は確実にと れる)です。しかし、投資に見合ったリターンでなければ意味がありません。 ということで、これからは、投資とリターンに着目したsimulationに フォーカスしてみます。
garumaさんは学校で人工知能の勉強をしているんでしょうか。 そういうことを学校で勉強出来るのは楽しいでしょうね。 今月のCマガジン(2002年/6月号)が人工知能を特集していて、 説明がとても判り易かったので、今現在、夢中になっています。 それでも理解するには大変です。ところが理論は難解でも プログラムは単純なので、こんなのでいいの?ってな感じ...。 さらに理解を深めようとして、たまたま下のURLを見つけました。 ニューラルネットワークの解説をしてるこのURLも、ものすごく 理解し易かったです。CマガとこのURLの説明を基にして、以前に あらさんから教えていただいた「サッカーくじ」の組合せ問題 をニューラルネットワークを使って再挑戦してました。 なんと、マルチ500以内程度なら最適解を見つけてくれました。 アッサリ書いた単純なプログラムなのに....面白いですねぇ。 「ノイズの振幅」(温度)を少しずつ小さくして行くと最適解に 収束しやすくなるという、それだけの「魔法」を初歩的に体験 しただけですが「相互結合型ネットワーク」はパズル問題の 解法にはかなり有効だと実感しました。http://mars.elcom.nitech.ac.jp/java-cai/neuro/menu.html
これは感動しました.
はじめまして. 反復深化A*アルゴリズムを検索しているとこのサイトに当たりました. 自分は人工知能の分野において「探索」という問題について研究しています. なにかいい題材がありましたらかきこんでください. よろしくお願いします.
こんにちは、deepgreenです。 XORの法則「歩数制限の幅を4刻みにしてよい」をとりこんでみました。 あまり期待はしていなかったのですが、意外な効果になりました。 前回 今回の改善版 #309 376.7秒 −−−> 166.6秒 #334 234.1秒 −−−> 92.4秒 #406 103.5秒 −−−> 38.2秒 #719 423.2秒 −−−> 157.7秒 #779 127.5秒 −−−> 64.6秒 一部には全く改善されない面もありましたが、2−3倍と大きく改善され るケースもかなりありました。なによりも、上記の苦手の面に大ききな効 果があったのは嬉しいです。
deepgreen さん、全面クリアおめでとうございます。 719面目で探索時間が最大になったということは、 正しい本格的な作りになっている証拠なのでしょう。 Solverの解説が楽しみです。