> Sounds easy, but how does your algorithm know if a move is "the best one"?

You keep searching and promote shorter and shorter solutions until you've
exhausted the search space.

> Some years ago I wrote a small script in perl that crackes the sloyd game.
> The larger variant of this game however seems to need so much RAM to hold
> the game positions that I haven't managed to crack it yet.

In college I wrote a program on the VAX there, to crack the Hi-Q peg game.
Like at this site http://gtkboard.sourceforge.net/games/Hiq/.

Anyway, I was having the same problem with memory.  There are more positions
in Hi-Q
than in sloyed, but I was able to compress each board into a 64 bit integer.
In the case of
sloyed you should be able to put it into two 32 bit integers.  The next way
to reduce memory
is to take board rotations and mirrors into account.  In sloyed, I think
only mirrors would come
into play, but in Hi-Q you could end up with the same board position only
rotated about the axis.


> Of course it's very easy to get *some* good solution, but of course we'd
> like to know what sequences are the most efficient ones. Algorithms
> involving genetic algorithms and such will never assure you that you've
> found the best solution(s) possible.....


Really, the only reason to keep board positions, is to reduce redundant
search time.  If you don't
care about the search time, you should at most only need to keep 86 boards,
since someone
on the high scores list has already proven it can be done in that many
moves.  Just limit your
recusion level to 86, and if you find a shorter solution, limit all future
attempts to that level
and so on, until you exhaust the space.

Post a reply to this message