ホームページへ戻る
倉庫番を解く for Windows Ver7.3
Sokoban copyright(c) 1982- THINKING RABBIT Inc. Japan
倉庫番自動解答プログラムVer7.3 (2021年8月)

  最新バージョンはここ

 ■ Windows版のダウンロード

 実行環境
 Windows 64bit版 メモリ最低4GB(6GB以上推奨)
 ダウンロード
 sokoban73.exe  (282 KB / 圧縮なし)
(2021/09/12 update)  
 インストール方法
 このソフトは「sokoban73.exe」というファイル
 だけで動くので、インストール作業は不要です。
 注意事項
 セキュリティー警告が出る場合。(ここを参照)

【注意】Windows 32bit版 では、動作しません。

 約13年半ぶりに倉庫番自動解答プログラムを更新しました。今回は、XSOKOBANを総て解く事にこだわりましたが、残念ながら他の問題集(レベルセット)に対しては、あまり良い結果を得ることが出来ませんでした。

XSokobanのレベルセットファイル

 ■ 実験とその成績 (解けた数)


レベルセット 問題数 Ver7.2.2 Ver7.3 備考
 XSOKOBAN 90  86  90  詳細
 パーフェクト 306  261  270  詳細
 リベンジ 306  244  250  詳細
 SMALL SET 200  192  192  詳細
         テスト環境
 CPU: Core-i7 10870H 2.20GHz
 メモリ: 8.0GB
 OS: Windows 10 Pro 64ビット
 制限時間: 600秒

 ■ アルゴリズムの解説

 以前のVer7.2.2を実行すると同時に別の探索ロジックを実行します。追加したロジックは2つですが、下記の通り、この2つのロジックは性質があまりに違い過ぎるので、レベル(問題面)によって、どちらか一つを実行しています。

・スレッド1(ロジック1)

 Ver7.2.2と同じものです。(バグの修正あり) 今、目指すべき目標を解析し、そのサブゴールに荷物を運ぶ探索を行い、それが達成されると、新たなサブゴールを解析し、また、そのサブゴールに荷物を運ぶ探索を行なうという動作を繰り返します。
 なお、探索中に表示される倉庫の途中図は、このロジックに基づいた実況中継となっています。ただ、明らかに詰んだ状況で考え込む画像を観ていると、作者は自分の未熟さに泣けてきます...

・スレッド1(ロジック2)

 Ver7.2.2と同じものです。(バグの修正あり) 通常探索と逆解き探索で挟み撃ちを行なうブルートフォース型の探索を行います。
・スレッド2(ロジック3) Ver7.3で追加

 大規模なストック処理が必要になるレベルに対して、それ専用の解析を行います。XSOKOBANでは、#50,#66,#69の3つがそれに該当します。どれもVer7.2.2では解けなかったものです。大きなストック領域に、荷物をどのように配置すれば良いのかを、詰め込んだ後に戻せることまで考慮して事前調査を行います。右図は調査が終了した瞬間の図。赤丸の荷物の移動から倉庫全体が開放された状態となる。
 残念ながら、このタイプのレベル(問題面)は、XSOKOBAN以外では少ないようです。
・スレッド2(ロジック4) Ver7.3で追加

 ロジック2に似たブルートフォース型の探索を行いますが、一定量の通常探索を行った後に、その結果を素にして逆解き用の評価マップを作成し、最良優先探索による逆解き探索を行います。ゴルフのパッティングに例えると、通常探索でホールを大きくして、パッティングの成功率を高めるイメージとなります。
幸いなことに、XSOKOBANの#29を解くことが出来ました。

↓ ↓ ↓


ホームページへ戻る