二维阵列中最优群的求解算法

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|

我可以拿三张牌(相同的数字，直的，平的)，而每一种类型的得分是不同的。我的问题是，如何计算一个正在进行的游戏的最大可能得分(找到最优组)，在那里一些卡片已经丢失。例如：

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。在每一步，检查哪个递归返回最大分数，并返回这个最大值。

让我们看看在这些步骤中发生了什么。假设我们看到的是红色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

​

对于几乎完全集的速度可以进一步提高，通过观察，如果所有三套西服都可以直接冲平当前的排名，那么这永远是最好的选择。这大大减少了递归的数量，因为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;
        }
    }