論文の概要: Solving QSAT problems with neural MCTS

• arxiv url: http://arxiv.org/abs/2101.06619v1
• Date: Sun, 17 Jan 2021 08:20:07 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-28 01:20:35.049637
• Title: Solving QSAT problems with neural MCTS
• Title（参考訳）: ニューラルMCTSを用いたQSAT問題の解法
• Authors: Ruiyang Xu, Karl Lieberherr
• Abstract要約: AlphaZeroの自己再生による最近の成果は、いくつかのボードゲームで顕著なパフォーマンスを示しています。 本稿では,alphazeroのコアアルゴリズムであるneural monte carlo tree search(neural mcts)の計算能力を活用しようとする。 すべての QSAT 問題が QSAT ゲームと等価であることを知ると、ゲームの結果は元の QSAT 問題の解を導出するために用いられる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent achievements from AlphaZero using self-play has shown remarkable performance on several board games. It is plausible to think that self-play, starting from zero knowledge, can gradually approximate a winning strategy for certain two-player games after an amount of training. In this paper, we try to leverage the computational power of neural Monte Carlo Tree Search (neural MCTS), the core algorithm from AlphaZero, to solve Quantified Boolean Formula Satisfaction (QSAT) problems, which are PSPACE complete. Knowing that every QSAT problem is equivalent to a QSAT game, the game outcome can be used to derive the solutions of the original QSAT problems. We propose a way to encode Quantified Boolean Formulas (QBFs) as graphs and apply a graph neural network (GNN) to embed the QBFs into the neural MCTS. After training, an off-the-shelf QSAT solver is used to evaluate the performance of the algorithm. Our result shows that, for problems within a limited size, the algorithm learns to solve the problem correctly merely from self-play.
• Abstract（参考訳）: セルフプレイによるAlphaZeroの最近の業績は、いくつかのボードゲームで顕著なパフォーマンスを示している。 知識ゼロから始まったセルフプレイは、トレーニングの後に特定の2人プレイの勝利戦略を徐々に近似することができると考えることができる。 本稿では、AlphaZeroのコアアルゴリズムであるニューラルモンテカルロ木探索(Neural MCTS)の計算能力を活用し、PSPACEを完備する量子ブール式満足度(Quantified Boolean Formula Satisfaction, QSAT)問題を解決する。 すべての QSAT 問題が QSAT ゲームと等価であることを知ると、ゲームの結果は元の QSAT 問題の解を導出するために用いられる。 本稿では,量子ブール式(QBF)をグラフとして符号化し,グラフニューラルネットワーク(GNN)を用いてQBFをニューラルネットワークに埋め込む方法を提案する。 トレーニング後、アルゴリズムの性能を評価するために、既製のQSATソルバが使用される。 この結果から,限られたサイズの問題に対して,アルゴリズムは自己プレイからのみ,正しい解法を学習することがわかった。

関連論文リスト

• Towards Less Greedy Quantum Coalition Structure Generation in Induced Subgraph Games [3.6021182997326022]
  100%再生可能エネルギーへの移行には、マイクログレードと呼ばれる有能なプロシューマーのサブセットに分割するなど、エネルギーネットワークを管理する新しい技術が必要である。 最適な方法で行うことは、誘導サブグラフゲームにおける結合構造生成問題に抽象化できるため、難しい最適化問題である。 本研究は,GCS-Qをソリューション品質の面で上回りうるかどうかを検証し,より控えめなQAベースのアプローチを提案する。
  論文  参考訳（メタデータ） (2024-08-08T10:54:56Z)
• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。 本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
  論文  参考訳（メタデータ） (2024-07-18T22:05:21Z)
• torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problem [1.5850859526672516]
  最大満足度問題(MaxSAT)の解を近似できる単一の微分可能関数を導出する。 我々は,我々の微分可能な関数をモデル化する新しいニューラルネットワークアーキテクチャを提案し,バックプロパゲーションを用いてMaxSATを段階的に解く。
  論文  参考訳（メタデータ） (2024-02-06T02:33:00Z)
• A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
  本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。 この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
  論文  参考訳（メタデータ） (2023-06-07T12:19:22Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm [0.05076419064097732]
  量子コンピューティング問題とは対照的に,QAOAがハード制約満足度問題を解く能力について検討する。 我々は,QAOAの平均成功確率を,満足度しきい値のランダムな式上で解析的に評価する。 約14のアンザッツ層に対して、QAOAは高性能な古典解法のスケーリング性能と一致することがわかった。
  論文  参考訳（メタデータ） (2022-08-14T20:39:48Z)
• An AlphaZero-Inspired Approach to Solving Search Problems [63.24965775030674]
  探索問題を解くためにAlphaZeroで使用される手法と手法を適応する。 本稿では,簡単な解法と自己還元という観点から表現できる可能性について述べる。 また,探索問題に適応したモンテカルロ木探索法についても述べる。
  論文  参考訳（メタデータ） (2022-07-02T23:39:45Z)
• Machine Learning Methods in Solving the Boolean Satisfiability Problem [72.21206588430645]
  本論文は, Boolean satisfiability problem (SAT) を機械学習技術で解くことに関する最近の文献をレビューする。 ML-SATソルバを手作り特徴を持つナイーブ分類器からNeuroSATのような新たなエンド・ツー・エンドSATソルバまで,進化するML-SATソルバについて検討する。
  論文  参考訳（メタデータ） (2022-03-02T05:14:12Z)
• Can Graph Neural Networks Learn to Solve MaxSAT Problem? [22.528432249712637]
  我々は,理論的および実践的両面から,マックスサット問題の解法学習におけるGNNの能力について検討した。 我々はベンチマークからMaxSATインスタンスの解法を学ぶために2種類のGNNモデルを構築し、実験によりGNNがMaxSAT問題を解く魅力的な可能性を示す。 また,アルゴリズムアライメント理論に基づいて,GNN が MaxSAT 問題のある程度の解法を学習できるという理論的な説明も提示する。
  論文  参考訳（メタデータ） (2021-11-15T07:33:33Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Goal-Aware Neural SAT Solver [2.609784101826762]
  現代のニューラルネットワークは問題に関する情報を取得し、入力値からのみ出力を算出する。 我々は、必ずしも最適ではなく、クエリメカニズムで拡張することで、ネットワークの性能を大幅に改善できると主張している。 本稿では、QuerySATと呼ばれるクエリ機構を備えたニューラルSATソルバを提案し、幅広いSATタスクにおいてニューラルベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-14T04:51:24Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。