About: Positional Games and QBF: The Corrective Encoding

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Positional Games and QBF: The Corrective Encoding Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : covidontheweb.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	Positional Games and QBF: The Corrective Encoding
Creator	Mayer-Eichberger, Valentin Saffidine, Abdallah
Source	PMC
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 (QBFs) 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.
has issue date	2020-06-26(xsd:dateTime)
bibo:doi	10.1007/978-3-030-51825-7_31
has license	no-cc
sha1sum (hex)	c62e7993366ebc53e94417c279dd6608358319c8
schema:url	https://doi.org/10.1007/978-3-030-51825-7_31
resource representing a document's title	Positional Games and QBF: The Corrective Encoding
has PubMed Central identifier	PMC7326552
schema:publication	Theory and Applications of Satisfiability Testing - SAT 2020
resource representing a document's body	covid:c62e7993366ebc53e94417c279dd6608358319c8#body_text
is schema:about of	named entity 'IMPROVES' named entity 'PREVIOUS' named entity 'Quantified Boolean Formulas' named entity 'Tic-tac-toe' named entity 'hypergraph' named entity 'positional game' named entity 'DYS' named entity 'DYS' named entity 'MCTS' named entity 'MCTS' named entity 'and/or' named entity 'Tic-Tac-Toe' named entity 'computational complexity' named entity 'QBF' named entity 'CNF' named entity 'quantifier' named entity 'Maker-Maker game' named entity 'QBF' named entity 'DYS' named entity 'positional game' named entity 'graph' named entity 'iterative deepening' named entity 'solving problems' named entity 'QBF' named entity 'preprocessor' named entity 'QBF' named entity 'QBF' named entity 'DYS' named entity '3-dimensional' named entity 'DYS' named entity 'quantifiers' named entity 'Japan' named entity 'QBF' named entity 'backtracking' named entity 'domain knowledge' named entity 'QBF' named entity 'Tic-tac-toe' named entity 'positional game' named entity 'DYS' named entity 'hyperedge' named entity 'constraint satisfaction problems' named entity 'command line' named entity 'CNF' named entity 'Maker-Breaker game' named entity 'polyomino' named entity 'first-order logic' named entity 'Monotonicity' named entity 'QBF' named entity 'finite set' named entity 'algorithm' named entity 'Hex' named entity 'Mickey Mouse' named entity 'gomoku' named entity 'Fig. 2' named entity 'negation' named entity 'QBF' named entity 'Hex' named entity 'orders of magnitude' named entity 'monotonicity' named entity 'DYS' named entity 'QBF' named entity 'symmetry breaking' named entity 'satisfiable' named entity 'World War II' named entity 'Maker-Breaker game' named entity 'QBF' named entity 'SAT solvers' named entity 'Monte Carlo Tree Search' named entity 'preprocessor' named entity 'QBF' named entity 'QBF' named entity 'QBF' named entity 'QBF' named entity 'heuristic' named entity 'positional game' named entity 'Maker-Maker game' named entity 'cardinality' named entity 'Gomoku' named entity 'preprocessor' named entity 'Hex' named entity 'DYS' named entity 'QBF'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software