 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> 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] hotmail com> 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
|
|
| |
| |
|
|
|
|
| |
