What values of (states * steps) suffice for a Turing machine that weakly solves chess?
Basic
4
Ṁ290
Jan 1
96%
<=10^60
79%
<=10^40
64%
<=10^20
56%
<= 10^10
Resolved
NO
<=1

Let us say that an n-state binary-tape Turing machine weakly solves chess in k steps if the following all hold:

  • The TM terminates in under k steps on any input.

  • Whenever the TM receives as input a chess position represented in FEN encoded on its tape in ASCII, the TM halts with another valid position in FEN on the tape, representing the position after a legal move.

  • When this algorithm for choosing moves plays all the moves for one player, it achieves the optimal outcome (win, loss, or draw) regardless of the opponent's play.

Let N be the smallest natural such that there exist n,k where N = n*k and there is an n-state binary-tape Turing machine weakly solving chess in k steps. This market resolves to all answers indicating values at or above N.

I may resolve some answers early if someone in the comments can prove how they resolve, but no guarantees about reading very long comments claiming proofs.

Get
Ṁ1,000
and
S3.00
Sort by:

If people do manage to prove upper or lower bounds, I'll add new answers that split the difference on the exponent.

<=1

Actually the proof that this doesn't suffice is very simple: A TM cannot read in the entire FEN in this many steps, and therefore can't output a legal first move.

© Manifold Markets, Inc.Terms + Mana-only TermsPrivacyRules