一、Games的特点

1. 规则简单、概念深刻；
2. 千百年的历史；
3. 有意义的IQ训练；
4. 人工智能的体现；
5. 现实世界的封装展现；
6. 游戏具有趣味性。

二、传统游戏的种类

1. 跳棋
2. 象棋
3. 黑白棋
4. 西洋双陆棋
5. 英语文字图版游戏
6. 围棋
7. 扑克
   ①完全信息游戏（游戏能被完全观测）：
   跳棋、象棋、黑白棋、西洋双陆棋、围棋
   ②不完全信息游戏（部分被观测）：
   英语文字图版游戏、扑克

三、游戏中的最优策略

（纳什均衡）
第个玩家的最优策略，其他的所有玩家策略为

单个智能体强化学习

把其他玩家当成环境的一部分，整个游戏可以简化成一个MDP，该智能体的最优响应就是整个MDP的最优策略；

自我对弈强化学习

游戏的所有玩家生成了experience： ~ ， ~ ，每一个玩家学习相对于其他玩家的最优响应，任意一个玩家的策略决定了其他玩家的环境，所有的玩家之间都互相适应。

零和博弈

有两个玩家（一黑一白）
两个玩家的奖励是平等且对立的：

在这样的零和博弈游戏中，我们考虑使用树搜索、自对弈强化学习来寻找纳什均衡点。

四、最大最小搜索

最大最小值函数将白色方的期望最大化，黑色方的期望最小化，即：

最大最小值函数是唯一的，最大最小策略就是纳什均衡点。

最大最小搜索
策略需要列出所有的招法，策略的使用次数随着树的深度呈指数形式增长，要完全搜索至游戏结束是不现实的。在树的宽度和深度上进行削减，可以减少计算量。一直策略模型，只列出有价值的前N个招法，能够在树的宽度上进行裁剪。在策略计算到第d层时，即使没法确定局面的最终结果，也可以停止训练，使用一个价值模型判断双方的局势，并估计最终的期望结果，即放弃一定的精度来换取时间，这能够在树的深度上进行裁剪。（Alpha-Beta剪枝）

线性组合

是特征向量，是权重

线性组合

五、自我对弈TD学习

在自我对弈游戏中基于值函数更新的强化学习应用：
①MC：

②TD(0)：
③TD(
对于确定性的游戏来说，能够评估
因为游戏规则已经定义了赢的状态
这样就能对两个玩家都更新策略至找到纳什均衡点。
在Logistello（黑白棋游戏程序）中创建了自己的特征，在不同的结构下创建了150万个特征，并用这些特征构建线性组合值函数，使用MC评估策略，Greedy更新策略，以6-0打败了世界冠军Takeshi Murukami。

TD-Gammon

非线性近似值函数
初始使用随机权重，通过自我对弈进行训练，使用非线性TD学习，使用Greedy策略进行提升。

简单的TD：

价值更新
通过权重
先用TD学习的方法学习值函数，再用值函数进行最大最小搜索：

简单的TD方法在黑白棋、西洋双陆棋中表现不错，但在跳棋和象棋中表现不佳，在象棋策略中找到位置标志是非常有必要的，如果没有搜索是很难找到能够将军的位置的。

TD Root

TD Root更新
在根节点
在下一个状态用最大最小搜索并反向传播：
TD Leaf更新
对于当前状态和下一个状态根节点都进行最大最小搜索，即：
反向传播：
TD Leaf在象棋中的应用：Knightcap，在跳棋中的应用：Chinook
Knightcap：使用TD Leaf学习权重 TreeStrap
在所有的节点都进行最大最小搜索

TreeStrap在象棋中的应用
Meep:2000个特征线性组合构建值函数，初始使用随机权重，通过TreeStrap进行权重调整。在自我对弈下也有效。

基于simulation的搜索

自我对弈强化学习可以代替搜索
从根状态开始自我对弈
应用强化学习1）MCTS；2）UCT算法；3）UCB平衡探索与利用
完全信息游戏：零和博弈、两个玩家的游戏；不完全信息游戏：看下一个选择
在很多具有挑战性的游戏中，MCTS是最好的方法，例如围棋、Hex卡牌游戏、集结棋、Amazons等，但在一些游戏中，简单的MC搜索就足够了，例如西洋双陆棋、英语文字图版游戏等。
简单的MC搜索在游戏中的应用：Maven

六、树搜索在不完全信息游戏中的应用

每一个信息状态都是一个节点，很多真实的状态会有相同的信息状态，很多状态有相似的价值。
不完全信息游戏的解决方法：1）向前搜索迭代的方法；2）自我对弈强化学习。Smooth UCT就是其中一种。
Smooth UCT
对信息状态游戏树进行MCTS
智能体学习对抗对手的平均行为
从节点行为中得出平均战略：
在每一个节点，根据下式进行动作选择：
以经验来说，在扑克游戏中，纯MCTS是发散的，Smooth UCT是能够找到纳什均衡点的。

七、总结

目前强化学习在游戏中有了较好的应用：