0

好吧，如果有人知道的话，我正在开发的纸牌游戏与 Scopa 非常相似。一副牌包含 40 张牌，分为 4 种不同的花色，每张 10 张牌（ace => 价值 1，二 => 价值 2，三 = ...，四，五，六，七，无赖，女王，国王 => 价值 10 ）。有 2 个玩家（实际上是一个 AI 和一个人类玩家），他们手里有 4 张牌。

桌上有 4 张免费牌可以拿走，玩家只能在遵守以下规则的情况下拿走它们： 1) 宫廷牌（无赖、皇后和国王）只能拿相同的宫廷牌（例如，如果我有一张皇后，我只能从桌子上拿一个皇后）。2) 数字卡（从 ace 到 7）可以取相同的数字卡或更小的数字卡（例如，如果我有一个 7，我可以取一个 7 或 { a ace, a 6 } 或 {a 3, a 4 } 或 { 一个 ace，三个 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);
            }
        }
    }

你认为这个算法可以以某种方式改进吗？我正在尝试尽可能地缩短此代码，以便它易于调试和易于维护......此外，如果有人有更优雅的解决方案来避免重复组合，我真的非常感谢它（我不想同时获得 {红桃 A，黑桃两张 } 和 {黑桃两张，红桃 A } ......只有其中一个）。

非常非常感谢提前！

4

1 回答 1

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

这看起来有点奇怪，但这是为了确保如果您只需要一张特定价值的卡，您就不必考虑拿起该价值的每张可用卡。

您可以通过按升序对数组进行排序来进一步优化这一点。

于 2012-02-14T22:00:19.050 回答