Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff the program halts?

The rules are the same as ordinary chess minus the 50 move rule, exchanges and castling.

And what is the minimum number of different types of pieces (i.e. the simplest game) that is needed for a chess-like game to be Turing-complete? (Each type of piece having a set of allowed moves that is invariant under translations)

share|improve this question
7  
How different from regular chess can the rules of the game be in order to call it "chess"? –  Robert Israel Oct 11 '11 at 17:22
    
The rules must be the same as ordinary chess except pawn-exchange and castling. This includes the game ending if it is in the same state 3 times. –  coffeemachine Oct 11 '11 at 17:33
6  
There is a closely related question on MathOverflow: Decidability of chess on an infinite board. –  Tsuyoshi Ito Oct 11 '11 at 18:52
2  
Also crossposted on cstheory.SE: cstheory.stackexchange.com/questions/8582/… –  Suresh Venkat Oct 11 '11 at 22:08
    
Is the first part of the question the same as the linked MO question? –  sdcvvc Oct 14 '11 at 1:30

4 Answers 4

The classic reference on this is the paper "Computing a Perfect Strategy for nxn Chess Requires Time Exponential in n" by Aviezri Fraenkel and David Lichtenstein; unfortunately, I can't find the (30-year-old!) paper online anywhere and while I think I have the proceedings it came from, it's buried in a pile of boxes. Of course, your board isn't finite, but your initial piece configuration is; this means that if there's any computable bound on the needed board size to resolve an initial position, then chess isn't Turing-complete. (If the status of all positions of diameter $d$ could be determined using boards of size no more than $f(d)$, then they can be determined in $\mathrm{EXP}(f(d))$ time by the EXPTIME completeness result, and thus wouldn't be Turing-complete). I vaguely recall seeing something about such a result, but unfortunately some quick searches aren't turning anything up. The expert on the mathematics of chess is Noam Elkies, so hopefully he can spot this and chime in...

share|improve this answer

If you allow for a board with an infinitely repeating looping section (to emulate the infinite tape), I'm pretty sure you can develop a turing complete chess board.

Pawns probably can't be used (because they can't be moved back to loop a calculation) and queens probably have too much movement range to be useful as well. You'll probably need "walls" on your board (impassable squares) and possibly even multiple kings (all of which can be checkmated).

Suggested computation method: white is 1 move away from having his king checkmated and must check the black king on every move. The black king is moved around various arrangements of walls, white rooks, bishops and knights which perform the various operations required for calculation. Calculation halts when the black king comes to a dead end and can never win or can always win.

share|improve this answer
    
It's relatively straightforward if you get 'infinite' pieces, which is what your mapping requires. The original question (infinite board, but only a finite number of pieces) is substantially more challenging. –  Steven Stadnicki 16 hours ago

Though I do not understand the question description compeltely (and forgive my wrong use of terminology, it is not really my field), the title compelled me to think about this.

Under the assumption that a game only ends if a draw is claimed, I believe that chess can be used to represent any brainfuck code. And, as brainfuck is turing complete, I would say that chess is turing complete.

Here is what I have in mind:

  1. Put the kings in a spot where they are not bothered (White king A1, pawn A2, B2; black king H1, pawn G2, H2)
  2. Designate a square for the queens to move (black C7-D8, white E7-D8)
  3. Map the 8 directions a queen can move in onto the 8 brainfuck commands

If the queen walks 'off the edge' she comes back into her area on the other side. (Example, moving down from A5, the queen goes to A8.)

To make sure each move uniquely identifiable, a queen move is followed by a king move iff the queen walked 'off the edge'.

share|improve this answer
    
The question is asking for a translation into a position, not into a move sequence - otherwise the answer is relatively trivial (there are plenty of non-interacting move sequences that you could use to encode just about anything). –  Steven Stadnicki Jul 9 at 15:16
    
A chess position can be defined as where the pieces are, and how they moved to get there. If you don't consider the last part then I suppose this answer does not hold. Based on the second comment to the question, I assumed the move history would be recorded. –  Dennis Jaheruddin Jul 9 at 15:20
    
(And nitpickily, there's a small problem with your encoding - if a queen is on e.g. b8 and she wants to move in a NW direction, your encoding would try to move her to c9 and 'wrap' that around to c5 - but b8-c5 isn't a legal queen move.) –  Steven Stadnicki Jul 9 at 15:22
    
@StevenStadnicki Thanks for the heads up! I think reducing the queens area to 2x2 solved the problem, but if there is still a mistake feel free to correct it. –  Dennis Jaheruddin Jul 9 at 15:26
    
The traditional definition of a 'position' does encode some information about past game data (e.g., whether either side can castle, what if any en passant captures are legal) but otherwise doesn't include any information as to how the pieces got to where they are; this is what makes e.g. retrograde analysis problems interesting. –  Steven Stadnicki Jul 9 at 15:29

As chess is played on a finite board with finite many pieces, the number of which can not grow but decline during the game, chess is a game with finite many states and thus never Touring-complete. Though the number of states grows exponentally with the size of the board chess only represents a finite state machine and will be won by computers at some time in the future.

share|improve this answer
3  
The question is about a generalization of chess played on an infinite board as stated in the very first sentence. –  Rahul Jul 8 at 13:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.