量化交易与机器学习第三十五篇

A股天机

量化交易与机器学习第三十五篇

来自：MACD论坛(bbs.macd.cn) 作者：A股天机 浏览：10558 回复：1

上周我们讨论了从博弈的minmax算法方面去考虑问题，本周我们继续讨论。
1，先说原理
      简单的Minmax算法有一个很大的问题就是计算复杂性。由于所需搜索的节点数随最大深度呈指数膨胀，而算法的效果往往和深度相关，因此这极大限制了算法的效果，其实这样一种朴素的思想：时时刻刻记得当前已经知道的最好选择，如果从当前格局搜索下去，不可能找到比已知最优解更好的解，则停止这个格局分支的搜索（剪枝），回溯到父节点继续搜索，即Alpha-beta算法
现在考虑这样一个游戏：有三个盘子A、B和C，每个盘子分别放有三张纸币。A放的是1、20、50；B放的是5、10、100；C放的是1、5、20。单位均为“元”。有甲、乙两人，两人均对三个盘子和上面放置的纸币有可以任意查看。游戏分三步：
甲从三个盘子中选取一个。
乙从甲选取的盘子中拿出两张纸币交给甲。
甲从乙所给的两张纸币中选取一张，拿走。
其中甲的目标是最后拿到的纸币面值尽量大，乙的目标是让甲最后拿到的纸币面值尽量小。
基本方法是从根节点开始采用深度优先的方式构造格局树，在构造每个节点时，都会读取此节点的alpha和beta两个值，其中alpha表示搜索到当前节点时已知的最好选择的下界，而beta表示从这个节点往下搜索最坏结局的上界。由于我们假设对手会将局势引入最坏结局之一，因此当beta小于alpha时，表示从此处开始不论最终结局是哪一个，其上限价值也要低于已知的最优解，也就是说已经不可能此处向下找到更好的解，所以就会剪枝
2，关于实践
从根节点开始，详述使用Alpha-beta的每一个步骤：
根节点的alpha和beta分别被初始化为−∞，和+∞。
深度优先搜索第一个孩子，不是叶子节点，所以alpha和beta继承自父节点，分别为−∞，和+∞
搜索第三层的第一个孩子，同上。
搜索第四层，到达叶子节点，采用评价函数得到此节点的评价值为1【见图一】
此叶节点的父节点为max节点，因此更新其alpha值为1，表示此节点取值的下界为1。

再看另外一个子节点，值为20，大于当前alpha值，因此将alpha值更新为20。
此时第三层最左节点所有子树搜索完毕，作为max节点，更新其真实值为当前alpha值：20。
由于其父节点（第二层最左节点）为min节点，因此更新其父节点beta值为20，表示这个节点取值最多为20。【见图二】
搜索第二层最左节点的第二个孩子及其子树，按上述逻辑，得到值为50（注意第二层最左节点的beta值要传递给孩子）。由于50大于20，不更新min节点的beta值。【见图三】
搜索第二层最左节点的第三个孩子。当看完第一个叶子节点后，发现第三个孩子的alpha=beta，此时表示这个节点下不会再有更好解，于是剪枝。【见图四】继续搜索B分支，当搜索完B分支的第一个孩子后，发现此时B分支的alpha为20，beta为10。这表示B分支节点的最大取值不会超过10，而我们已经在A分支取到20，此时满足alpha大于等于beta的剪枝条件，因此将B剪枝。并将B分支的节点值设为10，注意，这个10不一定是这个节点的真实值，而只是上线，B节点的真实值可能是5，可能是1，可能是任何小于10的值。但是已经无所谓了，反正我们知道这个分支不会好过A分支，因此可以放弃了。【见图五】在C分支搜索时遇到了与B分支相同的情况。因此讲C分支剪枝。【见图六】时搜索全部完毕，而我们也得到了这一步的策略：应该走A分支。
可以看到相比普通Minimax要搜索18个叶子节点相比，这里只搜索了9个。采用Alpha-beta剪枝，可以在相同时间内加大Minimax的搜索深度，因此可以获得更好的效果。并且Alpha-beta的解和普通Minimax的解是一致的。
3.    总结
Minimax算法的求解空间很大，需要用Alpha-beta剪枝，降低计算次数，也可以理解成一种搜索算法，通过查找，得到“最优解”。实际上获得全局最优解是很难的，大多数情况下，只能获得当下局部最优。
上周贴图进行解释，止损目标是为了实现“截断亏损，让利润奔跑”，交易时刻有风险，每次交易的风险应该控制在一个区域内，没有大失误，就取得了持续下去的基本条件。【见图七】

fm2017

谢谢老师教学 辅导 启蒙 !拜读！！！