作っちゃうおじさん制作記録ブラウザゲーム制作や暇つぶしに眺められる記事を書いています。未分類(このページは、もっとプログラマ脳を鍛える数学パズルの宣伝も含まれています。宣伝しているかというと、書籍プレゼント企画にめでたく当選したからです。QUESTというサイトをご存知だろうか。プログラマーヘッドハンティングを目的として、難問を解かせるサイトである。実際に遊んでみてほしい。下記リンクの黄色の砦、毒沼ノ試練をクリックしよう。QUESThttps://geek-out.jp/cp/code-quest/ver01/本来の趣旨はこの問題の解答をプログラムに解析させて解かせるものである。プログラムとかわからん!という方も大丈夫、私は人力で解いた。人力でもそこそこ時間をかければどうにかなる。(実はクリア後に高難易度版がある。裏面はさすがに人力では無理。)しかし、これをプログラムに解かせようとすると無茶苦茶難しくなるのだ。良い結果を返すように記述する。組み合わせ爆発により膨大な量の移動パターンが考えられるため、普通にやったら一生探索が終わらない事態になってしまうのである。【参考】組み合わせ爆発とは実際にコードを書いてみたとりあえず、全探索のアルゴリズムを作成したので、実際に動かしてみた。テキストに以下コードをコピーして、.htmlファイルで保存してから実行するだけ動作する。if(_hp>=goalhp){bestroute=route.slice();//もし、目的のhpに達していれば最適解なので通ってきた探索ルートを取得}}else{_map[ny][nx]="S";//そうでないときは回復か毒沼なので、その位置にSを移動besthp=Math.max(besthp,Search(_hp+nmap,_map));//次の位置に移動してSearch関数を再帰的に実行。besthp;//最適なHPを返す}document.write(Search(hp,map,route)+"best:"+bestroute);//Search関数を実行し、その結果と最適ルートを返す};再帰的にルート探索を実行している。深さ優先探索で、とりあえず全通り探索して魔王到達時に目的のHPになっているとそのHPとbestrouteに進むべき方向が記される寸法である。試してみた限りでは、6×6まではなんとか解析できた。7×7になるともう解析不能になってしまった。膨大な数の探索パターンが生まれてしまったからである。ここで大事なのが、「いかに探索パターンを削れるか」である。これを人は枝刈りという。経路探索問題において、ダイクストラ法が最も有名ではあるが、経路に負の値を持つと成り立たないため、この方法は使えない。(ダイクストラ法についてはこのページを見てね。)と、ここまで来て一旦あきらめてしまったのが去年の11月。数学パズルの本で再起を図る寝ぼけてはいけない。ここからは、ヒマさえあれば数学パズルの本を読み込んでいた自分の力を試すときである。ともこの難問を解析するプログラムを作って、数学パズルの本スゲー!という結論に持っていきたいところ。ちなみにこの本、最初の数ページの入門編からしてそこそこ難易度は高い。大まかな処理の流れを説明しているが、コメントアウトなどでコードの意味をほぼ書いていないので、プログラム処理の流れは自力で読み解く必要がある。どちらかといえば、プログラムにある程度慣れた方向けである。頑張ってコードを読み解いていくとなかなか面白いのだ。面白い解き方、より処理を短くする解き方など、目から鱗の内容ばかりである。一問一問そこそこ頭を使わなければならないので、集中力をかなり使うことになる。ちなみに、回答はjavascriptとrubyで書かれている。私はrubyを知らないので、javascriptのコードを見て勉強していた。ここからはこの本で得た知識とセンスを使うことになる。経路探索の枝刈りをしていくか。そこに絞って試行錯誤を以下に記す。・メモ化作戦あるマップが与えられたとき、最適な経路は一通りに定まるはずである。全探索中は、同じマップを何度も計算しなおすことになるから、あるマップでの到達HPを保存しておけば、何度も同じ計算をしなくて済みそう!ということで、書いてみたコードがこちら。(起動しないでください。if(_hp>=goalhp){bestroute=route.slice();//もし、目的のhpに達していれば最適解なので通ってきた探索ルートを取得}}else{_map[ny][nx]="S";//そうでないときは回復か毒沼なので、その位置にSを移動besthp=Math.max(besthp,Search(_hp+nmap,_map));//次の位置に移動してSearch関数を再帰的に実行。besthp;//最適なHPを返す}document.write(Search(hp,map,route)+"best:"+bestroute);//Search関数を実行し、その結果と最適ルートを返す};ダメでした!そもそも、全探索がナンセンスなことにこの時点でようやく気が付きました。最適解にたどり着きそうな経路をさがそう今回は、正解のルートはHP:50以上であれば問題ないはずです。全探索せずに、HP50以上ありそうなルートを深さ優先探索した方がよい気がします。うまくいかなそうな経路を枝刈りして検索してどんどん効率をあげていきます。具体的には、移動歩数が多くなるにつれHPの値は増えていくはず、という性質を利用します。移動歩数が増えれば、その際HPも一定以上でないといけないはず。いうことで、探索途中の現在HPが一定以下(この足切りラインは移動歩数によって決まる)ようにすれば、最適解を発見しやすくなりそうですね。その代わり、足切りラインで正解の経路を刈ってしまい、うまく計測できない可能性もあります。足切りラインをいかに適切に設定するかが重要です。いうことで、足切りライン追加後のコードがこちら。if(_hp>=goalhp){bestroute=route.slice();//もし、目的のhpに達していれば最適解なので通ってきた探索ルートを取得}}else{_map[ny][nx]="S";//そうでないときは回復か毒沼なので、その位置にSを移動besthp=Math.max(besthp,Search(_hp+nmap,_map));//次の位置に移動してSearch関数を再帰的に実行。besthp;//最適なHPを返す}document.write(Search(hp,map,route)+"best:"+bestroute);//Search関数を実行し、その結果と最適ルートを返す};ということで、先ほどのコードの18行目を以下に変更しました。//現在HPが(32+現在歩数/3)よりも小さければ探索終了HP0以下で打ち切りしていた部分の足切りラインを上げていく発想になります。このコードを実行すると、90秒ほどかかりますがきちんと回答を示してくれます。回答を翻訳したものが以下となります。(Routeには数字が出力されますが、これを上下左右に置き換えています。)できた!やったー!!!!!!試行錯誤のためにコードの処理時間を計測しようとはいえ、このコードの処理時間が気になるところ。Date())で引き算をすることで処理時間を計測してみましょう。(ついでに、出力は数字なので上下左右できちんと表示させてみました。if(_hp>=goalhp){bestroute=route.slice();//もし、目的のhpに達していれば最適解なので通ってきた探索ルートを取得}}else{_map[ny][nx]="S";//そうでないときは回復か毒沼なので、その位置にSを移動besthp=Math.max(besthp,Search(_hp+nmap,_map));//次の位置に移動してSearch関数を再帰的に実行。14855msメモ化処理でずいぶんと時間をかけていたことが判明したので、メモ処理を消しておきましょう。原因としては、同じマップはそう何度も出現しないこと、マップ情報が配列なので、文字列化に時間がかかりすぎるためと考えられます。計測前後の処理時間を計測すると試行錯誤がスムーズにいきそうです。今回の経路で変化したHPと足切り設定ラインのグラフです。足切りラインにギリギリつくかつかないかでHPが上下しているため、ギリギリで回答が枝刈りされずに済んだことがわかります。一歩の移動で±1しかなく、変化量が少ないため、今回の方式が成り立つのだと思います。これって足切りラインの設定が無茶苦茶大変そうじゃないですか。いうより、あり得ない可能性を切るよりも、あり得る可能性をどんどん追求していった方が早く解にたどり着きそうです。普通はどうやって解いていくか・・・。調べたところ、どうもビームサーチが有効であることがわかりました。いうことで、次回はビームサーチを使った解析を行ってみたいと思います。長くなってしまったので、今回はここまで!もっとプログラマ脳を鍛える数学パズルで勉強してきます!シェアするツイートフォローするhothukurou関連記事ふと思いついたネタを書き溜めてみるこの記事では、2018年末~2019年1月に、ふと思いついた創作のネタをまとめています。秋葉原の路上で売っていた福袋を開封しました。ブラウザゲー...記事を読むぼくの初合コンのトラウマを世界一わかりやすく共有しますぼくの初合コンのトラウマを世界一わかりやすく共有するために、ブラウザゲームにしました。ヨーロッパの街並みから失礼いたします。作っちゃうおじさんです。会社の鉄棒で、懸垂を10回達成するとある特殊なイベントが発生することがわかりました。今回、偶然にもイベント発生条件を満たした時の話をします。このページでは、創作活動を行う全ての人をハッピーにする思想をご紹介します。「助けてくれ!...記事を読む【検証】まねっこぬいぐるみを二体並べたら永遠に会話し続けるのかまねっこぬいぐるみ二体と戯れる土曜日。かわいいは正義ですね。~心をつかむ物語を求めて~100字で心が動く物語を作ってみました。この物語から喜怒哀楽の様々な感情を想起していただけると幸いです。コメントをキャンセルメールアドレスが公開されることはありません。名前メールアドレスサイト次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。