Implicit State and Goals in QBF Encodings for Positional Games (extended version)

Irfansha Shaik, Valentin Mayer-Eichberger, Jaco van de Pol +1

We address two bottlenecks for concise QBF encodings of maker-breaker positional games, like Hex and Tic-Tac-Toe. Our baseline is a QBF encoding with explicit variables for board p…