[rules-users] 8Puzzle problem with Drools Planner

[Anderson Rocha]

Hi Geoffrey, thanks for your reply.

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.
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).

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

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
>