A formula game is an artificial game represented by a fully quantified Boolean formula. Players' turns alternate and the space of possible moves is denoted by bound variables. If a variable is universally quantified, the formula following it has the same truth value as the formula beginning with the universal quantifier regardless of the move taken. If a variable is existentially quantified, the formula following it has the same truth value as the formula beginning with the existential quantifier for at least one move available at the turn. Turns alternate, and a player loses if he cannot move at his turn. In computational complexity theory, the language FORMULA-GAME is defined as all formulas such that Player 1 has a winning strategy in the game represented by . FORMULA-GAME is PSPACE-complete.
Famous quotes containing the words formula and/or game:
“I cannot give you the formula for success, but I can give you the formula for failure—which is: Try to please everybody.”
—Herbert B. Swope (1882–1958)
“The savage soul of game is up at once—
The pack full-opening various, the shrill horn
Resounded from the hills, the neighing steed
Wild for the chase, and the loud hunter’s shout—
O’er a weak, harmless, flying creature, all
Mixed in mad tumult and discordant joy.”
—James Thomson (1700–1748)