OKlibrary  0.2.1.6
Chess.hpp File Reference

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 parameter-variables 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, e2-e4" and "b, d7-d6". 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 field-variables etc.
  • The chess-rules are enforced by clauses like
    1. If w is to move, then a black move is forbidden.
    2. If some party has no king anymore, then the only move is the no-move.
    3. The move "w, e1-f1" 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.
    4. 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, e2-e4" 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 clause-sets). For example from one position to the next; as usual, the main challenge is to provide good inference for partial assignments.
  • With active clause-sets much more easily positional knowledge can be incorporated; then we more in direction to a general "player" (not just a check-mate solver), but then likely we need optimisation.
  • Are there optimisation variants of QBF? We need some like "(Quantor-prefix) F(x) >= k", where x is the variable vector, and F(X) is an evaluation function. If the decision "F(x) >= k" is rule-based, then perhaps we can fit it into the decision-framework?
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 position-variables (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 unit-clauses, 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 for-all 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 brute-force performance of a simple chess-programm.
Todo:
Active clauses?
  • It seems hard to identify active clauses (i.e., poly-time "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 "poly-time" intelligent algorithm involved. Is any "intelligent algorithm" known for chess? Besides brute-force?
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 end-games could be characterised by such invariants?
Todo:
Planning: Discuss the relations to planning problems
Todo:
Is there some C/C++ library for chess-programming?
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 PSPACE-complete, given the number of moves as part of the input?
  • While it is EXPTIME-complete, given that the number is moves is not bounded?
  • Given the PSPACE-completeness, 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.