Author: Frank Schneider
Date: 01:24:05 11/26/98
Go up one level in this thread
On November 25, 1998 at 17:26:58, Bas Hamstra wrote: >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"... > I think an important difference between TSP and Chess is, that there are usually many good solutions in TSP, but often there is only one good move (or variation) in chess. The probability to find it by luck is quite low, I think. What is nice about the idea is, that it is easy to program and that it can be easily parallelized. Frank > >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.