Games You Didn't Think Were Solved

You know about nim games? You might have heard about them as a kid in school but probably haven't been acquainted with them in a while, because they're not really much of a game. They're more of a math problem disguised as a game. The object of a nim game is, you and one or more other players are trying to count to a target number, and when your turn comes up, you can count by a certain small amount- the next one, two or three numbers in line, perhaps. The object can be either to be the one to count the target number, or if you're looking for a loser, that can be the one who's stuck with the target number.

Nobody plays them outside of K-12 math classes, because these have been solved. In any given game, there are checkpoint numbers that, as long as you reach them, guarantee victory, and these checkpoint numbers can be reliably reached by either the first or second player right from the beginning. The entire game is who goes first or second.

This is not the only game to have been solved, or is on its way to being solved. You of course know about chess, for which computer programs are continually being developed to solve in increasingly distant lengths from the endgame. Tic-Tac-Toe has been solved, solved, and solved again, to the point where Hollywood Squares had to have a five-square-win scenario built in for when the random easily-excitable people they plucked off the street and placed in front of semi-minor celebrities were able to inevitably place the game into a draw.

As luke McKinney of Cracked points out today, Connect Four has also been solved. Namely, it was solved by James D. Allen in 1989, and then again two weeks later (PDF) by Victor Allis of Vrije University in the Netherlands. Assuming perfect play, the first player is supposed to win. A man named John Tromp gave a stronger solution in 1995, allowing the first player to make mistakes and still guarantee victory.

You can do this with any two-player game with a finite number of moves under complete control of the player (e.g. no dice or any other random element) and a finite board. Eventually, given enough time, you can solve it, and figure out whether the game is supposed to have a winner or end in a draw, and what kind of margin of error you have to work with while still guaranteeing the result. The largest game to have been completely solved to date? Checkers. A checkers game is supposed to end in a draw. As with chess, people are still working on Go and Reversi.

The difference between a solved game nobody plays and a solved game people still play often is whether you can reasonably memorize the solution. Which is why people still play chess, and nobody plays nim games.

If you want a game that is, to this point, effectively unsolvable, though? Get a third player. Introduce a third player and the move and strategic possibilities grow by such a large proportion that all but the simplest games are turned unpredictable. I'm sure that eventually someone will come up with a solution to games of more than two people, such as Chinese Checkers, but so far, all that's out there is a solution to solitaire Chinese Checkers.

You know. If any of you have ever thought to play that.