Geek Trivia: Game within a (war)game

What is the most complex game ever completely solved under mathematical game theory — a form of competition far less complicated and subtle than the various types of nuclear war that were "solved" during the climax of the classic geek movie WarGames?

What is the most complex game ever completely solved under mathematical game theory — a form of competition far less complicated and subtle than the various types of nuclear war that were "solved" during the climax of the classic geek movie WarGames?

The most complex game ever solved is English draughts or, as it's known in the United States, checkers. It was solved by the Chinook computer program (the Deep Blue of checkers players, and the first checkers program to win the world checkers title) on April 29, 2007. That said, if the fate of the planet ever came down to guaranteeing a win in a game of checkers, Chinook may be the best player to have on your side, but it can't necessarily promise you a victory.

That's because checkers has only been weakly solved. Within game theory, there are three levels of solved games: ultra-weakly solved, weakly solved, and strongly solved. An ultra-weak solution means that, if both players play a perfect game — making no mistakes and always taking the optimal move at each turn — the outcome of the game can be predicted based on the first move. A weakly solved game means that, using the weak solution strategy, one side can guarantee a win and, if both sides use the weak solution, a stalemate is the inevitable outcome. A strongly solved game is one wherein there is a strategy that allows one side to win the game, or force a draw, no matter how far into the game the strategy is adopted. Put another way, a strong game solution is one that will let you draw or win even if you screw up the first 10 or 20 moves and have to fight your way back.

Checkers has a relatively small, finite number of possible positions, moves, and counter-moves, and it still took 200 PCs lashed together to give Chinook enough computing power to weakly solve the game. In WarGames, the Joshua supercomputer not only strongly solves Tic-Tac-Toe, but strongly solves nuclear war in under three minutes (complete with graphics, too). Given that chess eludes game theory's reach as yet, it seems unlikely that even the most powerful computer on Earth in 1983 could realize that "the only winning move is not to play."

That's not just some spurious cinematic supposition; it's a mathematically melodramatic mess of Geek Trivia.

The quibble of the week

If you uncover a questionable fact or debatable aspect of this week's Geek Trivia, just post it in the discussion area of the article. Every week, yours truly will choose the best quibble from our assembled masses and discuss it in a future edition of Geek Trivia.

Check out this week's quibble.

Falling behind on your weekly Geek fix?

Check out the Geek Trivia Archive, and catch up on the most recent editions of Geek Trivia.

Test your command of useless knowledge by subscribing to TechRepublic's Geek Trivia newsletter. Automatically sign up today!