論文の概要: Concise QBF Encodings for Games on a Grid (extended version)

• arxiv url: http://arxiv.org/abs/2303.16949v1
• Date: Wed, 29 Mar 2023 18:11:41 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-31 15:31:48.974651
• Title: Concise QBF Encodings for Games on a Grid (extended version)
• Title（参考訳）: グリッド上のゲームのための簡潔QBF符号化(拡張版)
• Authors: Irfansha Shaik and Jaco van de Pol
• Abstract要約: 計画領域におけるPDDLの成功に触発されたボードゲームドメイン定義言語(BDDL)を紹介する。 我々はBDDLからQBFへの効率的な翻訳を行い、境界深さの勝利戦略の存在を符号化する。 本稿では,QBF証明書と対話型ゲームプレイを用いて,勝利戦略の検証方法を示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Encoding 2-player games in QBF correctly and efficiently is challenging and error-prone. To enable concise specifications and uniform encodings of games played on grid boards, like Tic-Tac-Toe, Connect-4, Domineering, Pursuer-Evader and Breakthrough, we introduce Board-game Domain Definition Language (BDDL), inspired by the success of PDDL in the planning domain. We provide an efficient translation from BDDL into QBF, encoding the existence of a winning strategy of bounded depth. Our lifted encoding treats board positions symbolically and allows concise definitions of conditions, effects and winning configurations, relative to symbolic board positions. The size of the encoding grows linearly in the input model and the considered depth. To show the feasibility of such a generic approach, we use QBF solvers to compute the critical depths of winning strategies for instances of several known games. For several games, our work provides the first QBF encoding. Unlike plan validation in SAT-based planning, validating QBF-based winning strategies is difficult. We show how to validate winning strategies using QBF certificates and interactive game play.
• Abstract（参考訳）: qbfで2人プレイのゲームを正しく効率的にエンコーディングすることは、挑戦的でエラーやすい。 Tic-Tac-Toe,Connect-4,Domineering,Pursuer-Evader,Breakthroughなどのグリッドボード上でプレイされるゲームの簡潔な仕様と均一なエンコーディングを実現するため,計画領域におけるPDDLの成功に触発されたボードゲームドメイン定義言語(BDDL)を紹介した。 我々はBDDLからQBFへの効率的な翻訳を行い、境界深さの勝利戦略の存在を符号化する。 昇降符号化は, 基板位置を象徴的に扱い, 条件, 効果, 入賞構成の簡潔な定義を可能にする。 符号化のサイズは入力モデルと考慮された深さで線形に増加する。 このような汎用的アプローチの実現可能性を示すために、いくつかの既知のゲームにおける勝利戦略の臨界深さを計算するためにqbfソルバを用いる。 いくつかのゲームでは、最初のQBFエンコーディングを提供する。 SATベースの計画における計画検証とは異なり、QBFベースの勝利戦略の検証は困難である。 qbf証明書とインタラクティブゲームプレイを用いて、勝利戦略の検証方法を示す。

関連論文リスト

• Unlocking Reasoning Potential in Large Langauge Models by Scaling Code-form Planning [94.76546523689113]
  CodePlanは、テキストコード形式の計画を生成し、追跡するフレームワークで、高いレベルの構造化された推論プロセスの概要を擬似コードで示します。 CodePlanは、洗練された推論タスク固有のリッチなセマンティクスと制御フローを効果的にキャプチャする。 反応を直接生成するのに比べて25.1%の相対的な改善が達成されている。
  論文  参考訳（メタデータ） (2024-09-19T04:13:58Z)
• Lossy-and-Constrained Extended Non-Local Games with Applications to Cryptography: BC, QKD and QPV [0.0]
  制約や損失を考慮してそのようなゲームを拡張すると、SDPの最適値への収束が保たれることを示す。 この結果を応用し、相対論的ビットコミットメント、量子鍵分布、量子位置検証のためのプロトコルのより厳密なセキュリティを示すSDPを計算する。
  論文  参考訳（メタデータ） (2024-05-22T15:09:30Z)
• Experiments with Encoding Structured Data for Neural Networks [0.9051087836811617]
  このプロジェクトの目的は、Battlespaceと呼ばれるゲームプレイングドメインで良いアクションを選択することができるAIエージェントを作成することである。 本稿では,Python クラスに格納された複雑な構造化データを示すための符号化技術に焦点をあてる。
  論文  参考訳（メタデータ） (2024-02-15T19:45:15Z)
• Dual Associated Encoder for Face Restoration [68.49568459672076]
  低品質(LQ)画像から顔の詳細を復元するために,DAEFRという新しいデュアルブランチフレームワークを提案する。 提案手法では,LQ入力から重要な情報を抽出する補助的なLQ分岐を導入する。 合成と実世界の両方のデータセットに対するDAEFRの有効性を評価する。
  論文  参考訳（メタデータ） (2023-08-14T17:58:33Z)
• 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)
• Function Approximation for Solving Stackelberg Equilibrium in Large Perfect Information Games [115.77438739169155]
  汎用ゲームにおける状態値関数の一般化であるtextitEnforceable Payoff Frontier (EPF) の学習を提案する。 Stackelbergの設定にFAを適用する最初の方法です。
  論文  参考訳（メタデータ） (2022-12-29T19:05:50Z)
• VQFR: Blind Face Restoration with Vector-Quantized Dictionary and Parallel Decoder [83.63843671885716]
  本稿では,VQFRを用いた顔復元手法を提案する。 VQFRは高品質な顔から抽出された高品質の低レベル特徴バンクを利用する。 VQコードブックから生成されたリアルな詳細を「汚染」せず、入力から低レベルな特徴をさらに融合させるため、並列デコーダを提案する。
  論文  参考訳（メタデータ） (2022-05-13T17:54:40Z)
• Logic-based AI for Interpretable Board Game Winner Prediction with Tsetlin Machine [23.83480738752374]
  本稿では,ボードゲームポジションの獲得と敗戦を記述した命題論理式を提案する。 我々は、以前にプレイされたゲームからこれらの表現を学習するために、Tsetlin Machine (TM) を使用している。 平均して、TMテストの精度は92.1%であり、他の評価アルゴリズムよりも優れている。
  論文  参考訳（メタデータ） (2022-03-08T20:10:25Z)
• Positional Games and QBF: A Polished Encoding [0.897438370260135]
  ポジショナルゲームは、Tic-tac-toeとその一般化を含む2プレイヤーゲームのクラスである。 本稿では,これらのゲームを量子ブール式 (QBF) に符号化する手法を提案する。 本手法は,従来のQBFエンコーディングよりも複数の方法で改善されている。
  論文  参考訳（メタデータ） (2020-05-11T13:32:03Z)
• Robust Encodings: A Framework for Combating Adversarial Typos [85.70270979772388]
  NLPシステムは入力の小さな摂動によって容易に騙される。 このような混乱に対して防御するための既存の手順は、最悪の場合の攻撃に対して確実な堅牢性を提供する。 モデルアーキテクチャに妥協を加えることなく、ロバスト性を保証するロブエン(RobEn)を導入します。
  論文  参考訳（メタデータ） (2020-05-04T01:28:18Z)

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

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