<p>From the comments, the desiderata are:</p>
<blockquote>
<p>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 &quot;puzzle game&quot; in that it should have a significant visual component (like a board/grid, visible game pieces, etc.) plus it should involve only one player.</p>
</blockquote>
<p>Any &quot;puzzle&quot; from one of the EXPTIME-hard games should fulfill the requirements. For example, <strong>chess puzzles</strong>:</p>
<p>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.</p>
<h3>Is it EXPTIME-hard to find the best move in generalized chess?</h3>
<p>Probably? But I'm not 100% sure.</p>
<p>The EXPTIME-completeness result for generalized chess is <a href="https://www.sciencedirect.com/science/article/pii/0097316581900169" rel="nofollow noreferrer">Computing a perfect strategy for n × n chess requires time exponential in n, Fraenkel &amp; Lichtenstein, 1981</a>. The paper says that the following problem is EXPTIME-hard:</p>
<blockquote>
<p>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?</p>
</blockquote>
<p>In (generalized) chess puzzles, the question is a bit different:</p>
<blockquote>
<p>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).</p>
</blockquote>
<p>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.</p>
<p>If it is, then the argument from the Fraenkel &amp; Lichtenstein 1981 paper also applies to generalized chess puzzles.</p>
<p>(Note that this doesn't apply to puzzles of the form: &quot;Find mate in X for White&quot;, only to puzzles like &quot;Find a winning move&quot; (like puzzles on Lichess).</p>

CC BY-SA 4.0
2023-07-17T17:36:16.433Z
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**?
edit
CC BY-SA 4.0
2023-07-17T17:48:11.290Z
Actually I think your answer works (thought you meant against a CPU), though are you sure a one-move Chess puzzle is EXPTIME-complete?
edit
CC BY-SA 4.0
2023-07-17T19:23:12.313Z
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).
Kevin Wang
CC BY-SA 4.0
2023-07-18T16:16:39.900Z
@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.
Kevin Wang
CC BY-SA 4.0
2023-07-17T16:53:43.427Z
2023-07-18T16:07:58.393Z
2023-07-18T16:07:58.393Z
Kevin Wang
<p>I noticed a lot of 1-player games have been shown to be NP-Hard, like <a href="https://www.technologyreview.com/2012/01/26/188193/pac-man-proved-np-hard-by-computational-complexity-theory/" rel="nofollow noreferrer">Pac-Man</a>, <a href="https://web.math.ucsb.edu/%7Epadraic/ucsb_2014_15/ccs_problem_solving_w2015/More%20NP%20Complete%20Games.pdf" rel="nofollow noreferrer">The World's Hardest Game</a>, Tetris, etc.</p>
<p>For PSPACE-Complete, I noticed that Wikipedia listed these 1-player games:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>There are a few other 1-player games, like Super Mario Bros, that I saw are PSPACE-complete, too.</p>
<hr />
<p>However, when I looked for EXPTIME-complete games, I found some like Chess, checkers, and Go, although I was looking for <strong>1-player</strong> games. Are there any?</p>
<p>As for EXPSPACE-complete, do any games (1-player or otherwise) exist? Other than <a href="https://www.technologyreview.com/2019/05/07/135482/magic-the-gathering-is-officially-the-worlds-most-complex-game/" rel="nofollow noreferrer">undecidable Magic The Gathering</a>, I wasn't able to find a game at or beyond EXPSPACE.</p>

CC BY-SA 4.0
2023-07-17T04:47:38.197Z
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.
Shaull
CC BY-SA 4.0
2023-07-17T06:29:50.380Z
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.
edit
CC BY-SA 4.0
2023-07-17T16:50:38.373Z
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
Kevin Wang
<cc.complexity-theory><np-hardness><complexity-classes><gt.game-theory><pspace>
Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?
edit
# Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?

(Asked by: username_0 on 2023-07-17)

I noticed a lot of 1-player games have been shown to be NP-Hard, like [Pac-Man](https://www.technologyreview.com/2012/01/26/188193/pac-man-proved-np-hard-by-computational-complexity-theory/), [The World's Hardest Game](https://web.math.ucsb.edu/%7Epadraic/ucsb_2014_15/ccs_problem_solving_w2015/More%20NP%20Complete%20Games.pdf), 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](https://www.technologyreview.com/2019/05/07/135482/magic-the-gathering-is-officially-the-worlds-most-complex-game/), I wasn't able to find a game at or beyond EXPSPACE.

**Tags:** cc.complexity-theory, np-hardness, complexity-classes, gt.game-theory, pspace

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: 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  

---

## 1 answers

### Answer by username_2 on 2023-07-17. Score: 1 | Accepted answer

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](https://www.sciencedirect.com/science/article/pii/0097316581900169). 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).

> **Comments:**
> **username_0**: 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**?  
> **username_0**: Actually I think your answer works (thought you meant against a CPU), though are you sure a one-move Chess puzzle is EXPTIME-complete?  
> **username_2**: 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).  
> **username_2**: @username_0 I realized my earlier username_0 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.  

---

