June 8, 2010 Handout for OLLI summer workshop on
COMPUTERS VERSUS HUMANS*

Leader: Theo Pavlidis (t.pavlidis@ieee.org)

HOW COMPUTERS PLAY GAMES

The programmer must specify in detail how the machine is going to play in each situation. This is easy for simple games such as Tic-Tac-Toe (see the back page for a listing) but quite hard for games such as chess.

There are 20 different possible initial moves for white and the same number for black so there 400 possible first moves (move= move by white and move by black). If we are going to look four moves ahead, the number of possibilities is (400)⁴, roughly 25 billion. If a machine can look at a million moves a second, it will still require 25,000 seconds or about 7 hours. Expert human players may look 10 or moves ahead but they follow only a few possibilities.

In the old days computer programs that played chess tried to replicate human play and they did not go far that way. A breakthrough occurred in the 1970's when Ken Thompson (then at Bell Labs) hit upon a different idea. Take advantage of the speed of the machines and use a brute force to look at all possibilities for a small numbers of moves ahead. The result was Belle that used special purpose hardware to examine 160,000 positions per second. In 1980 Belle won the World Chess Championship and it achieved master level against human players.

The IBM machine, Deep Blue, used the same approach as Belle with improved special purpose hardware that could examine 200 million positions per second. In 1997 it beat the human world champion.

For more see http://www.theopavlidis.com/CvsH/ComputerChess.htm. The page contains links to additional resources.

ON LINE TIC-TAC-TOE GAMES

http://www.goriya.com/flash/tictactoe.shtml

http://ostermiller.org/calc/tictactoe.html (Has problems with the Chrome browser, so it best to use Internet Explorer.)

ON LINE CHESS

http://www.chess.com/

Or do a Google search for "Chess" and the first two returns are sponsored links with free online chess. (The URLs are a bit too cumbersome to list here.)