How can I determine the card possibilities for a game of Scopa?

Question

In the game of Scopa, at the player's turn, there could be anywhere from 0 to 39 cards on the table (although 10+ is an extreme). I'm trying to figure out the best way to figure out possibilities for the player to pick up cards off the table. Also, in Scopa, you can only pickup cards off the table if there's 1+ cards on the table that add to equal the value of the card in your hand.

Currently, I've got something close to:

for (Card card : cardsOnTable) {
    for (Card card2 : cardsOnTable) {
        if (card2 != card) {
           if (card.getValue() + card2.getValue() == cardInHandValue) {
              //Add to list of possibilities.
           }
        }
    }
}

But that only works out while checking the table for possibilities of two cards. The problem is that there could be possibilities of 3, 4, etc. cards, and that detecting how many cards it needs to check (how many nested loops) doesn't seem possible. What method could I go about using to check for card possibilities?

Answer 1

I'd suggest you change your approach. Instead of attempting to validate every possible set, let the player choose a bunch of cards to attempt to pick up, and then validate their chosen set.

Otherwise, you're looking at evaluating more than 2×10^46 combinations of cards

Answer 2

I agree with Jordaan's approach for the human player of your game...validate only when they've made a selection. If you're trying to make a selection for a computer player (or make a hint for the human player), you're going to have to generate some alternatives.
Since the goal is to find a set of cards from the table that have an equal value than the cards in the players hand, I suggest first sorting the table cards from high to low.
Scan the list to see if a single card equals the hand total (you can stop the loop once the table card is less than the hand total).
Next, look at the pairs by evaluating tableCard[0]+tableCard[1] through tableCard[0]+tableCard[n-1] Again, you can stop when the total is less than the hand's total! Move to tableCard[1] with tableCard[2] through tableCard[n-1], etc. to finish the pairs.
After all pairs, go to triples (the first group of triples would go from tableCard[0]+tableCard[1]+tableCard[2] through tableCard[0]+tableCard[1]+tableCard[n-1], the second group of triples would go from tableCard[1]+tableCard[2]+tableCard[3] through tableCard[1]+tableCard[2]+tableCard[n-1], etc.

Work a couple (relatively) small cases out by hand and you'll see the pattern for the loops.

You can stop as soon as you find a match. If you want to evaluate several legal moves, you could generate some alternatives and use a heuristic to pick the best move. For example, it may be in the "smart computer" player's best interest to take as many cards off of the table as possible.

I would generate the alternatives in a thread and set a time limit to come up with an answer. You could use several threads in parallel to generate different possibilities

Good Luck amb

Answer 3

In fact the maximum number of cards on a scopa table is 13. And by So you could list all possibilities rapidely. Here's a sketch:

class ScopaSum{
  int total;
  list<Card> cards;
  public void addCard(Card card){
    total+card.value;
    cards.add(card);
  }
}

public List<List<Cards>> getAllPossibilities(Card playedCard){
  List<ScopaSum> sums = new List<>();
  for(Card card : cardsOnTable){
    if(card.value > playedCard.value)
      continue;
    List<ScopaSum> allNewSums = new List<>();
    for(ScopaSum sum : sums){
      if(sum.value+card.value <= playedCard.value){
        ScopaSum newSum = new ScopaSum(sum);
        newSum.add(card);
        allNewSums.add(newSum);
      }        
    }
    ScopaSum newSum = new ScopaSum();
    newSum.add(card);
    allNewSums.add(newSum);
    sums.addAll(allNewSums);
  }

List<List<Cards>> allPossibleTake = new List<>();
for (ScopaSum sum : sums){
  if(sum == playedCard.value){
    allPossibleTake.add(sum.cards);
  }
}
return allPossibleTake;
}

Then you can certainly enhance a bit this code for a complete hand (3 cards) and add a weight to gold cards to pick up more interesting cards. And note that if the table contains a card with the same value, the player can only take a such card. (I've skipped this part on the algorithm)