強化学習

機械学習の一種，強化学習に関する話題．

入門書：
Reinforcement Learning: An Introduction
Richard S. Sutton and Andrew G. Barto
A Bradford Book

The MIT Press
Cambridge, Massachusetts
London, England
ttp://www.cs.ualberta.ca/%7Esutton/book/ebook/the-book.html

Truncated Temporal Differences を試した方いますか？

ttp://citeseer.ifi.unizh.ch/cichosz95fast.html

適格度トレースの計算量を減らすもののようなのですが，
論文を読みましたが何をどう操作するのか理解できず実装できません．
詳しい方がいましたら解説をお願いします．

強化学習は人気薄なのか．．．

というか，まだしばらくこの板は過疎り続けると思われ
下手な宣伝打てば板ごと消されかねないし，まったりチラシの裏として
使っていくしか．

で，教科書thx．おもろい論文もキボン

マルチエージェント学習に興味があるので，RoboCup Soccerで活躍されてる Stone さんの Survey を紹介します．

　Multiagent Systems: A survey from a machine learning perspective.
　Autonomous Robots, 8(3):345？, July 2000.
　ttp://www.cs.utexas.edu/~pstone/Papers/bib2html-links/MASsurvey.pdf

強化学習にもデータマイニングみたいな面白い応用があればいいのだけれど，
まだ理論的な研究の段階なのか私の寡聞に過ぎないのか，工学的な応用事例が
見付けられません．

あ〜，強化学習のみのスレッドがあるのか．
どうせ過疎なんだから機械学習全般でスレッド立てたら良かったのに……．

>>6
機械学習で作るか強化学習で作るか迷ったのですが，すでにGAや
ニューラルネットの単独スレがあったので．

もう少し育つようなら下のようなリンクをテンプレに持つスレを立てようかと思ってましたが，
どうやら計画倒れのようです．

■□■　機械学習全般　■□■

【ニューラルネットワーク】
　■ニューラルネットワークについて＠シミュレート板
　　ttp://science4.2ch.net/test/read.cgi/sim/1015733653/

【遺伝的アルゴリズム】
　■遺伝的アルゴリズムを学ぼう＠シミュレート板
　　ttp://science4.2ch.net/test/read.cgi/sim/1017102268/
　■遺伝アルゴリズム使ってますか？＠シミュレート板
　　ttp://science4.2ch.net/test/read.cgi/sim/960616675/

【強化学習】
　■強化学習＠情報学板
　　ttp://science4.2ch.net/test/read.cgi/informatics/1156413333/

【進化型計算】
　■進化型計算＠情報学板
　　ttp://science4.2ch.net/test/read.cgi/informatics/1157274058/

あげ

強化学習の応用製品ってどんなのがあるんでしょうか？
正直ロボットに対するいわゆるナビゲーションタスク的なものばかりな
気がしているんですが、どう思われますか？

>>9
AsynchronousなDPなんだから，DPの応用分野で
厳密解を要求されないようなものであれば使えるはず．

>>10
確かに、まぁ強化学習はモンテカルロ法とDPの間のようなもんでしょうから
代用品としてはそれなりに使えるとは思います。
気になったのは強化学習という手法の特色が生きるような使い方があるのか
というなって感じです。

×というなって感じです
○というような感じです

例えばDPでは計算量的に解くことが無理な大規模な問題を，
強化学習で解かせると最適解ではないがそこそこの解を実用的な時間で
返してくれるかも知れない．

問題なのは強化学習で得られた解がそこそこなのかどうなのか判断できない事ですね．

そうなんすよねぇ
自分もまぁ強化学習使って研究してる（修士）んですが、どうも実用的に
使えるのかどうかを判断できないところはあります

そもそも強化学習の扱う不完全な強化（教師）信号から学習するような
問題、言い換えれば、性能向上のためにパフォーマンスを下げるかもしれ
ない探索行動が認められるような問題、が実際的に許容されるのかという
点が頭を悩ませます

ほんと、企業に売り込める強化学習搭載の製品がおもいつかんのですわ。
以上長文失礼。

学習対象が変化しないのであればDynaみたいにオフラインで学習して
greedy方策で運用するという方法でいいのでは？

ところで強化学習の実装するのに何を使ってますか？C言語とかJavaとかでいくつか
ライブラリありますが，どれもしっくりこなくて結局自分で書いたのを使ってるんです．

そうですね。確かに、完全な教師は設定しにくいが、強化信号
（不完全な教師）は設定できるような問題（例えば２足歩行？）
なんかをベースに考えるってのは手なんですけどね。

で、ライブラリですか？
まぁあんまり言うとバレそうなんですが、アルゴリズム自体
の改良を研究のメインとしてますんで、モロ自分で書いてます。
今のところ、Q学習、SARSA、モデルベースな手法、適格度トレ
ースあたりは資産として出来上がってますね。
ただ、階層化の作り方がわからず手をこまねいてるとこです。

なぜ日本人女性は韓国男性に憧れるのだろうか。
まず韓国人男性は紳士的な振る舞いをします。
そして女性を大切に扱います そして情熱的です。
このような韓国人男性の振る舞いに日本人女性はコロリと落ちるのです。
日本人のような幼児的な男性にあきあきしてる裏返しの行動でしょう。
韓国人男性に憧れる日本女性は週末になるとソウルを訪れるそうです。
ソウルで運命的な出会いを期待しての訪韓です
ソウルでは毎週末にお見合いパーテーが開かれています
日本女性と韓国男性のお見合いパーテーです
日本女性の参加者が圧倒的に多く韓国男性を集めるのに苦労するそうです。
日本女性は婚前交渉に積極的だと聞きました。 韓国では婚前交渉はタブーです。
お見合いパーテーで知り合い、その日のうちに関係を持つカップルが多いと聞きます。
「日本人女性は優秀な遺伝子を求めて韓国で股を開く」と韓国のWEBサイトで話題になっていました。
韓国では不道徳なものは、東から来ると言われています。
韓国は日本から多くの不道徳を持ち込まれています。
すべて事実だ。 日本の女は淫乱で男はまったく魅力がないインポ。
かわいそうな劣等民族

やはり自作ですか．．．

代表的な強化学習アルゴリズム一覧
ttp://neuromancer.eecs.umich.edu/cgi-bin/twiki/view/Main/AlgorithmsOfRL

http://nnrl.mine.nu/ss.jpg
なんとなく、
卒研でつくったシミュレータのスクリーンショットを晒してみる。
Actor-CriticなNNです。
ほんとはDynaも入れたかったんだけど、時間切れで就職してそれっきり。。

ベイジアンネットワークのソフトウェアでお勧めなのはどれなのでしょうか？

http://www.cs.ubc.ca/~murphyk/Bayes/bnsoft.html
で比較されてるみたいですが
産総研の人が作ったのがリストにはいってなかったり
情報が間違ってるみたいな部分もあったりで、いまいち信用できません。

>20
おー。
GUIが頭よさそう。３D表示とか。

【福岡・中2自殺】
「あいつ死んで、せいせいした」 いじめ集団、
自殺生徒の通夜で笑いながら何度も棺をのぞきこむ
＜加害生徒の名前リスト＞
亀井義明←主犯
佐藤和彦←No.2、虐め指示、同級生への口封じ役確定
元木　一也←確定
綱島　明←確定
江藤　龍平←確定

ソース元は同級生
名前の確認は非常に近い関係者だ

合言葉は「だってめんどうなんだもーん」byスネーク

コピペよろしく

強化学習の良い応用を思いついたとしやう。

プログラムに強化学習のアルゴリズムを実装すると、「使用者の意図しな
い振る舞い」をさせることになるのだが。

で、そこんとこどうすんのよと。

>>24
つまりそれは良い応用ではないということですね

>>25
まじめにレスすると，
「使用者の意図しない振る舞い」があらかじめわかるということは学習対象についての知識が
すでにあるということですね．
強化学習は学習対象に関する事前知識が全くなくても適用可能な学習の枠組みになっていますが，
事前知識が得られる場合には，ルールベースで意図しない振る舞いを抑制するなりすればいいでしょう．
理論ではなく応用なのですから，その辺は臨機応変にやればいいと思いますよ．

いまいちスレの流れがよめないけど、
応用としてゲームなんかはどうかな。
結果が確率的で変化に富むという点で、
アミューズメント系には向いてるかと。

実際、一生懸命練習（勉強）してる様子を見てると、
それが自分で作ったプログラムだって事以上に楽しかった記憶が。

>>27
>>26を書いたのは>>25です．
名前欄間違いました．すみません．

>>27
ゲームへの応用は古くはバックギャモンとかでやられてるから，
もう少し役に立つ（工学的な）応用例が欲しいところですねぇ．

>>24はロボット制御とかを想定してるんじゃないでしょうか？
２足歩行とかをやみくもに学習させようとすると，アクチュエータを破壊する
行動を取る可能性もあるから，そういう行動をどうやって抑制するのかと．

まあ，まったく的外れかも知れませんが．

役に立つ応用かぁ。

個人的には役に立たない学問があってもいいと思うけど、それは別として。

やはり、全部をオンラインで学習させるのは厳しいですかね。

>>30
>やはり、全部をオンラインで学習させるのは厳しいですかね。
というより強化学習はオフラインでは学習できないものに使うべきものだと思います．

前に、「意図していない学習から、面白い物を作れないか」と問われたことがある。
つまり、現実世界ではありえない動きを作成する手段として作れないか、ということ。
ただこれはCGとかの場合だったので、実際の制御に使用するとなると「人間が意図して欲しい動作」が生まれてくるから、
あまり参考にはならないかもしれない。

意図していない学習を許容できる、工学的な応用例っていうのは難しそうですね。
役に立つ≒無駄な動作を省くって意味では、意図していない動作は許容しにくいし。

強化学習の応用として、ＰＣデスクトップ情報収集秘書を考えてみる。
ＰＤＳ（パーソナル・デスクトップ・セクレタリ）とかなんとか。

ユーザーがＰＣのブラウザからｸﾞｸﾞるのに使用した用語をＰＤＳは学習。
で、ＰＤＳはユーザーがＰＣを使っていない時間やＣＰＵ資源が空いてる時間
にさらにｸﾞｸﾞりまくって、要約集みたいなものを作成してローカルＨＤＤに保存。

ユーザーは、ＰＤＳがせっせと作成した要約集を時々目にして、気に入った
ら「よくできました」と褒めてやる（報酬を与える）。

ＰＤＳは自分の取った行動（ｸﾞｸﾞリ方と纏め方）と報酬期待値と実報酬を蓄積。
繰り返し。いつの日か、ユーザーには欠かせないデスクトップ情報収集秘書の
出来上がり。

仮にこういうのを作成したとすると、プログラムは勝手にｸﾞｸﾞる訳だから、
ワームだのウィルスだのと揶揄される可能性がある。
で、どーすべきなのかと。秘書同士が連絡を取り合うとさらに大変なことに。

>>33
「おまえを消す方法」

>>34

元の情報と似た情報をﾊﾞﾗまいて、元の情報を隠す？

>>33
対話型進化的計算がそんな感じじゃね？
あっちは世代→世代だけど

おちんちんを堅くする方法を教えてください

たくさんの体験をすることにより、学習できます。

ttp://www.uploda.org/uporg651552.jpg

こんなスレがあったとは知らなんだ。

連続タスクとエピソード的タスクについて質問なんですが、
「ある条件に入ったら、状態が初期値に戻る」ことがある場合は
すべてエピソード的タスクってことになるんでしょうか?

>>41
エージェントが探索の開始状態に戻るときにバックアップが初期化される場合はエピソードタスク．
バックアップが初期化されない場合は単に開始状態に状態遷移しただけではないだろうか？

人生は非エピソードタスク…?

>>42
超遅レスになってしまって済みません。
なんかちょっと理解できたように思います。
ありがとうございました。

強化学習なんてのもあるんですね。初めて知りました。

ところで、機械学習のいい入門書を知っていたら教えてください。
洋書がいいです。当方元々数学屋でしたが、ちょっと興味があるので

なんで要所が良いんだろう。

追加学習の入門書ってあります？

>>47
NNのスレで聞いてみては？

>>46
要所が読める人にっとては、
誰かの手によって訳された本よりも
細かいニュアンスがつかみ易い。

>>45
ものっそ遅レスになるけれど最近なら
http://www.amazon.co.jp/dp/0387310738
が一押しだと思います．

うちらから見れば20代になってしまえば皆オバちゃん。だいたいスーパーなんて高校生がやるバイトじゃん！２０越えたオバちゃんが遊びたい年頃って言ってんのがバカだと思うｗそんなの高校までっしょ。

どなたか
ttp://www.cs.ualberta.ca/%7Esutton/book/ebook/node64.html
のExample 6.5組んだりしてないでしょうか
Figure 6.11とどうしても合わないんですが･･･

スレ汚しすんません

>>52
グラフの横軸，縦軸の取りかたは合ってるのかな？
Figure 6.11 は横軸が通算の行動数，縦軸が通算のエピソード数になっててちょっと特殊なグラフだけど？
直線より上向きに曲がってるから，学習の進行とともにエピソードあたりのステップ数が少なくなるということ
だね。追試した訳じゃないけど，普通に学習できてればそうなるような気がする。

>>53
ありがとうございます
軸の取り方は合っていますが、どうしてもこの形のグラフが得られないんです
α＝0.1、壁方向の行動を選択可
の条件で試すと、8000ステップで38エピソードしか進まないと言う･･････

ＨＰのＦＡＱにα＝0.5の方が良いとか書いていたので、それで試してみるとエピソード数は178まで行きますが、傾きが全然よろしくない。
どうしても見本のような良い収束性が得られません

未だどこかプログラムに間違いがあるのか、それとも･･････

にしてもコレに載ってる例題は、ことごとく条件が全部書いていないのでプログラムを組むのに無駄に時間がかかるなぁ･･･

追試してみた。
たしかに alpha = 0.1 では再現しないね。
alpha=0.5でやった結果はこんな感じになった。（100回の平均値）
ttp://www-2ch.net:8080/up/download/1185907018531701.SehkbE
alpha=0.1でも時間ステップを多くとれば同じようなグラフにはなるみたい。

一応学習パラメータを示しておく。
alpha=0.1, gamma=1.0, epsiron=0.1,
ステップ毎に -1 の報酬。

ただ環境の難しさ自体は風が吹いても普通のMazeと変わらないから，
あんまり気にするような問題でもないと思うよ。

jikan=0
*main
jikan++
if jikan \ 10 = 0 : 処理

>>55
超遅レスすいません。
ありがとうございます。
安心しました。
こういうのってグラフと照らし合わせるぐらいでしか自分のプログラムの妥当性が分からないんですよね・・・

強化学習のコンペが行われるようです。
ttp://rl-competition.org/

おー。情報thx

行動価値関数Q^{\pi}に対するBellman方程式って
これであってますか?

Q^{\pi}\left(s, a\right) = \sum_{s'} P^{a}_{ss'} \left[R^{a}_{ss'} + \gamma \sum_{a'} \pi\left(s', a'\right) Q^{\pi}\left(s', a'\right)\right]

↓はてなのmimetexを借りてひょうじさせるとこんな幹事。
http://d.hatena.ne.jp/cgi-bin/mimetex.cgi?Q^{\pi}\left(s,%20a\right)%20=%20\sum_{s'}%20P^{a}_{ss'}%20\left[R^{a}_{ss'}%20+%20\gamma%20\sum_{a'}%20\pi\left(s',%20a'\right)%20Q^{\pi}\left(s',%20a'\right)\right]

参考→上記の病院のｈｐ（専門外来およびすべて）各学会専門医名簿(例　循環器→循環器学会）
上記の病院発行の請求書（領収書）　　　　六法全書
　　　空中伝播式非接解超音波画像解析（書籍)

￥ 年賀状　　　　　￥

謹賀新年　　明けましておめでとう。所沢　よいとこ　一度はおいで

バカ玉県所沢氏　吉川病院　吉川＜鶏＞哲夫　様（所沢氏医師会副会長、所沢氏看護学校長）
バカ玉県　 警察所沢氏署　掃溜め課
　 　署長　禿げ頭　及び　部下の忠犬　八公　様

２００５年８月より上記、バカ玉県所沢氏　吉川病院　吉川＜鶏＞哲夫　様の
くだらない妄想により､バカ玉県　警察所沢氏署　掃溜め課による超音波盗聴
および超音波盗撮および超音波を利用した人体への電波攻撃、人をかいした
嫌がらせ＆ほのめかし行為（八公、警察の掃溜め課の天下り先、近隣住民）、
電磁波盗聴（テンペスト）、車両での暴音走行によって　「違法」に迷惑をかけられています。
　今年もあいもかわらず知能のない嫌がらせを繰り返しするのでしょうが
ひとつお手柔らかにお願いします。くれぐれもあなたが行なう不正請求（こっそり加算）
にはお気をつけください。詐欺罪にあたります。なお、専門医資格のない専門外来
についても多々疑問があります。無資格専門外来医　吉川病院　吉川＜鶏＞哲夫　様

天網恢恢、そにして、洩らさず。

という言葉もございます。くれぐれも死後の世界での
因果応報にご注意、お気をつけ下さい。
　　　　　　　　　　　　　　　被害者一同

入力データの正規化とNN構造の設計最適化までやってくれる強化学習アルゴリズムはありますか？

たとえばロボットなどですと、隣り合ったセンサからの入力がほぼ同じになってしまったり、
一つのセンサだけノイズが乗ったり、拾える信号が小さかったりなど、入力データに偏りが
出ることが避けられないと思います。これらを適切に処理するアルゴリズムとかはあるのでしょうか？

>>62
ある、だが教えない、自分で検索しろ。

>>63
統計学の主成分解析を調べていますが、計算が魔術的すぎて実装できません！

>>64
ただの行列操作が実装できんのか？

Hi! What about you? anyway thanks for the post. ？<a href= http://buy-viagara.com/viagera/index.html >viagera ？order online usa</a>

ロボの行動学習はどうやれば？
SVM搭載ロボに教示すればいいのか？

SVMがReinforcement Learning?

Hello! How did I do it? Good article. Keep it up <a href= http://vaigra.infi ？nites.net/viagara/index.html >viagara pills</a>

>>67
SVMを理解せず、実装しようとしている時点で意味不明だ。
インストールすれば使えるような考えかたは有料なソフトウエアだけに
しておけ。

Eh.. But I知 getting way ahead of myself. Thank you for your suggestions.<a href= http://pressure.hostingweb.us/tenormin/index.html >tenormin price</a>

Hmmm... Well, believe it or not, Thanks a lot!<a href= http://pressure.hostingweb.us/tenormin/index.html >tenormin discount uk</a>

結局、厳密に設計しないとまともな学習は不可能なんだろう？
研究室の中でしか使えない玩具。

>>73
カエレ

あ

ＰＣの性能は伸びた、、、
ＰＣの性能は伸びた、、、
ＰＣの性能は伸びた、、、

超高性能なＰＣができた、しかし、ソフトウエアは進化しなかった。
原因は？
ハードウエアに頼りすぎ、
学習型人工無能ぐらい８ビットマイコン時代に存在した、その域から越えられない
笑いものｗ

チェスで世界チャンピオンと対等に戦えるほどの
量の変化による質の変化が起きているということも理解できない人ですか？

>>77
人間は学習することで、対象となる現象を分析しその欠点を見出すことができる
つまり量でも全数計算に激しく至らなければ、今後コンピュータが負け続ける
方法を人間が考え出すこともありえる。人間はこんな思考錯誤から科学技術を
生んできた。何時までも量だけで勝てるなんて単細胞なお前だけ。

チェスなどのプログラムの域ではポーカーなどで行われる駆け引きの戦術が
まだまだ、機械的な動きの特徴さえ見出せれば、それに合った戦略を立て
一時的に負けても人間が勝ちつづけることも。
プログラムを作る人が、チャンピオンに勝てない時点で数戦えば
プログラムのほうが不利になるのは必然

機械学習・強化学習の研究の先にあるものが人間の知能と
同じものかはまだ分かりません。だから人工知能と呼ばれるのでしょう。

もし仮りに機械学習・強化学習により獲得される知能が人間の知能と
同一のものであることが証明されたなら、その時にはそれを"知能"と
呼んでも構わないと私は思います。

ところで、人間がある事象を学習するメカニズムははっきりと解明されている
訳ではなく、学習が出来るという事実が知られているに過ぎません。

この人間の学習のメカニズムを解明するには、もちろん人間の脳の働きを
直接的に研究する脳科学は重要ですが、機会学習のように人間の学習と
似たような結果が得られるメカニズムを構築することにより、人間の学習の
メカニズムを間接的に探究するアプローチも重要だと思います。

# ちなみにですが、試行錯誤は人間の専売特許ではありませんよ。

>>79
試行錯誤 ×
思考錯誤 ○

人の行うのは思考で試行をするには仮説を考えないと（ｒｙ

>>80
2ちゃんねる流のtypoですね、わかります。

>>80
仮説なき試行では、デタラメそのものですね。
乱数で全数探索しているのと同じ。

>>82
どんな問題にも正しい仮説がたてられる人には機械学習は不要ですね。

>>83
仮説を立てるには情報を正しく認知して分析し、分解したり抽象化したり
あらゆる知識との比較を行える基本能力が必須なんだが。

>>84
古典人工知能のお話ですか？

パソコンに詳しい方いますか？

呼んだ？

>>83
アジア訛りで充分だろ
東洋人丸出しの顔で白人気取りに見えんのも逆に痛いし

>>85
高次に抽象化させることは古典的技術でもできないんだが。無知？

2ヶ月前のレスに煽り入れるなよ。

一週間以上前のレスじゃ、５０歩１００歩だろ。

このスレの流れなら２ヶ月なんて一瞬だろ。
つまり90みたいな馬鹿に触るのは（ｒｙ

１つ発言が進むのに（ｒｙ

>>90
２ヶ月前の本人だということを自分で説明しているのは楽しいのか？

4ヶ月前のレスに煽り入れるなよ。

１ヶ月前のレスに煽り入れるなよ。

2ヶ月前のレスに煽り入れるなよ。

age

>>98のIDがSEXageに見えた。惜しいな。
つか下げろよw

2ヶ月前のレスに煽り入れるなよ。

強化学習で15パズルは解けますか？

最適解を求めるには反復深化しかないと思うけど

最適じゃなくてもいいです
完成すれば

解くだけなら人工知能的な手法使わんでも、正解に近そうな局面を探索し続けてやれば解ける。
強化学習を使った解き方はやってみたことがないのでわからん。

つか下げろよw

オマエモナー

15パズルじゃ状態数が多すぎて、盤面に対応した評価値を保存するのが難しいです
なにかよい方法はありますか？

現在の状態と完成状態との距離を評価値として使っているのですがループしてしまいます
ループから抜け出す方法は何かありますか？

なんでループするんだ？
「距離がより小さい状態」を反復深化で探せば、探索終了ごとに必ず完成状態に近い
状態になると思うんだけど。

強化学習と探索を組み合わせた手法は何か無いのですか？

強化学習で迷路探索をしようと考えています
しかし、ランダムに探索を行ってもゴールまでたどり着かないので強化学習ができません
よい方法はありますか？

それは強化学習になってないでしょ
強化学習は、エージェントが環境に対してアクション起こしてそれに対する報酬を受けることで学習していくものなんだ

最初のうちはどのような行動で高い報酬が得られるか分からないからランダムでもいいけど、次第に学習していくんだからランダムな行動選択にならないようにすべき
その点は、Q学習でもSARSA学習でも適格度トレースでもいいけどボルツマン分布に基づくような方策にすればよい

迷路問題の詳しい設定は考慮しないが、ゴールに辿り着いたときに報酬を与えて、壁にあたると報酬を負にしたり(罰を与える)、通路を通るごとに罰を与えるようにすれば、一般的に最小ステップでゴールに到達するようになる

そもそもゴール辿り着けないのは、問題の設定がおかしいか、乱数の精度が悪いか、なんだろう

15パズルを強化学習で解きたいと質問した者です
何回も15パズルをシミュレーションして、最適解（それに近い解）を強化学習で探したいのですが
シミュレーションをしても解にたどり着かず、報酬を得ることができないので、学習を進めることができません
どのようにしたら学習ができるような環境を作ることができるかどなたか分かる人教えてください
お願いします。

>>109 の質問に答えてくれ。

>>114
反復深化や、全探索など探索処理を行えば完成状態に行き着くと思いますが
今回は、強化学習という形で、パズルの完成に行き着けるかを考えています

シミュレーションでの探索は全解を探索してる？
乱数だと、全解を探索するのにかかる時間が（同じ探索を枝切りしないと）えらくかかるよ。

>>116
なるほど、初めは盲目的に全探索（それに近いこと）をして強化学習をするのですね
ありがとうございます、ちょっとやってみます

いやそういうことを言いたいのではなくて。

系統的に全数を探索すれば、n個の選択肢はn回の探索で探索し終わるけど、
単純にランダムで探索してたら、n個の選択肢を全て探索するのにかなりの回数が
かかる、ということ。

単に1回やったルートを除外すればいいだけなのでは？

あ、116に書いてあったわ。ごめん

15パズルなら最適解じゃなくていいなら簡単に解けるのだから
まず確実にゆっくり解く関数を作る。
予め上限を決めておいて、それを超える数まで探索したら
その関数を呼んで総手数を評価値として戻す。