general.hpp File Reference

General plans regarding games. More...

Go to the source code of this file.

Detailed Description

General plans regarding games.

Create milestones
Generalising positional games to SAT
  • See "Positional games" in ComputerAlgebra/Hypergraphs/Lisp/plans/Colouring.hpp for the hypergraph versions.
  • The right generalisation of the n-player versions seems to be as follows:
    1. Given n clause-sets F_1,...,F_n.
    2. At the beginning the partial assignment phi to be constructed is empty.
    3. A move of player i is to choose a yet unassigned variable v and a value e for it, and to extend phi by <v -> e>
    4. The winner is i who has first an empty clause in phi * F_i.
    5. More precisely i wins iff it is his turn to move, and either there is already the empty clause in phi * F_i, or after his move the empty clause is in phi * F_i.
    6. It seems important that the players are not associated with truth values.
    7. So instead of boolean clause-sets F_1,..., F_n we can also have generalised clause-sets with non-boolean values --- this just yields more choices for the players.
    8. For a hypergraph G and n players the positional game on G, where every player has his own colour, is represented by the generalised clause-set representing the generalised colouring problem for n copies of G, where player i has the clauses using his colour. Here essentially there is no choice of truth-value, since only the truth value i can falsify a literal in a clause of F_i.

Definition in file general.hpp.