Author: Graham Laight
Date: 05:20:42 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"... > > >Bas Hamstra. This is an excellent post! However, I feel the title is wrong, so I've changed the title. Unfortunately, I don't think the method would work for chess, because a "good" path in the search tree is not good enough - if your opponent is competitive, you really need the "best" route.
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.