Author: Peter Fendrich
Date: 06:47:31 11/26/98
Go up one level in this thread
You are describing what I would call an "Evolutionary Algorithm" and it could as well be applied to "Genetic Algorithms" with about he same pros and cons. This is an optimization technique that works extremely well in certain domains where the optimum is not as important as an "optimal enough" solution. One of the really difficult tasks with this kind of alg's is how to put different kinds of restrictions and conditions on top of the problem defined. One important restriction in this case is of course the rules of chess. Not many of the variations generated are really legal. This restriction is probably solvable but much worse is the conditions introduced by the minimax optimisation. You can't really know if the variation is in any way optimal for both players and you don't know if it's near optimal either. The minimax type of domain places in a way conditions on each side dynamically depending on the other sides behaviour. Very sadly(!) I don't think it's applicable in this case because of the minimax condition. Prove me wrong, by taking a top 10 SSDF place, and I will try to nominate you for the Nobel Prize! //Peter 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 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.