纸牌游戏手牌评估的组合学，带通配符和重复
Combinatorics of cardgame hand evaluation for runs, with wildcards and duplicates
正在制作一款拉米风格的游戏，有几个曲折：
使用两副 5 组套牌而不是一组 4 组套牌（总共 116 张牌）。
套房 运行 从 3 到国王，每副牌有 3 张王牌（所以没有 2 也没有 A）。
11轮，第一轮每人3张牌，最后一轮每人13张牌。
除了小丑是百搭外，每张牌的价值都会轮到百搭，这对应于您手中的牌数。
所以第一轮 3 是狂野的，第二轮 4 是狂野的……第 11 轮国王是狂野的（国王的数值为 13）。
目标是放下所有牌。一旦有人 'gone out'（放下所有牌），剩下的玩家有一个回合也放下所有牌或尽可能多的有效 sets/runs。无论你手上剩下什么牌，你都会获得积分。
玩家只能成组或 运行 放置至少有 3 张牌的牌，即 set: {3:c, 3:d, 3:h}、run: {3:c, 4:c, 5:c}。还有一些回合你必须得到超过 3 张牌的set/run，因为手牌的数量不能被 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;
然后删除所有没有卡片的 suites/buckets。
集合评估非常简单，但 运行 评估...不是那么简单。
我想出了这个基于运行评估的范围
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);
});
}
}
}
}
};
这适用于很多情况，但很难解决套件中的重复问题。
我在玩游戏测试时 运行 遇到的最棘手的情况之一是：
{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（取决于我是先评估集合还是 运行s）
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）。
我的问题是： 是否有更好的way/algorithm来完成整个过程？
我目前解决这个问题的想法有点令人沮丧，因为它们涉及很多 case/if 特定手牌 lengths/game situations/suite 长度的陈述。有时我删除重复项，有时我不删除，有时我不删除重复项，有时我不删除……很多令人头疼的问题，基本上我不确定我是否涵盖了所有可能的 hands/partial 规定情况。
这是一个combinatorial optimization problem. Your algorithm produces only one solution. This is called a "greedy algorithm"。对于大多数问题，不存在可以保证最优解的贪心算法。您的问题似乎也是如此。
所以如果你想改善结果你应该产生几个甚至所有可能的解决方案并选择最好的一个。通过有效的方法和适当的 p运行ing 搜索树，应该可以始终找到适合您的问题大小的最佳解决方案。
一个好主意可能是将解决方案的生成分为“起始阶段”（创建 运行s 和最小大小为 3 的集合），然后是“填充阶段”（其中剩余的卡片将添加到现有 运行 和集合中。
对于每张未分配的牌（开始时所有牌都未分配），您有几种可能的“移动”。在开始阶段，这些可能属于以下类型：跳过、开始 运行 或开始一组。在“填满阶段”中，移动可能是：跳过，添加到 运行，添加到集合（可以有多种可能将卡片添加到 运行）。
对于 p运行 以下规则将有所帮助，因为它们不会影响解决方案的最佳发现值：
- 不要使用外卡代替未分配的卡。
- 不要开始与现有等级相同的新系列。
我对JavaScript不太熟悉，所以这里有一个Python的解决方案（也许你可以使用一个或另一个想法）：
# trying to solve
#
import copy
CLUBS, DIAMONDS, HEARTS, SPADES, STARS = range(5)
WILD = 0
testHand = [(CLUBS,3), WILD, (SPADES,3), (CLUBS,4), (CLUBS,5), (CLUBS,6), (CLUBS,6), (CLUBS,7), (CLUBS,8), (SPADES,10), (HEARTS,10), WILD]
def nextInRun(card):
if card[1] == 13:
raise ValueError("cannot determine next card in run for %s" % str(card))
return (card[0],card[1]+1)
def prevInRun(card):
if card[1] == 3:
raise ValueError("cannot determine previous card in run for %s" % str(card))
return (card[0],card[1]-1)
def fit2Set(card1, card2):
return card1 == WILD or card2 == WILD or card1[1] == card2[1]
START_RUN, START_SET = range(2)
def removeCard(hand, card, startIdx=None):
hand = copy.deepcopy(hand)
if startIdx != None and hand.index(card) < startIdx:
startIdx -= 1
hand.remove(card)
return ((hand, startIdx) if startIdx != None else hand)
def startMoves(handr1,card1,startIdx):
if card1 == WILD:
#print "trying to start run with 1 WILD card"
for card2 in set(handr1):
handr2,startIdx = removeCard(handr1, card2, startIdx)
if card2 == WILD:
#print "trying to start run with 2 WILD cards"
for card3 in set(handr2):
handr3,startIdx = removeCard(handr2, card3, startIdx)
if card3 == WILD:
yield (START_RUN, 3*[WILD], handr3, startIdx)
else:
try:
card2v = prevInRun(card3)
card1v = prevInRun(card2v)
yield (START_RUN, [card1,card2,card3], handr3, startIdx)
except ValueError:
pass
else:
#print "trying to start run with WILD card and %s" % str(card2)
try:
card1v = prevInRun(card2)
card3 = nextInRun(card2)
#print "card3 = %s, handr2 = %s" % (str(card3),str(handr2))
canContinueRun = card3 in handr2
if not canContinueRun and WILD in handr2:
card3 = WILD
canContinueRun = True
if canContinueRun:
handr3,startIdx = removeCard(handr2, card3, startIdx)
yield (START_RUN, [card1,card2,card3], handr3, startIdx)
except ValueError:
pass
return # no need to start a set with a WILD
else:
try:
card2v = card2 = nextInRun(card1)
canContinueRun = card2 in handr1
#print "card2 = %s, handr1 = %s" % (str(card2),str(handr1))
if not canContinueRun and WILD in handr1:
card2v = card2
card2 = WILD
canContinueRun = True
if canContinueRun:
handr2,startIdx = removeCard(handr1, card2, startIdx)
card3 = nextInRun(card2v)
canContinueRun = card3 in handr2
#print "card3 = %s, handr2 = %s" % (str(card3),str(handr2))
if not canContinueRun and WILD in handr2:
card3 = WILD
canContinueRun = True
if canContinueRun:
handr3,startIdx = removeCard(handr2, card3, startIdx)
yield (START_RUN, [card1,card2,card3], handr3, startIdx)
except ValueError:
pass
handrs = copy.deepcopy(handr1)
for card2 in set(handr1):
handrs.remove(card2)
if not fit2Set(card1,card2):
continue
handr2,startIdx = removeCard(handr1, card2, startIdx)
for card3 in set(handrs):
if not fit2Set(card1,card3):
continue
handr3,startIdx = removeCard(handr2, card3, startIdx)
yield (START_SET, [card1,card2,card3], handr3, startIdx)
def startings(hand,startIdx=0,runs=[],sets=[]):
#print "get startings for\n hand = %s\n startIdx = %d\n runs = %s\n sets = %s" % (str(hand),startIdx,str(runs),str(sets))
if len(hand) == 0 or startIdx >= len(hand):
yield copy.deepcopy(hand),copy.deepcopy(runs),copy.deepcopy(sets)
return
card = hand[startIdx]
while hand.index(card) < startIdx:
startIdx += 1 # do not try to start with the same card twice here
if startIdx >= len(hand):
yield copy.deepcopy(hand),copy.deepcopy(runs),copy.deepcopy(sets)
return
card = hand[startIdx]
#print " actual startIdx = %d" % startIdx
handr = removeCard(hand, card)
for move in startMoves(handr, card, startIdx):
if move[0] == START_RUN:
runs2 = copy.deepcopy(runs)
runs2.append(move[1])
for starting in startings(move[2], move[3], runs2, sets):
yield starting
elif move[0] == START_SET:
sets2 = copy.deepcopy(sets)
sets2.append(move[1])
for starting in startings(move[2], move[3], runs, sets2):
yield starting
for h,r,s in startings(hand, startIdx+1, runs, sets):
yield h,r,s
def runExtensions(run,handSet):
if set(run) == set([WILD]): # run consists only of WILD cards
for card in handSet:
yield card
else:
runUnique = list(set(run))
runUnique.sort()
cardv = runUnique[0] if runUnique[0] != WILD else runUnique[1]
idx = run.index(cardv)
lastCardVal = cardv
while idx < len(run)-1:
lastCardVal = nextInRun(lastCardVal)
idx += 1
try:
nextCardVal = nextInRun(lastCardVal)
if nextCardVal in handSet:
yield nextCardVal
return
if WILD in handSet:
yield WILD
except ValueError:
pass
def fillings(hand, runs, sets):
if len(runs) > 0:
run1 = runs[0]
noExtensionFound = True
usedWildExtension = False
for runExtension in runExtensions(run1,set(hand)):
noExtensionFound = False
run1e = copy.deepcopy(run1)
run1e.append(runExtension)
handr = removeCard(hand, runExtension)
runse = [run1e] + copy.deepcopy(runs[1:])
for filling in fillings(handr, runse, sets):
yield filling
if runExtension == WILD:
usedWildExtension = True
# when extending with WILD: also try without extending the first run; WILD card could be needed in another run
if noExtensionFound or usedWildExtension and len(runs) > 1:
for h,r,s in fillings(hand, copy.deepcopy(runs[1:]), sets):
r = [run1] + r
yield h,r,s
return
handr = copy.deepcopy(hand)
setse = copy.deepcopy(sets)
for card in hand:
for set_i in setse:
if fit2Set(card, set_i[0]):
handr.remove(card)
set_i.append(card)
break
yield handr,[],setse
def valueCard(card):
if card == WILD:
return 20
return card[1]
def value(hand):
return sum([valueCard(card) for card in hand])
def strRepSuit(suit):
if suit == CLUBS:
return 'clubs'
if suit == DIAMONDS:
return 'diamonds'
if suit == HEARTS:
return 'hearts'
if suit == SPADES:
return 'spades'
if suit == STARS:
return 'stars'
def strRepCard(card):
if card == WILD:
return 'WILD'
return '%s%d' % (strRepSuit(card[0]), card[1])
def strRepCardSuit(card):
if card == WILD:
return 'WILD'
return strRepSuit(card[0])
def strRepVal(card):
if card == WILD:
return 'WILD'
return '%d' % card[1]
def strRepRun(run):
setRun = set(run)
if setRun == set([WILD]):
return '%d * %s' % (len(run),strRepCard(run[0]))
runUnique = list(setRun)
suit = (runUnique[0] if runUnique[0] != WILD else runUnique[1])[0]
return '%s %s' % (strRepSuit(suit), ','.join([strRepVal(card) for card in run]))
def strRepSet(set_):
setUnique = list(set(set_))
val = (setUnique[0] if setUnique[0] != WILD else setUnique[1])[1]
return '%d %s' % (val, ','.join([strRepCardSuit(card) for card in set_]))
def strRepSol(hand,runs,sets):
return ' runs: %s\n sets: %s\n hand: %s\n hand value: %d' % ('; '.join([strRepRun(run) for run in runs]), '; '.join([strRepSet(set_) for set_ in sets]), ','.join([strRepCard(card) for card in hand]), value(hand))
def optimizeHand(hand):
lowestHandValue = value(hand)
bestSolution = hand,[],[]
for handr,runs,sets in startings(hand):
#print "starting with\n runs = %s\n sets = %s\n handr = %s" % (str(runs),str(sets),str(handr))
if len(runs) == 0 and len(sets) == 0:
continue
if len(handr) == 0:
print "solution generated without filling"
lowestHandValue = 0
bestSolution = [],runs,sets
break
for solution in fillings(handr,runs,sets):
handValue = value(solution[0])
if handValue < lowestHandValue:
lowestHandValue = handValue
bestSolution = solution
print "solution improved:\n%s" % strRepSol(bestSolution[0], bestSolution[1], bestSolution[2])
if lowestHandValue == 0:
break
if lowestHandValue == 0:
break
print "best solution:\n%s" % strRepSol(bestSolution[0], bestSolution[1], bestSolution[2])
#return lowestHandValue, bestSolution
现在让代码在您的示例上运行，我们得到以下输出：
>>> optimizeHand(testHand)
solution improved:
runs: clubs 3,4,5,6; spaded WILD,WILD,10; clubs 6,7,8
sets:
hand: spaded3,hearts10
hand value: 13
solution improved:
runs: clubs 3,4,5,6; clubs WILD,7,8
sets: 10 spaded,WILD,hearts
hand: spaded3,clubs6
hand value: 9
solution improved:
runs: clubs 3,4,5,6; clubs WILD,6,7,8
sets: 10 spaded,WILD,hearts
hand: spaded3
hand value: 3
solution generated without filling
best solution:
runs: clubs 4,5,6; clubs 6,7,8
sets: 3 clubs,WILD,spaded; 10 spaded,WILD,hearts
hand:
hand value: 0
在我的电脑上执行时间约为0.1s。
以上代码还找到了其他邪恶的解决方案：
>>> optimizeHand([WILD,WILD,(CLUBS,3)])
...
runs: clubs 3,WILD,WILD
>>> optimizeHand([WILD,WILD,(CLUBS,13)])
...
runs: clubs WILD,WILD,13
>>> optimizeHand([WILD,WILD,(CLUBS,13),(CLUBS,11)])
...
runs: clubs WILD,11,WILD,13
这是一款功能完备的牌手评估器（尽管仍有一部分需要优化以提高效率）。它使用递归来检查所有可能的组合，returns 是具有最低剩余值的组合。
卡片存储为 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
在这个表示中，一个运行是一个非零的水平序列，一个集合是一条竖线，加起来等于或大于3。
该函数通过搜索组合、创建手的副本、从副本中删除组合，然后在副本上调用自身来递归工作。
（实际上，递归是从矩阵的开头 运行 ；通过更好的算法来排列长融合的较短部分，递归可以是 运行 从当前点，从而避免检查组合两次。）
该示例生成并评估一手随机的 13 张 K 牌。
通过取消注释底部的代码，您可以输入特定的手牌进行检查。
（数组克隆函数之后的所有代码只是运行示例并输出到控制台）。
// 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);
这是一个优化版本。集合的递归现在从当前点 运行 开始，运行s 的递归仍然从 0,0.运行 开始。
将 findSets 函数优化到所有递归都可以从当前点开始 运行 的点会增加复杂性，我认为这会消除任何可能的速度增益。
findRuns 和 findSets 函数现在 return 是 运行 和集合的变体数组；这也解决了 运行s.
中主要小丑的问题
"multi" 变量也已被删除，因为只有在一种特定情况下才需要它，这也可以通过 运行 从 0,0.
对集合进行递归来解决。
// CODE FOR SECOND VERSION REMOVED BECAUSE OF ANSWER LENGTH CONSTRAINTS
实际上，理论上的 "optimised" 版本被证明只对多张双牌的手牌更快，而对于简单的手牌要慢得多，所以我决定制作一个混合版本。对于任何复杂的手牌，这比之前的两种算法都快 10%。
需要注意的是，为了简化代码，它将 运行 中的主要小丑添加到 运行 的末尾，因此 *QK 运行 将显示为 QK* .
// 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) {
if (suit == undefined || number == undefined) {
// NOT A RECURSION: CONVERT WILDS TO JOKERS
suit = number = 0;
this.convertWilds();
}
// START WITH ONLY JOKERS AS OPTIMAL COMBINATION
if (this.jokers > 2) {
for (var i = 0; i < this.jokers; i++) {
this.melds.push({s:-1, n:-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 (number > 10 || this.cards[suit][number] == 0) {
if (++number > 10) {
number = 0;
if (++suit > 4) return;
}
}
// FIND RUNS OR SETS STARTING AT CURRENT POINT
for (var meldType = 0; meldType < 2; meldType++) {
var meld = meldType ? this.findSet(suit, number) : this.findRun(suit, number);
// TRY DIFFERENT LENGTHS OF LONG MELD
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
meldType ? test.findMelds(suit, number) : test.findMelds(0, 0);
// BETTER COMBINATION FOUND
if (test.value < this.value) {
this.value = test.value;
// REPLACE BEST COMBINATION BY CURRENT MELD + MELDS FOUND THROUGH RECURSION
this.melds.length = 0;
this.melds = [].concat(meld.slice(0, len), test.melds);
}
}
}
number++;
}
}
// 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 (ADDED TO END FOR CODE SIMPLICITY)
while (jokers-- > 0) {
run.push({s:-1, n:-1});
}
return run;
}
// FIND SET STARTING WITH CURRENT CARD
Hand.prototype.findSet = function(s, n) {
var set = [];
while (s < 5) {
for (var i = 0; i < this.cards[s][n]; i++) {
set.push({s:s, n:n});
}
s++;
}
// ADD JOKERS
for (var i = 0; i < this.jokers; i++) {
set.push({s:-1, n:-1});
}
return set;
}
// REMOVE ARRAY OF CARDS FROM HAND
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,2,1,1,0,0,0],
// [0,0,0,1,1,2,0,0,0,0,0],
// [0,0,0,0,0,1,0,0,0,0,0],
// [0,0,0,0,0,0,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);
以前的版本不是最佳的，因为它们会多次检查某些组合。在尝试找到确保每个选项只检查一次的最佳方法时，我意识到 运行s 和集合的不同性质需要两种不同的方法，并且查找集合不需要递归。最后，这是最优策略：
- 先找到运行；仅在必要时使用小丑。
- 当找到 运行 时，递归手的副本，然后继续寻找 运行s。
- 当找不到更多 运行 时，切换到查找集。
- 使用所有可用的没有百搭的完整集。
- 在有百搭牌可用的情况下，完成最有价值的一张或两张牌组。
- 添加剩余的小丑。
令我惊讶的是，尽管集合的代码有点繁琐，但对于复杂的手牌，该算法的速度要快 10 倍以上。
// 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 > 0) {
this.addToMelds([{s:-1, n:-1}]);
}
}
// ADD SET TO MELDS
Hand.prototype.addToMelds = function(set) {
this.removeCards(set);
while (set.length) this.melds.push(set.shift());
}
// REMOVE ARRAY OF CARDS FROM HAND
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 = [];
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
var round = 10; // count from zero
var jokers = 0;
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,1],
// [0,0,0,0,0,1,0,0,0,0,0],
// [0,1,0,0,1,2,0,0,0,0,0],
// [0,0,0,0,0,2,1,0,0,1,1],
// [0,0,0,0,0,0,0,0,0,0,0]];
// jokers = 1;
// CREATE INSTANCE OF HAND OBJECT, EVALUATE AND SHOW RESULT
var x = new Hand(matrix, jokers, round); // CALL WITHOUT FOURTH (WILDS) PARAMETER
showHand(x.cards, x.jokers, x.round, x.value);
x.findMelds(); // CALL WITHOUT PARAMETERS TO INITIATE EVALUATION
showResult(x.melds, x.value);
正在制作一款拉米风格的游戏，有几个曲折：
使用两副 5 组套牌而不是一组 4 组套牌（总共 116 张牌）。
套房 运行 从 3 到国王，每副牌有 3 张王牌（所以没有 2 也没有 A）。
11轮，第一轮每人3张牌，最后一轮每人13张牌。
除了小丑是百搭外，每张牌的价值都会轮到百搭，这对应于您手中的牌数。
所以第一轮 3 是狂野的，第二轮 4 是狂野的……第 11 轮国王是狂野的（国王的数值为 13）。
目标是放下所有牌。一旦有人 'gone out'（放下所有牌），剩下的玩家有一个回合也放下所有牌或尽可能多的有效 sets/runs。无论你手上剩下什么牌，你都会获得积分。
玩家只能成组或 运行 放置至少有 3 张牌的牌，即 set: {3:c, 3:d, 3:h}、run: {3:c, 4:c, 5:c}。还有一些回合你必须得到超过 3 张牌的set/run，因为手牌的数量不能被 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;
然后删除所有没有卡片的 suites/buckets。
集合评估非常简单，但 运行 评估...不是那么简单。
我想出了这个基于运行评估的范围
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);
});
}
}
}
}
};
这适用于很多情况，但很难解决套件中的重复问题。
我在玩游戏测试时 运行 遇到的最棘手的情况之一是：
{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（取决于我是先评估集合还是 运行s）
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）。
我的问题是： 是否有更好的way/algorithm来完成整个过程？
我目前解决这个问题的想法有点令人沮丧，因为它们涉及很多 case/if 特定手牌 lengths/game situations/suite 长度的陈述。有时我删除重复项，有时我不删除，有时我不删除重复项，有时我不删除……很多令人头疼的问题，基本上我不确定我是否涵盖了所有可能的 hands/partial 规定情况。
这是一个combinatorial optimization problem. Your algorithm produces only one solution. This is called a "greedy algorithm"。对于大多数问题，不存在可以保证最优解的贪心算法。您的问题似乎也是如此。
所以如果你想改善结果你应该产生几个甚至所有可能的解决方案并选择最好的一个。通过有效的方法和适当的 p运行ing 搜索树，应该可以始终找到适合您的问题大小的最佳解决方案。
一个好主意可能是将解决方案的生成分为“起始阶段”（创建 运行s 和最小大小为 3 的集合），然后是“填充阶段”（其中剩余的卡片将添加到现有 运行 和集合中。
对于每张未分配的牌（开始时所有牌都未分配），您有几种可能的“移动”。在开始阶段，这些可能属于以下类型：跳过、开始 运行 或开始一组。在“填满阶段”中，移动可能是：跳过，添加到 运行，添加到集合（可以有多种可能将卡片添加到 运行）。
对于 p运行 以下规则将有所帮助，因为它们不会影响解决方案的最佳发现值：
- 不要使用外卡代替未分配的卡。
- 不要开始与现有等级相同的新系列。
我对JavaScript不太熟悉，所以这里有一个Python的解决方案（也许你可以使用一个或另一个想法）：
# trying to solve
#
import copy
CLUBS, DIAMONDS, HEARTS, SPADES, STARS = range(5)
WILD = 0
testHand = [(CLUBS,3), WILD, (SPADES,3), (CLUBS,4), (CLUBS,5), (CLUBS,6), (CLUBS,6), (CLUBS,7), (CLUBS,8), (SPADES,10), (HEARTS,10), WILD]
def nextInRun(card):
if card[1] == 13:
raise ValueError("cannot determine next card in run for %s" % str(card))
return (card[0],card[1]+1)
def prevInRun(card):
if card[1] == 3:
raise ValueError("cannot determine previous card in run for %s" % str(card))
return (card[0],card[1]-1)
def fit2Set(card1, card2):
return card1 == WILD or card2 == WILD or card1[1] == card2[1]
START_RUN, START_SET = range(2)
def removeCard(hand, card, startIdx=None):
hand = copy.deepcopy(hand)
if startIdx != None and hand.index(card) < startIdx:
startIdx -= 1
hand.remove(card)
return ((hand, startIdx) if startIdx != None else hand)
def startMoves(handr1,card1,startIdx):
if card1 == WILD:
#print "trying to start run with 1 WILD card"
for card2 in set(handr1):
handr2,startIdx = removeCard(handr1, card2, startIdx)
if card2 == WILD:
#print "trying to start run with 2 WILD cards"
for card3 in set(handr2):
handr3,startIdx = removeCard(handr2, card3, startIdx)
if card3 == WILD:
yield (START_RUN, 3*[WILD], handr3, startIdx)
else:
try:
card2v = prevInRun(card3)
card1v = prevInRun(card2v)
yield (START_RUN, [card1,card2,card3], handr3, startIdx)
except ValueError:
pass
else:
#print "trying to start run with WILD card and %s" % str(card2)
try:
card1v = prevInRun(card2)
card3 = nextInRun(card2)
#print "card3 = %s, handr2 = %s" % (str(card3),str(handr2))
canContinueRun = card3 in handr2
if not canContinueRun and WILD in handr2:
card3 = WILD
canContinueRun = True
if canContinueRun:
handr3,startIdx = removeCard(handr2, card3, startIdx)
yield (START_RUN, [card1,card2,card3], handr3, startIdx)
except ValueError:
pass
return # no need to start a set with a WILD
else:
try:
card2v = card2 = nextInRun(card1)
canContinueRun = card2 in handr1
#print "card2 = %s, handr1 = %s" % (str(card2),str(handr1))
if not canContinueRun and WILD in handr1:
card2v = card2
card2 = WILD
canContinueRun = True
if canContinueRun:
handr2,startIdx = removeCard(handr1, card2, startIdx)
card3 = nextInRun(card2v)
canContinueRun = card3 in handr2
#print "card3 = %s, handr2 = %s" % (str(card3),str(handr2))
if not canContinueRun and WILD in handr2:
card3 = WILD
canContinueRun = True
if canContinueRun:
handr3,startIdx = removeCard(handr2, card3, startIdx)
yield (START_RUN, [card1,card2,card3], handr3, startIdx)
except ValueError:
pass
handrs = copy.deepcopy(handr1)
for card2 in set(handr1):
handrs.remove(card2)
if not fit2Set(card1,card2):
continue
handr2,startIdx = removeCard(handr1, card2, startIdx)
for card3 in set(handrs):
if not fit2Set(card1,card3):
continue
handr3,startIdx = removeCard(handr2, card3, startIdx)
yield (START_SET, [card1,card2,card3], handr3, startIdx)
def startings(hand,startIdx=0,runs=[],sets=[]):
#print "get startings for\n hand = %s\n startIdx = %d\n runs = %s\n sets = %s" % (str(hand),startIdx,str(runs),str(sets))
if len(hand) == 0 or startIdx >= len(hand):
yield copy.deepcopy(hand),copy.deepcopy(runs),copy.deepcopy(sets)
return
card = hand[startIdx]
while hand.index(card) < startIdx:
startIdx += 1 # do not try to start with the same card twice here
if startIdx >= len(hand):
yield copy.deepcopy(hand),copy.deepcopy(runs),copy.deepcopy(sets)
return
card = hand[startIdx]
#print " actual startIdx = %d" % startIdx
handr = removeCard(hand, card)
for move in startMoves(handr, card, startIdx):
if move[0] == START_RUN:
runs2 = copy.deepcopy(runs)
runs2.append(move[1])
for starting in startings(move[2], move[3], runs2, sets):
yield starting
elif move[0] == START_SET:
sets2 = copy.deepcopy(sets)
sets2.append(move[1])
for starting in startings(move[2], move[3], runs, sets2):
yield starting
for h,r,s in startings(hand, startIdx+1, runs, sets):
yield h,r,s
def runExtensions(run,handSet):
if set(run) == set([WILD]): # run consists only of WILD cards
for card in handSet:
yield card
else:
runUnique = list(set(run))
runUnique.sort()
cardv = runUnique[0] if runUnique[0] != WILD else runUnique[1]
idx = run.index(cardv)
lastCardVal = cardv
while idx < len(run)-1:
lastCardVal = nextInRun(lastCardVal)
idx += 1
try:
nextCardVal = nextInRun(lastCardVal)
if nextCardVal in handSet:
yield nextCardVal
return
if WILD in handSet:
yield WILD
except ValueError:
pass
def fillings(hand, runs, sets):
if len(runs) > 0:
run1 = runs[0]
noExtensionFound = True
usedWildExtension = False
for runExtension in runExtensions(run1,set(hand)):
noExtensionFound = False
run1e = copy.deepcopy(run1)
run1e.append(runExtension)
handr = removeCard(hand, runExtension)
runse = [run1e] + copy.deepcopy(runs[1:])
for filling in fillings(handr, runse, sets):
yield filling
if runExtension == WILD:
usedWildExtension = True
# when extending with WILD: also try without extending the first run; WILD card could be needed in another run
if noExtensionFound or usedWildExtension and len(runs) > 1:
for h,r,s in fillings(hand, copy.deepcopy(runs[1:]), sets):
r = [run1] + r
yield h,r,s
return
handr = copy.deepcopy(hand)
setse = copy.deepcopy(sets)
for card in hand:
for set_i in setse:
if fit2Set(card, set_i[0]):
handr.remove(card)
set_i.append(card)
break
yield handr,[],setse
def valueCard(card):
if card == WILD:
return 20
return card[1]
def value(hand):
return sum([valueCard(card) for card in hand])
def strRepSuit(suit):
if suit == CLUBS:
return 'clubs'
if suit == DIAMONDS:
return 'diamonds'
if suit == HEARTS:
return 'hearts'
if suit == SPADES:
return 'spades'
if suit == STARS:
return 'stars'
def strRepCard(card):
if card == WILD:
return 'WILD'
return '%s%d' % (strRepSuit(card[0]), card[1])
def strRepCardSuit(card):
if card == WILD:
return 'WILD'
return strRepSuit(card[0])
def strRepVal(card):
if card == WILD:
return 'WILD'
return '%d' % card[1]
def strRepRun(run):
setRun = set(run)
if setRun == set([WILD]):
return '%d * %s' % (len(run),strRepCard(run[0]))
runUnique = list(setRun)
suit = (runUnique[0] if runUnique[0] != WILD else runUnique[1])[0]
return '%s %s' % (strRepSuit(suit), ','.join([strRepVal(card) for card in run]))
def strRepSet(set_):
setUnique = list(set(set_))
val = (setUnique[0] if setUnique[0] != WILD else setUnique[1])[1]
return '%d %s' % (val, ','.join([strRepCardSuit(card) for card in set_]))
def strRepSol(hand,runs,sets):
return ' runs: %s\n sets: %s\n hand: %s\n hand value: %d' % ('; '.join([strRepRun(run) for run in runs]), '; '.join([strRepSet(set_) for set_ in sets]), ','.join([strRepCard(card) for card in hand]), value(hand))
def optimizeHand(hand):
lowestHandValue = value(hand)
bestSolution = hand,[],[]
for handr,runs,sets in startings(hand):
#print "starting with\n runs = %s\n sets = %s\n handr = %s" % (str(runs),str(sets),str(handr))
if len(runs) == 0 and len(sets) == 0:
continue
if len(handr) == 0:
print "solution generated without filling"
lowestHandValue = 0
bestSolution = [],runs,sets
break
for solution in fillings(handr,runs,sets):
handValue = value(solution[0])
if handValue < lowestHandValue:
lowestHandValue = handValue
bestSolution = solution
print "solution improved:\n%s" % strRepSol(bestSolution[0], bestSolution[1], bestSolution[2])
if lowestHandValue == 0:
break
if lowestHandValue == 0:
break
print "best solution:\n%s" % strRepSol(bestSolution[0], bestSolution[1], bestSolution[2])
#return lowestHandValue, bestSolution
现在让代码在您的示例上运行，我们得到以下输出：
>>> optimizeHand(testHand)
solution improved:
runs: clubs 3,4,5,6; spaded WILD,WILD,10; clubs 6,7,8
sets:
hand: spaded3,hearts10
hand value: 13
solution improved:
runs: clubs 3,4,5,6; clubs WILD,7,8
sets: 10 spaded,WILD,hearts
hand: spaded3,clubs6
hand value: 9
solution improved:
runs: clubs 3,4,5,6; clubs WILD,6,7,8
sets: 10 spaded,WILD,hearts
hand: spaded3
hand value: 3
solution generated without filling
best solution:
runs: clubs 4,5,6; clubs 6,7,8
sets: 3 clubs,WILD,spaded; 10 spaded,WILD,hearts
hand:
hand value: 0
在我的电脑上执行时间约为0.1s。
以上代码还找到了其他邪恶的解决方案：
>>> optimizeHand([WILD,WILD,(CLUBS,3)])
...
runs: clubs 3,WILD,WILD
>>> optimizeHand([WILD,WILD,(CLUBS,13)])
...
runs: clubs WILD,WILD,13
>>> optimizeHand([WILD,WILD,(CLUBS,13),(CLUBS,11)])
...
runs: clubs WILD,11,WILD,13
这是一款功能完备的牌手评估器（尽管仍有一部分需要优化以提高效率）。它使用递归来检查所有可能的组合，returns 是具有最低剩余值的组合。
卡片存储为 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
在这个表示中，一个运行是一个非零的水平序列，一个集合是一条竖线，加起来等于或大于3。
该函数通过搜索组合、创建手的副本、从副本中删除组合，然后在副本上调用自身来递归工作。
（实际上，递归是从矩阵的开头 运行 ；通过更好的算法来排列长融合的较短部分，递归可以是 运行 从当前点，从而避免检查组合两次。）
该示例生成并评估一手随机的 13 张 K 牌。 通过取消注释底部的代码，您可以输入特定的手牌进行检查。 （数组克隆函数之后的所有代码只是运行示例并输出到控制台）。
// 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);
这是一个优化版本。集合的递归现在从当前点 运行 开始，运行s 的递归仍然从 0,0.运行 开始。
将 findSets 函数优化到所有递归都可以从当前点开始 运行 的点会增加复杂性，我认为这会消除任何可能的速度增益。
findRuns 和 findSets 函数现在 return 是 运行 和集合的变体数组；这也解决了 运行s.
中主要小丑的问题
"multi" 变量也已被删除，因为只有在一种特定情况下才需要它，这也可以通过 运行 从 0,0.
// CODE FOR SECOND VERSION REMOVED BECAUSE OF ANSWER LENGTH CONSTRAINTS
实际上，理论上的 "optimised" 版本被证明只对多张双牌的手牌更快，而对于简单的手牌要慢得多，所以我决定制作一个混合版本。对于任何复杂的手牌，这比之前的两种算法都快 10%。
需要注意的是，为了简化代码，它将 运行 中的主要小丑添加到 运行 的末尾，因此 *QK 运行 将显示为 QK* .
// 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) {
if (suit == undefined || number == undefined) {
// NOT A RECURSION: CONVERT WILDS TO JOKERS
suit = number = 0;
this.convertWilds();
}
// START WITH ONLY JOKERS AS OPTIMAL COMBINATION
if (this.jokers > 2) {
for (var i = 0; i < this.jokers; i++) {
this.melds.push({s:-1, n:-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 (number > 10 || this.cards[suit][number] == 0) {
if (++number > 10) {
number = 0;
if (++suit > 4) return;
}
}
// FIND RUNS OR SETS STARTING AT CURRENT POINT
for (var meldType = 0; meldType < 2; meldType++) {
var meld = meldType ? this.findSet(suit, number) : this.findRun(suit, number);
// TRY DIFFERENT LENGTHS OF LONG MELD
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
meldType ? test.findMelds(suit, number) : test.findMelds(0, 0);
// BETTER COMBINATION FOUND
if (test.value < this.value) {
this.value = test.value;
// REPLACE BEST COMBINATION BY CURRENT MELD + MELDS FOUND THROUGH RECURSION
this.melds.length = 0;
this.melds = [].concat(meld.slice(0, len), test.melds);
}
}
}
number++;
}
}
// 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 (ADDED TO END FOR CODE SIMPLICITY)
while (jokers-- > 0) {
run.push({s:-1, n:-1});
}
return run;
}
// FIND SET STARTING WITH CURRENT CARD
Hand.prototype.findSet = function(s, n) {
var set = [];
while (s < 5) {
for (var i = 0; i < this.cards[s][n]; i++) {
set.push({s:s, n:n});
}
s++;
}
// ADD JOKERS
for (var i = 0; i < this.jokers; i++) {
set.push({s:-1, n:-1});
}
return set;
}
// REMOVE ARRAY OF CARDS FROM HAND
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,2,1,1,0,0,0],
// [0,0,0,1,1,2,0,0,0,0,0],
// [0,0,0,0,0,1,0,0,0,0,0],
// [0,0,0,0,0,0,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);
以前的版本不是最佳的，因为它们会多次检查某些组合。在尝试找到确保每个选项只检查一次的最佳方法时，我意识到 运行s 和集合的不同性质需要两种不同的方法，并且查找集合不需要递归。最后，这是最优策略：
- 先找到运行；仅在必要时使用小丑。
- 当找到 运行 时，递归手的副本，然后继续寻找 运行s。
- 当找不到更多 运行 时，切换到查找集。
- 使用所有可用的没有百搭的完整集。
- 在有百搭牌可用的情况下，完成最有价值的一张或两张牌组。
- 添加剩余的小丑。
令我惊讶的是，尽管集合的代码有点繁琐，但对于复杂的手牌，该算法的速度要快 10 倍以上。
// 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 > 0) {
this.addToMelds([{s:-1, n:-1}]);
}
}
// ADD SET TO MELDS
Hand.prototype.addToMelds = function(set) {
this.removeCards(set);
while (set.length) this.melds.push(set.shift());
}
// REMOVE ARRAY OF CARDS FROM HAND
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 = [];
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
var round = 10; // count from zero
var jokers = 0;
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,1],
// [0,0,0,0,0,1,0,0,0,0,0],
// [0,1,0,0,1,2,0,0,0,0,0],
// [0,0,0,0,0,2,1,0,0,1,1],
// [0,0,0,0,0,0,0,0,0,0,0]];
// jokers = 1;
// CREATE INSTANCE OF HAND OBJECT, EVALUATE AND SHOW RESULT
var x = new Hand(matrix, jokers, round); // CALL WITHOUT FOURTH (WILDS) PARAMETER
showHand(x.cards, x.jokers, x.round, x.value);
x.findMelds(); // CALL WITHOUT PARAMETERS TO INITIATE EVALUATION
showResult(x.melds, x.value);