Performance/Optimization of Knapsack(ish) algorithm for move generation for a game

Question

I'm writing an AI for an italian Card game scopa http://en.wikipedia.org/wiki/Scopa And as part of it i need to generate all moves available to the user.

A move consists of finding cards in the centerboard that sum to a card in the players hand.

For example if I have a 5 in my hand and the center contains a [5,4,3,2,1,2] the possible moves would be:

pick up the 5 with my five

pick up the 4 and 1 with my five

pick up one of the twos and the three with my five

pick up the other tow and the three with my five

pick up both 2s and the 1 with my five

After profiling my code it shows that this is by far the most expensive part of the program (about 95 percent of execution time being spent here)

Can you see any way to optimize these methods?

this one actually generates all the possible moves.

private void generateMoves(Card myCard,ArrayList<Card> CurrentMove,
              ArrayList<Card> centerCards,ArrayList<Move> moves, int moveSum) {
    if(moveSum>myCard.value)
    {
        return;
    }
    else if(moveSum == myCard.value)
    {
        Move m = new Move(myCard, new ArrayList<>(CurrentMove));
        rateMove(m);
        moves.add(m);
        return;
    }

    for (Card card :centerCards) {
        if(!card.selected)
        {
            CurrentMove.add(card);
            card.selected = true;
            moveSum += card.value;
            generateMoves(myCard, CurrentMove, centerCards, moves, moveSum);
            moveSum -= card.value;
            CurrentMove.remove(card);
            card.selected = false;
        }
    }
}

this one removes any duplicates (the code above would return 4,1 and 1,4 as different moves from the example) I know its hacky but i couldn't think of anything that would be faster. Ideally they would be combined and duplicates would never be returned but i couldn't get it to work.

 protected void removeDuplicates(ArrayList<Move> moves)
{
    ArrayList<Move> temp = new ArrayList<>(moves);

    for(Move move : temp)
    {
        while(moves.remove(move));
        moves.add(move);
    }
}

Any suggestions would be appreciated.

Answer 1

In your recursive generateMoves method, you can reduce a huge amount of the duplicates by limiting where in the centerCards list you operate in.

My suggestion would be to pass that list through the recursion with a pointer to your current position in the array.... for example:

generateMoves(Card myCard,ArrayList<Card> CurrentMove,
          ArrayList<Card> centerCards, int centercardpos,
          ArrayList<Move> moves, int moveSum)

Then, in your method you can change the loop:

for (Card card :centerCards) { ...

to be:

for (int ci = centercardpos; ci < centerCards.size(); ci++) {
    Card card = centerCards.get(i);

        generateMoves(myCard, CurrentMove, centerCards,
               centercardpos + 1, // new increased limit.....
               moves, moveSum);

This will substantially reduce the number of possible moves (and still get the right answers). Reducing the values you gnerate will also substantially reduce duplicates, which in turn will also improve th pwerformance of removeDuplicates ...

The only time removeDuplicates will have effect is when you have something like (using your example: [5,4,3,2,1,2] ) the moves [5,2] and [5,2] (but the 'other' 2).

Answer 2

If you switch to using HashSet instead of ArrayList, that would remove the need for your entire removeDuplicates method. A HashSet takes care of everything that the removeDuplicates method does.

I would also change a part of your generateMoves method

private void generateMoves(Card myCard, Set<Card> CurrentMove,
              Set<Card> centerCards, List<Move> moves, int moveSum) {
    ...
    for (Card card :centerCards) {
        if(!CurrentMove.contains(card))
        {
            Set<Card> newMove = new HashSet<Card>(CurrentMove);
            newMove.add(card);
            generateMoves(myCard, newMove, centerCards, moves, moveSum + card.value);
        }
    }
}

Although perhaps not a great speed optimization, this removes the need for temporarily adding and removing with moveSum, CurrentMove and card.selected.

I think the major thing you should change is to switch from ArrayList to HashSet. Just remember that when using HashSet, you need to take a look at your implementation of hashCode and equals. Probably you don't want a 2 to be equal to another 2 considering it should be possible for both 2s to be within the same move. It is possible that the default implementation from the Object class is enough for your purpose. But either way, make sure that it obeys the rule "If two objects are equal they should have the same hashCode. If two objects have the same hashCode, they do not need to be equal.