Are there any examples of non-random games whose perfect-play outcome is proven but not solved?

238 Views Asked by At

My curiosity is inspired by the world-championship chess match of a couple days ago, when a supercomputer announced that mate-in-thirty-moves could be forced, but could not prove/explain it to humans because the database of combinations was much too large. (The game ended in a draw because the player was only human.)

This makes me wonder about game-solving, and specifically the title question here. Some games are weakly-solved, whereby a perfect strategy has been outlined... but has any game been "weakly proven" to be a win (or draw) with perfect play, but without this actually being translatable into victory? In other words, that some winning strategy exists but is unknown?

1

There are 1 best solutions below

2
On BEST ANSWER

There are two-player games where it is impossible to draw, and which also cannot continue on indefinitely. This means that there is a winning strategy for one of the players, because either the first player can force a win (i.e. there exists winning strategy for the first player), or else there must be some way for the second player to make him not win (which makes this a winning strategy for the second player because the game must end eventually). So there is a winning strategy, but we just don't know for which player.

There are also such finite draw-less games which are symmetric, i.e. where the two players have exactly the same available moves and the same goal (apart from using different coloured pieces), and for which being one move ahead is never a disadvantage. If the second player had a good (supposedly winning) strategy, then in this type of game the first player could apply the same strategy and always be ahead and hence win. The second player therefore cannot really have a winning strategy, so the first player must have one, even though we don't know what it is.

This is called the strategy stealing argument. The best known game for which this works is the game of hex. So there always exists a winning strategy for the first player in hex, however large the playing board is. Computers can only find this winning strategy for relatively small boards.