11
$\begingroup$

Trappist-1 is a variant of infinite chess that has a piece called huygens which leaps any prime number of squares orthogonally. To actually implement this game, it should have decidable mate-in-$0$ (checkmate detection) and stalemate-in-$0$ (stalemate detection). Whether there is a checking piece is clearly decidable. Testing whether a player has no move left can be done like this:

  1. Check that leapers can't move. Since there are only finitely many moves we can check that for each move the king gets in check.
  2. Check that riders can't move. Suppose that there is a checking piece. The rider should capture or block (if the checking piece is also a rider) it, and there are only finitely many possible squares to do so. In this case it is similar to step 1. If there are no checking piece, we should check if it is pinned by opponent riders. Remove the piece and find all the checking riders. If there exists any, the only squares the piece can move to is the squares which block their finitely many potential paths to the king. Since there are only finitely many possible squares to do so, it is also similar to step 1.
  3. Check that huygenses can't move. This is the same as riders.

And then I thought about mate-in-$1$ for Trappist-1. The only piece that can give infinitely many direct checks is huygens (infinitely many discovery checks can be given by other riders too). In order to give infinitely many direct checks it should be on the same file or rank of the king.

For example, in the following position, the red huygens can give infinitely many checks if there are infinitely many cousin primes. White pawn is a pawn, White huygens is a huygens, White king is a king.

Example position

This position is mate-in-$1$ for red if there exists a prime $p$ such that $p + 4$ is a prime, but $p + 8$ isn't (so that the white huygens couldn't recapture). Since $p = 7$ satisfies it, this position is a mate-in-$1$ for red. This is a simple position, and in general, it would be much more complicated to check if it is mate-in-$1$.

The wiki page for Trappist-1 states about huygens that This game feature excludes Trappist-1 from the proof that the mate-in-$n$ problem is decidable.

Is mate-in-$1$ undecidable? Or are there any results that mate-in-$n$ is undecidable for some $n$?

$\endgroup$
2
  • $\begingroup$ You need an undecidable primality statement? - I don't think any are known. $\endgroup$
    – Vepir
    Jun 10, 2022 at 10:34
  • $\begingroup$ @Vepir I think that undecidability is different from what I meant. I am saying in the context of decision problems rather than provability. $\endgroup$
    – Ris
    Jun 14, 2022 at 3:00

0

Reset to default

You must log in to answer this question.