[rules-users] 8Puzzle problem with Drools Planner

[Geoffrey De Smet]

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
>