对抗搜索算法

博弈游戏
博弈游戏可以形式化为包含以下组成部分的搜索问题:
\(s_0\)初始状态;
\(Player(s)\) 定义此时该谁行动;
\(Actions(s)\) 定义此状态下的合法移动集合;
\(Result(s,a)\) 转移模型;
\(Terminal\_Test(s)\) 终止测试,若游戏结束返回真;
\(Utility(s, p)\) 效用函数,定义游戏者p在终止状态s下的数值。

Minimax算法
结点的极大极小值(Minimax)即为效用值。
\[Minimax(s) =\begin{cases} Utility(s), & Terminal(s)\\ \max\limits_{a\in Actions(s)} Minimax(Result(s,a)), &MAX\_Node(s)\\ \min\limits_{a\in Actions(s)}Minimax(Result(s,a)), &MIN\_Node(s)\end{cases}\]

\(\alpha-\beta\)剪枝
\(\alpha\)是到目前为止的路径上,发现的MAX的最佳选择;
\(\beta\)是到目前为止的路径上, 发现的MIN的最佳选择。
对于MAX,如果新分支v比\(\alpha\)还差,则剪掉这一分支。
对于MIN,如果新分支v比\(\beta\)更好,则剪掉这一分支。

不完美决策
确定性(deterministic)的游戏可能有不完全的信息。
使用截断测试\(Cutoff\_Test(s, d)\)代替终止测试。

    所属分类:人工智能     发表于2022-05-18