Игра в карты - Сумма подмножества - Можно ли оптимизировать следующий алгоритм?

Question

Хорошо, игра в карты, которую я разрабатываю, очень похожа на Scopa, если кто-то это знает. Колода содержит 40 карт, разделенных на 4 разных масти по 10 карт каждая (туз => значение 1, два => значение 2, три = ..., четыре, пять, шесть, семь, мошенник, королева, король => значение 10 ). Есть 2 игрока (на самом деле ИИ и человек-игрок), и у них в руке 4 карты.

На столе есть 4 бесплатных карты, и игроки могут брать их только при соблюдении следующих правил: 1) Карты суда (мошенник, королева и король) могут брать только одинаковые карты суда (например, если у меня есть королева, я могу взять только королеву со стола). 2) Цифровые карты (от туза до семи) могут принимать одинаковые числовые карты или карты меньшего размера по сумме (например, если у меня есть семерка, я могу взять семерку или {туз, шесть} или {три, четыре } или {туз, три два}).

Теперь пришло время выяснить, какие карты ИИ может в итоге взять в свой ход:

    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);
            }
        }
    }

Как вы думаете, этот алгоритм может быть как-то улучшен? Я пытаюсь сократить этот код настолько, насколько смогу, чтобы его можно было легко отлаживать и поддерживать ... также, если у кого-то есть более элегантное решение, позволяющее избежать дублирования комбинаций, я бы очень, очень признателен ( я не хочу получать оба (туз червей, две пики} и {две пики, туз червей} ... только один из них).

Большое, большое спасибо заранее!

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

Это выглядит немного странно, но это гарантирует, что если вам нужна только одна карта с определенным значением, вам не нужно излишне брать в руки каждую доступную карту с этим значением.

Вы можете оптимизировать это еще больше, сортируя массив в порядке возрастания.