- 1 名前：名前は開発中のものです。 mailto:sage [04/07/03 08:04 ID:/HqS7Sh0]
- 国産パズルゲームの名作「倉庫番」の問題面を
自動で生成したり解いたりするには
どのようなプログラムを書けばいいでしょうか？
プログラムの達人から初心者まで
興味のある方は是非参加してください。
- 35 名前：名前は開発中のものです。 mailto: [04/07/13 07:26 ID:gifgN+Yd]
- 日経ソフトウエア2004年6月号
地球にやさしいアルゴリズム第8回
倉庫番を解くアルゴリズム
software.nikkeibp.co.jp/software/download/down04c.html
software.nikkeibp.co.jp/software/download/0406/algo0406.zip
さくら美緒、takaken、DeepGreen、疋田輝雄、
どのSolverが最も賢い？
- 36 名前：名前は開発中のものです。 mailto:sage [04/07/27 12:57 ID:H2IKfXqP]
- 人が歩いた歩数でなく、荷物が動いた歩数で考えた方が楽なのだろうか？
- 37 名前：名前は開発中のものです。 mailto:sage [04/07/28 13:16 ID:awaEZIr2]
- 完成状態の盤面を0番として記憶しておく。
初期の荷物の状態を1として、そこから移行できる全状態を2以降の番号をつけて生成し、記憶。
１番からどの番号へ移行できるかも記憶しておく。
続いて、２番の状態から移行できる全状態を生成し、記憶。もちろん重複チェックもさせるので
前の番号へ移行できるような状態も作られる。
次々に生成していって、０番への移行ができるような盤面が現れたら解決方法あり。
１番からの深度チェックをしていって、荷物を何手動かしたかの最短を出す。
ただし確実な最短を出すためには全手数のチェックが必要。
解く方のやり方を想定してみたが、こんな感じなのか？
- 38 名前：名前は開発中のものです。 mailto:sage [04/07/28 23:27 ID:OaJflA5G]
- 大体そんな感じだと思う。
＞ただし確実な最短を出すためには全手数のチェックが必要。
幅優先探索でやれば最初に見つかったのが最短手順。
「幅優先探索」で検索してみて。
＞もちろん重複チェックもさせるので前の番号へ移行できるような状態も作られる。
？ 前と同じ状態に戻る場合は発生させなくてよいと思う。
- 39 名前：名前は開発中のものです。 mailto:sage [04/07/29 01:54 ID:EpgRoJim]
- 指数オーダーで状態が増えていくから全列挙ベースじゃ規模の小さい問題しか解けない。
これは探索の方向を変えたところでどうしようもない。
人間が解いて面白いような規模の問題を解くのは無理っぽい。
で、どうするかというとA*とか分枝限定法とかの下界値を利用して枝刈りするような手法が使われる。
もっともそっちの世界でも倉庫番は難しい問題として知られてるから、良い方法が作れればそれだけで論文書けるかも。
まあ、そこまでいかなくても単純なA*くらいは入れた方が良いと思う。
経路探索にも使える（というかそっちの方が多い）から知ってて損はないし。
- 40 名前：37 mailto:sage [04/07/29 05:40 ID:4YxMTCfg]
- ご意見どうもでつ。なるほど、かなり奥が深そうだ。
調べてみたら、双方向探索とか行き詰まりのつぶしとか色々あるようだし。
- 41 名前：名前は開発中のものです。 mailto:sage [04/08/01 03:05 ID:Q2G2XU2Z]
- プログラムによる自動生成全52面
ttp://www.ne.jp/asahi/ai/yoshio/sokoban/auto52/index.html
- 42 名前：名前は開発中のものです。 mailto:sage [04/08/01 11:46 ID:YiQa0gMz]
- >>41
そのプログラムそのものはどこかにないの？
- 43 名前：名前は開発中のものです。 mailto:sage [04/08/01 14:16 ID:VNo3uGvt]
- 移転前
ttp://web.archive.org/web/20020609073807/www.ne.jp/asahi/ai/yoshio/sokoban/main.htm
自動生成のプログラムそのものはないみたい
- 44 名前：名前は開発中のものです。 [04/08/07 00:22 ID:xSvexrpg]
- この小田原研究が見たいが、見つからない。
ttp://www.graco.c.u-tokyo.ac.jp/kawai-kaneko-lab.html
- 45 名前：名前は開発中のものです。 mailto:sage [04/08/07 00:35 ID:XI18DeZP]
- >>35をコンパイルしたの頂けないでしょうか
- 46 名前：名前は開発中のものです。 [04/08/07 10:54 ID:t8/IjFAc]
- >>45
バイナリじゃないんだ。。。
readme.txtによるとBorland C++ Compilerでビルドせよとのこと。
Borland C++ Compilerは以下から無償で入手できるよ
www.borland.co.jp/cppbuilder/freecompiler/bcc55steps.html
メール登録(無料)が必要らしいね。
さすがにユーザー登録的な手続きまでするのは面倒くさいから
気が向いたら自分でチャレンジしてみて。
コンパイル自体は楽勝で誰だって出来るから
- 47 名前：名前は開発中のものです。 mailto:sage [04/08/09 07:53 ID:LuKJ2ExA]
- いきなりネタ無くなってる感がするんだが
他のパズルの自動プログラムもＯＫ？
- 48 名前：名前は開発中のものです。 mailto:sage [04/08/09 14:22 ID:Bm7y7lhR]
- 基本は変わらないし、参考になるから
いいんじゃないか？
- 49 名前：名前は開発中のものです。 mailto:sage [04/08/09 18:45 ID:BKqxHMzO]
- それじゃ、昔やったナンバーリンクの自動解答に挑戦してみる。
- 50 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 00:00 ID:50wtaTHU]
- 49だが、ハンドルさらし。とりあえず今日は面を読み込んで表示するところまでできた。
で、ナンバーリンクとは何かだが、ぐぐれば判るとおりマス目に書かれた同じ数字を
線で結んで全部繋ぐ紙面パズル。だが、これが別解を見つけるのが異様に困難な
パズルだったりする。複数解があるのは紙面パズルとして致命傷。
ショートカットでつなげられる答えがあるなどもってのほかだったりする。
自動で解くプログラムはいくつかあるようだけど、線が通らないマス目がある別解は
見つけられない。なので自分が挑戦してみようかと、こういう経緯。
- 51 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 00:08 ID:50wtaTHU]
- んで実際にどうみつけるかだけど、いろいろ探ってみたところ
ここに線が引かれるはずだから、あーしてこーして・・・なんて線を延ばすやりかたがほぼ全部。
でも、このやりかたって、ショートカット解はみつけられなかったりするんだよな。
なんたって角地に線が通ることをまず確定させてるし。
で、自分が考え出したパターンはこれとは違い、線ではなくて壁を見るやりかた。
線を引かない部分を壁として、その壁の有無を総あたりでチェックする方法。
具体的なやりかたは次回に。
- 52 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 11:21 ID:x1eX9+9e]
- すまんけど、解説するとかなり長々した文になりそうだ。
スレ乗っ取りになりそうなので、どこか別の糞スレに移って
そこで解説したほうが良さそう。
- 53 名前：名前は開発中のものです。 mailto:sage [04/08/10 13:28 ID:xunPxqDS]
- >>52
いや、このスレもうほとんど止まってたし・・・このまま進めて欲しいな
- 54 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 20:33 ID:P6c4IZR0]
- >53
そうか、ならば・・・
- 55 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 20:34 ID:P6c4IZR0]
- ,ｨｨr-- ..__､j
ﾙ! { ｀ヽ, ∧
N { l ` ,、 i ＿|＼/ ∨ ∨
ゝヽ _,,ｨjjハ、 | ＼
`ニr‐tﾐ-rr‐ｔｭ<≧rﾍ > ここはしばらくMNR（もっとナンバーリンクの会）が
{___,ﾘ ヽ二´ﾉ }ｿ ∠ 乗っ取らせてもらうことにする！！
'､ `,-_-ｭ u /| ∠
ヽ`┴ ' ／／l＼ |／＼∧ /
--─‐ｧ'| ｀ニ--‐'´ / |`ｰ ..__ `´
く__レ1;';';';>､ / __ | ,=､ ___
「 ∧ 7;';';'| ヽ/ _,|‐､|」 |Ｌ..! {L..l ))
| |::.V;';';';'| /.:.|トl｀´.! l _,,,ｌ | _,,| , -,
! |:.:.:l;;';';';'|/.:.:.:||=|=; | | | | .l / 〃 ))
l |:.:.:.:l;';';'/.:.:.:.:| ! ヽ ＼!‐=:l/ `:lj 7
| |:.:.:.:.l;'/.:.:.:.:.:.! ヽ:::＼:: ::::| ::l /
- 56 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 20:35 ID:P6c4IZR0]
- ＿人人人人人人人人人人人人人人＿
＞ な なんだってー！！ ＜
￣^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^￣
_,,.-‐-..,,_ _,,..--v--..,_
／ ｀''.v'ν Σ´ `､_,.-'""｀´""ヽ
i' ／￣""''--i 7 | ,.ｲi,i,i,､ ､,､ Σ ヽ
. !ﾍ /‐- 、u. |' |ﾉ-､ ' ` `,_` | /i'i^iﾍ､ ,､、 |
|'' !ﾞ i.oﾆ'ｰ'〈ｭﾆ! iiヽ~oj.`'<_o.7 !'.__ ' ' ``_,,....､ .|
. ,`| u ..ゝ! ∥ .j (} 'o〉 `''o'ヽ |',`i
_,,..-<:::::＼ (二> ／ ! _`-っ / | 7 ￣ u |i'/
. |、 ＼:::::＼ '' ／ ＼ '' ／〃.ヽ `''⊃ , 'v>、
!､＼ ＼. ,￣ γ/|￣ 〃 ＼二-‐' ／／`
- 57 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 20:36 ID:P6c4IZR0]
- _,,.-‐-..,,_
／ ｀''.v'ν
i' ／￣""''--i 7
!ﾍ /‐- 、u. |' ちょ、ちょっと待ってくれよキバヤシ、
|'' !ﾞ i.oﾆ'ｰ'〈ｭﾆ! ナンバー（NUMBER）リンク（LINK）だったら
,`| u ..ゝ! 頭文字はMNLに・・・
<:::::＼ (二> ／
＼::::＼ '' ／
＼ ＼. ,￣
＿
- 58 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 20:38 ID:P6c4IZR0]
-
|丶 ＼ ￣￣~Ｙ～ ､
| ＼ ＿＿ / ＼
|ゝ､ヽ ─ / ヽ |
│ ヾ ゝ＿ ＼ |
│ ヽ＿ ＿ ／ /| |＼ ＼｜
＼ヽ ＿ ／/ / | ＼ ｜
ヽ＼二＿二// ∠二二二| ﾍ| ナワヤ！勘違いをするな！
| | | ヽゝｿゝ|TT|<ゝｿ ﾌ |/ｂ｝ 日本放送協会（NHK）的な
ヾ| ヽ＿__ ﾉ/|| .ミ＿＿ ﾉ | ﾉ 略語だから何の問題もない！
| ⊿ /ﾌ
| u .F二二ヽ /|/
＼. |/⌒⌒| ｲヽ
/. ＼ ＝＝′／ |.| |
￣|｜ ヽ＿＿／ / /￣
＼ヽ＿＿＿＿＿ノ ﾉ
- 59 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 20:38 ID:P6c4IZR0]
- _,,.-‐-..,,_
／ ｀''.v'ν
i' ／￣""''--i 7
!ﾍ /‐- 、u. |'
|'' !ﾞ i.oﾆ'ｰ'〈ｭﾆ! ・・・・・・・・・
,`| u ..ゝ!
<:::::＼ (二> ／
＼::::＼ '' ／
＼ ＼. ,￣
＿
- 60 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 21:24 ID:P6c4IZR0]
- すまん、連続投稿に引っかったから普通に進めることにする。←バカ者
- 61 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 22:11 ID:P6c4IZR0]
- とりあえずナンバーリンクそのものの説明は以下のURLで
ttp://www.nikoli.co.jp/puzzles/4/
で、このパズルだけど解き方の基本としてえいやっと線を引くってのがメインだったりする。
理詰めで少しづつ解いていくんじゃなくて、直感が大半な珍しいパズルでして・・・
で、作る方も同じく直感で作るわけだけど、困ったことに別解チェックがとても大変。
なんたって理詰めで解いていくパズルでないだけに、意外なところから線が引けたり
マス目が全部埋まらないショートカット解があったりと、難儀だったりするんだな。
- 62 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 22:30 ID:P6c4IZR0]
- で、これを解く為のソルバープログラムなんだけど、検索してみたところ
ソフトの存在はベクターに一つだけって状況で、しかもそれはショートカットの別解を
チェックできなかったりする。他のページの日記には、これの解答ソフトは
要望はあるけどモノが無い、と書かれている存在だそうで。
だったら俺が作ってやろうと思い立ったわけで・・・っていうか、実は理論なら
とうの昔にできていて、しかもその内容がとあるトコに掲載されたこともあったりして。
かなり昔のことなんだけどね。資料はまだ残っていたから作成はできるはず。
ただ、今回はこれを別解を確認できるように拡張していくという課題も追加。
- 63 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 22:39 ID:P6c4IZR0]
- さてさて、それで具体的なやり方だけど、上に書いてあるとおりマス目に線を引くんじゃなくて
線を通過しない壁のほうに重みを置いてみる解き方です。
例えば上のニコリのページの問題。一番上の左端のマス目を通る線は
必ず右と下を通過するはずです。普通ならこの角の理論を適用して線を延ばしていくのですが
自分の考えはここからが違う。線を引く部分でなく、線を引かない上と左の壁に注目しました。
判りやすく下の答えを見てみましょう。線を引かない境界の点線に壁を引っ張ると
二つの法則を導きだされます。
「線を引くマスは必ず２方向が壁になる」
「数字の書いてあるマスは必ず３方向が壁になる」
この壁の数を利用して解いていこうというのが、自分の理論です。
- 64 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 22:50 ID:P6c4IZR0]
- 具体的には、あるマスAにおいて上と左の壁数を確認します。
線を引くマスで上と左の壁数が
０なら、右と下は必ず壁になる。
１なら、右か下、どちらかが壁。
２なら、右と下は必ず壁が無い。
数字のマスで上の左の壁数が
０はありえないので、それ以前の壁がおかしい
１なら、右と下両方が壁になる。
２なら、右か下、どちらかが壁。
どちらかが壁の場合、仮に右を壁にして下を無しにしておいて次のマスへ進み
ありえない状況になったら戻って下だけ壁に変更して調べなおし、というやりかたです。
それでも駄目ならさらに前に戻って壁を変更します。
これを左上のスタート地点から右へと進めていって、右端についたら改行して
２段目の左端から、と進めていきます。ようするにしらみつぶしなんですね。
- 65 名前：進可 ◆Sinka1my5k mailto:sage [04/08/10 23:06 ID:P6c4IZR0]
- でもこのしらみつぶし、結構有効な方法だったりします。
線を伸ばしてどっちへ行くのか調べるとなると、それこそ上下左右好きな方向に
進められるので、相手の数字につくまで途方も無いパターンがあります。
が、この方法で調べていくなら少ないパターンで進めていける上に
壁に矛盾が無くなったら、最後に同じ数字同士が連結しているかを
チェックするだけですみます。
とりあえずこの上と左を見るやり方を、ガンマ方式と名づけます。命名理由は変換したらわかるはず。
実際には、これに加えてありえない壁の形になったらNGにするようプログラムした結果
11×11の面を即断で解けるようになりました。はい、実はもうプログラムはできてます。
今日一日でなんとか完成しました。ただ、盤面入力はテキストファイルだし、結果出力は
イメージに文字出力のみだしで、見た目がかなり汚いので発表はまだです。
っていうか、じっくり解説しながら作ろうと思ってたのに、一日でできるとは自分でもおもわなんだ。
というわけで今日はこれにて。
- 66 名前：進可 ◆Sinka1my5k mailto:sage [04/08/11 13:00 ID:0BPyFEfS]
- 続き～
そういえば、まだショートカットの探索方法書いてなかったな。
基本的には同じだけど、ショートカットができるってことは何も通らないマス目があるってこと。
これを便宜的に「壁マス」と呼ぶことにして話を進めます。
で、そこの部分の壁をどうするかだけど、線マスと壁マスの間は必ず壁があるが
壁と壁同士はあっても無くてもいいことになってややこしい。なので、壁マスは四方を必ず
壁に囲まれていると定義しておく。その考えで上の探索に追加。
線を引くマスで上と左の壁数が
０なら、右と下は必ず壁になる。
１なら、右か下、どちらかが壁。
＊２なら、右と下は必ず壁が無いか、壁マスとして両方とも壁。
＊の部分の探索を追加するだけ。ただ、これをやると探索数が一気に増えます。
７＊７のショートカット解のみの面でテスト
ショートカット探索無し：解答0。79回探索。
ショートカット探索有り：解答430。3114906探索。
7＊７ショートカット解なしの面でテスト
短絡無し：解答１。196回探索。
短絡有り：解答０。2992135回探索。
11＊11の面でテストしましたが、短絡ありだと３０分かけても戻ってきませんでした。
これでは実用にならないのでもうちょっと考えて見ます。
- 67 名前：結果のテキスト出力 mailto:sage [04/08/11 18:53 ID:k24CCh2Y]
- ┌─┬─┬─┬─┐
│┏┿━┿━┥１│
├╂┼─┼─┼─┤
│┃│２┝━┥２│
├┸┼─┼─┼─┤
│１│３┝━┥３│
└─┴─┴─┴─┘
こんなのどう？
- 68 名前：進可 ◆Sinka1my5k mailto:sage [04/08/11 23:01 ID:HfZVR1XV]
- >67
そんなふうにやりたいですなー。
ところで、最後に同じ数字を結んでいるかをチェックするのを
壁作成途中でもチェックするようにした結果
7＊７ショートカット解なしの面でテスト
短絡無し：解答１。196→181回探索。
短絡有り：解答１。2992135→435102回探索。
と短くなりました。
（上の短絡有り：解答０。は解答１の間違いです。）
このおかげで15＊15の面を短絡無しで
100秒かかっていたのが１秒かからなくなりました。
でも短絡ありだと10＊10の面で帰ってこなくなるので、まだまだなにか
画期的なアイデアが必要です。
- 69 名前：進可 ◆Sinka1my5k mailto:sage [04/08/12 13:12 ID:FoaiKiVA]
- 最終ﾁｪｯｸ＝マス目に壁が全部埋まった時点で全部の数字の到達先を調べる
途中ﾁｪｯｸ＝現在のマスが数字で上か左が開いていたらリンク先を調べる
改行ﾁｪｯｸ＝マスが一段埋まるたびにマス確定した上段数字マスの到達先を全部ﾁｪｯｸ。
7*7での回数
ｼｮｰﾄｶｯﾄﾁｪｯｸ あり なし
最終ﾁｪｯｸのみ 181 435102
+途中もﾁｪｯｸ 179 303781
+改行もﾁｪｯｸ 167 228814
数は減らせたけど、指数的に減ってないのでダメです。
10*10でｼｮｰﾄｶｯﾄありだと、探索が遅くなるばかりで解ける気配がぜんぜんありません。
ちなみに回数とは、最初のマスの壁の有無を確定して１回、次のマスの壁を確定して2回
という風に数えてます。それを考えると３ケタですんでるのは驚異的なんだけどね。
でもｼｮｰﾄｶｯﾄ探索ありだと、ぜんぜん太刀打ちできないんだよな。
- 70 名前：進可 ◆Sinka1my5k mailto:sage [04/08/12 13:18 ID:FoaiKiVA]
- ところでパズル板ができたね。
hobby5.2ch.net/puzzle/
とりあえず７＊７までならチェックできたし
これ以上の改良は、なんかとてつもなく長くなりそうだから
一旦ここで打ち切って、移動した方がよさげ。
倉庫番探索もそのうち考えます。
- 71 名前：名前は開発中のものです。 mailto:sage [04/08/12 17:51 ID:6v5uYIwl]
- あ゛～、見てるだけで終わってしまった。
- 72 名前：進可 ◆Sinka1my5k mailto:sage [04/08/12 22:00 ID:tDHsu3jM]
- なんか新しいパターンがあったら伝えますですのことよ。
ところで倉庫番で考えてるんだけど、荷物の位置を不確定にできないかなというアイデア。
例えば４×４の空間に荷物一個と人がいるとして
中央四つのどこかに荷物がある可能性がある場合はその場所をBとして
■■■■■■
■ ■
■ B .B ■
■ B .B ■
■ ■
■■■■■■
こんな感じにどれかに存在する可能性がある
- 73 名前：進可 ◆Sinka1my5k mailto:sage [04/08/12 22:01 ID:tDHsu3jM]
- で、それを上に押し付けた場合は
■■■■■■
■ B .B ■
■ ■
■ ■
■ ■
■■■■■■
こんな風に不確定の位置が変わる。
まだ大雑把な考えだから、これからどう発展させるかはわかってませんが
こんなアイデアもあるよということで晒しておきます。
- 74 名前：進可 ◆Sinka1my5k mailto:sage [04/09/17 20:11:24 ID:zbFgFr5N]
- こっちにも報告
ナンバーリンクソルバーが形になったよ。
15*15でも１時間以内で解けます。
ttp://www.interq.or.jp/moonstone/person/numlink/index.html
- 75 名前：進可 ◆Sinka1my5k mailto:sage [04/11/15 16:42:23 ID:KRK43JVG]
- 自主制作報告のほうにもｱｹﾞたけどこっちにも
ttp://gamdev.org/up/img/1872.lzh
とりあえずは２ｃｈ上でやりとりできるようなシステムを作った
ボタンでマップチップのテキストを置く
テキストのセーブ＆ロード
ステップの戻しと前進
プレイ中の面をテキストへコピー
プレイしたステップをテキストへコピー
書き出したステップをプレイ開始時に読み込み
■■■■■■■×
■×××××■■
■×田回回回×■
■×回××回足■
■×回××回×■
■×回回回◎×■
■×××××■■
■■■■■■■×
ddldllURdllluuuuurrrDDDuuullld
dRRDrUllluurD
こういう感じで面と解答ステップのやりとりが２ｃｈ上で可能に。
肝心な作り方と解き方は全然だけどな。
- 76 名前：名前は開発中のものです。 mailto:sage [04/11/15 18:00:20 ID:ci0UTB+u]
- このスレなにげに楽しみにしてるのでがんがれ
- 77 名前：名前は開発中のものです。 [04/12/04 01:52:51 ID:jMAxBzXc]
- あー
- 78 名前：進可 ◆Sinka1my5k mailto:sage [2005/04/09(土) 20:30:09 ID:FzAyxfw2]
- ふと考えた。倉庫番を解くプログラムを作る前に、スライドパズルを
解けるようなプログラムを作らないとダメなのではないだろうか？
もっと考えて、１５パズルを解けるようなプログラムを作らないと
ダメなのではないだろうか？
- 79 名前：名前は開発中のものです。 mailto:sage [2005/04/09(土) 23:52:01 ID:f0QdQ2zj]
- 作れるんじゃね？
- 80 名前：名前は開発中のものです。 mailto:sage [2005/04/09(土) 23:53:30 ID:f0QdQ2zj]
- つーか
ttp://www.ic-net.or.jp/home/takaken/so/15pz/index.html
- 81 名前：名前は開発中のものです。 mailto:age [2006/05/15(月) 15:01:25 ID:iqNZ3zgN]
-
- 82 名前：進可 ◆Sinka1my5k [2006/06/23(金) 01:17:15 ID:rNoNlc0C]
- 【北朝鮮】「悪いやつらをなくそう」 国家公式サイトにオンラインゲーム登場 日本人と米国人の泥棒を退治
ttp://news19.2ch.net/test/read.cgi/newsplus/1150945519/l50
北朝鮮がゲーム作ったと思ったら、ルールも面も日本のパクリだったよｗ
- 83 名前：名前は開発中のものです。 mailto:sage [2006/08/11(金) 14:34:16 ID:XHr3GWC7]
- 状態空間探索も知らずに頑張っていたのか・・・
- 84 名前：名前は開発中のものです。 mailto:sage [2006/08/11(金) 15:36:04 ID:+c/odd+z]
- しかし倉庫番というのはなんでああも中途半端な所へ荷物を「片付ける」必要があるのだろう。
- 85 名前：名前は開発中のものです。 mailto:sage [2006/08/12(土) 06:15:40 ID:2SZsaOQK]
- >状態空間探索
詳しく
- 86 名前：名前は開発中のものです。 mailto:sage [2007/01/07(日) 01:43:57 ID:3utMDeTC]
- >>75
最近、倉庫番のはまりだまして活用させて頂いております。
大変ありがとうございます。
- 87 名前：名前は開発中のものです。 [2007/07/21(土) 13:46:08 ID:ZgxFvFBu]
- 携帯版 倉庫番Firststep の37面が
かれこれ数年解けません orz
- 88 名前：名前は開発中のものです。 mailto:sage [2007/07/26(木) 04:13:55 ID:MyeVtBFN]
- 絶対荷物を移動させない位置を塗り潰し
荷物ごとに可動範囲を設定
目標には置ける可能性のある荷物のインデックスでも持たせる
ある程度絞り込めそうだけど、どうだろ
書いてると作りたくなるｗ
- 89 名前：名前は開発中のものです。 mailto:sage [2008/08/12(火) 14:02:26 ID:X38yz9YK]
- vintermann.paranoidkoala.org/archives/000077.html
この人のがどうなったのか気になる
なんかすごい自信満々なんだがソルバがおいてない…
- 90 名前：名前は開発中のものです。 mailto:sage [2008/11/15(土) 17:39:16 ID:50CPL4Xv]
- YASGenあるじゃん
- 91 名前：名前は開発中のものです。 mailto:sage [2010/08/27(金) 23:10:51 ID:ys+uGMbs]
- 人がうろうろさせると探索空間が発散するので、
人の厳密な位置を無視して、
荷物の配置だけを状態とみた木で探索したら
木が小さくなったりしないかな。
荷物の配置が決まると「荷物を押さずに動ける範囲」という
部分空間がいくつかできる。
人の位置は、今どの部分空間にいるか？という情報だけに縮退させる。
最短解は出ないけど、荷物の移動回数の最短解と言う形でとりあえずの解は
効率的に出せそう。
このアプローチで組むのってすでにいっぱいやられてたりする？
- 92 名前：名前は開発中のものです。 mailto:sage [2010/08/28(土) 12:58:32 ID:nNbfcnRU]
- 自分は聞いたことはないな。
しかし、情報は「どの部分空間にいるか？」で持つよりも
「荷物をどっち方向に動かせるか？」で持った方が良くないか？
- 93 名前：91 mailto:sage [2010/08/28(土) 19:05:52 ID:9E55durh]
- >>92
なるほど。
今のところ、部分空間の内で一番数字の若い位置を
その部分空間を特定する情報にして組み始めてた。
確かに >>92 まで出してからデータベース化した方が
最探索時に早いね。
データ量と一致判定の速さもそんなに変わらないし。
そっちに変えてみよう。
- 94 名前：91 mailto:sage [2010/09/01(水) 00:05:03 ID:dLsy+EFF]
- うーん。xsokoban の screen.1 すら解けないな(笑)
７段目くらいで8000×3500程度の探索済み重複チェックが終わらない。
盤面みると全然進んでない。
まあハッシュすら使ってないし仕方ないか
- 95 名前：名前は開発中のものです。 mailto:sage [2010/09/26(日) 01:56:41 ID:EUCOONMp]
- 意外に一般的なやり方のようでした。
意外でもないわ。
- 96 名前：名前は開発中のものです。 mailto:sage [2010/09/26(日) 02:11:47 ID:maTkzKHY]
- そうなの？
- 97 名前：名前は開発中のものです。 mailto:sage [2010/10/17(日) 01:11:39 ID:js/8V7SC]
- google 上位の pdf の初心者向けソルバ解説とかそれだった
その後、ゴール部屋の中での最後の荷物整理部分をなくして、
ゴール部屋の玄関までくれば荷物が消えるようにしてxsokoban の screen.1 はクリアした。
ヒューリスティック過ぎて好きじゃないが。
ゴール部屋の自動検出も一応考えたが、実装がちょっと大変そう…
XSokoban は結構この手の無駄に広いゴール部屋があるのよね。
ソルバ対策？
- 98 名前：名前は開発中のものです。 mailto:sage [2012/01/06(金) 23:52:10.91 ID:mG+XCcAE]
- こんな記事がITproにあった
地球にやさしいアルゴリズム
第8回 倉庫番を解くアルゴリズム
itpro.nikkeibp.co.jp/article/COLUMN/20070411/268003/
|
 |
