Today, let's ask how computers help us see mathematical truths. The University of Houston presents this series about the machines that make our civilization run, and the people whose ingenuity created them.
Think back to when you realized that, if neither player makes a mistake, a game of Tic-Tac-Toe always leads to a draw. Why did similar reasoning not lead you to find a perfect strategy in other games of skill, such as connect-four, checkers or chess? If you've tried, you quickly concluded that the number of possibilities is such that no human could consider them all. If you take a second to consider a single position in checkers, it would take a 1000 times the age of the universe to weigh every possibility.
Yet checkers has been solved — just like Tic-Tac-Toe. If both sides play it perfectly, it ends in a draw. Indeed, the best checkers player in the world is a program called Chinook written by a team at the University of Alberta. The program played competitively against humans until winning the man-machine world title in the mid nineties, at which point it was retired from competition. Chinook became provably unbeatable in 2007. This was accomplished by essentially examining all possible games of checkers — and it took 20 years of continuous computations on dozens to hundreds of computers to exhaust all the possibilities.
Brute force computation has yielded answers to many long-standing problems in mathematics: How should quarters be arranged on a surface so that they take up the least space? The honeycomb pattern in which the centers of the quarters form a hexagonal lattice seems to be the obvious answer. Yet it was not until 1953 that all other possibilities were conclusively ruled out by Hungarian mathematician Laszlo Fejes Toth. Toth, who did not use a computer, also considered a similar conjecture proposed by the astronomer Johannes Kepler which answers the question: What is the best way to stack perfectly round oranges so that they take up the least space? Kepler suggested the arrangement used in grocery stores: Start with a layer of oranges arranged in a hexagonal pattern, add a second layer so that the oranges fall within the depressions in the first layer, and continue in a similar fashion. Showing that this is the perfect arrangement turns out to be very difficult. It was only in 1998 that Thomas Hales, currently at the University of Pittsburgh, accomplished it by breaking the problem into a number of cases that were checked by — you guessed it — a computer.
At the basic level, each operation a digital computer performs is very simple — it could be done by a pre-schooler. Yet, strung together in the right way these computations can go far further than the unaided human mind. Yet, I still remain somewhat bewildered, not by what we have learned, but by how we have learned it. It's as if your friend tells you the solution to a puzzle you have been working on for a while, but you aren't fully able to comprehend how she arrived at the answer. While you trust your friend's abilities, some nagging doubt about the answer remains until you are able to check it for yourself.
We have to accept that some problems have solutions that are too complex for the human mind to fully comprehend. I am certain that our children will become more comfortable and more adept with using computers to extend their mind's reach. They will be able to trust these new instruments of exploration, just as we have come to trust that what we see through a microscope is as real as what we see with our own eyes.
I'm Kreso Josic, at the University of Houston, where we're interested in the way inventive minds work.
While chess will probably not be solved in the near future, many other popular games have been solved. For a list see https://en.wikipedia.org/wiki/Solved_game.
A board game is solved, in the weakest sense, when it can be determined whether the first player will win, loose or draw in a perfect game. For other definitions of the term you can look at https://en.wikipedia.org/wiki/Solved_game.
Chinook, the program that can play a perfect Checkers game is available at http://www.cs.ualberta.ca/~chinook/project/. Here you can also find more information about how checkers has been solved.
A lengthy, but very interesting article, about the last time that Chinook was tested to its limits can be found here http://web.archive.org/web/20060829085713/http://www.math.wisc.edu/~propp/chinook.html. It is hard to appreciate how great a player Marion Tinsley truly was.
Alternatively, here is a nice obituary of Tinsley which discusses the issue as well http://www.wylliedraughts.com/Tinsley.htm.
Part of the tree of possible choices in the game of tic-tac-toe.
Interestingly, there is another two player game that looks completely different, but is equivalent to tic-tac-toe: The players take turns in choosing numbers between one and nine without repetition. The first player to choose three numbers that add to 15 wins the game. Arranging the numbers in a magic square shows that a player will win if and only if the numbers chosen lie along a row, column or diagonal.