 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I'm currently working on a game in macromedia flash. Graphics are done with
POV-Ray :)
At this moment the thing is only available in the Dutch language. English
will follow later.
www.liuhemen.org/games/sloyd/
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Apache" <apa### [at] hotmail com> wrote in message
news:4053e7b9$1@news.povray.org...
> I'm currently working on a game in macromedia flash. Graphics are done
with
> POV-Ray :)
> At this moment the thing is only available in the Dutch language. English
> will follow later.
>
> www.liuhemen.org/games/sloyd/
WOW.
Nice!
It didn't record my score, though. Did I do that bad? :-)
--
- Respectfully,
Dan
http://<broken link>
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
-[It didn't record my score, though. Did I do that bad?]-
This can be done in 46 moves, and I think no better than that. One such
optimal solution is
1 1 1
1 1 1
1 1 0 2 2
2 2 2
2 2 2
1 1 1
1 1 0
1 1 1 2 2
2 2 2
2 2 2
1 1 1
1 1 2
1 1 1 2 2
0 2 2
2 2 2
1 1 1
1 1 2
1 1 1 2 2
2 2 2
0 2 2
1 1 1
1 1 2
1 1 0 2 2
2 2 2
1 2 2
1 1 1
1 1 2
0 1 1 2 2
2 2 2
1 2 2
1 1 1
0 1 2
1 1 1 2 2
2 2 2
1 2 2
1 1 1
2 1 0
1 1 1 2 2
2 2 2
1 2 2
1 1 1
2 1 2
1 1 1 2 2
0 2 2
1 2 2
1 1 1
2 1 2
1 1 1 2 2
2 2 0
1 2 2
1 1 1
2 1 2
1 1 1 2 2
2 2 2
1 2 0
1 1 1
2 1 2
1 1 1 2 2
2 2 2
0 2 1
1 1 1
2 1 2
1 1 0 2 2
2 2 2
1 2 1
1 1 0
2 1 2
1 1 1 2 2
2 2 2
1 2 1
0 1 1
2 1 2
1 1 1 2 2
2 2 2
1 2 1
2 1 1
0 1 2
1 1 1 2 2
2 2 2
1 2 1
2 1 1
2 1 0
1 1 1 2 2
2 2 2
1 2 1
2 1 1
2 1 2
1 1 1 2 2
0 2 2
1 2 1
2 1 1
2 1 2
1 1 0 2 2
1 2 2
1 2 1
2 1 1
2 1 2
1 0 1 2 2
1 2 2
1 2 1
2 1 1
2 1 2
1 2 1 0 2
1 2 2
1 2 1
2 1 1
2 1 2
1 2 1 2 0
1 2 2
1 2 1
2 1 1
2 1 2
1 2 0 2 1
1 2 2
1 2 1
2 1 0
2 1 2
1 2 1 2 1
1 2 2
1 2 1
2 0 1
2 1 2
1 2 1 2 1
1 2 2
1 2 1
2 2 1
2 1 2
1 0 1 2 1
1 2 2
1 2 1
2 2 1
2 1 2
1 2 1 0 1
1 2 2
1 2 1
2 2 1
2 1 2
1 2 1 2 1
1 2 2
1 0 1
2 2 1
2 1 2
1 2 1 2 1
1 2 2
0 1 1
2 2 1
2 1 2
1 2 0 2 1
1 2 2
1 1 1
2 2 1
2 1 2
0 2 1 2 1
1 2 2
1 1 1
2 2 1
2 1 2
2 0 1 2 1
1 2 2
1 1 1
2 2 1
2 1 2
2 2 1 0 1
1 2 2
1 1 1
2 2 1
2 1 2
2 2 1 2 1
1 0 2
1 1 1
2 2 1
2 1 2
2 2 1 2 1
0 1 2
1 1 1
2 2 1
2 1 2
2 2 1 2 1
2 1 0
1 1 1
2 2 1
2 1 2
2 2 1 2 0
2 1 1
1 1 1
2 2 1
2 1 2
2 2 0 2 1
2 1 1
1 1 1
2 2 0
2 1 2
2 2 1 2 1
2 1 1
1 1 1
2 2 2
2 1 0
2 2 1 2 1
2 1 1
1 1 1
2 2 2
2 0 1
2 2 1 2 1
2 1 1
1 1 1
2 2 2
2 2 1
2 0 1 2 1
2 1 1
1 1 1
2 2 2
2 2 1
2 2 1 0 1
2 1 1
1 1 1
2 2 2
2 2 1
2 2 0 1 1
2 1 1
1 1 1
2 2 2
2 2 0
2 2 1 1 1
2 1 1
1 1 1
2 2 2
2 2 2
2 2 1 1 1
0 1 1
1 1 1
2 2 2
2 2 2
2 2 0 1 1
1 1 1
1 1 1
-Chris
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Still having some CGI problems with the server there. Will be fixed within
two weeks.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thanks for spoiling the game :P
Maybe I'll have to change the rules of that puzzle :P
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Cracking this version is easy, but what about the extreme version of this
game? www.elje.net/games/sloydextreme/
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
There is not much dutch in it, and I can read that
anyway ;) . The rules do look rather simple and I
am wondering if there is (except for stupid moves)
any other strategy than the optimal.
The game looks nice (as can be expected from you,
of course), but I do not think I have
the urge to play it more than ones.
It did not my score either and the top 100 has
a scrollbar that does not function very well.
No feedback when touched and you can not click
in the bar to scroll it one page.
Andrel
Apache wrote:
> I'm currently working on a game in macromedia flash. Graphics are done with
> POV-Ray :)
> At this moment the thing is only available in the Dutch language. English
> will follow later.
>
> www.liuhemen.org/games/sloyd/
>
>
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Sorry about that...
The way I generated that solution was with a program which plays the game
and looks around for good sequences of a few moves, then plays the best one
and looks for moves again.
Perhaps doing it in 3D would be more complicated!
-Chris
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Sounds easy, but how does your algorithm know if a move is "the best one"?
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.
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.....
So Chris, please crack the sloyd extreme if you like:
www.elje.net/games/sloydextreme/
Regards,
Apache
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Apache" <apa### [at] hotmailcom> wrote in message
news:40551ff9@news.povray.org...
> Sounds easy, but how does your algorithm know if a move is "the best one"?
>
> 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.
> 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.....
>
> So Chris, please crack the sloyd extreme if you like:
> www.elje.net/games/sloydextreme/
A great site to test your programming prowess is http://www.neopets.com/
It's against thier rules to write programs to solve their games, but then
again, the whole site is just a trick to put advertising in front of you so
hack away. Corporate vampires are fair game.
--
- Respectfully,
Dan
http://<broken link>
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Who cares about neopets? :P
All I care of is sloyd extreme.......
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Apache" <apa### [at] hotmailcom> wrote in message
news:40552f86@news.povray.org...
> Who cares about neopets? :P
>
> All I care of is sloyd extreme.......
Ah, so -- yer yella, eh? Can't write the software to crack the 'pets, eh?
'kay, fella, you're not chikn'. =-)
--
- Respectfully,
Dan
http://<broken link>
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Apache" <apa### [at] hotmailcom> wrote in message
news:4057361a@news.povray.org...
> > 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.
What about calculating a probability weight for each board assuming 86 is
the shortest path? For example at 0 depth, the pegs are on opposite sides
so that's the aboluste worst and the weight is 0%. The closer you get to 86
moves you calculate the percentage of pegs on their proper sides. So if you
are 10 moves deep, and your weight isn't close to 12% (10/86) you stop
searching that branch. I'm not sure how many paths this would cut out, but
it might cut out some. Of course I'm assuming the best solution doesn't
involve too much backward travel.
AW
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
This still isn't going to be a proof.
I'm not sure quite how I'd go about doing that. Finding some kind of upper
and lower bound might be helpful. If it can be proved that the optimal
solution never takes a non-optimal move under a given heuristic (which can
be complex, since it only needs to be evaluated 86 times), a brute force
search might be possible for the 4x4 (sloyd extreme). I suspect this
problem is in general NP-hard, though.
-Chris
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I have an algorithm that will definitely bring the best solution(s)
possible. It works very fast when I used it for cracking the regular sloyd,
but it needs too much RAM for the extreme version. When I find the time I
might optimize the thing enough to get it working on smaller RAM sizes
(under 512 megs).
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>non-optimal move
define a non-optimal move....
any optimal solution consists of optimal moves, no matter what those moves
are or how counter-intuitive those moves are
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> >non-optimal move
> define a non-optimal move....
>
> any optimal solution consists of optimal moves, no matter what those moves
> are or how counter-intuitive those moves are
I was playing with a 2x2 sloyed and calculating weights using a simple
scheme like the following.
+2_+1
+1__0_-1
___-1_-2
I can solve it in 15 moves, but at move #7 a peg moves from the middle back
to it's own side.
Temporarily decreasing the weight, but the very next move increases again.
So in that case, there is one non-optimal move that appears to be backward
using this particular weighting scheme.
I also don't think you have to search 86 levels deep. You should go down,
and look for mirrors and flips of the boards you've already processed. If
you find one, you know you can solve it the reverse of how you got to it.
Instead of keeping all boards, you could build a database (in memory, or
disk) of as many levels deep as you had storage room for. Then instead of
searching 86 deep, you only have to search 86-(database level) deep.
Something tells me there's some solution out there, that goes 43 deep, and
then just reverses for the solve, assuming 86 is optimal which it probably
isn't.
Also you could compress the boards to 5 bytes. 4 bytes for one colors
position, and one byte to store the empty spots location.
AW
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I'd say: go ahead and crack the game!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Wish, I could, but I never have the time. Just thought I'd throw in my two
cents worth. If one of you smart people does solve it, I'd like to see it.
AW
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I think I have found a very efficient way to crack the game. It will give
the best set of solutions for sure and it probably needs much less RAM than
my previous attempts and that of Zirconium :)
Now for finding the time to code the thing..... :P
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
So what's the secret?
AW
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
1.
Avoid depth-first search, go width-first.
2.
Keep track of every position encountered.
Every position has a pointer to the previous position in the game. (That
position also has it's own previous position etc etc). If the position has
been encountered before, ignore it and don't save it, because when the
program "met" it before, it had done less moves/steps to reach it.
3.
When a single step makes the game situation flip-invertable, you're halfway
and the rest of the game is like the beginning but than flipped-inverted
going backward.
4.
Throw away step sequences that are *absolutely* unnecessary. This is the
trickiest part :-P
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
