> 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

I can't even read that website..... too much stuff for the eye to view
there. And I took the time/patience to look at it for 10 seconds even!

Post a reply to this message

Been there
Done that
Got the T-shirt

and on the shirt you'll find the text: "I need at least 2 gigs of RAM for
this"

Post a reply to this message

"Apache" <apa### [at] hotmailcom> wrote in message
news:40553783$1@news.povray.org...
> I can't even read that website..... too much stuff for the eye to view
> there. And I took the time/patience to look at it for 10 seconds even!

'scuses
'scuses
'scuses

:-)

-- 
- Respectfully,
Dan
http://<broken link>

Post a reply to this message

:-)

Post a reply to this message

-[Just limit your recusion level to 86]-
There are at least two possible moves that can be made on each turn - are
you saying that we want to examine 2^86 possible games?

-Chris

Post a reply to this message

-[how does your algorithm know if a move is "the best one"]-
It doesnt - it only finds a "good" solution. Good was good enough in this
case though.

-Chris

Post a reply to this message

> -[Just limit your recusion level to 86]-
> There are at least two possible moves that can be made on each turn - are
> you saying that we want to examine 2^86 possible games?

Actually, aren't there more than two possible moves in some cases?
Since storing board positions in memory isn't an option, then yes, if you
don't care about how long it took to find the best solution.  Something like
this should be distributed on several machines.  And if a shorter solution
is found in there somewhere all future scans become shorter.  A depth first
scan though won't run out of memory though, it'll just take a very long
time.  If the computer could look at 1000 board positions a second it'd take
about 2487501686449854 years.  Hmmm, sounds like genetic algorithms would be
better in this case.

AW

Post a reply to this message

> Hmmm, sounds like genetic algorithms would be better in this case.
Not if we want *prove* that there aren't any better solutions to the puzzle.
Setting up a small script that will find a *very good* solution isn't a big
deal, but getting the set of best solutions is something else.

Post a reply to this message

Because the amount of games is limited :)

Post a reply to this message