Games and Computers

In their book, Weird Maths, David Darling and Agnito Banerjee have a chapter on whether certain sports can be “solved”, i.e., can a winning (or at minimum, avoid a loss) strategy be found for every game that can be played in that sport?

 

Chess has far too many variations that increase exponentially as the game progresses, and thus not solvable for every possible game. However:

“The top computers are now so far beyond the rating ever achieved by a human that it’s safe to say that no one will ever defeat the best computer chess players again.”

 

More interestingly:

“Games don’t need a big board in order to be complex.”

Remember that game, dots and boxes? You create a rectangular grid of points. Players alternately draw a line between any two points (horizontally or vertically, not diagonally). The person who joins the fourth side of a square to complete it “gets” that square. At the end, whoever has more squares wins. Now for the interesting point: once the grid is of a decent size to make the game interesting:

“Theoriticians have no clue who will win at the start.”

 

Then there’s the Chinese game, Go, played on a 19x19 board (much bigger than chess’ 8x8 board). Now, computers using AI (instead of brute force) have defeated the human world champion at Go. Some of the moves of such computers are options no human has ever conceived of in thousands of years of game play!

 

Or take draughts, also known as checkers. In 2007, computers finally proved that the game of draughts or checkers will always end in a draw, as long as both players played perfectly, making no mistakes.

 

But all of the above are “games of perfect information”. Both players have all the necessary information, nothing is hidden, there is no element of chance. Can computers ever “solve” games like poker, where information is hidden, and the element of chance exists? For such games, the definition of “solved” has to be changed. After all, no matter how good the algorithm, a very bad computer hand of cards would still lose to a human who got a great hand. So the definition of “solved” for such games is statistical: over a long run, can a computer always win at games with imperfect information, like poker? The answer to that modified question is Yes.

 

How about Rock-Paper-Scissors? The optimal strategy is to play each type 1/3 of the time. But that’s easier said than done. Why? Because we humans can never replicate true randomness. We tend to favour and follow patterns, even if it is unconsciously. And so a computer playing true random and reacting to your patterns would win most of the time.

 

Trust a computer to take the fun out of a game…