Sutton 强化学习，21 点游戏的策略蒙特卡洛值预测作者|MyEncyclopedia来源|MyEncycloped

文章插图
作者 | MyEncyclopedia
来源 | MyEncyclopedia（ID：MyEncyclopedia）
头图 | CSDN 下载自东方IC
从这期开始我们进入 Sutton 强化学习第二版，第五章蒙特卡洛方法。蒙特卡洛方法是一种在工程各领域都存在的基本方法，在强化领域中，其特点是无需知道环境的 dynamics ，只需不断模拟记录并分析数据即可逼近理论真实值。蒙特卡洛方法本篇将会用21点游戏作为示例来具体讲解其原理和代码实现。
文章插图
21点游戏问题
21点游戏是一个经典的赌博游戏。大致规则是玩家和庄家各发两张牌，一张明牌，一张暗牌。玩家和庄家可以决定加牌或停止加牌，新加的牌均为暗牌，最后比较两个玩家的牌面和，更接近21点的获胜。游戏的变化因素是牌 Ace，既可以作为11也可以作为1来计算，算作11的时候称作 usable。
Sutton 教材中的21点游戏规则简化了几个方面用于控制问题状态数：

已发的牌的无状态性：和一副牌的21点游戏不同的是，游戏环境简化为牌是可以无穷尽被补充的，一副牌的某一张被派发后，同样的牌会被补充进来，或者可以认为每次发放的牌都是从一副新牌中抽出的。统计学中的术语称为重复采样（sample with replacement）。这种规则下极端情况下，玩家可以拥有 5个A或者5个2 。另外，这会导致玩家无法通过开局看到的3张牌的信息推断后续发牌的概率，如此就大规模减小了游戏状态数。
庄家和玩家独立游戏，无需按轮次要牌。开局给定4张牌后，玩家先行动，加牌直至超21点或者停止要牌，如果超21点，玩家输，否则，等待庄家行动，庄家加牌直至超21点或者停止要牌，如果超21点，庄家输，否则比较两者的总点数。这种方式可以认为当玩家和庄家看到初始的三张牌后独立做一系列决策，最后比较结果，避免了交互模式下因为能观察到每一轮后对方牌数变化产生额外的信息而导致的游戏状态数爆炸。

有以上两个规则的简化， 21点游戏问题的总状态数有下面三个维度

自己手中的点数和（12到21）
庄家明牌的点数（A到10)
庄家明牌是否有 A（True, False）。

状态总计总数为三个维度的乘积 10 * 10 * 2 = 200 。
关于游戏状态有几个比较 subtle 的假设或者要素。首先，玩家初始时能看到三张牌，这三张牌确定了状态的三个维度的值，当然也就确定了 Agent 的初始状态，随后按照独立游戏的规则进行，玩家根据初始状态依照某种策略决策要牌还是结束要牌，新拿的牌更新了游戏状态，玩家转移到新状态下继续做决策。举个例子，假设初始时玩家明牌为8 ，暗牌为6 ，庄家明牌为7 ，则游戏状态为 Tuple (14, 7, False) 。若玩家的策略为教材中的固定规则策略：没到20或者21继续要牌。下一步玩家拿到牌3 ，则此时新状态为 (17, 7, False) ，按照策略继续要牌。
第二个方面是游戏的状态完全等价于玩家观察到的信息。比如尽管初始时有4张牌，真正的状态是这四张牌的值，但是出于简化目的，不考虑 partially observable 的情况，即不将暗牌纳入游戏状态中。另外，庄家做决策的时候也无法得知玩家的手中的总牌数。
第三个方面是关于玩家点数。考虑玩家初始时的两张牌为2 ， 3 ，总点数是5 ，那么为何不将5加入到游戏状态中呢？原则上是可以将初始总和为2到11都加入到游戏状态，但是意义不大，原因在于我们已经假设了已发牌的无状态性，拿到的这两张牌并不会改变后续补充的牌的出现概率。当玩家初始总和为2到11时一定会追加牌，因为无论第三张牌是什么，都不会超过21点，只会增加获胜概率。若后续第三张牌为8 ，总和变成13 ，就进入了有效的游戏状态，因为此时如果继续要牌，获得10 ，则游戏输掉。因此，我们关心的游戏状态并不完全等价于所有可能的游戏状态。