카드 게임 - 부분 집합 합계 - 다음 알고리즘을 최적화 할 수 있습니까?

Question

좋아, 내가 개발하고있는 카드 게임은 Scopa와 비슷하다. 누군가 알고 있다면. 데크에는 각각 10 장씩 4 개의 다른 수트로 나뉘어 진 40 장의 카드가 들어 있습니다 (에이스 => 값 1, 두 => 값 2, 세 = ..., 네, 다섯, 여섯, 일곱 번째, 여왕, 여왕, 10). 2 명의 플레이어가 있습니다 (실제로 AI와 인간 플레이어). 그들은 4 장의 카드를 가지고 있습니다.

테이블에는 4 개의 무료 카드가 있으며, 플레이어는 다음 규칙을 준수해야합니다. 1) 코트 카드 (노크, 퀸 및 킹)는 동일한 코트 카드 만 사용할 수 있습니다 (예 : 여왕 나는 테이블에서 여왕 만 데려 갈 수있다). 2) 숫자 카드 (에이스에서 일곱 번째까지)는 합계로 동일한 숫자 카드 또는 더 작은 숫자 카드를 사용할 수 있습니다 (예를 들어, 내가 7을 가졌 으면 7을 취할 수 있거나 {에이스, 6을} 또는 {3, 4} 또는 {에이스, 3 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); 
      } 
     } 
    } 

는이 알고리즘이 어떻게 든 개선 될 수 있다고 생각하십니까? 디버깅하기 쉽고 유지 보수가 쉽도록이 코드를 줄이려고합니다 ... 누군가가 중복 된 조합을 피하기위한 좀 더 우아한 해결책을 가지고 있다면 정말 감사 할 것입니다. (나는 {하트 하트, 스페이드 하트 2 개}와 {스페이드 2 개, 하트 에이스 2 개} 중 하나만 얻고 싶지 않습니다.

미리 감사드립니다.

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 

그것은 조금 이상한 보이지만 그 보장의 당신은 특정 값 당신이 돈의 하나 개의 카드를 필요로하는 경우 불필요하게 그 값의 사용 가능한 각 카드를 가져 오는 것을 고려하지 마십시오.

배열을 오름차순으로 정렬하여 더 최적화 할 수 있습니다.