[FOM] Robust Chess?

[Harvey Friedman]

In this reasonably clean formulation, WHICH MAY BE WELL KNOWN AND WELL
STUDIED, we preserve most but not all features of chess. We will include
only the memoryless part of chess in this formulation, and only the part
that does not single out special squares. I.e., we exclude castling,
promotion, en passant, first-move-of-a-pawn.

We play on an n x n game board, with two players, white and black.

We have k1 pieces of type t1, k2 pieces of type t2, ... , kr pieces of type
tr. These pieces come in WHITE or in BLACK.

WHITE and BLACK alternate moves, WHITE moving first. Each white move is the
result of moving a white piece to an empty square, to which that white piece
has occupation access, or to a square occupied by a black piece, to which
that white piece has capturing access, and removing the black piece. Each
black move is the result of moving a black piece to an empty square, to
which that black piece has occupation access, or to a square occupied by a
white piece, to which that black piece has capturing access, and removing
the white piece. 

Stalemate occurs when no legal move is available. We assign a tie to
stalemate, although it is also interesting and perhaps more natural to
assign a loss to stalemate.

The game ends either in stalemate, or in the capture of all white pieces of
type t1, or in the capture of all black pieces of type t1. The game results
in, respectively, a draw (or see above paragraph for alternative), a win for
black, or a win for white.

Some interesting alternatives are as follows.

1. The game ends either in stalemate, or in the capture of one white piece
of type t1, or in the capture of one black piece of type t1.

2. The game ends in the capture of all white pieces, or in the capture of
all black pieces. 

We now come to the crucial matter of just what the occupation access squares
and what are the capturing access squares of pieces?

The most general kind of access sets would consist of a set E of ordered
pairs (x,y) from Z x Z. The positions (occupation or capture) accessed from
a piece of a given type currently at position (i,j) would be the positions
(i,j) + (x,y) lying in [1,n] x [1,n], where (x,y) lies in E\{(0,0)}. (We
will insist that no piece has access to the same square on which it sits).

However, we don't want to consider the ridiculously general setup where E is
arbitrary. We want E to be given in a simple natural way, independently of
the dimension n. 

A good choice of allowable E's would be

***the signed order invariant subsets of Z x Z relative to finitely many
constants from Z***

This is the reason I am making this posting. The order invariant subsets of
Zk are an extremely robust and important family of subsets of Zk (here k =
2). The same is true of the signed order invariant subsets of Zk.

V containedin Zk is called order invariant if and only if membership of x in
V depends only on the relative order of the k coordinates of x.

V containedin Zk is called order invariant relative to constants c1,...,cp
in Z if and only if membership of x in V depends only on the relative order
of the k coordinates of x and c1,...,cp.

V containedin Zk is called signed order invariant if and only if membership
of x in V depends only on the relative order of the k coordinates of x and
their additive inverses.

V containedin Zk is called order invariant relative to constants c1,...,cp
in Z if and only if membership of x in V depends only on the relative order
of the k coordinates of x and their additive inverses, and c1,...,cp.

Using only the constants {1,2}, this covers the moves and captures in chess
by knights, pawns*, bishops, queens, rooks, kings**.

*no double pawn moves, and no en passant and no promotion.
**we think of chess where there is exactly one white king and exactly one
black king and there are no checks, but instead the kings are subject to
capture, where the capture of the king ends the game - this is according to
the general format given above.

To be specific about these constants, we comment on the pieces.

kings. Occupation and capture access the same. Use constants 1.
pawns. Occupation and capture access not the same. Use constant 1.
bishops. Occupation and capture access the same. Use no constants.
rooks. Occupation and capture access the same. Use no constants.
queens. Occupation and capture access the same. Use no constants.
knights. Occupation and capture access the same. Use constants 1,2.

It is interesting to insist that the constants used be SMALL. If we bound
the constants used, then there are only FINITELY MANY powers of pieces. If
we further restrict the number of pieces of each kind, there are only
finitely many games to consider (with the parameter left being the size of
the board).

Now that we have this setup, we can ask lots of traditional computational
complexity questions. E.g., game evaluations, strategies, access of one
position from another, etc.

But one issue of a little different kind is this. What kind of simplicity is
needed about the V's that ensures that the obvious computational complexity
questions can be decided in polynomial or better time? And what kind of
complexity is needed about the V's that ensures that the obvious
computational complexity questions cannot be decided in polynomial time?

It makes sense to, among other things, focus on the case of constants 1,2,
or more radically, on the case of no constants, or just the constant 1.

Harvey Friedman