博弈树 极小极大分析法_极大极小分析法

一、博弈概述

博弈特点：

（1）博弈的初始格局是初始节点

（2）在博弈树中，“或”和“与”是交替出现的。自己一方的扩展节点是“或”关系，对方扩展的节点是“与”关系。双方轮流扩展节点。

（3）所有自己一方获胜的终局都是本原问题，相应的节点是可解节点，所有使对方获胜的终局都认为是不可解点。

假设有两方博弈，若A先走则成处于奇数深度的节点都应由A走，所有偶数级都应该由B走。

博弈树是一棵“与或”树，我们必须要站在某个对象的角度进行观察。那我们最终应该在这颗与或树上进行搜索，直至到最优结果。

二、极小极大分析法

静态估值：

站在某一方，估算当前博弈树节点的得分，当格局对对方有利时，估计函数给出的估值分值小

* 若P是A的必胜的棋局，则e（P）=+无穷

* 若P是B的必胜的棋局 ，则e（p）=-无穷

*若P是胜负未定的棋局，则e（p）=e（+P）-e（-P）

 其中e（+p）表示棋局P上有可能使X成为三子一线的数目e（-P）表示棋局P上有可能使O成为三子一线的数目

那么对于棋局的静态估值，如果站在X方，最希望是哪个棋局？

需要做一下假设：

1、A先走棋，站在A的立场上

2、博弈树每次仅扩展两层，（A，B）各走一步

3、具有对称性的两个棋局算作一个棋局

上面的图片中对于X来说最好的结果果断是S3，而当X走S3后，O肯定会走S4，因为对于X最不利。

极大极小分析法：

当A当前有多个行动方案时，A总是挑选对自己最有利的行动

当B行动时，A要充分估计对方对自己最为不利的行动