[rules-users] 8Puzzle problem with Drools Planner
Geoffrey De Smet
ge0ffrey.spam at gmail.com
Mon Nov 15 14:14:34 EST 2010
I 've been thinking about this: 8puzzle isn't really a planning problem
as you model it, here's the main problem:
a planner move != an 8puzzle move
I 'll call a 8puzzle move "a sliding of a number" from now on, to avoid
confusion.
A perfectly valid planner move would basically move 1 to place and 2 to
place 2 and 3 to place 3.
But the whole point of 8puzzle is to find the sequence of valid 8puzzle
"slidings of a number" to come for a certain problem instance to the
final state.
So if you really want to make 8puzzle work in planner, model it differently:
a possible solution = a sequence of "slidings of a number"
a move = add or remove "slidings", change a "sliding"s direction or
change the order of "slidings"
hard score: if after all the slidings, it's not the perfect endstate:
sum of distance each number still have to slide
soft score: count number of slidings
With kind regards / Met vriendelijke groeten,
Geoffrey De Smet
Op 14-11-10 21:01, Geoffrey De Smet schreef:
> 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 at 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 at lists.jboss.org
>>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>>
>>> --
>>> With kind regards,
>>> Geoffrey De Smet
>>>
>>>
>>> _______________________________________________
>>> rules-users mailing list
>>> rules-users at lists.jboss.org
>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users at lists.jboss.org
>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
>
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>
More information about the rules-users
mailing list