3
$\begingroup$

I noticed a lot of 1-player games have been shown to be NP-Hard, like Pac-Man, The World's Hardest Game, Tetris, etc.

For PSPACE-Complete, I noticed that Wikipedia listed these 1-player games:

It is also possible for puzzles played by a single player to be PSPACE-complete. These often can be interpreted as reconfiguration problems, and include the solitaire games Rush Hour, Mahjong, Atomix and Sokoban, and the mechanical computer Turing Tumble.

There are a few other 1-player games, like Super Mario Bros, that I saw are PSPACE-complete, too.


However, when I looked for EXPTIME-complete games, I found some like Chess, checkers, and Go, although I was looking for 1-player games. Are there any?

As for EXPSPACE-complete, do any games (1-player or otherwise) exist? Other than undecidable Magic The Gathering, I wasn't able to find a game at or beyond EXPSPACE.

$\endgroup$
3
  • 4
    $\begingroup$ What exactly do you mean by "1 player game"? You need to limit your definition in some way, otherwise you can take the following game: given a TM M, the player needs to generate a word accepted by the TM, if one exists, or say that one doesn't exist. This game is generally undecidable, but can be made to be in any complexity class by restricting the TM to be e.g., one that runs in EXPTIME, EXPSPACE, etc. $\endgroup$
    – Shaull
    Commented Jul 17, 2023 at 4:47
  • $\begingroup$ Preferably, a game that is/was in play by some human population (as opposed to one whose rules were written to have it fall in the complexity class that I am looking for), and one that involves only one player. Otherwise, if none can be found, preferably the game should have its rules written to resemble a "puzzle game" in that it should have a significant visual component (like a board/grid, visible game pieces, etc.) plus it should involve only one player. $\endgroup$
    – edit
    Commented Jul 17, 2023 at 6:29
  • 1
    $\begingroup$ well, chess puzzles are played by a lot of humans, only involve one player, and resemble a puzzle game. The difficulty of finding the best move in a chess puzzle position should be exactly the same as the difficulty of finding the best move in a position in a 2-player chess game. So that should fulfill the requirements. EDIT: turned this comment into an answer $\endgroup$
    – Kevin Wang
    Commented Jul 17, 2023 at 16:50

1 Answer 1

1
$\begingroup$

From the comments, the desiderata are:

Preferably, a game that is/was in play by some human population (as opposed to one whose rules were written to have it fall in the complexity class that I am looking for), and one that involves only one player. Otherwise, if none can be found, preferably the game should have its rules written to resemble a "puzzle game" in that it should have a significant visual component (like a board/grid, visible game pieces, etc.) plus it should involve only one player.

Any "puzzle" from one of the EXPTIME-hard games should fulfill the requirements. For example, chess puzzles:

Chess puzzles are played by a lot of humans, only involve one player, and resemble (are) a puzzle game. The difficulty of finding the best move in a chess puzzle position should be exactly the same as the difficulty of finding the best move in a position in a 2-player chess game. So if we accept that finding the best move in a generalized 2-player chess position is EXPTIME-hard, then so is finding the best move in a chess puzzle.

Is it EXPTIME-hard to find the best move in generalized chess?

Probably? But I'm not 100% sure.

The EXPTIME-completeness result for generalized chess is Computing a perfect strategy for n × n chess requires time exponential in n, Fraenkel & Lichtenstein, 1981. The paper says that the following problem is EXPTIME-hard:

Given an arbitrary position of a generalized chess game on an n x n chessboard from our class of chess games, can White (Black) win from that position?

In (generalized) chess puzzles, the question is a bit different:

Given an arbitrary position of a generalized chess game on an n x n chessboard from our class of chess games, where white (black) has a winning strategy, find a winning move for White (Black).

The first problem is at least as hard as the second problem, because you can use an oracle for the first to find a solution to the second in polynomial time: simply try all possible moves and ask whether the resulting position is winning or not. Then, once you find a move which results in a winning position, that move is the answer to the second problem. The first problem is EXPTIME-hard. I guess it's not instantly clear whether the second problem is as well, but it seems like it probably is.

If it is, then the argument from the Fraenkel & Lichtenstein 1981 paper also applies to generalized chess puzzles.

(Note that this doesn't apply to puzzles of the form: "Find mate in X for White", only to puzzles like "Find a winning move" (like puzzles on Lichess).

$\endgroup$
4
  • $\begingroup$ Well, the CPU player is still a player. How about I list a few examples of 1-player games instead: Tetris, Rush Hour, Mahjong, Atomix, and Sokoban. There is no ambiguity there. How about if you can’t find an unambiguously 1-player game that already exists in the same sense as those listed, could you create general rules for a game similar to one of the games I listed in this comment? $\endgroup$
    – edit
    Commented Jul 17, 2023 at 17:36
  • $\begingroup$ Actually I think your answer works (thought you meant against a CPU), though are you sure a one-move Chess puzzle is EXPTIME-complete? $\endgroup$
    – edit
    Commented Jul 17, 2023 at 17:48
  • 1
    $\begingroup$ I guess if the puzzle is like "find mate in X" then it's not EXPTIME-complete. But if the puzzle is like "find the best move" (lichess puzzles are like this) then I think it is (although I'm not 100% sure -- I'll update the answer with this). $\endgroup$
    – Kevin Wang
    Commented Jul 17, 2023 at 19:23
  • $\begingroup$ @edit I realized my earlier edit made a reasoning error and stated definitely that finding a winning move is EXPTIME-hard, which I now realize is not actually supported by my reduction (it's the wrong direction). I'm still 90% sure it's EXPTIME-hard but don't have a proof or reference to put in the answer. Letting you know in case you want to remove it as an accepted answer. $\endgroup$
    – Kevin Wang
    Commented Jul 18, 2023 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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