Re: [rules-users] 8Puzzle problem with Drools Planner

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&lt;ge0ffrey.spam(a)gmail.com&gt;: >> 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 > _______________________________________________ rules-users mailing list rules-users(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/rules-users