I'm looking for an example of a game where, just by looking at the current game state, you can tell uniquely the entire game history.

Are there any games with these properties?

I'm looking for a game with two players, that uses a board, and the larger the game tree the better, but preferably not infinite.

  • $\begingroup$ Well it is easy enough to just invent such a game. Why do you want such a game? $\endgroup$ – Eric Wofsey Mar 19 at 7:16
  • 1
    $\begingroup$ I took a crack at inventing a game, but my games are stupid. I believe that if such a game exists, then its game tree can be searched efficiently by programming the rules into a quantum computer. If there's already a game with many known properties, that saves me a lot of work $\endgroup$ – psitae Mar 19 at 7:19
  • $\begingroup$ I'm not sure I understand what you're looking for. We certainly could take a regular game and attach the entire history to each position, but a state like "it's the end of the game and Player 1 wins" shouldn't care about the history, and similarly working backwards from the end. It seems, at my first glance, like you would be adding unnecessary details and distinguishing positions that should be treated the same (if only to make algorithms more efficient). $\endgroup$ – Mark S. Mar 19 at 21:02
  • $\begingroup$ @MarkS., Since game trees explode exponentially, I expect that simply stating the entire game history as the game state will overload the quantum computation I want to do, because you're increasing the memory needed for any computation by a lot. Similarly, if information is destroyed moving forward, then there's no unique was to retrace your steps once you reach the end. The proposed quantum algorithm would brute force the entire game tree, examine the ending states, and then retrace the entire game tree, using interference to eliminate losing branches of the tree. $\endgroup$ – psitae Mar 19 at 22:24
  • $\begingroup$ With a small extension of notation, the games Tic-Tac-Toe, Connect Four or Quatro would be examples of such games. The small extension would be to add the move number to each placement of X or O (in the first case), each colored piece (in the second case) or each Quatro piece (in the last case). $\endgroup$ – Jens Mar 22 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.