博弈算法的起源
Ernst Zermelo：Minimax algorithm最小最大算法
Claude Shannon：evaluation fundtion，selective search评价函数和选择性搜索
John McCarthy：Alpha-beta search Alpha-beta搜索
Arthur Samuel：Checkers program that learns its own evaluation function学习自身评价函数的程序
两玩家博弈的特点：确定性、完整信息、轮流、零和
形式化定义搜索问题：
初始状态 ：博弈开始时的设定
玩家PLAYERS(s)：定义在状态s下轮到哪个玩家做动作
动作ACTIONS(s)：返回某个状态下的合法动作
转移模型RESULTS(s,a)：定义在状态s下，进行动作a后带来的结果
终止检测TERMINAL-TEST(s)：若博弈结束则返回true，否则返回false
效用UTILITY(s,p)：定义在状态s下玩家p的效用值
极小极大算法
Minimax算法伪代码：
Alpha-beta剪枝伪代码：
每一个节点都有各自的alpha值和beta值，alpha代表按照先根遍历，这个节点Minimax搜索到这一点的值的下确界，beta代表上确界。
alpha代表从根节点到当前节点的路径上的所有max节点能取到的最大的值
beta代表从根节点到当前节点的路径上的所有min节点能取到的最小值
对于Min节点，若子节点返回的值小于alpha，则停止拓展并返回；若小于beta，则更新beta
对于Max节点，若子节点返回的值大于beta，则停止拓展并返回；若大于alpha，则更新alpha
在实际的程序代码中，α和β是值传递的局部变量
不完美实时决策
用启发式评估函数代替效用函数，用阶段测试取代终止测试
随机博弈
随机博弈是一种具有概率转换的动态博弈
蒙特卡洛方法
蒙特卡洛方法一大类计算方法，凭借重复随机采样来获得数值结果