論文の概要: Solvable Sokoban Without a Solver via Diffusion
- arxiv url: http://arxiv.org/abs/2608.15958v1
- Date: Sun, 16 Aug 2026 23:17:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-18 19:59:03.479964
- Title: Solvable Sokoban Without a Solver via Diffusion
- Title（参考訳）: 拡散による可溶性ソコバン
- Abstract要約: 変換器をベースとした離散拡散モデルでは,解答器,報酬,可解性ラベルへのアクセスがなく,純粋にタイル完備化に基づいて学習し,77.4%の可解性が得られることを示す。
マスクされた細胞のみを埋めるように訓練されたモデルが、トレーニングされたことのない可溶性を引き継いでいる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Deciding whether a Sokoban puzzle is solvable is PSPACE-complete (Culberson, 1997): solutions can be exponentially long and there is no short certificate to check. Solvability is also a fragile property, since even a single misplaced wall can silently render an entire puzzle unsolvable. In this work, we show that a transformer-based discrete diffusion model trained purely on tile completion, with no access to solvers, rewards, or solvability labels, achieves a solvability rate of 77.4%, with 94.5% of the remaining failures rendered solvable by removing a single wall. In other words, a global, search-heavy property follows from a local training objective: trained only to fill in masked cells, the model inherits solvability it was never trained on. An autoregressive model factorizes as $p(c_k \mid c_1 \dots c_{k-1})$, meaning a fixed order, always conditioned on a prefix. Masked diffusion does not: it hides a random subset of cells and learns $p(c_k \mid \text{any subset})$, so at generation time it can reveal cells in any order, each one conditioned on everything already placed, wherever it sits on the board. A puzzle's difficulty comes from exactly this kind of non-local interaction, a decision in one part of the grid constraining what will work somewhere else entirely. A generator that is not locked into a single fixed order is therefore a better structural match for the problem than one that is. The training pipeline is adapted from MD4 (Shi et al., 2024) and the dataset is DeepMind's Boxoban (Guez et al., 2019). The trained model and instructions for generating puzzles are publicly available.
- Abstract（参考訳）: ソコバンパズルが解けるかどうかを決定することは、PSPACE完全である(Culberson, 1997)。
難解性もまた脆弱な性質であり、一つの誤配置の壁でさえパズル全体を無音で解けない状態にすることができる。
本研究では, 変圧器をベースとした離散拡散モデルにおいて, 解法, 報酬, 可解性ラベルへのアクセスがなく, 可解性率は77.4%であり, 残った障害の94.5%は1つの壁を除去することで解決可能であることを示す。
言い換えれば、グローバルで検索に重きを置く性質は、局所的なトレーニング目標から導かれるものだ。
自己回帰モデルは$p(c_k \mid c_1 \dots c_{k-1})$と分解される。
マスケド拡散は、セルのランダムな部分集合を隠して$p(c_k \mid \text{any subset})$を学習するので、任意の順序でセルを発見できる。
パズルの難しさは、まさにこの種の非局所的な相互作用であり、グリッドの一部で、何が他のどこかで完全に機能するかを制約する決定である。
したがって、単一の固定順序にロックされていないジェネレータは、問題に対してより優れた構造的マッチングである。
トレーニングパイプラインはMD4(Shi et al , 2024)から適応し、データセットはDeepMindのBoxoban(Guez et al , 2019)である。
パズルを生成するための訓練されたモデルと指示が公開されている。
関連論文リスト
- Capability Sheaves for Compositional Agent-Harness Repair: Controlled Quotients and a Real-Repository Stress Test [0.0]
エージェントハーネスは、検索、ルーティング、状態、証明、検証を組み合わせるが、ローカルに成功したコンポーネントは共有状態に異を唱えることがある。
我々は、この失敗を有限エンハンパビリティ層でモデル化する:ストークは型付き動作シグネチャを符号化し、制限マップは共有フィールドを保持し、受け入れられた実行は有用なグローバルセクションである。
20以上のタスククラスタで制御された実験では、生の状態がニュアンス変数である隠された内部メディエータが導入された。
次に、PatchFuseBenchのSWE-benchプールから分離した発見法について、20のリポジトリから160の課題、875の実際の候補パッチ、2,579のソースを意識した編集原子をテストした。
論文 参考訳（メタデータ） (2026-08-13T13:31:09Z) - DecompRL: Solving Harder Problems by Learning Modular Code Generation [27.116622101805984]
本稿では,階層型コード構造を明示的に分解・実装するRLアルゴリズムDecompRLを紹介する。
LiveCodeBenchとCodeContestsでは、DecompRLが標準および多様性に最適化されたRLベースラインを、問題毎に105ドルのトークンよりも上回っている。
論文 参考訳（メタデータ） (2026-07-02T16:25:10Z) - Flow Reasoning Models: Scaling Reasoning Through Iterative Self-Refinement [13.205772367296353]
フローモデルを用いた構造化推論のためのトレーニングおよびテスト時間スケーリングフレームワークであるReasoning Flow Modelsを紹介する。
正しい答えは、解法力学の安定な固定点であり、再帰的かつ再解法されたときに自分自身に戻る。
セルフコンディショニングチャネルでフローモデルをトレーニングし、推論でそれをクローズすることで、自分たちで過去の予測を洗練できます。
論文 参考訳（メタデータ） (2026-06-28T02:10:36Z) - I Dropped a Neural Net [6.4158736375778185]
Residual Networkの非ラベリング層を考慮し、レイヤの正確な順序を復元する。
問題は各ブロックの入力と出力のプロジェクションをペアにし、再組み立てされたブロックを順序付けする。
順序付けには、Delta-norm や $|W_textout|_F$ のような粗いプロキシでシードし、その後平均二乗誤差をゼロにする。
論文 参考訳（メタデータ） (2026-02-23T13:49:05Z) - Learning the Boundary of Solvability: Aligning LLMs to Detect Unsolvable Problems [51.62477754641947]
本研究では,実現可能な問題を解き,固有の矛盾を検知し,能力を超えたタスクを慎重に拒否するUnsolvableQAとUnsolvableRLを提案する。
具体的には、双トラック手法を用いて導出される、ペアで解決可能かつ解決不可能なインスタンスのデータセットであるUnsolvableQAを構築する。
このデータセット上に構築されたUnsolvableRLは,精度,未解決性,難易度を考慮した3つの報酬成分を備えた強化学習フレームワークである。
論文 参考訳（メタデータ） (2025-12-01T13:32:59Z) - Causal Language Modeling Can Elicit Search and Reasoning Capabilities on Logic Puzzles [14.777731830394357]
本研究では,因果言語モデリングが,数独パズルの解法などの複雑な課題を学習できるかどうかを考察する。
この合成タスクで訓練されたトランスフォーマーモデルが実際にスドクスの解法を学習できることが示される。
また、分析結果をZebraパズル(アインシュタインパズルとして知られる)に拡張し、モデルが92.04 %のパズルを完全に正しく解いていることを示す。
論文 参考訳（メタデータ） (2024-09-16T17:42:15Z) - Do Deep Neural Network Solutions Form a Star Domain? [68.66750305473163]
本稿では,与えられた学習課題のスターモデルを求めるスターライトアルゴリズムを提案する。
得られた恒星領域上でのベイズモデル平均値に対するより良い不確実性の推定を実証する。
論文 参考訳（メタデータ） (2024-03-12T13:59:23Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - Learning by Fixing: Solving Math Word Problems with Weak Supervision [70.62896781438694]
数学用語問題(mwps)の従来のニューラルネットワークソルバは、完全な監視によって学習され、多様なソリューションを生み出すことができない。
MWPを学習するためのテキスト弱教師付きパラダイムを提案する。
この手法は最終回答のアノテーションのみを必要とし、単一の問題に対して様々な解決策を生成できる。
論文 参考訳（メタデータ） (2020-12-19T03:10:21Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z) - Private Learning of Halfspaces: Simplifying the Construction and
Reducing the Sample Complexity [63.29100726064574]
有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。
学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
論文 参考訳（メタデータ） (2020-04-16T16:12:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。