4.6 实例讲解
本节以“十点半”游戏为例，分别使用在线策略蒙特卡罗和离线策略蒙特卡罗寻找最优策略，并比较两种算法在处理上的异同。
4.6.1 “十点半”游戏
1．简单“十点半”游戏介绍
“十点半”是一种流行于浙江一带的扑克游戏，这种游戏老少皆宜。在“十点半”游戏中，手牌（A，2，3，4，5，6，7，8，9，10）为普通牌，其中，A为1点，其余牌点数为本身的点数。手牌（J，Q，K）为人牌，牌点数视为半点。
游戏者的目标是使手中的牌的点数之和在不超过十点半的情况下尽量大。本文的简单十点半由一个庄家和一个玩家进行对局游戏，并且在游戏中增加了特殊牌型（人五小、天王、五小、十点半），针对特殊牌型，添加了加倍功能，使游戏更有趣，更刺激。
牌型说明如下。
人五小：5张牌，且每张都由人牌组成，5倍回报。
天王：5张牌，且牌面点数总和为十点半，4倍回报。
五小：5张牌不都是人牌，且总点数小于十点半，3倍回报。
十点半：5张牌以下，牌的总点数正好等于十点半，2倍回报。
平牌：5张牌以下，牌的总点数小于十点半，1倍回报。
爆牌：牌的总点数大于十点半。
其中，（人五小、天王、五小、十点半）属于特殊牌型。
比牌规则如下。
牌型大小：人五小>天王>五小>十点半>平牌>爆牌
游戏开始时，庄家为玩家发一张牌，玩家可根据自己的手牌，决定要牌或停牌。玩家最多可连续要4张牌，即手牌数目不能超过5张。
玩家拿到牌型为十点半以上（包含）的牌（人五小，天王，五小，十点半），则立即获胜，庄家立输，玩家按照游戏规则，获得相应回报。玩家拿到总分为十点半以上的牌，则为爆牌，玩家立输，庄家立即获胜。
玩家拿到十点半以下的牌并停牌，则庄家要牌，再和玩家比大小。
庄家如果当前分数小于玩家，则继续要牌，直至分出胜负。如果庄家等于玩家分数则比较手牌的数量，若手牌数小于等于玩家的手牌数，则判定为庄家获胜。庄家手牌也同样遵循牌型规则。
在计算回报时，普通牌型赢牌回报1，输牌回报-1。如遇特殊牌型，应该根据各牌型的相应倍率计算回报。比如，庄家为人五小时，玩家回报为-5。
2．环境描述
接下来对“十点半”游戏的马尔可夫决策过程模型进行描述M=<S，A，P，R，γ>。
状态空间S：（多达200种，根据对状态的定义可以有不同的状态空间，这里采用的定义是玩家手牌总分，手牌数目，人牌数目）。
（1）当前手牌总分（0.5，1，1.5，2，2.5，3，3.5，4，4.5，…，10.5）。
（2）手牌数目（1，2，3，4，5）。
（3）人牌数目（0，1，2，3，4，5）。
行为空间A：
（1）要牌，用1表示。
（2）停牌，用0表示。
回报R（要牌）：这里的回报是指玩家获得的回报，如果输掉比赛，得分用负数表示。
（1）+5：如果玩家手牌为人五小。
（2）+4：如果玩家手牌为天王。
（3）+3：如果玩家手牌为五小。
（4）+2：如果玩家手牌为十点半。
（5）+1：玩家手牌分数大于庄家手牌分数，指的是玩家没遇到特殊牌型，也没爆牌。
（6）-1：如果玩家手牌分数超过十点半。
回报R（停牌）：同上，这里的回报是指玩家获得的回报，如果输掉比赛，得分用负数表示。
（1）-5：如果庄家手牌为人五小。
（2）-4：如果庄家手牌为天王。
（3）-3：如果庄家手牌为五小。
（4）-2：如果庄家手牌为十点半。
（5）+1：如果庄家手牌分数超过十点半。
（6）-1：如果庄家手牌分数大于玩家手牌分数，指的是庄家没有遇到特殊牌型，也没有爆牌的情况下，和玩家手牌比大小。
状态转换：玩家采取要牌动作，要到一张牌后，玩家的手牌状态发生变化（手牌总分加上新牌分数，手牌总数加1，若新牌为人牌，则人牌数目加1）；玩家采取停牌动作，玩家手牌状态不发生变化，开始给庄家发牌。
求解问题：玩家应该采取的最优策略。
3．环境代码
接下来基于gym构建“十点半”游戏的环境，以下代码主要定义了“十点半”游戏马尔可夫决策过程模型的状态空间、行为空间，以及分别采取不同行为后的状态转换和回报等信息。
主要包含如下方法。
· def draw_card（np_random）：随机发牌。
· def sum_hand（hand）：求取当前手牌总分。
· def get_card_num（hand）：获取当前手牌的数量。
· def get_p_num（hand）：获得当前手牌的人牌数量。
· def_step（self，action）：基于当前的状态和输入动作，得出下一步的状态、回报和是否结束。如果动作为叫牌：给玩家发一张手牌，改变玩家手牌的状态，判断玩家当前手中的牌型，返回（玩家当前手牌状态、回报和是否结束）。如果动作为停牌：庄家开始补牌，点数比玩家大，庄家获胜，游戏结束，否则继续补牌至分出胜负（注意：当点数相同时，比较手牌，庄家手牌大于等于玩家，庄家胜，否则继续补牌）。
· def_get_obs（self）：获取当前的状态空间（玩家手牌数的总分、玩家手中的总牌数、玩家手中的人牌数）。
· def cmp（dealer，player）：庄家和玩家比较手牌总分。如果庄家大，返回True，玩家大，返回False。当点数相同时比较手牌数量，庄家手牌数小于等于玩家，返回False，大于则返回True。
· def gt_bust（hand）：判断手牌总分是否超过10.5。
· def is_dest（hand）：判断手牌总分是否刚好等于10.5。
· def is_rw x（hand）：判断是否为人五小。
· def is_tw（hand）：判断是否为天王。
· def is_wx（hand）：判断是否为五小。
· def hand_types（hand）：根据手牌返回结果（牌型、回报、结束状态）。
具体代码如下：
4.6.2 在线策略蒙特卡罗
1．算法详情
使用在线策略蒙特卡罗方法对“十点半”游戏马尔可夫问题进行求解的总体思路是以ε-贪心策略采样数据，生成完整轨迹。每生成一条完整轨迹，进行一次策略评估和策略改进。规定轨迹总数目为500 000条，每条轨迹最多200个时间步。超出轨迹数目之后，输出所有状态对应的最优行为。
（1）初始化行为值函数Q=0。
Q_on = defaultdict(lambda:np.zeros(env.action_space.n))
（2）初始化环境，随机给玩家发一张牌。
如：玩家当前手牌状态为（0.5，0，1）。
state = env._reset()
（3）遵循ε-贪心策略选择行为，返回结果。例如：选择行为要牌后（1），状态转换为（5.5，1，1），回报为0，标记轨迹未结束（done=false）。继续使用ε-贪心策略选择行为停牌（0），返回结果：状态转换为（5.5，1，1），回报为-1，标记轨迹结束（done=true），详见代码（env._step（action）函数）。
（4）使用初访法计算轨迹中的状态行为对的行为值函数，并进行更新。
（5）结合更新后的行为值函数，对原始策略进行更新。
# 策略的改进就是不断改变该状态下的Q
Q[state][action] = returns_sum[sa_pair] / returns_count[sa_pair]
（6）重复步骤（2）～（5），直至轨迹数=500 000。最终得到的最优策略如图4-3所示。
图4-3 最优策略
不同状态下最优策略的三维图如图4-4～图4-8所示。
图4-4 没有人牌时的最优策略
图4-5 一张人牌时的最优策略
图4-6 两张人牌时的最优策略
图4-7 三张人牌时的最优策略
图4-8 四张人牌时的最优策略
2．核心代码
接下来对在线策略蒙特卡罗算法的代码进行描述。在线方法的主体函数是mc_control_epsilon_greedy，输入为：十点半环境env，样本的总步数num_episodes，衰减因子discount_factor，epsilon值。输出为：行为值函数Q和最优策略。此方法采样数据时，使用了ε-贪心策略，此策略是通过调用函数make_epsilon_greedy_policy生成的。
此代码用到的方法如下。
· def make_epsilon_greedy_policy（Q，epsilon，nA）：基于给定的Q行为值函数和epsilon值创建一个ε-贪心策略。
· def policy_fn（observation）：求取该状态对应的最大行为值函数。
具体代码如下。
4.6.3 离线策略蒙特卡罗
1．算法详情
使用加权重要性采样离线策略蒙特卡罗方法对“十点半”游戏马尔可夫问题进行求解的总体思路是以随机策略采样数据，生成完整轨迹。每生成一条完整轨迹，通过加权重要性采样的方法进行一次策略评估和策略改进。评估和改进的策略都是贪心策略。轨迹总数目为500 000条，每条轨迹最多200个时间步。超出轨迹数目之后，输出所有状态对应的最优行为。
（1）初始化行为值函数Q=0。加权重要性采样权重分母C（s，a）=0，折扣因子为1。
# 行为值函数
Q_off = defaultdict(lambda: np.zeros(env.action_space.n))
# 加权重要性采样公式的累积分母(通过所有的episodes)
C = defaultdict(lambda: np.zeros(env.action_space.n))
（2）初始化环境，随机给玩家发一张牌，如玩家当前手牌状态为（0.5，1，1）。
state = env._reset()
（3）遵循随机策略选择行为，返回结果。例如：选择要牌（1）后，状态转换为（1.0，2，2），回报为0，标记轨迹未结束（done=false）。继续执行随机策略，直至轨迹结束。状态转换及回报情况见代码（env._step（action）函数）。最终生成的轨迹如下。
（0.5，1，1），1，0，（1.0，2，2），1，0，（1.5，3，3），1，0，（8.5，4，3），0，1
离线策略蒙特卡罗算法初始所遵循的随机策略如下。
random_policy = create_random_policy(env.action_space.n)
def create_random_policy(nA):
A = np.ones(nA, dtype=float) / nA
def policy_fn(observation):
return A
return policy_fn
离线策略蒙特卡罗算法需要评估改进的目标策略为贪心策略。
target_policy = create_greedy_policy(Q_off)
def create_greedy_policy(Q):
def policy_fn(state):
A = np.zeros_like(Q[state],dtype = float)
best_action = np.argmax(Q[state])
A[best_action] = 1.0
return A
return policy_fn
调用离线策略蒙特卡罗算法。
Q_off, target_policy, C, episode_off = off_policy(state, random_policy, episode_off,
discount_factor, target_policy, C, Q_off)
根据当前状态遵循随机策略求出每个行为的对应概率，根据概率随机选取行为，并且根据当前行为获取下一个状态、回报、是否结束等结果。
# 根据当前的状态返回一个行为概率数组
probs = behavior_policy(state)
# 根据返回的行为概率数组随机选择动作
action = np.random.choice(np.arange(len(probs)), p = probs)
# 根据当前动作确认下一步的状态、回报,以及是否结束
next_state, reward, done, _ = env._step(action)
（4）针对每一条轨迹，从终止状态到开始状态，以倒序的方式计算每一个时间步的累积回报G：
G←γ G+rt+1
更新权重分母C（st，at）：
C（st，at）←C（st，at）+W
更新Q（st，at）：
同时对权重分子进行更新：
最后针对更新后的行为值函数，对当前状态的策略进行更新，各时间步的行为值函数和策略取值见表4-1。
表4-1 轨迹
对应代码如下。
# 累计回报的值
G = 0.0
# 权重
W = 1.0
# 对于每一个episode,倒序进行计算
for t in range(len(episode))[::-1]:
state, action, reward = episode[t]
# 从当前步更新总回报
G = discount_factor * G + reward
# 更新加权重要性采样公式分母
C[state][action] += W
# 使用增量更新公式更新动作值函数
Q[state][action] += (W / C[state][action]) * (G - Q[state][action])
# 如果行为策略采取的行动不是目标策略采取的行动,则跳出循环
if action != np.argmax(target_policy(state)):
break
W = W * 1. / behavior_policy(state)[action]
（5）重复（4）步，直至轨迹数=500 000。最终得到的最优策略如图4-9～图4-14所示。
图4-9 最优策略
图4-10 没有人牌时的最优策略
图4-11 一张人牌时的最优策略
图4-12 两张人牌时的最优策略
图4-13 三张人牌时的最优策略
图4-14 四张人牌时的最优策略
2．核心代码
接下来对离线策略蒙特卡罗算法的代码进行描述。此处的代码采用了加权重要性采样的方法。
离线策略蒙特卡罗算法的主体函数是mc_control_importance_sampling，输入输出与在线策略蒙特卡罗算法的主体函数相同。此方法采样数据时，使用了随机策略，此策略是通过调用函数create_random_policy生成的。改进的策略是贪心策略，此策略通过调用函数create_greedy_policy生成。
此代码用到的方法如下。
· def create_random_policy（nA）：随机策略。
· def create_greedy_policy（Q）：贪心策略。
· def policy_fn（observation）：求取该状态对应的最大行为值函数。
对应代码如下。
4.6.4 实例小结
分别使用蒙特卡罗在线策略算法和离线策略算法针对“十点半”游戏，运行500、1000、2000、5000、1万、2万、10万、20万、30万、40万、50万条轨迹。早期，无论是在线策略方法还是离线策略方法，其对应的最优值函数均随着轨迹的增多迅速增加，但到达一定取值之后，其对应的值函数基本稳定在一个范围内，但后期还是会在一定范围内波动，这说明两种方法都有一定的探索。且最终两者对应的最优值函数基本一致，图4-15是当人牌数为0时，两种方法计算出来的最优值函数对比，其中五星表示在线策略算法，倒三角表示离线策略算法。
图4-15 两种方法计算出来的最优值函数对比图（见彩插）