用于跑步的卡片游戏手的组合,带有通配符和重复项

Question

用于跑步的卡片游戏手的组合,带有通配符和重复项

Rya*_*yan 7 javascript algorithm combinatorics

制作一个有几个曲折的拉米风格的游戏:

使用两个5套房甲板而不是一个4套房甲板(总共116张卡).
套房从3到King,每个套牌有3个笑话(所以没有2,没有Ace).
11轮,第一轮每位玩家有3张牌,最后一轮每位玩家有13张牌.
除了Jokers狂野之外,每张牌的价值都变得狂野,这与你手中的牌数相对应.
因此围绕一个三分球是狂野的两轮四分球是狂野的...第11轮国王是狂野的(国王的数值是13).

目标是放下你所有的牌.一旦有人'走出去'(放下所有牌),剩下的玩家可以转一圈,同时放下所有牌或尽可能多的有效牌/跑.你手里拿着任何牌都可以获得积分.

玩家只能躺在卡下来集或具有最小的在其中3张卡,即运行set: {3:c, 3:d, 3:h},run: {3:c, 4:c, 5:c}.还有一些轮次你需要获得超过3张卡的设置/运行,因为手中的牌数不能被3整除.

为了开始手工评估,我将卡分成这些结构:

var suites = {
    'clubs' : [],
    'diamonds' : [],
    'hearts' : [],
    'spades' : [],
    'stars' : []
};
var wilds = [];
var buckets = {
    3 : [],
    4 : [],
    5 : [],
    6 : [],
    7 : [],
    8 : [],
    9 : [],
    10 : [],
    11 : [],
    12 : [],
    13 : []
};
//can have more then one run/set so these are used to hold valid runs/sets
var runs = [];
var sets = [];
var r_num = -1; //starts at -1 so ++ will give 0 index
var s_num = -1;

Run Code Online (Sandbox Code Playgroud)

然后删除任何没有任何卡片的套件/桶.
设定评估非常简单,但运行评估是......不那么直截了当.

我想出了这个基于范围的运行评估

    for (var s in suites){
        if(suites.hasOwnProperty(s)){
            var suite_length = suites[s].length;
            if(suite_length >= 2){ //only evaluate suits with at least 2 cards in them
                var range = suites[s][suite_length - 1].value - suites[s][0].value;
                r_num++;
                runs[r_num] = [];

                if( (range - 1) >= wilds.length && (range - 1) == suite_length){
                    suites[s].forEach(function(card){ //large range needs several wilds
                        runs[r_num].push(card);
                    });
                    while(runs[r_num].length <= (range + 1) && wilds.length != 0){
                        runs[r_num].push(wilds.pop());
                    }
               }else if(range == 1 && wilds.length >= 1){ //needs one wild
                    suites[s].forEach(function(card){
                        runs[r_num].push(card);
                    });
                    runs[r_num].push(wilds.pop()); 
                }else if( range == suite_length && wilds.length >= 1){ //also needs one wild
                    suites[s].forEach(function(card){
                        runs[r_num].push(card);
                    });
                    runs[r_num].push(wilds.pop());
                }else if( (range + 1) == suite_length){ //perfect run
                    suites[s].forEach(function(card){
                        runs[r_num].push(card);
                    });
                }
            }
        }
    } 
};

Run Code Online (Sandbox Code Playgroud)

这适用于很多情况,但它在套件中重复.我在玩游戏测试时遇到的最棘手的案例之一是以下几行:
{3:clubs, wild, 3:spades, 4:clubs, 5:clubs, 6:clubs, 6:clubs 7:clubs, 8:clubs, 10:spades, 10:hearts, wild}

因此可以形成12张牌和一张有效的牌照:看起来像这样:
sets: [{3:c, 3:s, wild},{10:s, 10:h, wild}]
runs: [{4:c, 5:c, 6:c}, {6:c, 7:c, 8:c}]

不幸的是,我最终得到了以下几点:
sets: [{6:c, 6:c, wild}, {10:s, 10:h, wild}]
runs: [{3:c,4:c,5:c}]
OR(取决于我是否评估集合或先运行)
sets: [{10:s, 10:h, wild, wild}]
runs: [{3:c, 4:c, 5:c, 6:c, 7:c, 8:c}]
与剩下的其他卡片.

当我有这样的牌时,我也会在前几轮遇到
{6:h, 7:h, 7:h, 8:h}
问题:当试图放下局部手牌时,上面是一个问题.在部分手牌情况下
{6:h, 7:h, 8:h} 是一个有效的运行,玩家只剩下7分.但是因为我没有摆脱重复,所以它不会将其评估为可能的运行并且玩家留下了所有的分数(28).

我的问题是: 是否有更好的方法/算法来完成整个过程？

我目前解决这个问题的想法有点令人沮丧,因为它们涉及许多case/if特定手牌长度/游戏情况/套件长度的陈述.有时我删除重复的时候有时我不会拆分套件有时候我不会...很多头痛基本上我不确定我是否覆盖了所有可能的手/部分放置情况.

Answer 1 · 2015-07-25T00:35:39.000927+08:00

m69*_*g'' 5

这是一个功能齐全的人工评估器（尽管其中一部分仍然需要优化以提高效率）。它使用递归检查所有可能的组合，并返回具有最低剩余值的组合。

卡以5 x 11矩阵存储，值0、1或2代表该类型的卡数，如下所示：

    3 4 5 6 w 8 9 T J Q K
CLB 1,0,0,0,2,0,1,0,0,0,0 
DMD 0,0,1,0,1,0,1,0,0,0,0 
HRT 0,0,0,0,0,0,1,1,1,0,0 
SPD 0,1,0,0,1,0,0,0,0,0,0 
STR 0,0,0,0,0,0,0,0,0,0,0 
    jokers: 1   value: 93

Run Code Online (Sandbox Code Playgroud)

在此表示形式中，游程是非零的水平序列，集合是相加达3个或更多的垂直线。

该函数通过搜索熔体，创建手的副本，从副本中删除熔体，然后在副本上调用自身来递归工作。

（实际上，递归是从矩阵的开头开始的；通过更好的算法来排列长熔体的较短部分，可以从当前点开始递归，从而避免两次检查组合。）

该示例生成并评估一张随机抽取的13张王牌为野生王牌的牌。通过取消注释底部的代码，您可以输入特定的指针进行检查。（数组克隆功能之后的所有代码仅用于运行示例并将其输出到控制台）。

    3 4 5 6 w 8 9 T J Q K
CLB 1,0,0,0,2,0,1,0,0,0,0 
DMD 0,0,1,0,1,0,1,0,0,0,0 
HRT 0,0,0,0,0,0,1,1,1,0,0 
SPD 0,1,0,0,1,0,0,0,0,0,0 
STR 0,0,0,0,0,0,0,0,0,0,0 
    jokers: 1   value: 93

Run Code Online (Sandbox Code Playgroud)

这是一个优化的版本。现在，集合的递归从当前点开始运行，而运行的递归仍然从0,0开始运行。
将findSets函数优化到可以从当前点开始执行所有递归的程度会增加一些复杂性，我认为这会抵消任何可能的速度提高。
现在，findRuns和findSets函数返回运行和集合的变体数组；这也解决了领先的小丑在跑步中的问题。
“ multi”变量也已删除，因为仅在一种特殊情况下才需要它，这也可以通过运行从0,0开始的递归来解决。

// OBJECT HAND CONSTRUCTOR

function Hand(cards, jokers, round, wilds) {
    this.cards = clone(cards);
    this.jokers = jokers;
    this.wilds = wilds || 0;
    this.round = round;
    this.melds = [];
    this.value = this.leftoverValue();
}

// FIND MELDS AFTER CURRENT POINT

Hand.prototype.findMelds = function(suit, number, multi) {

    if (suit == undefined || number == undefined || multi == undefined) {
        // NOT A RECURSION
        suit = number = multi = 0;
        this.convertWilds();
    }

    // START WITH ONLY JOKERS AS OPTIMAL COMBINATION
    if (this.jokers > 2) {
        for (i = 0; i < this.jokers; i++) {
            this.melds.push({s:-1, n:-1, m:-1});
        }
    this.value -= 25 * this.jokers - (22 - round) * (this.jokers < this.wilds ? this.jokers : this.wilds);
    }

    // SEARCH UNTIL END OR FULL LAY-DOWN
    while (this.value > 0) {

        // FIND NEXT CARD IN MATRIX
        while (this.cards[suit][number] <= multi) {
            multi = 0;
            if (++number > 10) {
                number = 0;
                if (++suit > 4) return;
            }
        }

        for (var type = 0; type < 2; type++) {
            // FIND MELD AT CURRENT POINT
            var meld = type ? this.findSet(suit, number, multi) : this.findRun(suit, number, multi);

            // TRY DIFFERENT LENGTHS OF LONG MELD
            // (to be improved: try permutations with jokers of each length)
            for (var len = 3; len <= meld.length; len++) {

                // CREATE COPY OF HAND AND REMOVE CURRENT MELD
                var test = new Hand(this.cards, this.jokers, this.round, this.wilds);
                test.removeCards(meld.slice(0, len));

                // RECURSION ON THE COPY
                // test.findMelds(suit, number, multi); // USE ONLY WITH MELD PERMUTATION ALGORITHM
                test.findMelds(0,0,0);                 // RESULT OK, BUT MAY CHECK THINGS MULTIPLE TIMES

                // BETTER COMBINATION FOUND
                if (test.value < this.value) {
                    this.value = test.value;
                    while (this.melds.length) this.melds.pop();
                    for (var i = 0; i < len; i++) {
                        // ADD CURRENT MELD (DON'T DESTROY YET)
                        this.melds.push(meld[i]);
                    }
                    // ADD MELDS FOUND THROUGH RECURSION
                    while (test.melds.length) this.melds.push(test.melds.shift());
                }
            }
        }
        multi++;
    }
}

// CHECK IF CARD IS START OF SET

Hand.prototype.findSet = function(s, n, m) {
    var set = [];
    while (s < 5) {
        while (m < this.cards[s][n]) {
            set.push({s:s, n:n, m:m++});
        }
        m = 0; s++;
    }

    // ADD JOKERS
    for (i = 0; i < this.jokers; i++) {
        set.push({s:-1, n:-1, m:-1});
    }
    return set;
}

// CHECK IF CARD IS START OF RUN

Hand.prototype.findRun = function(s, n, m) {
    var run = [], jokers = this.jokers;
    while (n < 11) {
        if (this.cards[s][n] > m) {
            run.push({s:s, n:n, m:m});
        } else if (jokers > 0) {
            run.push({s:-1, n:-1, m:-1});
            jokers--;
        }
        else break;
        m = 0; n++;
    }

    // ADD JOKERS (TRAILING OR LEADING)
    while (jokers-- > 0 && run.length < 11) {
        if (n++ < 11) run.push({s:-1, n:-1, m:-1});
        else run.unshift({s:-1, n:-1, m:-1});
    }
    return run;
}

// REMOVE ARRAY OF CARDS FROM HAND: [{s:x, n:y} ... ]

Hand.prototype.removeCards = function(cards) {
    for (var i = 0; i < cards.length; i++) {
        if (cards[i].s >= 0) {
            this.cards[cards[i].s][cards[i].n]--;
        } else this.jokers--;
    }
    this.value = this.leftoverValue();
}

// GET VALUE OF LEFTOVER CARDS

Hand.prototype.leftoverValue = function() {
    var leftover = 0;
    for (var i = 0; i < 5; i++) {
        for (var j = 0; j < 11; j++) {
            leftover += this.cards[i][j] * (j + 3) // cards count from 0 vs 3
        }
    }
    return leftover + 25 * this.jokers - (22 - round) * (this.jokers < this.wilds ? this.jokers : this.wilds);
}

// CONVERT WILDCARDS TO JOKERS

Hand.prototype.convertWilds = function() {
    for (var i = 0; i < 5; i++) {
        while (this.cards[i][this.round] > 0) {
            this.cards[i][this.round]--;
            this.jokers++; this.wilds++;
        }
    }
    this.value = this.leftoverValue();
}

// UTILS: 2D ARRAY DEEP-COPIER

function clone(a) {
    var b = [];
    for (var i = 0; i < a.length; i++) {
        b[i] = a[i].slice();
    }
    return b;
}

/* ******************************************************************************** */

// UTILS: SHOW HAND IN CONSOLE

function showHand(c, j, r, v) {
    var num = "    3 4 5 6 7 8 9 T J Q K";
    console.log(num.slice(0, 2*r+4) + "w" + num.slice(2*r+5));
    for (var i = 0; i < 5; i++) {
        console.log(["CLB ","DMD ","HRT ","SPD ","STR "][i] + c[i]);
    }
    console.log("    jokers: " + j + "  value: " + v);
}

// UTILS: SHOW RESULT IN CONSOLE

function showResult(m, v) {
    if (m.length == 0) console.log("no melds found");
    while (m.length) {
        var c = m.shift();
        if (c.s == -1) console.log("joker *");
        else console.log(["clubs","dmnds","heart","spade","stars"][c.s] + " " + "3456789TJQK".charAt(c.n));
    }
    console.log("leftover value: " + v);
}

// TEST DATA: CREATE ARRAY OF ALL CARDS TO DRAW FROM

var pack = [{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1}];
for (var i = 0; i < 5 ; i++) {
    for (var j = 0; j < 11; j++) {
        pack.push({s:i, n:j}, {s:i, n:j});
    }
}

// TEST DATA: CREATE 2D ARRAY TO STORE CARDS

var matrix = [];
var jokers = 0;
var round = 10; // count from zero

for (var i = 0; i < 5; i++) {
    matrix[i] = [];
    for (var j = 0; j < 11; j++) {
        matrix[i][j] = 0;
    }
}

// TEST DATA: DRAW CARDS AND FILL 2D ARRAY

for (i = 0; i < round + 3; i++)
{
    var j = Math.floor(Math.random() * pack.length);
    var pick = pack[j];
    pack[j] = pack.pop();
    if (pick.s > -1) matrix[pick.s][pick.n]++;
    else jokers++;
}

// USE THIS TO TEST SPECIFIC HANDS

// round = 10; // count from zero
// matrix = [[0,0,0,0,0,1,0,0,0,0,0],
//           [0,0,0,0,0,1,0,0,0,0,0],
//           [0,0,0,0,0,1,1,1,0,0,0],
//           [0,0,0,0,0,1,0,0,0,0,0],
//           [0,0,0,0,0,1,0,0,0,0,0]];
// jokers = 1;

// CREATE INSTANCE OF HAND OBJECT, EVALUATE AND SHOW RESULT

var x = new Hand(matrix, jokers, round); // no wilds parameter: automatic conversion
showHand(x.cards, x.jokers, x.round, x.value);
x.findMelds();
showResult(x.melds, x.value);

Run Code Online (Sandbox Code Playgroud)

实际上，从理论上讲，“优化”版本仅对具有多张双卡牌的手更快，而对单手则慢得多，因此我决定制作一个混合版本。对于任何复杂程度的操作，这都比以前的两种算法快10％。
一个警告是，为了简化代码，它在运行结束时添加了领先的小丑，因此*QK运行将显示为QK*。

// CODE FOR SECOND VERSION REMOVED BECAUSE OF ANSWER LENGTH CONSTRAINTS

Run Code Online (Sandbox Code Playgroud)

先前的版本并不是最佳选择，因为它们会多次检查某些组合。在尝试找到确保仅一次检查每个选项的最佳方法时，我意识到运行和集合的不同性质需要两种不同的方法，而寻找集合不需要递归。最后，这是最佳策略：

查找首先运行；仅在必要时使用小丑。
找到奔跑时，递归于手的副本，然后继续寻找奔跑。
如果找不到更多的运行，请切换到查找集。
使用所有可用的成套工具而无需开玩笑。
当有小丑时，请完成最有价值的一两张牌。
添加剩余的小丑。

令我惊讶的是，尽管集合的代码有点怪异，但对于复杂的手来说，该算法的速度却快了十倍以上。

// OBJECT HAND CONSTRUCTOR

function Hand(cards, jokers, round, wilds) {
    this.cards = clone(cards);
    this.jokers = jokers;
    this.wilds = wilds || 0;
    this.round = round;
    this.melds = [];
    this.value = this.leftoverValue();
}

// FIND MELDS FROM CURRENT POINT

Hand.prototype.findMelds = function(suit, number) {

    // IF NOT A RECURSION: CONVERT WILDCARDS TO JOKERS AND START FROM 0,0
    if (suit == undefined || number == undefined) {
        suit = number = 0;
        var noRecursion = true;
        this.convertWilds();
    }

    // FIND CARDS FROM CURRENT POINT UNTIL END OR FULL LAY-DOWN
    while (suit < 5 && this.value > 0) {
        if (this.cards[suit][number] > 0) {

            // FIND RUNS STARTING WITH CURRENT CARD
            var run = this.findRun(suit, number);

            // TRY DIFFERENT LENGTHS OF LONG RUN
            for (var len = 3; len <= run.length; len++) {

                // SKIP LONG RUNS ENDING WITH A JOKER
                if (len > 3 && run[len - 1].s == -1) continue;

                // CREATE COPY OF HAND, REMOVE RUN AND START RECURSION
                var test = new Hand(this.cards, this.jokers, this.round, this.wilds);
                test.removeCards(run.slice(0, len));
                test.findMelds(suit, number);

                // SAVE CURRENT RUN AND MELDS FOUND THROUGH RECURSION IF BETTER VALUE IS FOUND
                if (test.value < this.value) {
                    this.value = test.value;
                    this.melds.length = 0;
                    this.melds = [].concat(run.slice(0, len), test.melds);
                }
            }
        }

        // MOVE THROUGH CARD MATRIX
        if (++number > 10) {
            number = 0;
            ++suit;
        }
    }

    // AFTER ALL CARDS HAVE BEEN CHECKED FOR RUNS, CREATE COPY OF HAND AND FIND SETS
    if (this.value > 0) {
        var test = new Hand(this.cards, this.jokers, this.round, this.wilds);
        test.findSets();

        // SAVE SETS IF BETTER VALUE IS FOUND
        if (test.value < this.value) {
            this.value = test.value;
            this.melds.length = 0;
            while (test.melds.length) this.melds.push(test.melds.shift());
        }
    }

    // FIX NO MELDS AND ONE JOKER EXCEPTION
    if (noRecursion && this.melds.length < 3) {
        this.melds.length = 0;
        this.value = this.leftoverValue();
    }
}

// FIND RUN STARTING WITH CURRENT CARD

Hand.prototype.findRun = function(s, n) {
    var run = [], jokers = this.jokers;
    while (n < 11) {
        if (this.cards[s][n] > 0) {
            run.push({s:s, n:n});
        } else if (jokers > 0) {
            run.push({s:-1, n:-1});
            jokers--;
        } else break;
        n++;
    }

    // ADD LEADING JOKERS (AT END FOR CODE SIMPLICITY)
    while (run.length < 3 && jokers--) {
        run.push({s:-1, n:-1});
    }

    // REMOVE UNNECESSARY TRAILING JOKERS
    while (run.length > 3 && run[run.length - 1].s == -1) {
        run.pop();
    }
    return run;
}

// FIND SETS

Hand.prototype.findSets = function() {
    var sets = [[], []], values = [[], []];
    for (var n = 0; n < 11; n++) {
        var set = [], value = 0;
        for (var s = 0; s < 5; s++) {
            for (var i = 0; i < this.cards[s][n]; i++) {
                set.push({s:s, n:n});
                value += n + 3;
            }
        }

        // ADD COMPLETE SET TO MELDS, OR INCOMPLETE SET TO CANDIDATES TO RECEIVE JOKERS
        if (set.length >= 3) {
            this.addToMelds(set);
        }
        else if (set.length > 0) {
            // STORE ONE-CARD SETS IN sets[0] AND TWO-CARD SETS IN sets[1]
            sets[set.length - 1].push(set);
            values[set.length - 1].push(value);
        }
    }

    // IF TWO JOKERS ARE AVAILABLE: COMPLETE MOST VALUABLE TWO-CARD SET OR ONE-CARD SET(S)
    while (this.jokers > 1 && sets[0].length > 0) {
        var select = values[0][sets[0].length - 1];
        for (var i = sets[1].length - 1; i >= 0 && i > sets[1].length - 3; i--) {
            select -= values[1][i];
        }
        if (select > 0) {
            set = sets[0].pop(); values[0].pop();
            set.push({s:-1, n:-1}, {s:-1, n:-1});
            this.addToMelds(set);
        } else {
            for (var i = 0; i < 2 && sets[1].length > 0; i++) {
                set = sets[1].pop(); values[1].pop();
                set.push({s:-1, n:-1});
                this.addToMelds(set);
            }
        }
    }

    // IF JOKER IS AVAILABLE: COMPLETE MOST VALUABLE TWO-CARD SET
    while (this.jokers > 0 && sets[1].length > 0) {
        set = sets[1].pop();
        set.push({s:-1, n:-1});
        this.addToMelds(set);
    }

    // ADD LEFT-OVER JOKERS
    while (this.jokers

归档时间：	10 年，10 月前
查看次数：	489 次
最近记录：	10 年，10 月前