2

Is there a game with infinite possible board arrangements (infinite experience conditions?), but which has been strongly solved, i.e. whose optimal move at every stage of the game has been solved?

If such a game exists and if its name is given, it will be of great help to me. Waiting for it. This is going to allow me make certain conclusions in other domains via analogy.

  • 1
    In what way does this take into account e.g. the threefold repetition rule of chess? Theoretically two queens can loop around the board forever, but at a certain point they'll hit a previous state for the third time, enabling a person to end the game -- but it's not automatic. – doppelgreener Jul 9 '17 at 11:16
  • @doppelgreener: Thank you for the comment. I have changed the question. The previous question having infinite moves instead of infinite board arrangements seem to not help me. What I am seeing for see is the conclusion that, even if there are infinite experience conformations/arrangements, optimal decision can be taken at every experience environment by only knowing the game rules. – Immortal Player Jul 9 '17 at 11:28
  • I will also go through your previous link, but only wanted to make changes quickly, as imprecision in question indicated on the surface. By previous question, intentionally two players can perform infinite moves :) – Immortal Player Jul 9 '17 at 11:32
  • Can a board game have infinite possible board arrangements? It seems to be finite for every size of the board. Waiting for a unbelievable experience now. – Immortal Player Jul 9 '17 at 11:34
  • Thanks for clarifying. This will definitely need to look at some atypical games: a finite number of pieces with a finite number of allowed board positions will probably never have infinite possible arrangements, which e.g. rules out most games we'd identify with a checkerboard. – doppelgreener Jul 9 '17 at 11:41
5

Yes, with Nim being the best-known example

You ask for a strongly solved game (presumably referring to the term in combinatorial game theory). According to Wikipedia, games that are strongly solved

Provide an algorithm that can produce perfect moves from any position, even if mistakes have already been made on one or both sides.

It goes on to note that in many cases, this is determined by brute force:

By contrast, "strong" proofs often proceed by brute force—using a computer to exhaustively search a game tree to figure out what would happen if perfect play were realized. The resulting proof gives an optimal strategy for every possible position on the board.

For instance, we can strongly solve 3x3 tic-tac-toe because we can brute force every possible combination and determine perfect moves. Of course, brute force is impossible for an infinite board size, and some games are only strongly solved up to a certain board size. For instance, Hex is only strongly solved up to a 6x6 board. Still, the hope is that this brute force on games like these will lead to an algorithm for perfect play that works for an infinite size (e.g. an NxN board).

The best studied strongly solved game is Nim, where an algorithm has been found that produces perfect play from any position of any size heaps and objects. This game can be played on a board (or just by drawing on a piece of paper), so it counts as a board game.

Most other combinatorial games are played on a fixed board and are not typically studied at NxN sizes. In some cases, an algorithm for those sizes may not be possible. As described above Hex has been strongly solved for a 6x6 board. However, an algorithm that works for NxN boards is unlikely to be found because the problem is PSPACE-complete, meaning that the number of possibles moves increases polynomially in relation to the size of the board, and it would take a polynomial amount of time to solve the game for a given size. It is suspected that this type of game is unsolvable because calculating for an infinite size would take a polynomially infinite amount of time.

Note that games like Chess, Checkers, and Go are EXPTIME-complete, which means that the number of possible moves increases exponentially in relation to the size of the board. Since an infinite board takes exponentially infinite time to solve, EXPTIME-complete problems like this one are also suspected to be unsolvable. Since exponential time takes longer than polynomial time, and PSPAE-complete problems are suspected to be unsolvable, EXPTIME-complete problems are generally considered to be completely unsolvable.

For reference, it took 18 years to strongly solve 8×8 checkers by brute force. It would take exponentially more work to solve a 9x9 board.

(It's been a long time since I've studied this stuff, but I vaguely recall some research considering what impact quantum computers might have on this type of problem. As I recall, it might be possible to reduce a PSPACE problem to a P problem, which can be efficiently solved in polynomial time regardless of the size of the input. That said, I'm not an expert in this field, so take it worth a grain of salt.)

Caveat: I'm not an expert in this field and it's been years since I've studied it. If I've made any incorrect statements about PSPACE-Complete etc. in this answer, please point it out in the comments or correct it.

  • Thank you for the answer. Is it that the optimal moves at every stage of an infinite sized board game exist, but we are not able to know them now, because of computational low power? I am going through the links now. – Immortal Player Jul 9 '17 at 16:50
  • 1
    @ImmortalPlayer I've added a bit more to this. I'm not an expert in this field, but my understanding is that the problem set grows too big as we approach infinity to completely solve the problem such that we can never feasibly solve the problem. PSPACE-complete grows at a slower rate than EXPTIME-complete. Nim is in a different category of complexity in that we have an algorithm that doesn't depend on the size of the game. – Thunderforge Jul 9 '17 at 18:08
  • 1
    Note the difference between "infinite" and "arbitrarily large". Nim is solved for arbitrarily large states - with 10 piles, 100, 1000, etc, the winning strategy is known. Thus Nim is solved for an infinite number of different states. Yet no individual Nim state is infinite. Most games aren't well-defined on infinite boards, and depending on how you define them they might be trivially solved even if the normal game isn't - e.g. in infinite checkers (using the first definition I think of), all moves are equally optimal since the game can never end. – Benjamin Cosman Jul 9 '17 at 19:02
  • 2
    @BenjaminCosman isn't nim also solved for infinite ordinals? – Gabriel C. Drummond-Cole Jul 10 '17 at 0:04
  • 1
    Exactly. We know how to play infinite Nim, but infinite Chess isn't really well defined, so we'd have to figure out what that means before we even consider it for anything larger than a standard 8x8 board. – Thunderforge Jul 10 '17 at 3:04
1

A non-Nim example is one usually presented as a puzzle, such as this Puzzling.SE question. The rules of the game are:

Given a symmetrical (normally circular or square) table, two players take turns putting coins on the table such that no two coins overlap. The player who is first unable to place a coin loses.

There are an infinite number of board positions, because the coins can be placed anywhere within the space of the table, and (at least in a pure abstraction) any epsilon-sized change in the position of a coin is technically a different board state.

The game is solved, because the first player's optimal strategy is:

  1. Place the first coin exactly in the centre of the table.
  2. On all turns after the first, place a coin in the reflection of the position the other player placed their last coin.

As long as the first player does this, the second player always loses regardless of their strategy (and if the first player doesn't do it, I suspect there's a way for the second player to strategy-steal the win in many cases).

Your Answer

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

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