Chess and Computers: Using Brute Force

In 1975 in my 4th computer programming course at Boston State as a grad student, I learned the new programming language called Basic. Having completed all my projects, the professor threw at me the challenge/assignment to write a program that would perform a knight's tour. I was to figure a way to use arrays and code a virtual knight hopping around the board with the goal of not stepping on the same square twice. Then print out the successful route.

We were no longer using the IBM 8K cpu computer (yes 8K=8000) but allowed to use the State College Ciber 7 system. To use it people had to take a number like in a deli and wait for hours for the privilege to use the incredible Dec writer terminals or less elegant teletype terminals in order to key in their programs. Programming success in those days was due to perseverance, patience, and insensitive butts.

CPU time at the processor level was rationed to 3 minutes CPU time a job due to wise guy students like Mike Griffin who wrote a program that used 3.5 hours to calculate 28 places of Pi, but I digress.

My first approach in writing the tour was to have the program "look ahead" and store potential legal moves until it saw all 64. But that approach was going badly. Then in a flash of inspiration, I resorted to using the random number generator to just have my knight jump in randomly generated virtual legal hops, store the jumps, and reset all over again if unsuccessful: if having landed on a square twice. But if successful, print out the notation and try again until I gave the command to escape. This monkey banging on the typewriter approach was successful a couple of times per my 3 minutes per attempts. My professor was impressed when I walked in with printouts of my knight's tours. He was tickled at my unexpected approach. Then by brain storming we developed a heuristic weight system; making the center squares more valuable and the biased knight would try hopping away from the center if possible. This really cut down on the unsuccessful attempts.

Use of the brute force of computers to solve problems, instead of relying on elegant programs, has served me well professionally many times. Let the computer do the work, while you avoid the pain of having to think too hard.

For you geeks who like brute force there is a tremendous article at the Chess Cafe by Dadi Jonsson about how GM Helgi Olafsson, demonstrated to Bobby Fischer using a very extensive endgame position filtering methodology and PC/chess software, that Fischer's claim about the 1984 Karpov – Kasparov match in Moscow being fixed was unjustified.

A very interesting story. For you geeks; you can speed read past the chess diagrams just get a hang Fischer's claim.

And for you pure chess-junkies you can speed read past the position filtering details just get a hang of Olafsson's methodology.

But the conclusion is way cool and I bet some of you geek-chess-junkies will put this approach to good use some day in your future.

BTW I feel demonstrations like this prove adjournments should never happen anymore unless we create special ground rules like: U1800 have to use 286's and U3000 have to use 386's.
http://www.chesscafe.com/text/chessok17.pdf

What do you think about banning all adjournments?

Do you have chess computer stories?

Or feelings about the 1984 world championships?

Please comment Mike Griffin 04/29/2008

For more on the knights tour and computers, read the adjacent post of an extremely interesting article by Frederick Friedel.