在2D阵列中寻找最佳群体的算法

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作为最大牌的组合：三的一类R8-Y8-B8，同花顺R6 -r7-r8，以及每个可能的直* 6 * 7-r8。对于其中的每一个，从集合中取出卡片，然后递归检查黄色8，然后是蓝色8，然后是红色7，黄色7，蓝色7，红色6 ......的组合，直到您检查了除2之外的所有内容和1;如果可以的话添加3-2-2-2和1-1-1。在每一步中，检查哪个递归返回最大分数，并返回此最大值。

---

让我们来看看在每个步骤中会发生什么。假设我们正在研究红色8的组合;我们有像可用卡：

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

首先，采用三的一类R8-Y8-B8，如果可能的话。创建的可用卡的复制，删除8的，以及直改乘7的：

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

（尝试三的一类在当前卡为红色时才需要这样做，以避免重复）

然后，如果可能的话，使用直冲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个）。对于这些，创建的可用卡的复印件，取出三张牌，并改乘黄色8：

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

然后，终于，在不使用递归红8：创建的可用卡的复印件，祛红8改乘黄色8：

score = max_score(cards_copy, next = yellow 8) 

你再计算其中的这些选项具有最大得分（加上它的递归返回的得分），并返回最高得分。

---

在JavaScript中的快速测试显示，全套24卡，该算法经过3000万个递归找到最高分560，并变得非常缓慢。但是，一旦3张高价值卡片被移除，递归次数就会降至100万以下，大约需要1秒钟，并且移除6张高价值卡片后，它会降至20,000以下，几乎立即返回。

对于几乎完整的集合，您可以预先计算最大分数，并且只在移除特定数量的卡后才计算分数。无论如何，很多套都会重复;去除r6-r7-r8将得到与去除y6-y7-y8相同的最大分数;删除r6-y7-b8是删除b6-y7-r8的重复...因此，首先将输入更改为规范版本，然后查找预先计算的分数。例如。使用预先计算的分数为3或6张卡片移除的所有组将需要存储45,340分数。

---

作为一个代码示例，这里是我测试的算法的JavaScript代码：

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位而不是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

几乎成套的速度可以通过使用观察得到进一步改善，如果可以进行所有三种花色同花顺对于当前的排名，那么这总是最好的选择。这大大减少了递归次数，因为可以一次跳过九张牌。这种检查应加努力为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; 
     } 
    }