Hi,
Sounds like your pet AI project :)
> The problem space soon blows up rather large for
> larger board sizes. For instance, I've seen it run out
> of memory on a large machine (caching boards) for N=7
> (7 pegs on a side, 28 holes total), having cached
> about 1M boards.
>
> But N=8 finds a solution in a few minutes. Stopping at
> the first solution, it doesn't run out of memory.
>
> I'm working on balancing time and memory so that
> larger N will still find a solution in a reasonable
> time, but not run out of memory.
What about a meet-in-the-middle algorithm, with one graph
created by running forwards, and one by running backwards.
You would require to calculate ALL board positions to a
given depth in each direction.
Next you compare the two caches looking for duplicates -
these are where a path exists between the start and end.
Perhaps you no longer know *how* to get from the start to
the middle spot, but you can always "Divide and Conquer"
to rediscover what it was.
As a further optimisation, you could work both directions
simutaneously allowing opportunity to short circuit full
creation of both graphs. Recognising impossible positions
would save much computation and memory also.
Jonathan Paton
=====
#!perl
$J=' 'x25 ;for (qq< 1+10 9+14 5-10 50-9 7+13 2-18 6+13
17+6 02+1 2-10 00+4 00+8 3-13 3+12 01-5 2-10 01+1 03+4
00+4 00+8 1-21 01+1 00+5 01-7 >=~/ \S\S \S\S /gx) {m/(
\d+) (.+) /x,, vec$ J,$p +=$2 ,8,= $c+= +$1} warn $J,,
__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page
from News and Sport to Email and Music Charts
http://uk.my.yahoo.com
