0

わかりました、私が開発しているカードゲームは、誰かがそれを知っていれば、スコパにかなり似ています. デッキには 40 枚のカードが含まれており、それぞれ 10 枚のカードの 4 つの異なるスートに分割されています (エース => 値 1、2 => 値 2、3 = ...、4、5、6、7、ナイフ、クイーン、キング => 値 10)。 ）。2 人のプレイヤー (実際には AI と人間のプレイヤー) がいて、手札に 4 枚のカードがあります。

テーブルには 4 枚のフリー カードがあり、プレイヤーは次のルールに従ってのみそれらを受け取ることができます。テーブルからクイーンを取る）。2) 数字カード (エースから 7) は、同じ数字のカードまたはそれより小さい数字のカードを合計で取ることができます (たとえば、7 を持っている場合、7 または {エース、6} または {3、4) を取ることができます。 } または { エース、スリー ツー })。

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

このアルゴリズムを何らかの方法で改善できると思いますか? このコードをできる限り短くして、デバッグと保守を容易にしようとしています...また、誰かが重複した組み合わせを避けるためのよりエレガントなソリューションを持っている場合は、本当に感謝します(私は{ ハートのエース、スペードの 2 つ } と { スペードの 2 つ、ハートのエース } の両方を取得したくありません... そのうちの 1 つだけです)。

よろしくお願いします！

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

少し奇妙に見えますが、これは、特定の値のカードが 1 枚しか必要ない場合に、その値の利用可能な各カードを不必要に拾うことを検討しないようにするためです。

配列を昇順でソートすることにより、これをさらに最適化できます。

于 2012-02-14T22:00:19.050 に答える