Computers are now the masters of Checkers. The perfect strategy results in a draw. A win only occurs when the losing player made more mistakes than the winning player.

We know that all games of perfect imformation have saddle points. If it has a saddle point, then there is a perfect strategy for each player.

After 13 years of brute-force computer analysis examining all 500 billion billion possible board positions, researchers announced Thursday that they had solved the centuries-old game of checkers.

The result?

A perfect game cannot be won or lost but will inevitably end in a draw, according to the research published in the journal Science online.

Computers calculated the results of every single move and counter-move in checkers. They formed a game matrix and discovered saddle points.

A dominating strategy is where one strategy is better than any others for a player regardless of what his opponent does. If there is a dominating strategy, there is a saddle point.

The saddle point is really a point of inflection. In a game matrix, it’s the smallest value for its row and largest value for its column – that is, the “minimax.” Saddle points represent the best result for a player seeking to minimize his losses and maximize his gains.

We know about the saddle points in many simple games. Tic-Tac-Toe has a known perfect strategy. Player 1 marks Xs in three corners. In 4 moves, he wins regardless of what player 2 does.

Checkers has saddlepoints and dominate strategies. So if one player deviates from the perfect strategy, they will lose. Rationally, they should stick to the perfect strategy.

Games like Chess and Go also have perfect strategies, although we have not discovered them yet because the games are more complex.

This applet graphs out a game matrix so you can visualize the saddlepoint.

Some games have multiple saddlepoints. Players use Mixed Strategies in these cases. In a game, a player may decide he gets the highest benefit with a 4/9 chance of playing strategy one and a 5/9 chance of playing strategy two. Relying on one strategy alone results in a loss. By mixing the strategies the player minimizes his losses.

This also tells us a bit about heuristics. Humans are versatile machines, but we tend to make gross estimations with high probabilities of error. When we played checkers, we do not calculate the values of billions of moves. We estimate. Good estimates can set us on the right path, but the errors accumulate and we make mistakes.

Computers are dumb AIs right now. They can be programmed to accurately calculate the perfect strategy in games of perfect information like Checkers and Chess but they are restricted to only type of game. Humans can play Chess, Checkers, Go, then go into the real world and run a business, manage relationships and families, and create military strategies.

Computers so far cannot handle stochastic games. Human estimation and rough pattern analysis is superior to raw calculation in games of random chance. Evolutionary heuristics gives us an advantage in the real world. I can see Dumb AIs serving as advisors by calculating the probabilities and values for strategies in a confined environment. This would reduce our margins of error from bad estimates at least.

Advertisements