2:01 p.m.
See below.
With kind regards / Met vriendelijke groeten,
Geoffrey De Smet
Op 13-11-10 19:33, Anderson Rocha schreef:
Hi Geoffrey, thanks for your reply.
Overall, 8 puzzle isn't a natural planning problem fit, like bin
packing, employee rostering, freight routing or even n queens.
But it should be possible to solve this with planner.
When I try the tabu search like you suggested, if I use 7 or 5 in the
move tabu, it ends up with a wrong solution, and if I use 3 or 1, it
gets into loop. Here is my Drools Planner configuration:
<?xml version="1.0" encoding="UTF-8"?>
<localSearchSolver>
<environmentMode>DEBUG</environmentMode>
<scoreDrl>/rules/eightPuzzleScoreRules.drl</scoreDrl>
<scoreDefinition>
<scoreDefinitionType>SIMPLE</scoreDefinitionType>
</scoreDefinition>
<selector>
<moveFactoryClass>solver.move.factory.EightPuzzleMoveFactory</moveFactoryClass>
</selector>
<acceptor>
<completeSolutionTabuSize>1000</completeSolutionTabuSize>
<completeMoveTabuSize>7</completeMoveTabuSize>
</acceptor>
<forager>
<pickEarlyType>NEVER</pickEarlyType>
</forager>
<termination>
<scoreAttained>0</scoreAttained>
</termination>
</localSearchSolver>
I tried out 2 score calculations:
1- The number of 8Puzzle pieces that are out of place.
that's bad, the score
should favouritize solutions closers to the final
solution
2- The sum of the number of moves that each 8Puzzle piece that is
out
of place need to do to go to its place. This is calculated with the
Manhattan Distance (http://en.wikipedia.org/wiki/Taxicab_geometry).
that's
better. But maybe it's even better to double or exponentialize
that distance.
So distance 1 = 1*1 = 1
distance 2 = 2*2 = 4
distance 3 = 3*3 = 9
distance 4 = 4*4 = 16
To simplify the Email, I will tell you how I defined the first score
calculation. I defined a state as a String, like "6751#2430", where
the character '#' is the empty space, that I called white space. So,
the final state should be "01234567#". The moves are:
1- WhiteUpMove -> from "6751#2430" to "6#5172430"
2- WhiteDownMove -> from "6751#2430" to "6751324#0"
3- WhiteLeftMove -> from "6751#2430" to "675#12430"
4- WhiteRightMove -> from "6751#2430" to "67512#430"
And here are the rules that calculate the score:
rule "0 out of place"
when
$p : Puzzle(gameState not matches "0........")
then
insertLogical(new UnweightedConstraintOccurrence("0 out of place", $p));
end
matches uses regex, that's very unoptimal
Don't use a String to represent the gameState of the problem, use new
int[3][3] or even better new NumberEnum[3][3]
rule "1 out of place"
when
$p : Puzzle(gameState not matches ".1.......")
then
insertLogical(new UnweightedConstraintOccurrence("1 out of place", $p));
end
rule "2 out of place"
when
$p : Puzzle(gameState not matches "..2......")
then
insertLogical(new UnweightedConstraintOccurrence("2 out of place", $p));
end
rule "3 out of place"
when
$p : Puzzle(gameState not matches "...3.....")
then
insertLogical(new UnweightedConstraintOccurrence("3 out of place", $p));
end
rule "4 out of place"
when
$p : Puzzle(gameState not matches "....4....")
then
insertLogical(new UnweightedConstraintOccurrence("4 out of place", $p));
end
rule "5 out of place"
when
$p : Puzzle(gameState not matches ".....5...")
then
insertLogical(new UnweightedConstraintOccurrence("5 out of place", $p));
end
rule "6 out of place"
when
$p : Puzzle(gameState not matches "......6..")
then
insertLogical(new UnweightedConstraintOccurrence("6 out of place", $p));
end
rule "7 out of place"
when
$p : Puzzle(gameState not matches ".......7.")
then
insertLogical(new UnweightedConstraintOccurrence("7 out of place", $p));
end
rule "# out of place"
when
$p : Puzzle(gameState not matches "........#")
then
insertLogical(new UnweightedConstraintOccurrence("# out of place", $p));
end
rule "hardConstraintsBroken"
when
$occurrenceCount : Number() from accumulate(
$unweightedConstraintOccurrence : UnweightedConstraintOccurrence(),
count($unweightedConstraintOccurrence)
);
then
scoreCalculator.setScore(- $occurrenceCount.intValue());
end
Thanks again,
Anderson
2010/11/13, Geoffrey De Smet<ge0ffrey.spam(a)gmail.com>:
> Hi Anderson,
>
> Try a solution tabu of 1000 and combine it a move tabu of 7 (or even a
> smaller prime number), tweak from there with the benchmarker.
> How did you define your score function?
>
> Op 13-11-10 01:27, Anderson Rocha schreef:
>> Hi all,
>>
>> I am wondering if Drools Planner can handle the 8Puzzle problem. I
>> once resolved it with the A* search. But I do not know these simulated
>> annealing and tabu search that Drools Planner implements. So I am
>> having a "Getting stuck in local optima" problem, and depending on the
>> start sollution it gets into loop. But if you enter a really simple
>> start solution it resolves, because it choose the best scores until
>> finish with few steps. If some one can help, let me know what I can
>> send (source code, configuration files) to get some help.
>>
>> Thanks,
>> Anderson
>>
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users(a)lists.jboss.org
>> https://lists.jboss.org/mailman/listinfo/rules-users
>
> --
> With kind regards,
> Geoffrey De Smet
>
>
> _______________________________________________
> rules-users mailing list
> rules-users(a)lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users