Author: Bas Hamstra
Date: 14:26:58 11/25/98
A while ago me and some friends did some puzzling programming. N-queens problem etc (I'm still proud of my 220 byte assembler COM program which you could start up with "Queens [n]", n being the number of queens on a n x n board). We also did the travelling salesman for up till 100 cities or so. For smaller numbers of cities you could use brute force. With some tricks to get early cutoffs, but still 100% brute force. But for larger numbers of cities brute force was simply inadequate. Fun days. New length records every day, by a growing number of people on the "bulletin board". It appeared that you could get to a nearly optimal solution *extremely* fast by... random mutations! Of course you had to do something to get out of local optima, so that a certain mutation might lenghten the "path" somewhat temporarily, to move to a better local optimum afterwards. Just pick a random piece of the path, and "mirror" it. If it shorter, great. If the path gets longer than the previous path plus some tolerance (else you get stuck in local minima) just "mirror back". Repeat this steps. Example: StartPath = A B C D E F G H I J K L Pick random piece: C D E F And mirror it: A B F E D C G H I J K L If the path becomes *longer* reverse the mutation. And WHAM!*Extremely* short paths in seconds. Amazing! Just stupid RANDOM swapping gives very short paths *instantly* ! After a while the path doesn't change anymore and you probably have the optimal solution. But... you never will know if it IS optimal. However displaying plotting the path in a 2 dimensional graph shows you that it likely IS the shortest path (closed, circle like plot, with no crossing lines), though you still can't prove it. The point is that random mutations can (in certain cases) reach very good solutions very fast for problems Brute Force would cost thousands of years to solve. Not THE OPTIMAL solution, but A FAST ADEQUATE solution. Now I have been wondering if this principle could be used in a chess program. Difference of course being that in a chess program 2 players "work against each other"... Bas Hamstra.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.