紙牌遊戲 - 子集合 - 可以優化以下算法嗎？

Question

好吧，我正在開發的紙牌遊戲與Scopa非常相似，如果有人知道的話。 甲板上有40張卡片，分成4張不同的10張卡片（ace => value1，two => value2，three = ...，4,5,6,7，knave，queen，king => value 10）。 有2名玩家（實際上是一名AI和一名人類玩家），他們手中有4張牌。

桌上有4張免費牌，玩家只能遵守以下規則： 1）法庭卡（kn，，王后和國王）只能使用相同的法庭卡（例如，如果我有一個女王，我只能從桌上拿一個女王）。 2）數字卡（從王牌到七）可以採用相同的數字卡或總和較小的數字卡（例如，如果我有一個七我可以拿七或{一個王牌，一個六}或{一個三，一四個}或{一個王牌，三個二}）。

現在時機已到，找到這期間，卡它打開AI最終可以採取：

private List<List<Card>> CalculateAITake() 
    { 
     List<Int32> handValues = new List<Int32>(); 
     List<List<Card>> takes = new List<List<Card>>(); 

     /* here i take every hand card value, in a unique way 
     * in order to avoid processing two or more times the 
     * same value 
     */ 
     foreach (Card card in m_AIHand) 
     { 
      Int32 cardValue = (Int32)card.Rank; 

      if (!handValues.Contains(cardValue)) 
       handValues.Add(cardValue); 
     } 

     /* for each hand card value now, I calculate the 
     * combinations of cards I can take from table 
     */ 
     foreach (Int32 handValue in handValues) 
     { 
      // it's a court card, let's use a direct and faster approach 
      if (handValue >= 8) 
      { 
       foreach (Card card in m_CardsOnTable) 
       { 
        if ((Int32)card.Rank == handValue) 
        { 
         List<Card> take = new List<Card>(); 
         take.Add(card); 

         takes.Add(take); 
        } 
       } 
      } 
      else 
       // it's a numeric card, let's use recursion 
       CalculateAITakeRecursion(takes, (new List<Card>(m_CardsOnTable)), 0, (new List<Card>()), handValue, 0); 
     } 

     return takes; 
    } 

    private void CalculateAITakeRecursion(List<List<Card>> takes, List<Card> cardsExcluded, Int32 cardsExcludedIndex, List<Card> cardsIncluded, Int32 sumWanted, Int32 sumPartial) 
    { 
     for (Int32 i = cardsExcludedIndex; i < cardsExcluded.Count; ++i) 
     { 
      Card cardExcluded = cardsExcluded[i]; 
      Int32 sumCurrent = sumPartial + (Int32)cardExcluded.Rank; 

      /* the current sum is lesser than the hand card value 
      * so I keep on recursing 
      */ 
      if (sumCurrent < sumWanted) 
      { 
       List<Card> cardsExcludedCopy = new List<Card>(cardsExcluded); 
       cardsExcludedCopy.Remove(cardExcluded); 

       List<Card> cardsIncludedCopy = new List<Card>(cardsIncluded); 
       cardsIncludedCopy.Add(cardExcluded); 

       CalculateAITakeRecursion(takes, cardsExcludedCopy, ++cardsExcludedIndex, cardsIncludedCopy, sumWanted, sumCurrent); 
      } 
      /* the current sum is equal to the hand card value 
      * we have a new valid combination! 
      */ 
      else if (sumCurrent == sumWanted) 
      { 
       cardsIncluded.Add(cardExcluded); 

       Boolean newTakeIsUnique = true; 
       Int32 newTakeCount = cardsIncluded.Count; 

       /* problem: sometimes in my results i can find both 
       * { ace of hearts, two of spades } 
       * { two of spades, ace of hearts } 
       * not good, I don't want it to happens because there 
       * is still a lot of work to do on those results! 
       * Contains() is not enought to guarantee unique results 
       * so I have to do this! 
       */ 
       foreach (List<Card> take in takes) 
       { 
        if (take.Count == newTakeCount) 
        { 
         Int32 matchesCount = 0; 

         foreach (Card card in take) 
         { 
          if (cardsIncluded.Contains(card)) 
           matchesCount++;  
         } 

         if (newTakeCount == matchesCount) 
         { 
          newTakeIsUnique = false; 
          break; 
         } 
        } 
       } 

       if (newTakeIsUnique) 
        takes.Add(cardsIncluded); 
      } 
     } 
    } 

你認爲該算法能夠以某種方式改進？ 我試圖儘可能地縮短這段代碼，這樣它可以很容易調試和易於維護...另外，如果有人有一個更優雅的解決方案，以避免重複的組合，我真的，真的很感激它（我不想同時獲得{ace的心，兩個黑桃}和{兩個黑桃，一顆心} ......只有其中一個）。

很多，很多預先感謝！

Answer 1

與其考慮您手中的每張數字卡片並尋找總數可用的免費卡片，我會考慮每個可能的免費卡片總數，然後在您的手中尋找與之匹配的數字卡片。您可以使用某種比特位來加速手中匹配卡的檢查，如果按照升序對免費卡進行排序，則可以避免添加與您跳過的卡匹配的卡，並且如果您添加了卡，則可以停止添加卡你超過了你手中最高的數字卡。

編輯：僞代碼如下（對不起，我在命名變量沒有好）：

call find_subset_sum(1, List<int>, 0) 
// Passing the total because it's easy to calculate as we go 
sub find_subset_sum(int value, List<int> play, total) 
    if total > max_hand_card 
    return // trying to pick up too many cards 
    if total in hand_set 
    call store_play(play) 
    if value > max_free_card 
    return // no more cards available to pick up 
    // try picking up higher value cards only 
    find_subset_sum(value + 1, play, total) 
    // now try picking up cards of this value 
    for each free card 
    if card value = value // only consider cards of this value 
     total += value 
     play.append(card) 
     find_subset_sum(value + 1, play, total) 
    // you could remove all the added cards here 
    // this would avoid having to copy the list each time 
    // you could then also move the first recursive call here too 

這看起來有點奇怪，但是這是要確保，如果你只需要一個特定的值，你不要一卡不必考慮拿起每張可用的卡片。

您可以通過按升序對數組進行排序來進一步優化。