論文の概要: Positional Games and QBF: The Corrective Encoding

• arxiv url: http://arxiv.org/abs/2005.05098v1
• Date: Mon, 11 May 2020 13:32:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-04 20:47:14.997420
• Title: Positional Games and QBF: The Corrective Encoding
• Title（参考訳）: 位置ゲームとqbf:the corrective encoding
• Authors: Valentin Mayer-Eichberger, Abdallah Saffidine
• Abstract要約: ポジショナルゲームは、Tic-tac-toeとその一般化を含む2プレイヤーゲームのクラスである。 本稿では,これらのゲームを量子ブール式 (QBF) に符号化する手法を提案する。 本手法は,従来のQBFエンコーディングよりも複数の方法で改善されている。
• 参考スコア（独自算出の注目度）: 3.6550217261503675
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Positional games are a mathematical class of two-player games comprising Tic-tac-toe and its generalizations. We propose a novel encoding of these games into Quantified Boolean Formulas (QBF) such that a game instance admits a winning strategy for first player if and only if the corresponding formula is true. Our approach improves over previous QBF encodings of games in multiple ways. First, it is generic and lets us encode other positional games, such as Hex. Second, structural properties of positional games together with a careful treatment of illegal moves let us generate more compact instances that can be solved faster by state-of-the-art QBF solvers. We establish the latter fact through extensive experiments. Finally, the compactness of our new encoding makes it feasible to translate realistic game problems. We identify a few such problems of historical significance and put them forward to the QBF community as milestones of increasing difficulty.
• Abstract（参考訳）: 位置ゲームは、Tic-tac-toeとその一般化を含む2人プレイヤゲームの数学的クラスである。 本稿では,これらのゲームが量子ブール式 (QBF) に符号化され,ゲームインスタンスが第1プレイヤーの勝利戦略を認め,対応する公式が真である場合に限る。 本手法は,従来のqbfエンコーディングを複数の方法で改善する。 まず、これはジェネリックであり、hexのような他の位置ゲームもエンコードできます。 第二に、位置ゲームの構造特性と不正な動きの慎重な処理により、最先端のQBFソルバによってより高速に解けるよりコンパクトなインスタンスを生成することができる。 我々は広範な実験を通じて後者の事実を確立する。 最後に、新しいエンコーディングのコンパクトさにより、現実的なゲーム問題への翻訳が可能になった。 歴史的に重要な問題をいくつか特定し,難易度向上のマイルストーンとして,QBFコミュニティに先駆けた。

関連論文リスト

• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
  エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。 不完全なリコールを伴う広範囲形式のゲームフレームワークにおいて、マルチプレイヤー設定における平衡を求める際の計算複雑性を解析する。
  論文  参考訳（メタデータ） (2024-06-23T00:27:28Z)
• Concise QBF Encodings for Games on a Grid (extended version) [0.0]
  計画領域におけるPDDLの成功に触発されたボードゲームドメイン定義言語(BDDL)を紹介する。 我々はBDDLからQBFへの効率的な翻訳を行い、境界深さの勝利戦略の存在を符号化する。 本稿では,QBF証明書と対話型ゲームプレイを用いて,勝利戦略の検証方法を示す。
  論文  参考訳（メタデータ） (2023-03-29T18:11:41Z)
• Automated Graph Genetic Algorithm based Puzzle Validation for Faster Game Desig [69.02688684221265]
  本稿では,コンピュータゲームにおける論理パズルを効率的に解くための進化的アルゴリズムを提案する。 制約満足度問題に対するハイブリッド遺伝的アプローチの様々なバリエーションについて論じる。
  論文  参考訳（メタデータ） (2023-02-17T18:15:33Z)
• Implicit State and Goals in QBF Encodings for Positional Games (extended version) [2.7528170226206434]
  我々は,Hex や Tic-Tac-Toe のようなメーカブレーカの位置決めゲームにおいて,QBF の簡潔なエンコーディングのボトルネックに対処する。 我々のベースラインは、ボード位置の明示的な変数と勝利構成の明示的な表現を備えたQBF符号化である。 本稿では,ボードサイズとゲーム深度に応じて,複数のエンコーディングのサイズを評価する。また,これらのエンコーディングにおけるQBFソルバの性能についても報告する。
  論文  参考訳（メタデータ） (2023-01-18T07:28:41Z)
• Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract) [68.8204255655161]
  グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全時間的アプローチを提案する。 これは、データセットの60%の勝利領域を正しく決定し、残りの領域で小さなエラーしか発生しない。
  論文  参考訳（メタデータ） (2022-10-18T15:10:25Z)
• Turning Mathematics Problems into Games: Reinforcement Learning and Gr\"obner bases together solve Integer Feasibility Problems [4.746723775952672]
  我々は、線形方程式と不等式の系が整数値の解を持つかどうかを判定する問題である整数実現可能性問題を考察する。 本稿では,エージェントが整数実現可能性問題と同等のゲームをすることができる,新しい代数的強化学習フレームワークについて述べる。 概念実証として、エージェントが2方向テーブルの最も単純なバージョンをうまくプレイできることを実験で実証する。
  論文  参考訳（メタデータ） (2022-08-25T16:24:34Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Learning in Congestion Games with Bandit Feedback [45.4542525044623]
  我々は、良質な理論構造と広い実世界の応用を持つゲームのクラスである混雑ゲームについて検討する。 まず,渋滞ゲームにおける不確実性原理に直面する楽観性に基づく集中型アルゴリズムを提案する。 次に,Frank-Wolfe法とG-Optimal設計を組み合わせた分散アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-04T02:32:26Z)
• Public Information Representation for Adversarial Team Games [31.29335755664997]
  対戦チームゲームは、プレイ中にチームメンバーが利用可能な非対称情報の中にあります。 本アルゴリズムは,対戦相手を持つ逐次チームゲームから古典的な2プレイヤーゼロサムゲームに変換する。 この問題のNPハード性のため、結果のパブリックチームゲームは元のゲームよりも指数関数的に大きいかもしれない。
  論文  参考訳（メタデータ） (2022-01-25T15:07:12Z)
• Contextual Games: Multi-Agent Learning with Side Information [57.76996806603094]
  各ラウンドでコンテキスト情報によって駆動されるコンテキストゲームの新しいクラスを定式化する。 カーネルベースの規則性仮定を用いて、異なるコンテキストとゲーム結果の相関関係をモデル化する。 本研究では,個々のプレイヤーの文脈的後悔を最小限に抑えるために,そのような相関を利用した新しいオンライン(メタ)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-13T18:37:37Z)

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

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