論文の概要: Searching for Primes: A Neural AlphaZero Approach to a Factoring Game
- arxiv url: http://arxiv.org/abs/2609.22968v1
- Date: Sat, 19 Sep 2026 11:39:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-24 17:19:27.620693
- Title: Searching for Primes: A Neural AlphaZero Approach to a Factoring Game
- Title（参考訳）: 素数探索: ファクタリングゲームに対するニューラルアルファゼロアプローチ
- Abstract要約: 我々は、Ntimes N$ボード上のワンプレイヤートークンゲームを調査し、トークンが斜めに沿ってスライドしたり、近隣のトークンに重複したりして、長方形の$Rtimes S$を形成する。
この2N$-bit $W'$を2つの$N$-bit Factorに到達し、長方形の行と列をエンコードする2N$-bit Factorを証明した。
我々は、この制約空間を、学習されたポリシ/バリューネットワークとAlphaZeroスタイルのモンテカルロ木探索を用いて、ファクタリング等価環境におけるニューラルルックアヘッドの限界を探索する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a one-player token game on an $N\times N$ board where tokens slide along diagonals or duplicate onto neighbouring ones to form a combinatorial rectangle $R\times S$. A conserved integer weight $W'$ and a strict monovariant guarantee $O(N^2)$-length solutions, placing the game in $\mathsf{NP}$. We prove that reaching a final position factors this $2N$-bit $W'$ into two $N$-bit factors $V,M < 2^N$ that encode the rectangle's rows and columns. Consequently, solving the game for a balanced-semiprime target is equivalent to integer factoring. However, if the target rectangle is known, the solution reduces to two polynomial-time steps: a forced downward chip-flow and a $0/1$-polynomial factorisation leveraging Cohn's theorem. The game's entire difficulty is thus isolated to the initial number-theoretic split. Supplying the popcounts of the factors as a promise preserves this asymptotic hardness but bounds the target search space. We exploit this constrained space using a learned policy/value network and an AlphaZero-style Monte-Carlo tree search, empirically probing the limits of neural look-ahead on a factoring-equivalent environment.
- Abstract（参考訳）: N のボード上で、トークンが対角線に沿ってスライドしたり、隣接するものに重複したりして、組合せ長方形 $R\times S$ を形成するワンプレイヤートークンゲームについて研究する。
保存された整数ウェイト$W'$と厳密な単変量により$O(N^2)$長解が保証され、ゲームは$\mathsf{NP}$に置かれる。
この2N$-bit $W'$を2つの$N$-bit Factorに到達し、長方形の行と列をエンコードする2つの$N$-bit Factorに到達したことを証明した。
したがって、バランスの取れたセミプライムターゲットのゲームは整数ファクタリングと等価である。
しかし、対象の矩形が分かっていれば、解は2つの多項式時間ステップに還元される:強制下降チップフローとコーンの定理を利用した0/1$-ポリノミカル分解である。
これにより、ゲーム全体の難易度は初期数理論分割に分離される。
因子のポップカウントを約束として供給することは、この漸近的な硬さを保ちながら、対象の検索空間を束縛する。
我々は、この制約空間を、学習されたポリシ/バリューネットワークとAlphaZeroスタイルのモンテカルロ木探索を用いて、ファクタリング等価環境におけるニューラルルックアヘッドの限界を実証的に探索する。
関連論文リスト
- Computational Hardness of Private Coreset [84.99100741615423]
与えられた点の入力集合に対して、コアセットは任意の候補解に対する$k$-meansの目的が乗法的な$(, 1/n(1))$ factor(およびいくつかの加法因子)まで保存されるような点の別の集合である。
no-time $(, 1/n(1))$-DPアルゴリズムは、ある定数$> 0$(およびいくつかの定数加法因子)に対して$ell_infty$-metricの$k$-meansのコアセットを計算することができることを示す。
$k$-means in the
論文 参考訳（メタデータ） (2026-02-19T15:58:49Z) - Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。
効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。
また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文 参考訳（メタデータ） (2025-02-25T19:08:26Z) - An Efficient Quantum Decoder for Prime-Power Fields [1.0878040851638]
ブロックサイズ$n$に対して$p$が小さい$q = pm$の場合、時間内の問題を解く量子アルゴリズムが存在することを示す。
一方、古典的アルゴリズムはこの問題をはるかに小さな逆因子に対してのみ効率的に解くことができる。
論文 参考訳（メタデータ） (2022-10-20T19:35:50Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳（メタデータ） (2022-02-03T18:18:28Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。