|
|
前言
斗地主残局，双方都是明牌，玩家作为地主方先出，只要优先出完所有手牌即表示战胜，比较考验玩家的斗地主水平和智商。
很多斗地主的应用里面都会有残局闯关模式，例如：欢乐斗地主，途游斗地主等等。记得小时候庙会，就会有斗地主残局的摆摊，5块钱一局，我只围观过并没有玩过，如今想来有点遗憾。到了现如今，随着网络的迅速发展，直播平台也出现了斗地主残局的身影，前段时间我就在抖音上刷到过。
那么问题来了，有的斗地主残局可能是套路局，也就是必输局，我们怎么快速的计算判断残局是否有解呢？其实，因为完全信息，有限的步骤（手牌数有限，打完结束），我们完全可以模拟出所有的出牌组合，来暴力计算结果。
示例
可以先看下残局破解的效果：
很容易看出，该残局我方要先出2保证能必胜。为什么不出其他的呢？
1. 我出3行不行？如果出3，对面过7然后压大王，就输了。
2. 我先出对子行不行？显然不行，由于我方的的两个单牌都会被对方的大王压制，必定会输。
3. 所以我方应该出2保证只留一个单牌，同时我方的对J会压制对面的对10，才是必胜的关键。
这里只是简单的分析一下，具体算法往下看。
核心逻辑
我们可以利用递归的思路，计算所有可能性组合。
我们定义一个函数handOut模拟出牌过程，函数有三个参数：我的手牌mePokers，对方的手牌enemyPokers，以及对方上次的出牌lastHand。函数的返回值是一个bool类型，表示我方能否战胜对方。
function handout(mePokers, enemyPokers, lastHand);既然是递归，那就会有函数的终止条件：一方出完牌游戏终止；当我方出完牌表示胜利，对方出完牌表示失败。
// 我全部出完牌，直接获胜
if (mePokers.length == 0) {
return true;
}
// 对手全部出完牌，我失败
if (enemyPokers.length == 0) {
return false;
}模拟出牌就需要知道可以出哪些牌型，这个算法很简单这里就不在阐述了。举个栗子，例如：手牌为A Q 10 10，可出牌的组合就是：（A）、（Q）、（10）、（10 10）、（不出），一共五种可出牌型。
1. 遍历这五种组合，模拟出牌；
2. 根据我方出牌，模拟对手出牌，然后递归调用handOut把双方互换（站在对方角度）；
// 获取我当前可以出的所有手牌组合，包括过牌
var allHands = getAllHands(mePokers);
// 遍历我的所有出牌组合，进行模拟出牌
for (var hand of allHands) {
// 如果上一轮对手出了牌，则这一轮我必须要出比对手更大的牌
// 或者 对手上一轮选择过牌，那么我只需出任意牌，但是不能过牌
// 或者 如果上一轮对手出了牌，但我这一轮选择过牌
if ((lastHand.type != PASS && canComb2BeatComb1(lastHand, hand) ||
(lastHand.type == PASS && hand.type != PASS) ||
(lastHand.type != PASS && hand.type == PASS))) {
// 模拟对手出牌，如果对手不能取胜，则我必胜
if (!handout(enemyPokers, previewMakeHand(mePokers, hand), hand)) {
return true;
}
}
}其他
1. 关于牌值的定义
将 3，4，5，6，7，8，9，10，J，Q，K，A，2，小王，大王
用 3，4，5，6，7，8，9，10，11，12，13，14，16，18，19 表示
目的是更方便判断顺子和大小关系。
2. 出牌大小比较
除了炸弹，只有相同牌型才能比较。比较主牌的大小，例如（5 5 5 K K）和（Q Q Q 3 3），第一个牌型的主牌是5，第二个是Q也就是12，显然（Q Q Q 3 3）大于（5 5 5 K K）。
/**
* comb1 先出，问后出的 comb2 是否能打过 comb1
* 1. 同种牌型比较 main 值, main 值大的胜
* 2. 炸弹大过其他牌型
* 3. 牌型不同, 后出为负
*
* @param {Array} comb1 牌1
* @param {Array} comb2 牌2
* @returns comb2是否能打过comb1
*/
function canComb2BeatComb1(comb1, comb2) {
if (comb2.type == PASS) {
return false;
}
if (comb1.type == PASS) {
return true;
}
if (comb1.type == comb2.type) {
return comb2.main > comb1.main;
}
return comb2.type == BOMB;
}优化
1. 缓存优化
已经计算的结果，缓存起来，下次直接取来用，不用重复计算。
这里使用我方手牌、对方手牌、上次对方出牌为键，能否必胜为值，存入缓存集合。
const key = mePokers.toString() + enemyPokers.toString() + JSON.stringify(lastHand);2. 多线程优化
将初始的所有出牌n种可能，每一个分发给一个线程（服务器），并发的执行，最后再汇总结果。可以提升n倍的效率。
最后
通过斗地主残局破解算法的研究，我明白了一个道理：人与人的区别主要在于思维方式，一个人的思维方式，决定了他看待世界的角度，一个人的思维方式，决定了一个人的人生高度。
如有不当之处，欢迎指正。 |
|
发表于 2023-1-19 12:56:09