Submodule for chess playing and SAT.
More...
Go to the source code of this file.
Detailed Description
Submodule for chess playing and SAT.
 Todo:
 Basic decision problem

The appropriate decision problem seems to be: Given a position P and a natural number k (where the position includes the party who is to move), does there exist a legal sequence of k moves, so that finally the enemies king is taken?
 Todo:
 Encodings

Easiest seems to use 64 parametervariables for the fields, with values {Q, K, B, R, K, P} x {w,b}, and one variable per move, with values all possible pairs like "w, e2e4" and "b, d7d6". Then one variable for the party who is to move is needed, and some additional variables for information whether rochade is been performed etc. Likely for pawns rows 1 and 8 should be forbidden.

A position is encoded via setting of the 64 fieldvariables etc.

The chessrules are enforced by clauses like

If w is to move, then a black move is forbidden.

If some party has no king anymore, then the only move is the nomove.

The move "w, e1f1" is not possible if no white figure is at e1, or a white figure is on f1, or the white figure on e1 is a bishop or a knight.

For the rochade one needs to express that certain fields are not under attack of the other party; this could be expressed by explicitely stating all attacking scenarios (for example, that f1 is not under attack could be stated as a long list like "no black king an g1", "no black rook
on f8, while the rest of the column is free" etc.

A move changes all position variables accordingly (for the next stage): "If w, e2e4" then all fields excepts of e2 and e4 are invariant, while e2 is now empty, and e4 contains the figure from e2."

Better one has a hierarchy of abstractions for the moves (using active clausesets). For example from one position to the next; as usual, the main challenge is to provide good inference for partial assignments.

With active clausesets much more easily positional knowledge can be incorporated; then we more in direction to a general "player" (not just a checkmate solver), but then likely we need optimisation.

Are there optimisation variants of QBF? We need some like "(Quantorprefix) F(x) >= k", where x is the variable vector, and F(X) is an evaluation function. If the decision "F(x) >= k" is rulebased, then perhaps we can fit it into the decisionframework?
 Todo:
 Problem formulations

That in position P white has a check mate in 2 moves can be expressed by the QBF There exists a move_1 of white such that for moves_2 of black there exists a move_3 of white such that for all moves_4 of black there exists a move_5 of white, such that after that the black king as been taken. For each of the 6 stages we have the positionvariables (in 6 variations) and the rules for excluding illegal moves linking the position variables with the five move variables. The initial position is encoded by unitclauses, the final situation without the black king is encoded by the assertion, that no field contains the black king.

Besides asking whether a position has an enforced winning, one can also ask if both sides help, what is the fastest win? For example, what is the shortest game (from the initial position)? One problem in the formulation is that either we have an forall quantifier for the last move of black, or we formulate as a rule that a check must be eliminated if possible.

Or we count solutions.

Optimising the heuristics could also be very interesting.

Likely the whole problem is very hard, and a great challenge should be just to reach the simple bruteforce performance of a simple chessprogramm.
 Todo:
 Active clauses?

It seems hard to identify active clauses (i.e., polytime "partially
instantiable constraints").

One could try to add artificial constraints, corresponding to rules of good playing ?!?

Such an active clause could have a certain horizon, and could ask whether something desirable could be achieved in a few moves.

Still there would be no "polytime" intelligent algorithm involved. Is any "intelligent algorithm" known for chess? Besides bruteforce?
 Todo:
 Iterated finite functions

Chess can be described by a transition function, how to go from one position to the next.

Analogous to the situation with model checking, one then considers the iteration of this function from one starting position.

So one could use such tools, and apply the standard considerations.

An additional perspective would be to look for invariants.

One could hope that perhaps some endgames could be characterised by such invariants?
 Todo:
 Planning: Discuss the relations to planning problems
 Todo:
 Is there some C/C++ library for chessprogramming?
 Todo:
 Generalised chess

Playing chess with different dimensions than 8, and/or with different pieces, should be interesting, since less is known, and the problem also becomes scalable.
 Todo:
 Completeness of generalised chess

It seems that generalised chess is PSPACEcomplete, given the number of moves as part of the input?

While it is EXPTIMEcomplete, given that the number is moves is not bounded?

Given the PSPACEcompleteness, one could then express for example QBF (or what is "closest") via such a generalised chess problem! Worth a try.

Which problems could be translated into standard chess? And how would the problems look like?
Definition in file Chess.hpp.