2次元配列で最適なグループを見つけるアルゴリズム

Question

24枚のカード（8枚の赤、8枚の青、8枚の黄色のカード）があります。

red |1|2|3|4|5|6|7|8| 
yellow |1|2|3|4|5|6|7|8| 
blue |1|2|3|4|5|6|7|8| 

それぞれ3つのカード（同じ番号、ストレート、真っ直ぐなフラッシュ）を使用できますが、タイプごとに異なるスコアが付けられます。 私の質問は、いくつかのカードが既に欠落している進行中のゲームの最大可能スコア（最適グループを見つける）を計算する方法です。例えば ：

red |1|2|3|4|5|6|7|8| 
yellow |1|2|3| |5| |7|8| 
blue |1|2| |4|5|6| |8| 

---

三の-種類のスコアである：

1-1-1 20 
2-2-2 30 
3-3-3 40 
4-4-4 50 
5-5-5 60 
6-6-6 70 
7-7-7 80 
8-8-8 90 

直線のスコアである：

1-2-3 10 
2-3-4 20 
3-4-5 30 
4-5-6 40 
5-6-7 50 
6-7-8 60 

スコアストレートフラッシュの場合：

1-2-3 50 
2-3-4 60 
3-4-5 70 
4-5-6 80 
5-6-7 90 
6-7-8 100 

Answer 1

再帰的にすべての組み合わせは次のように行くだろうしようとする解決策：

スタートは最高のカードとして赤8を持っている組み合わせを見て：3のユニークなR8-Y8-B8、ストレートフラッシュのR6 -r7-r8、およびすべての可能なストレート* 6- * 7-r8を使用します。これらのそれぞれについて、セットからカードを取り出し、黄色8、青8、赤7、黄7、青7、赤6の組み合わせをチェックして、および1;可能であれば、3つの種類の2-2-2と1-1-1を追加します。各ステップで、どの再帰が最大スコアを返すかをチェックし、この最大値を返します。

---

これらの各ステップで何が起こるかを見てみましょう。赤8との組み合わせを見ているとしましょう。可能であれば、3のユニークなR8-Y8-B8を使用し、

red ...|6|7|8| 
yellow ...|6| |8| 
blue ...| |7|8| 

最初に：私たちのような利用できるカードを持っています。利用できるカードのコピーを作成し、8代を削除し、7のにまっすぐに再帰：現在のカードは、重複を避けるために、赤のとき

score = 90 + max_score(cards_copy, next = red 7) 

（3-の-種類を試すにのみ行われるべきです溶液）

次に、可能であればストレートフラッシュr6-r7-r8を使用してください。利用できるカードのコピーを作成し、R6、R7およびR8、および8黄色に再帰削除：

その後

score = 100 + max_score(cards_copy, next = yellow 8) 

、非フラッシュストレート赤8を含むあらゆる可能性を使用します。この例では、r6-b7-r8、y6-r7-r8、y6-b7-r8です（最大9つあります）。これらのそれぞれについて、利用できるカードのコピーを作成し、3枚のカードを削除し、8黄色に再帰：

score = 60 + max_score(cards_copy, next = yellow 8) 

その後、赤8を使用することなく、最終的には、再帰的に：赤を削除、利用できるカードのコピーを作成8,8黄色に再帰：

score = max_score(cards_copy, next = yellow 8) 

あなたは、その後（その再帰追加によって返されたスコア）最大のスコアを持っているこれらのオプションのどちらを計算し、その最大スコアを返します。

---

JavaScriptで簡単なテストは、24枚のカードのフルセットのために、アルゴリズムは最大スコア560を見つけることが3000万再帰を通過することを示しており、非常に遅くなります。ただし、3枚の高価値カードが削除されるとすぐに、再帰回数は100万回を下回り、1秒ほどかかり、6枚の高価値カードが削除されると、2万回を下回り、ほとんど瞬時に復帰します。

ほぼ完全なセットの場合、最大スコアを事前に計算して、一定数のカードが削除された後にのみスコアを計算することができます。とにかく多くのセットが複製されます。 r6-r7-r8を削除すると、y6-y7-y8を削除するのと同じ最大スコアが得られます。 r6-y7-b8を削除することはb6-y7-r8を削除した複製です...まず入力を標準バージョンに変更してから、事前に計算したスコアを調べます。例えば。 3枚または6枚のカードが取り除かれたすべてのセットで事前計算されたスコアを使用すると、45,340点のスコアを格納する必要があります。

function clone(array) {         // copy 2-dimensional array 
 
    var copy = []; 
 
    array.forEach(function(item) {copy.push(item.slice())}); 
 
    return copy; 
 
} 
 
function max_score(cards, suit, rank) { 
 
    suit = suit || 0; rank = rank || 7;        // start at red 8 
 
    var max = 0; 
 
    if (rank < 2) {        // try 3-of-a-kind for rank 1 and 2 
 
     if (cards[0][0] && cards[1][0] && cards[2][0]) max += 20; 
 
     if (cards[0][1] && cards[1][1] && cards[2][1]) max += 30; 
 
     return max; 
 
    } 
 
    var next_rank = suit == 2 ? rank - 1: rank; 
 
    var next_suit = (suit + 1) % 3; 
 
    max = max_score(clone(cards), next_suit, next_rank); // try skipping this card 
 
    if (! cards[suit][rank]) return max; 
 
    if (suit == 0 && cards[1][rank] && cards[2][rank]) {   // try 3-of-a-kind 
 
     var score = rank * 10 + 20 + max_score(clone(cards), 0, rank - 1); 
 
     if (score > max) max = score; 
 
    } 
 
    for (var i = 0; i < 3; i++) {      // try all possible straights 
 
     if (! cards[i][rank - 2]) continue; 
 
     for (var j = 0; j < 3; j++) { 
 
      if (! cards[j][rank - 1]) continue; 
 
      var copy = clone(cards); 
 
      copy[j][rank - 1] = 0; copy[i][rank - 2] = 0; 
 
      var score = rank * 10 - 10 + max_score(copy, next_suit, next_rank); 
 
      if (i == suit && j == suit) score += 40; // straight is straight flush 
 
      if (score > max) max = score; 
 
     } 
 
    } 
 
    return max; 
 
} 
 
document.write(max_score([[1,1,1,1,1,0,1,1], [1,1,1,1,1,1,1,0], [1,1,1,0,1,1,1,1]]));

アルゴリズムをスピードアップするために明白な方法は、24ビットを使用することです：コード例として

---

、ここで私は、アルゴリズムをテストしたJavaScriptコードですカードを表現するための3x8ビット配列の代わりにパターンを使用します。そのようにしてアレイの複製はもはや必要なくなり、ほとんどのコードはビット操作に変わります。 JavaScriptでは、約8倍高速です：

function max_score(cards, suit, rank) { 
 
    suit = suit || 0; rank = rank || 7;        // start at red 8 
 
    var max = 0; 
 
    if (rank < 2) {        // try 3-of-a-kind for rank 1 and 2 
 
     if ((cards & 65793) == 65793) max += 20;  // 65793 = rank 1 of all suits 
 
     if ((cards & 131586) == 131586) max += 30; // 131586 = rank 2 of all suits 
 
     return max; 
 
    } 
 
    var next_rank = suit == 2 ? rank - 1: rank; 
 
    var next_suit = (suit + 1) % 3; 
 
    var this_card = 1 << rank << suit * 8; 
 
    max = max_score(cards, next_suit, next_rank);   // try skipping this card 
 
    if (! (cards & this_card)) return max; 
 
    if (suit == 0 && cards & this_card << 8 && cards & this_card << 16) { // try 3oaK 
 
     var score = rank * 10 + 20 + max_score(cards, 0, rank - 1); 
 
     if (score > max) max = score; 
 
    } 
 
    for (var i = 0; i < 3; i++) {      // try all possible straights 
 
     var mid_card = 1 << rank - 1 << i * 8; 
 
     if (! (cards & mid_card)) continue; 
 
     for (var j = 0; j < 3; j++) { 
 
      var low_card = 1 << rank - 2 << j * 8; 
 
      if (! (cards & low_card)) continue; 
 
      var cards_copy = cards - mid_card - low_card; 
 
      var score = rank * 10 - 10 + max_score(cards_copy, next_suit, next_rank); 
 
      if (i == suit && j == suit) score += 40; // straight is straight flush 
 
      if (score > max) max = score; 
 
     } 
 
    } 
 
    return max; 
 
} 
 
document.write(max_score(parseInt("111101110111111111011111", 2))); 
 
//         B  Y  R 
 
//         876543218765432187654321

スピードはほぼ完全なセットのためには、さらに3つのすべてのスーツであればストレートフラッシュを作ることができることを観察を使用することによって改善することができます現在のランクでは、これは常に最適なオプションです。これにより、9つのカードを一度にスキップすることができるため、再帰回数が大幅に削減されます。このチェックは、ランク1と2の3種類のタイプを試した直後に追加する必要があります。

if (suit == 0) {        // try straight flush for all suits 
     var flush3 = 460551 << rank - 2;  // 460551 = rank 1, 2 and 3 of all suits 
     if ((cards & flush3) == flush3) { 
      max = rank * 30 + 90; 
      if (rank > 2) max += max_score(cards - flush3, 0, rank - 3); 
      return max; 
     } 
    }