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)

enter image description 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.

• Simon Forsberg: Have you implemented hashCode and equals properly in your Move class and your Card class?
• Simon Forsberg: 520 seconds runtime? How many cards do you have on the board and in your hand, really?
• thermite: I ran 300 games and at each move it performs 200 roll outs of a Monte Carlo tree search. And equals yes hashCode no

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

• thermite: thanks your suggestion Cut run time of the same data set from 500+ seconds to just over 100
• rolfl: 100 seconds is a long time for this code still....
• thermite: 36 moves per game 6 available moves per turn (average) 200 simulated playouts to the end of the game for each move at each turn in the simulation we need to figure out what moves are available to us so on average 18 times 300 games so it gets called approximately 116640000 times

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.