18
$\begingroup$

           (While the world chess championship is in progress in Sochi...)

Is there mathematical evidence that standard chess is somehow optimally (or unusally) rich compared to other possible chess-like games, e.g., using fairy chess pieces and/or following chess variant rules?

I am wondering if chess is something like Conway's game of Life in that its moves/rules are delicately balanced to achieve Turing completeness; one can build a Universal Turing Machine (UTM) in Life.

Here, I suppose, we must talk about "infinite chess," in the sense employed in

Dan Brumleve, Joel David Hamkins, Philipp Schlicht. "The mate-in-$n$ problem of infinite chess is decidable." 2012. (arXiv link).

An alternative to the "delicately balanced" hypothesis is that the moves & rules are a historical accident, and many nearby variants of standard chess have (or may have) similar mathematical properties. To ask specific questions:

Q1. Can infinite chess simulate a UTM?

Q2. Are nearby chess variants analogously powerful, or does standard chess (seem to) have just the right complexity properties?

Update. Both questions are largely answered in the comments. Q1 is open in a formal sense but the likely answer is Yes, $\infty$-chess can simulate a UTM. For Q2, there is every reason to believe that chess rules are not delicately balanced, that likely most reasonable variants would have the same complexity properties.

Improve this question
$\endgroup$
8
  • 4
    $\begingroup$ I have thought about this a great deal, and so far haven't made progress. It seems to be more tractable if you allow the set-up position to involve infinitely many pieces, although they should follow some extremely regular pattern, if not be periodic or eventually periodic. That is, in order to simulate the Turing machine, it will help to have a lot of structure already on the chessboard, to provide the structure of the cells. One idea I looked at is that the black king, say, should play the role of the head, moving from one room to the next, with other pieces playing the roles of the states. $\endgroup$
    – Joel David Hamkins
    Commented Nov 17, 2014 at 1:35
  • 4
    $\begingroup$ Chess is EXPTIME-complete: seeA. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll. Automata, Languages, and Programming, Springer LNCS 115 (1981) 278-293 and J. Comb. Th. A 31 (1981) 199-214. In some sense this implies that you can simulate a Turing machine on it. But in that sense it is not unusual; I would expect the same to be true of most fairy chess variants. $\endgroup$
    – David Eppstein
    Commented Nov 17, 2014 at 8:17
  • 5
    $\begingroup$ Making an analogy with the categorization of one-dimensional cellular automata in Wolframs NKS, it would not be surprising if a positive fraction of all "random" chess variants with fairy pieces have the properties you ask for. $\endgroup$
    – Per Alexandersson
    Commented Nov 17, 2014 at 8:54
  • 8
    $\begingroup$ I'm not sure I agree with the "delicately balanced" metaphor, because the various computational models that are Turing complete, such as Turing machines, register machines and so on, tend to be robust rather than delicate, and retain their Turing completeness after diverse modifications (restricted instruction sets, big alphabets, many tapes, few tapes, and so on). The fact that these models all turned out equivalent was important evidence in favor of the Church-Turing thesis, that we've got the right model of computation. Conway's game is an outlier in this respect, I suppose. $\endgroup$
    – Joel David Hamkins
    Commented Nov 17, 2014 at 18:14
  • 4
    $\begingroup$ Can someone give an example of a "non-rich" chess? I.e., can we change the number/position/allowed moves of the pieces so that the game becomes boring? Of course, exclude trivial solutions, like if the king can be taken in the first move. $\endgroup$
    – domotorp
    Commented Nov 17, 2014 at 20:03

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .