|
极大极小过程 一、概述
在人工智能发展的早期，就开始了对博弈问题的研究。本节讨论的博弈属于双人完备信息博弈。这里博弈由两人对垒，两人轮流走步。双方既知道对方走过的棋步，也可估计对方今后的棋步。棋的结局是一方赢，一方输，或者和局。另一种博弈为机遇性博弈，既存在不可预测的博弈。 三、极大极小过程 定义：为了计算非叶结点的估值，必须从叶结点向上倒推。对于ＭＡＸ结点，由于ＭＡＸ方总是选择使估值最大的走步，因此ＭＡＸ结点的倒推值应取后继结点估值的最大值。对于ＭＩＮ结点，由于ＭＩＮ方总是选择使估值最小的走步，因此ＭＩＮ结点的倒推值应取其后继结点估值的最小值。这样一步下地计算倒推值，直至计算出初始结点的倒推值为止。由于我们研究的是ＭＡＸ方的走步，所以应选择其后继结点中具有最大倒推值的走步。这一过程就称为极小极大过程。 四、一字棋示例 |