用js写卡牌游戏（八）

前言

好久不见，离发布上次分享，已经过去很久很久了，这段时间发生了很多变故，经历了跳槽、离职、创业等等，手头也一直有很多事情在忙，不过鸽这么久其实是有别的理由，有一个非常重要的功能一直卡住，没有思路，但不做这个功能我又觉得这个项目就无法继续下去，那就是：卡牌ai。

线上地址：http://cardgame.xiejingyang.com
github：https://github.com/xieisabug/card-game

同样建议大家看着视频，同步看文章，会比较直观：https://www.bilibili.com/video/BV18e411P74S/

背景

为什么会在这个阶段就想要做ai呢？这个游戏相信大家看的出来，参照的就是炉石传说，炉石传说中的单机体验是非常吸引我的，不光是得益于关卡和数值设计的精彩，更是因为其中电脑对手也有丰富的随机情况出现，有神抽，也有卡手的时候，给玩家像和真人在对战一样的体验，感受的到ai也是在打牌，我相信这不是脚本所能达到的效果，也正因为这样给了玩家一次又一次挑战的动力。

我前几关的故事模式都是直接编写的脚本，在设计到第10关的时候，我希望玩家和ai开始对战，但是如果一直是编排的脚本，之后会需要编写大量重复且难以维护的脚本，我产生了制作一个会自己打牌的ai的想法，这样就能花更多的时间精力去完成数值和关卡的设计。所以，我将ai放在了很多游戏功能之前。并且在之后增加游戏功能的时候，也可以从ai的角度去进行系统设计。

无关紧要的哔哔

目前这个简陋的ai已经做好了，关键技术是一个叫蒙特卡洛树搜索的算法。接下来我会按照：寻找合适的技术 ⇒ 设计算法 ⇒ 编码完成ai，这几个步骤来进行分享，并且同时会顺带简单介绍一下蒙特卡洛树搜索。

寻找合适的技术

寻找技术解决方案的时候，尝试了两个方案，第一个方案是定义一个动作优先级，然后按照优先级模拟所有可以进行的动作，评分分数是上涨了还是降低了，上涨了则保留，降低了则回退动作，这个方案很像贪心算法，可惜这种卡牌游戏并不能使用贪心算法来求最优解，动作的顺序和卡牌的配合非常重要，要赢下比赛并不是某一个动作决定的，而是整个回合的配合运营，不过这个方案有蒙特卡洛树的影子了，也为后来改成蒙特卡洛树提供了很多思路。

第二个方法企图使用机器学习，使用类似决策森林的方式来获取最佳行动，如果将足够多的对局放到模型中进行训练，会生成许多决策树，在决策树中模拟动作之后投票选择出最佳方案。但是我也说了，需要足够多的对局来进行模型训练，因为缺少训练集，而且游戏的动作量化难度非常高，所以也这个方案也失败了。

当我一筹莫展的时候，有天闲来无事逛b站，我看到了一个up主的科普视频（https://www.bilibili.com/video/BV1qR4y1J7ht），提到了这个蒙特卡洛树，我才了解到在对于这种对弈游戏或者非对称信息游戏的ai，一般都是使用这个算法来解决，而且alpha go的一部分就是用到这个算法。

简单介绍一下蒙特卡洛树。蒙特卡洛是一座著名的赌城，相传最开始蒙特卡洛方法就是在某个数学家玩扑克的时候发明的，蒙特卡洛方法解释起来很容易理解，不停的模拟对局，并且在模拟的基础上进行一些统计方法，在模拟的框架内对于统计的数据又进行反向传递来影响模拟路径的选择，从而实现比普通的模拟要更加有效率更加准确的效果。

可以用我们的卡牌游戏来举个例子，能更生动的理解它。

设计算法

当前的场景下，我们可以操作的动作有：出牌、攻击卡牌、攻击英雄，这时，蒙特卡洛会生成根节点，然后根据这三个动作拓展根节点的分支，对所有分支进行模拟对战，然后对于对战的结果进行统计，对拓展的分支重复这个操作，直到某个停止的条件达成，这个条件可以是模拟10000次，也可以是200ms等等，最后对于模拟的对战进行统计对比，选择最适合的动作集。

听起来挺简单的对吧，蒙特卡洛的难点在于将整个游戏转化为它的框架中的步骤，它分为：选择、拓展、模拟、反向传播，四个阶段，蒙特卡洛会不停的重复这四个阶段来进行游戏模拟，只要将获取结果的过程转化为这四个步骤就行了。

编码完成ai

由于我们的游戏是类炉石的卡牌游戏，和棋类这种信息对称的游戏使用蒙特卡洛树的方式不同，类炉石的卡牌游戏在一个回合内自己是可以连续做许多动作，并且对方拥有的卡牌也是未知的，棋类的蒙特卡洛树可以模拟互相对弈的过程来复现人类对弈时的思考，也就是模拟出对方可能会怎么做，而类炉石卡牌游戏只能将蒙特卡洛树用来模拟人类对当前场面的思考，也就是只能模拟出我们自己的行动。所以我们需要将整个算法的过程，映射到这一回合的多个动作之中，进行模拟来选出当前使用哪一个动作能够达到最佳。

首先需要定义好蒙特卡洛的四个阶段对应的函数，select、expand、simulate、backPropagation，并且定义一个对外接口 getBestAction，然后将蒙特卡洛树的搜索过程填入到这个接口中。

class MonteCarloTreeSearch {

  // 根据当前游戏状态返回最佳行动。
  getBestAction(myTableCard, otherTableCard, myHandCard, myRemainingCard, fee, myLife, otherLife) {
        
  }
  
  // 使用蒙特卡洛树搜索算法选择下一个要探索的节点。
  select(state) {
  }
  
  // 扩展给定节点，通过向树中添加它的可能子节点。
  expand(node) {
  }
  
  // 从给定节点模拟随机游戏，以估计其潜在价值。
  simulate(node) {
  }
  
  // 根据模拟的结果，反向传播给定节点的值和访问次数。
  backPropagation(node, win) {
  }
}

为了让ai更快，我们需要对ai每次思考的时间进行限制，所以先将ai的模拟运行时间，限制在我们可控制的范围内：

getBestAction(myTableCard, otherTableCard, myHandCard, myRemainingCard, fee, myLife, otherLife) {
		// 初始化cacheTree
    this.cacheTree = {};
    // 初始化state
    let state = { myTableCard, otherTableCard, myHandCard, myRemainingCard, fee, myLife, otherLife };

		// 计算规定时间
		let end = Date.now() + this.maxTime * 1000;
		let win;

		// 在规定时间内不断模拟
    while (Date.now() < end) {
        // 蒙特卡洛树搜索算法...
    }
}

根据蒙特卡洛树的框架，我们将过程可以转化为：根据当前的对战状态获取模拟的节点，对节点进行扩展，从扩展之后的节点开始进行模拟，最后对模拟后的结果再进行反向传递：

// 在规定时间内不断模拟
while (Date.now() < end) {
		// 获取模拟的节点
    let node = this.select(state);
    if (node && !node.isLeaf() && !this.isWin(node.state)) {
				// 对节点进行扩展
        node = this.expand(node);
				// 对扩展的节点进行模拟
        win = this.simulate(node);
    }
		// 对模拟后的结果再进行反向传递
    this.backPropagation(node, win);
}

”选择“的目的其实是获取一个当前最需要模拟的节点，策略是这样的：如果节点能扩展，则选择这个能扩展的节点，否则在子节点中选择一个最佳的子节点，并且继续判断子节点是否扩展，不停重复这一动作，直到找到可拓展的节点或者叶子节点。

可能在刚刚的描述中会注意到一个特殊的词，那就是“最佳”，这也是第一个使得蒙特卡洛树更加科学的秘诀，我在这里使用的是UCB算法，关于UCB算法大家可以理解为根据游玩的次数和获胜的次数得到一个分数，分数越高评价就越好。具体的UCB算法原理大家可以去网上看看别人的讲解，比我讲的要更好。

完善select函数，大部分解释我都通过注释的方式在代码里表达了：

select(state) {
    // 用于防止无限向下寻找的情况，最大层数
    let maxLevel = 0;
    // 从缓存中拿出当前状态对应的节点
    let node = this.cacheTree[hashState(state)];

    while (node.isFullyExpanded() && !node.isLeaf()) {
        maxLevel ++;

        // 获取节点所能做的所有动作
        let actions = node.allActions();
        let bestAction;
        let bestUCB1 = -Infinity;

        // 遍历所有动作，找到最佳评价的动作
        actions.forEach(a => {
            let action = a.action;
            let child = node.childNode(action);
            if (child) {
		// 使用UCB算法对节点进行评分
                let childUCB1 = child.getUCB1(this.UCB1);

                if (childUCB1 > bestUCB1) {
                    bestAction = action;
                    bestUCB1 = childUCB1;
                }
            }
        });

        if (bestAction) {
            node = node.childNode(bestAction);
        }

        if (maxLevel > this.maxDeep) {
            break;
        }
    }

    return node;
}

在刚刚的定义中，我们为node设计了许多函数，接下来就创建node类，并且为这些函数添加上实现（这种自顶向下的设计方式也是我很喜欢的编程方式，能让我的思路更加清晰）：

const { range, hashState } = require('../../utils');

class MonteCarloTreeSearchNode {
    /**
     * 构造函数，初始化节点
     * 记录下节点的父节点、产生的动作、当前的状态
     * 
     * 为了性能更好，所以我们提前将所有的子节点缓存起来，也就是cacheAllChildren函数做的事情
     */
    constructor(parent, action, state) {
        this.parent = parent;
        this.action = action;
        this.state = state;
        // 用于缓存子节点
        this.children = {};

        // 对局数量
        this.n_plays = 0;
        // 获胜数量
        this.n_wins = 0;

        // 当前状态的hash值，也是为了性能提前计算好
        this.hash = hashState(this.state);
        // 缓存当前节点能够进行的所用动作的子节点
        this.cacheAllChildren();
    }

    /**
     * 缓存当前节点能够进行的所用动作的子节点
     */
    cacheAllChildren() {
        if (this.action && this.action.event === "END_MY_TURN") {
            return;
        }

        let action;
        let myHandCard = this.state.myHandCard, otherTableCard = this.state.otherTableCard, 
            myTableCard = this.state.myTableCard, fee = this.state.fee;

        // 缓存结束回合节点
        action = {
            event: "END_MY_TURN"
        };
        this.children[this.actionHash(action)] = {
            action,
            node: null
        };

        // 出牌判断，所有在费用内可以出的牌
        for (let i = 0; i < myHandCard.length; i++) {
            if (myHandCard[i].cost <= fee) {
                action = {
                    event: "OUT_CARD",
                    card: Object.assign({}, myHandCard[i]),
                    i
                };
                
                this.children[this.actionHash(action)] = {
                    action,
                    node: null
                };
            }
        }

        // 如果有嘲讽，必须先攻击嘲讽，如果没有，则随意攻击
        let dedicationIndexList = []; // 嘲讽卡牌的index
        let attackCardList = []; // 卡牌index对应的card元数据
        // 查找所有嘲讽
        otherTableCard.forEach((i, index) => {
            if (i.isDedication) {
                dedicationIndexList.push(index);
                attackCardList.push(i);
            }
        });
        let hasDedication = true;
        // 如果没有嘲讽，则所有的都可攻击，为了方便，直接放在attackCardList和dedicationIndexList里
        if (attackCardList.length === 0) {
            hasDedication = false;
            attackCardList = otherTableCard.slice();
            dedicationIndexList = range(otherTableCard.length)
        }
        
        // 攻击卡牌判断
        for (let i = 0; i < myTableCard.length; i++) { 
            if (!myTableCard[i].isActionable) continue; // 行动过的不需要继续了

            let attackCard = Object.assign({}, myTableCard[i]);

            // 如果没有嘲讽，则可以攻击对方的英雄
            if (!hasDedication) {
                // 攻击对方英雄
                action = {
                    event: "ATTACK_HERO",
                    k: attackCard.k
                };
                this.children[this.actionHash(action)] = {
                    action,
                    node: null
                }
            }

            // 攻击可攻击的卡牌
            for (let j = 0; j < attackCardList.length; j++) {
                let beAttackCard = Object.assign({}, attackCardList[j]);
                action = {
                    event: "ATTACK_CARD",
                    card: attackCard,
                    attackCard: beAttackCard,
                    myK: attackCard.k,
                    attackK: beAttackCard.k,
                    i,
                    j: dedicationIndexList[j]
                };

                this.children[this.actionHash(action)] = {
                    action,
                    node: null
                }
            }

        }
    }

    /**
     * 获取当前节点所有可执行的动作
     * @returns 所有可以执行的动作
     */
    allActions() {
        return Object.values(this.children);
    }

    /**
     * 拓展节点
     * @returns 子节点
     */
    expand(action, childState) {
        if (Object.keys(this.children).indexOf(this.actionHash(action)) == -1) {
            throw new Error("No such play!");
        }
        let childNode = new MonteCarloTreeSearchNode(this, action, childState)
        this.children[this.actionHash(action)] = { action, node: childNode }
        return childNode
    }

    /**
     * 获取动作对应的子节点
     * @returns 子节点
     */
    childNode(action) {
        let hash = this.actionHash(action);
        if (!this.children[hash]) {
            return null;
        }
        return this.children[hash].node;
    }

    /**
     * 获取没有被拓展的节点集合
     * @returns 没有扩展的子节点集合
     */
    unexpandedActions() {
        let ret = [];
        Object.values(this.children).forEach(child => {
            if (child.node === null) {
                ret.push(child.action);
            }
        });
        
        return ret;
    }

    /**
     * 根据是否胜利更新当前节点的对局状态
     */
    update(win) {
        this.n_plays += 1;
        this.n_wins += win ? 1 : 0;
    }

    /**
     * 动作hash
     * @returns 动作的hash值
     */
    actionHash(action) {
        switch(action.event) {
            case "OUT_CARD":
                return `${action.event}_${action.i}`;
            case "ATTACK_HERO":
                return `${action.event}_${action.k}`;
            case "ATTACK_CARD":
                return `${action.event}_${action.i}_${action.j}`;
            default:
                return action.event;
        }
    }

    /**
     * 是否叶子节点
     */
    isLeaf() {
        return this.allActions().length <= 1; // 只能结束回合
    }

    /**
     * UCB算法
     */
    getUCB1(biasParam) {
        return (this.n_wins / this.n_plays) + Math.sqrt(biasParam * Math.log(this.parent.n_plays) / this.n_plays);
    }

    /**
     * 是否子节点全拓展
     */
    isFullyExpanded() {
        return this.unexpandedActions().length === 0 || (this.unexpandedActions().length === 1 && this.unexpandedActions()[0].event === "END_MY_TURN");
    }
}

module.exports = MonteCarloTreeSearchNode;

子节点所有的函数都完成了，继续完善蒙特卡洛树的框架，到了第二步expand，expand相对来说比select更好理解，就是为当前选定的节点进行向下个状态的扩展，随机选择一个还没有进行过的动作，然后模拟执行这个动作生成新的状态，通过这个状态生成节点，就完成了expand的操作：

expand(node) {
    // 获取节点没有拓展的动作
    let actions = node.unexpandedActions();
    // 随机选择一个动作
    let index = Math.floor(Math.random() * actions.length);
    let action = actions[index];
    
    // 进行节点拓展
    let childState = nextStateByAction(node.state, action);
    let childNode = node.expand(action, childState);

    // 如果是end_turn，则会造成state不变的情况，所以tree出现问题了
    if (action.event !== 'END_MY_TURN') {
        this.cacheTree[hashState(childState)] = childNode;
    }

    return childNode
}

需要注意的是，在我们游戏中有一个特殊的动作，就是直接结束回合，这个动作是非常重要的，在对局中，我们有很多动作可以选择，但有时候什么都不做却是最好的选择，在蒙特卡洛树算法中由于我们是很依赖于状态的，而直接结束回合这个动作是不会改变状态的，所以对这个动作，我们要和其他的动作分开。

再下一步就是要将剩下的这个回合模拟完，和expand有些相似，随机选取动作不停向下扩展，直到没有动作了，只不过不会将这个过程真正的扩展和缓存，而是只要最终的结果。

当然模拟到回合结束的时候，需要判断这一系列的动作是否起到正向作用，这也是我们算法的重中之重，也就是：场面价值评估。

/**
 * 模拟打牌的过程
 * @param {*} node 模拟的node
 * @returns 是否胜利
 */
simulate(node) {
    let state = node.state;
    let tempNode = node;

    // 没有胜利或者没有结束完行动的情况下，不停模拟
    while (!this.isWin(state) && !this.isEndMyTurn(state)) {
        let actions = tempNode.allActions();
        let index = Math.floor(Math.random() * actions.length);
        let action = actions[index].action;

        let childState = nextStateByAction(tempNode.state, action);
        
        tempNode = new MonteCarloTreeSearchNode(tempNode, action, childState)
        
        state = childState;
    }

    // 判断是否胜利
    return this.checkValue(state.myTableCard, state.otherTableCard, state.myHandCard, state.myRemainingCard, state.fee, state.myLife, state.otherLife) > this.currentValue;
}

checkValue就是场面评估的函数了，用于对比是否胜利的currentValue就是在ai运行的最初状态所评估出来的场面价值。

先将currentValue计算的代码写出来，并且为根节点进行初始化：

getBestAction(myTableCard, otherTableCard, myHandCard, myRemainingCard, fee, myLife, otherLife) {
		// 初始化当前状态value
    this.currentValue = this.checkValue(myTableCard, otherTableCard, myHandCard, myRemainingCard, fee, myLife, otherLife);
		// 初始化cacheTree
    this.cacheTree = {};
    // 初始化state
    let state = { myTableCard, otherTableCard, myHandCard, myRemainingCard, fee, myLife, otherLife };

		// 初始化root
    this.cacheTree[hashState(state)] = new MonteCarloTreeSearchNode(null, null, state);

		// 计算规定时间
		let end = Date.now() + this.maxTime * 1000;
		let win;

		// 在规定时间内不断模拟
    while (Date.now() < end) {
        let node = this.select(state);
		    if (node && !node.isLeaf() && !this.isWin(node.state)) {
		        node = this.expand(node);
		        win = this.simulate(node);
		    }
		
		    this.backPropagation(node, win);
    }
}

接下来就分析checkValue需要如何完成。

以我对卡牌游戏的理解，场面的价值会要考虑到双方场上怪物的生命值攻击力，怪物如果有特殊的词缀或者效果也需要进行考虑，如果是己方的怪物则为正相关，敌人的怪物则为负相关，两方抵消掉，就成为最终的场面价值。

进行了这些基础计算之后，还需要考虑到如果桌面的卡牌能够打出combo，那么卡牌的评价会得到提升，如果手牌中有未打出的combo牌，那么也有评价的提升，再或者说卡组中还有非常强力的牌没有抽到，那么也可以得到评价提升，所以这个checkValue函数是可以不断的去完善的，我放出我目前使用的checkValue给大家参考：

/**
 * 计算当前场面的价值
 * @param {*} myTableCard 我桌面卡组
 * @param {*} otherTableCard 对方桌面卡组
 * @param {*} myHandCard 我的手牌
 * @param {*} myRemainingCard 我剩余卡牌
 * @returns 当前场面的价值
 */
checkValue(myTableCard, otherTableCard, myHandCard, myRemainingCard, fee, myLife, otherLife) {
    // 算法：己方场面价值 + 己方手牌价值 + 己方牌库价值 - 对手场面价值
    // 目的：打出更多的combo，计算出各种出牌的顺序和各种出牌的方法中己方价值最大化的方法
    //
    //   注: 特殊怪物属性价值计算 = 嘲讽2 + 战吼0 + 亡语1 + 每回合5 + 圣盾1 + 吸血2 + 精力充沛1
    //       固定组合价值 = 固定组合设置价值 + 原卡价值
    //
    // 己方场面价值算法 = 己方场攻 + 己方怪物生命值 + 己方特殊怪物属性 + 固定组合价值 * 1.5    固定价值乘以一个放大的数字是为了让ai更多的打出combo
    // 对手场面价值算法 = 对手场攻 + 对手怪物生命值 + 对手特殊怪物属性 + 固定组合价值 * 1.5
    // 己方牌库价值 = 固定组合价值
    // 己方手牌价值 = 固定组合价值

    return (myTableCard.length ? myTableCard.reduce((pre, current) => {
            return pre + current.attack + current.life + this.calSpecialValue(current)
        }, 0) : 0)
        + this.comboCardValue(myTableCard)
        + this.calHandCardValue(myHandCard)
        + this.calRemainingCardValue(myHandCard, myRemainingCard)
        + (myLife - otherLife)
        - (otherTableCard.length ? otherTableCard.reduce((pre, current) => {
            return pre + current.attack + current.life + this.calSpecialValue(current)
        }, 0) : 0)
}

/**
 * 计算特殊怪物属性的价值
 * 嘲讽2  战吼0  亡语1  每回合5  圣盾1  吸血2  精力充沛1
 * @param {*} card 卡牌
 * @returns 特殊值
 */
calSpecialValue(card) {
    let value = 0;
    value += (card.isDedication ? 2 : 0);
    value += (card.isStrong ? 1 : 0);
    value += (card.isFullOfEnergy ? 1 : 0);
    value += (card.onEnd ? 1 : 0);
    value += (card.onMyTurnEnd ? 5 : 0);
    value += (card.onMyTurnStart ? 5 : 0);
    value += (card.specialValue != undefined ? card.specialValue : 0); // 因为specialValue可以为负数，所以只能直接判断undefined

    return value
}

/**
 * 
 * @param {*} cardList 
 */
comboCardValue(cardList) {
    return 0
}

calHandCardValue(myHandCard) {
    myHandCard.forEach(card => { // 遍历手牌，看是否有特殊组合

    })

    return 0;
}

calRemainingCardValue(handCard, remainingCard) {
    return 0
}

这样模拟也算是完成了，那么就剩下最后一步，也是相对来说简单的一步：反向传播，反向传播在一些机器学习的算法中也会使用到，它让每次模拟的结果都对下次模拟结果的准确率进行提升：

/**
 * 反向传播，向上更新父节点相关的值
 * @param {*} node 模拟的node
 * @param {*} winner 是否胜利
 */
backPropagation(node, win) {
    let tempNode = node;
    // 不停向上传递，直到根节点
    while (tempNode) {
        tempNode.update(win);
        tempNode = tempNode.parent;
    }
}

好了，到了这里，已经完成了蒙特卡洛树的搜索阶段，接下来就是获取当前结果了，将这些代码添加到getBestAction的后部，这样就可以直接调用getBestAction获取到蒙特卡洛树搜索得出的动作结果了：

// 如果节点没有完全拓展开，那么证明模拟没有完成
if (this.cacheTree[hashState(state)].isFullyExpanded() === false)
    throw new Error("未能模拟完成")

let node = this.cacheTree[hashState({ myTableCard, otherTableCard, myHandCard, myRemainingCard, fee, myLife, otherLife })]
let allActions = node.allActions()
let bestAction

// 如果只有一个选择并且是结束回合，那么可以直接返回无需计算
if (allActions.length === 1 && allActions[0].action.event === 'END_MY_TURN') {
    return allActions[0].action
}

// 遍历所有的动作，对动作进行胜率计算，胜率高的动作为最佳动作
let max = -Infinity
for (let a of allActions) {
    let action = a.action;

		// 当动作是直接结束回合的时候，胜率定为0.5，如果有胜率超过50%的则替换，否则执行结束回合
    if (action.event === 'END_MY_TURN') {
        bestAction = action;
        if (max < 0.5) {
            bestAction = action
            max = 0.5
        }
    } else {
        let childNode = node.childNode(action)
        if (!childNode) {
            console.error("childNode is null", node.children, action);
        }
        let ratio = childNode.n_wins / childNode.n_plays

        if (ratio > max) {
            bestAction = action
            max = ratio
        }
    }
}

return bestAction

总结

后续的关卡如果涉及到对战的，我就会使用这个算法来进行ai对战了。

其中有很多可以改进的地方，比如checkValue可以更加科学，蒙特卡洛树的很多分支可以进行剪枝和权重调整，让搜索往更有用的分支进行等等，你们也可以自行调整这些地方，让ai能够达到更智能的效果。