Consider a game like chess on an infinite board, where we have the usual chess piece types and an additional piece which moves a prime number of square horizontally or vertically.

If we assume a finite number of pieces, is it decidable if there is a mate in n in a given position? The additional piece rules out solutions using Presberger arithmetic or automatic structures.

  • 1
    $\begingroup$ So at the very least you should be able to algorithmically decide if a given composite integer $n$ is a difference of 2 primes both greater than another given integer $N$ (mate in 1 when the black king cannot move, the additional white piece is on the right horizontal $n$ squares away, and small moves are blocked by other white pieces or under attack by black pieces if you don't allow jumping). Can you show me an algorithm for that "trivial partial case"? $\endgroup$ – fedja May 26 '18 at 2:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.