Sokoban AI Solver - Optimal solutions in your browser

▲ 69enjoyyourlife42 HNでの議論
Sokoban AI Solver - Optimal solutions in your browser

Sokoban AI Solverは、1980年代の古典パズル「倉庫番」をブラウザ上で遊べるようにしたインタラクティブなプロジェクトです。プレイヤーは箱をゴールまで押し、さらに自分自身もゴールに到達する必要があります。このソルバーは、A*アルゴリズムを最適化したもので、各ボードの最短手数をミリ秒単位で証明付きで計算します。ボード1〜14はライブで最適解を表示し、ボード15はオフラインで計算された184手の最適解を再生します。技術的には、ビットマスクによる状態圧縮、ダイヤルバケットキュー、デッドロック枝刈りなど、高度な最適化が施されています。ソースコードはGitHubで公開されており、開発者やパズル愛好家にとって魅力的な内容です。

このソルバーは、単なる解ではなく、証明可能な最短手数を返します。
原文を読む →HNでの議論RSS

HNでの議論

42
  1. TimTheTinker

    「AI」という言葉が古典的な意味で使われているのを見るのが大好きです。昔のAIは魅力的な発展に満ちています。エキスパートシステム、A*探索、任意の解を生成するためのS式上の遺伝的アルゴリズム、SATアルゴリズムは、いつかAGIにスケールするかもしれないとかつて考えられていました。

    次の大きなAIブレークスルーは、少なくとも部分的には、古いAIのアプローチでLLMの決定を制約することによってもたらされるのではないかと疑っています。フランク・コイルは約1か月前、オントロジーがLLMの出力を制約するというアイデアを発表しました: https://www.youtube.com/watch?v=Sir59K8ZDPU

    さらに進んで、エージェントが仮定と既知の事実（信頼度/区間付き）の実行中のリストを保持し、それらを（能動的かつ受動的に）テストし、観察が矛盾するときに更新し、それらに基づいて行動することを、創発的な振る舞いとしてだけでなく、トランスフォーマーアーキテクチャに埋め込まれた証明可能な正しい（古いAIベースの）アルゴリズムとして行えるかどうか疑問に思っています。

  2. GPerson

    「ここで実行されているのは、私が書いたネイティブC++最適ソルバーのプレーンJavaScriptポートです。」

    10年前の古い意味でのAIのように思えますが？

  3. epiccoleman

    自分がこれを楽しんでいることに驚いています。なぜなら、箱押しゲームに対してある種の嫌悪感を持っていたからです。（たぶんポケモンの滑るブロックのトラウマでしょうね、へへ）。克服しつつあると思います（たぶんBaba Is Youの楽しい思い出のおかげです）。

    とにかく、ここで楽しいことの1つは、任意のボード状態からAIソルブをトリガーできることです。特にパズル12では、開始位置の「箱」から脱出するための最初のプッシュが、実行不可能だと諦めていたものが、実際には最適解であることがわかり、興味深かったです。そしてもちろん、ソルバーが私が解いた初期条件に取り組むのを見るのは楽しいです（そしてそれでも私の手数を上回ります）。

    「悲観化」パズルをプレイするのも楽しいかもしれません。つまり、どのようにブロックを動かして、「AIで解く」ボタンを押すのに最大限敵対的な位置を提供できるか？（明らかに、ボード上の初期の移動は数えられません。そうでなければ、行ったり来たりして最も悲観的な（メルに感謝）解を得ることができます。）

    編集: パズル14は奇妙に感じます。超簡単なのに、なぜ14にあるのでしょう？多分、私が見逃している何かトリッキーな点があるのでしょう。おそらくアリーナの形状がA*を難しくしているとか？

    また、15は興味深く、私が気づいていたテーマを強調しています。それは、パズルの最初の動きはかなり固定されているように見え、AIが私の解から手数を削る場所は、ゴールへの箱の「積み重ね」への巧妙なアプローチにあるということです。書き出してみると、それはかなり明白に思えます。

    とにかく、何か[…]ありがとう。

  4. npinsker

    直感的に、最終ボードもブラウザで処理できるかもしれないと感じます。WASMを使用してソルバーを高速化すれば。

    疑問: 状態が過度に圧縮されているのでは？(箱、[キーパーが押さずに到達できるすべての位置])を(箱、代表的なキーパー位置)の代わりに保存することで、キーパーが歩き回る再計算を減らせるのでは？

    疑問: A*は逆効果なのでは？明白なヒューリスティックには罠があるのでは？BFSの方が良いのでは？

    疑問: 検索は実際には「歩行状態」をスキップせず、キュー内の各要素の処理に隠しているだけなので、キューに追加する方が実際には速いのでは？

    疑問: 組み込める他の単純な枝刈りテクニックはありますか？SOTAのSokobanソルバーからの学びはありますか？例えばこれ: https://ieee-cog.org/2020/papers/paper_44.pdf

    多くの興味深い質問があります...残念ながら、ウェブページはAIによって書かれているため、これらのトレードオフ、将来の道筋、却下されたアイデアについての議論はゼロで、「証明可能な最適」についての無意味な自己満足的なコピーと、バケットキューがアロケーションフリーであるというばかげた主張だけがあります。

  5. tintor

    このSokobanソルバーは、小さくて単純なSokobanレベルで動作し、利用可能ないくつかのSOTA Sokobanソルバーに遅れを取っています。

    http://www.sokobano.de/wiki/index.php?title=Solver_Statistic...

この日のほかの記事

2026-08-17