- 1 名前：名前は開発中のものです。 mailto:sage [04/07/03 08:04 ID:/HqS7Sh0.net]
- 国産パズルゲームの名作「倉庫番」の問題面を
自動で生成したり解いたりするには
どのようなプログラムを書けばいいでしょうか？
プログラムの達人から初心者まで
興味のある方は是非参加してください。
- 2 名前：名前は開発中のものです。 mailto: sage [04/07/03 08:04 ID:/HqS7Sh0.net]
- 公式
www.sokoban.jp/
クローン
perso.wanadoo.fr/mrbozo/sokoban/
www.sourcecode.se/sokoban/
www.sokomind.de/
問題面集
levels.sokomind.de/
www.sourcecode.se/sokoban/levels.php
- 3 名前：名前は開発中のものです。 mailto: sage [04/07/03 08:05 ID:/HqS7Sh0.net]
- まずは、縦10 x 横10、荷物3個くらいまでの
小さな問題面(を作る・解く)からだと思うのですが
何から手をつければよいのやら
作るためにはまず解けなければならないのか、
それとも解くルーチンが脆弱でもそこそこは作れるのかな？
- 4 名前：名前は開発中のものです。 mailto:sage [04/07/03 08:31 ID:7RtovP1J.net]
- >>1
疋田センセにでも聞け。糸終
- 5 名前：名前は開発中のものです。 [04/07/03 08:56 ID:T5561hDd.net]
- 解けない面を作られても困るし作るよりも解く方が先。
で、そいつで解けるレベルのものなら作れると
- 6 名前：名前は開発中のものです。 mailto:sage [04/07/03 13:20 ID:QlamLHhp.net]
- >>1
www.ic-net.or.jp/home/takaken/so/soko/index.html
www.ic-net.or.jp/home/takaken/nt/soko/index.html
- 7 名前：名前は開発中のものです。 mailto: sage [04/07/04 11:07 ID:39IxYScY.net]
- 荷を引っ張る倉庫番プログラムなら簡単に問題作成できそう
- 8 名前：名前は開発中のものです。 mailto:sage [04/07/04 20:54 ID:WaLy+q++.net]
- どっかで問題作成をプログラミングしてたような気がするが、どこだったかは忘れた
- 9 名前：名前は開発中のものです。 mailto: [04/07/05 09:54 ID:NuSjOHhl.net]
- 疋田センセの書いたプログラムってネット上には無いの??
bit vol.26-27に紙か磁気で公開されてたりすんのかな。
あったとしても1994年だとWindows上では無理か。
Rogue系みたいに、毎回自動で作られたマップを遊べる倉庫番
なんてのがあるとアツイんだけどなー
- 10 名前：名前は開発中のものです。 mailto:sage [04/07/05 12:13 ID:+7Vba4Jo.net]
- すぐ飽きるとおもう一部の変質者以外
- 11 名前：名前は開発中のものです。 mailto:sage [04/07/05 23:54 ID:n2HoeUWw.net]
- マルチスレか。良い根性してるな。
- 12 名前：名前は開発中のものです。 mailto:sage [04/07/06 21:32 ID:+dqSWx6h.net]
- ＃＃＃＃＃＃＃＃＃＃
＃ ＄ ． ＃
＃ ． ＃
＃ ＄ ＃
＃＃ ． ＃
＃＃＃ ＄ ＃＃
＃＃ ＠ ＃
＃＃＃＃＃＃＃＃＃＃
こんなんばっかになりそう。
- 13 名前：名前は開発中のものです。 mailto: sage [04/07/07 06:30 ID:tnHXX92c.net]
- >>12
そんなんツマンネ
ざっと見た感じ17歩くらいか
難易度設定できたら
少しはマシになるかもな
n=ユーザー設定項目クリアに必要な最低歩数;
while(n歩以下で解けたら){やり直し;}
で50歩くらいを設定しとけば
少しは手応えのある面になると思うが
- 14 名前：名前は開発中のものです。 mailto:sage [04/07/07 22:31 ID:+MuW8iQV.net]
- >13
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
＃ ＄ ．＃
＃ ＄ ．＃
＃ ＄ ．＃
＃ ＄ ．＃
＃ ＄ ．＃
＃ ＄ ．＃
＃ ＄ ＠ ．＃
＃ ＃
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
- 15 名前：名前は開発中のものです。 mailto:sage [04/07/07 23:43 ID:u5TlYlHT.net]
- >>13
手数 * (1 / 正当数) = 難易度
とかの方が良くないか？>>14みたいに手数は多いが同時に正当数がいっぱいある奴は当然難易度は下がると。
- 16 名前：名前は開発中のものです。 mailto: sage [04/07/08 10:03 ID:NzVDRXHr.net]
- あとは面の広さか若しくは移動可能チップ数
さらに荷物の数も要素に加えて難易度を算出すれば
精度が高まる気がする。
- 17 名前：名前は開発中のものです。 mailto:sage [04/07/08 17:17 ID:CnPgVFe8.net]
- 倉庫番を解く for Windows
www.ic-net.or.jp/home/takaken/so/soko/index.html
参考にどうぞ
- 18 名前：12,14 mailto:sage [04/07/08 17:49 ID:zY8B1Wlv.net]
- 10×10の中心からランダムに領域を広げていくという方法で作った部屋の例1
＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃
＃ ＃＃＃＃ ＃＃＃ ＃＃＃ ＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃
＃＃ ＃＃ ＃ ＃＃＃ ＃＃ ＃ ＃＃＃＃＃＃ ＃ ＃＃＃＃＃＃＃＃＃＃
＃＃ ＃ ＃＃＃ ＃ ＃ ＃＃ ＃ ＃＃＃＃＃＃＃＃＃＃
＃＃ ＃＃ ＃＃＃ ＃＃＃＃＃ ＃ ＃ ＃＃＃ ＃＃
＃＃＃ ＃＃ ＃＃＃ ＃ ＃＃＃ ＃ ＃ ＃ ＃＃＃ ＃
＃＃＃ ＃ ＃＃＃ ＃＃ ＃ ＃ ＃ ＃＃＃ ＃
＃＃＃ ＃ ＃＃＃ ＃ ＃ ＃ ＃＃＃＃＃＃ ＃
＃＃ ＃ ＃＃＃ ＃＃＃ ＃＃ ＃ ＃＃＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃
- 19 名前：12,14 mailto:sage [04/07/08 17:50 ID:zY8B1Wlv.net]
- 10×10の中心からランダムに領域を広げていくという方法で作った部屋の例2
＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃ ＃＃ ＃＃ ＃＃＃ ＃＃＃＃ ＃ ＃ ＃ ＃ ＃ ＃
＃＃＃ ＃ ＃ ＃＃＃ ＃＃＃ ＃＃＃＃ ＃ ＃ ＃ ＃ ＃
＃＃ ＃ ＃＃＃ ＃ ＃＃＃＃ ＃ ＃ ＃
＃＃＃ ＃ ＃ ＃ ＃＃＃ ＃ ＃＃ ＃
＃＃＃ ＃＃ ＃ ＃ ＃＃＃＃ ＃ ＃ ＃
＃＃＃ ＃＃ ＃ ＃ ＃＃＃ ＃ ＃ ＃＃＃ ＃
＃＃＃ ＃＃＃ ＃ ＃ ＃＃ ＃＃ ＃ ＃＃＃ ＃
＃＃＃＃ ＃＃＃＃ ＃ ＃ ＃ ＃＃ ＃＃＃＃ ＃＃＃＃ ＃
＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃
- 20 名前：12,14 mailto:sage [04/07/08 17:58 ID:zY8B1Wlv.net]
- ＃と全角スペースが同じ幅になるようなフォントで見て下ちい。
- 21 名前：名前は開発中のものです。 [04/07/09 00:11 ID:4wETax93.net]
- ジャーナル アブストラクトVol.39 No.03 - 007
「倉庫番」の問題の自動作成
www.ipsj.or.jp/members/Journal/Jpn/3903/article007.html
ぐぐったらこんなん見つかった
でも会員じゃないと内容読めないみたい
- 22 名前：概要 mailto:sage [04/07/09 03:13 ID:sexttaP2.net]
- 読んでみたけど別段どうという事のない論文だな。
普通にプログラミングの能力のある人なら
考え付きそうな事をやってるだけで。
作ってる問題は 盤は8x8, 荷物は3つ。
リンク先にあるように
・問題作成→解を求める→面白さを評価
というステップを繰り返して、詰まらない問題は自動判定して捨てて、
面白い問題がいくつ出来るか、とかやってる。
実験結果の例
作成失敗 2
解なし 153
解ありだかつまらないと自動判定されて捨てられた 287
解ありでプログラムで捨てられなかった 58
合計 500
500回ループさせて残った問題が58。そのうち筆者が実際に解いて
面白いと感じられた問題が13だったと。
- 23 名前：セックスタップ2 mailto:sage [04/07/09 03:24 ID:sexttaP2.net]
- 部屋の作り方
・初期状態は以下のようにする。
＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃
＃＃ ＃＃
＃＃ ＃＃ ＃＃
＃＃ ＃＃
＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃
これに下の3つのパーツをランダムに投下して部屋を作る。
口口 （3*2の空白パーツ）
口口
口口
口口 （2*2の空白パーツ）
口口
口口口 （3*3の空白パーツの中央に壁）
口＃口
口口口
部屋のパーツを選ぶ事でつまらない部屋が出来ないようにするらしい。
- 24 名前：セックスタップ2 mailto:sage [04/07/09 03:42 ID:sexttaP2.net]
- ゴールをおけないパターンにはどういうものがあるか考察してあり、
（まあ、ある程度考えれば考え付くようなパターン）
それをさけてゴールをランダムに配置。
また同様にある程度考えて荷物と人を配置。
面の作成はそれくらい。
次のステップで幅優先探索で最短の解を求める。
次の評価のステップだが、面白さの評価基準は
(1)手数、(2)荷物の持ち替え回数、(3)遠回り数、(4)部屋の広さ（マスの数）
を基準に判定している。
遠回りというのは、みかけの荷物とゴールの最短距離と
実際に荷物が移動した距離の差、らしい。
（距離は“マンハッタン距離”とか書いてある。）
持ち替えとは今持っている荷物を離し別の荷物を押す事を示す。
荷物の持ち替えが 多く必要な程、面白いと判断されるから、との事。
判定の具体的な数値は
・遠回りせずに解ける
・荷物の持ち替えが3回以下
・解が6手以内
の一つ以上あてはまったら、この問題を捨てる、との事。
考察に置いて、プログラムに実装されているかどうかに関わらず
以下のように述べている。
・荷物の持ち替え数のパラメータは難しさの評価に有効と言える。
・荷物の方向転換。面白い問題では同じ荷物を押し続ける時でも
こまめに方向転換する必要がある傾向が認められる。
・手数。多い方がよいが、単に荷物とゴールの距離が遠いだけの事もある。
・遠回り。発見しやすい遠回りもあるので面白さに直結しない場合もある。
- 25 名前：セックスタップ2 mailto:sage [04/07/09 04:06 ID:sexttaP2.net]
- 考察の続き
・ゴールが邪魔。ゴールが隅の邪魔にならない所にあるのは簡単になりやすい。
面白い問題の多くはゴールを荷物が何度も通過する。
・荷物の軌跡が複雑。荷物の軌跡が他の荷物の軌跡と交差したり
絡み合ってると面白い事が多い。しかし軌跡が重ならなくても
面白いものはある。
実際に作成された問題の例
（＃:壁, ・:ゴール, ＄:荷物, ■ゴール＋荷物, 人:人）
＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃
＃＃＃ ＃＃＃ ＃＃＃＃＃＃＃＃
＃＃ ＃＃ ＃＃ ・ ＃＃
＃ ・ ・＄＃＃ ＃＃人＃ ■＃＃
＃ ＄人 ＃ ＃＃ ＄ ＃＃
＃＃＃＃■＃ ＃ ＃＃ ＃■ ＃＃
＃＃＃＃ ＃ ＃＃ ＃＃
＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃
＃＃ ＃＃ ＃＃ ・ ■＃＃
＃＃・＃＃＄ ＃ ＃＃ ＃ ＃
＃ ・・＄ ＃ ＃＃人＄■ ＃
＃ ＃＄ ＃ ＃＃＃ ＃＃
＃ 人 ＃＃＃ ＃＃＃ ＃＃
＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃
（以上）
- 26 名前：セックスタップ2 mailto:sage [04/07/09 04:27 ID:sexttaP2.net]
- 荷物をゴールに置いて逆の動作で荷物を移動して
問題を作ればいいかなと思っていたんだけど
著者らはそういう事はしていないですね。
- 27 名前：名前は開発中のものです。 mailto:sage [04/07/09 10:34 ID:mw4kM0V8.net]
- なるほど、つまり･･･
１：壁とゴールと人の最終形をランダムで作成。
２：ランダムに一つずつ荷物を引く
３：その形の最短手順を調べる
４：一番手数の多い面を初期配置とする
ってことか。
- 28 名前：名前は開発中のものです。 mailto:sage [04/07/09 10:43 ID:mw4kM0V8.net]
- いや待てよ、２：の引っ張りは、同じ形を繰り返す可能性が高いから無駄が多いかも。
だとしたら･･･
２：荷物を移動させた全パターンを調べる
３：一番最短の手数の多い面を初期配置とする
のほうが速いかもな。
なんか結局上のと似たようなものになってしまった。
- 29 名前：名前は開発中のものです。 mailto:sage [04/07/10 00:11 ID:AGnyOuyl.net]
- どうでも良いがいい加減空白調整してくれ。
読むに至らない論文は内容に依らず勝ちはない。
- 30 名前：セックスタップ2 mailto:sage [04/07/10 00:19 ID:ErOnlOXh.net]
- マカー。
- 31 名前：セックスタップ2 mailto:sage [04/07/10 00:20 ID:ErOnlOXh.net]
- 自分で見てるとバッチリなんですよねぇ
- 32 名前：名前は開発中のものです。 mailto:sage [04/07/10 00:23 ID:AGnyOuyl.net]
- あれ？矯正IDになってる？
- 33 名前：セックスタップ2 mailto:sage [04/07/10 00:26 ID:ErOnlOXh.net]
- ? この板始めてだからよく知らない。（プログラム技術板からついて来た）
- 34 名前：名無しさん＠そうだ選挙に行こう mailto:sage [04/07/11 09:25 ID:YxVEQ1eT.net]
- 漢なら自動プログラムなどに頼るな
- 35 名前：名前は開発中のものです。 mailto: [04/07/13 07:26 ID:gifgN+Yd.net]
- 日経ソフトウエア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.net]
- 人が歩いた歩数でなく、荷物が動いた歩数で考えた方が楽なのだろうか？
- 37 名前：名前は開発中のものです。 mailto:sage [04/07/28 13:16 ID:awaEZIr2.net]
- 完成状態の盤面を0番として記憶しておく。
初期の荷物の状態を1として、そこから移行できる全状態を2以降の番号をつけて生成し、記憶。
１番からどの番号へ移行できるかも記憶しておく。
続いて、２番の状態から移行できる全状態を生成し、記憶。もちろん重複チェックもさせるので
前の番号へ移行できるような状態も作られる。
次々に生成していって、０番への移行ができるような盤面が現れたら解決方法あり。
１番からの深度チェックをしていって、荷物を何手動かしたかの最短を出す。
ただし確実な最短を出すためには全手数のチェックが必要。
解く方のやり方を想定してみたが、こんな感じなのか？
- 38 名前：名前は開発中のものです。 mailto:sage [04/07/28 23:27 ID:OaJflA5G.net]
- 大体そんな感じだと思う。
＞ただし確実な最短を出すためには全手数のチェックが必要。
幅優先探索でやれば最初に見つかったのが最短手順。
「幅優先探索」で検索してみて。
＞もちろん重複チェックもさせるので前の番号へ移行できるような状態も作られる。
？ 前と同じ状態に戻る場合は発生させなくてよいと思う。
- 39 名前：名前は開発中のものです。 mailto:sage [04/07/29 01:54 ID:EpgRoJim.net]
- 指数オーダーで状態が増えていくから全列挙ベースじゃ規模の小さい問題しか解けない。
これは探索の方向を変えたところでどうしようもない。
人間が解いて面白いような規模の問題を解くのは無理っぽい。
で、どうするかというとA*とか分枝限定法とかの下界値を利用して枝刈りするような手法が使われる。
もっともそっちの世界でも倉庫番は難しい問題として知られてるから、良い方法が作れればそれだけで論文書けるかも。
まあ、そこまでいかなくても単純なA*くらいは入れた方が良いと思う。
経路探索にも使える（というかそっちの方が多い）から知ってて損はないし。
- 40 名前：37 mailto:sage [04/07/29 05:40 ID:4YxMTCfg.net]
- ご意見どうもでつ。なるほど、かなり奥が深そうだ。
調べてみたら、双方向探索とか行き詰まりのつぶしとか色々あるようだし。
- 41 名前：名前は開発中のものです。 mailto:sage [04/08/01 03:05 ID:Q2G2XU2Z.net]
- プログラムによる自動生成全52面
ttp://www.ne.jp/asahi/ai/yoshio/sokoban/auto52/index.html
- 42 名前：名前は開発中のものです。 mailto:sage [04/08/01 11:46 ID:YiQa0gMz.net]
- >>41
そのプログラムそのものはどこかにないの？
- 43 名前：名前は開発中のものです。 mailto:sage [04/08/01 14:16 ID:VNo3uGvt.net]
- 移転前
ttp://web.archive.org/web/20020609073807/www.ne.jp/asahi/ai/yoshio/sokoban/main.htm
自動生成のプログラムそのものはないみたい
- 44 名前：名前は開発中のものです。 [04/08/07 00:22 ID:xSvexrpg.net]
- この小田原研究が見たいが、見つからない。
ttp://www.graco.c.u-tokyo.ac.jp/kawai-kaneko-lab.html
|
 |
