第五章-对抗搜索分析课件.ppt

1、计算机科学技术学院计算机科学技术学院一颗两层的博弈树一颗两层的博弈树( )( )( )( )max( , )min( , )a Actions sa Actions sMINIMAX sUTILITY sMINIMAX RESULT s aMINIMAX RESULT s assMAXsMIN为终止状态为结点为结点 剪枝：剪枝：如果如果m比比n好，我们就不会走到好，我们就不会走到n。( )( )( )max( , ),1)min( , ),1)a Actions sa Actions sEVAL sHMINIMAX RESULT s a dHMINIMAX RESULT s a d( , )M

2、AXMINCUTOFF TEXT s dss如果为真为结点为结点)(1sfwinii（a）黑棋有）黑棋有1个马、个马、2个个 兵的优势，能够取胜。兵的优势，能够取胜。（b）黑棋会被白棋吃掉皇后，从而失败。）黑棋会被白棋吃掉皇后，从而失败。state chance a is )(imaxexpectimin)(state MIN a is )(imaxexpectiminminstate MAX a is )(imaxexpectiminmaxstate terminala is )(utility)(imaxexpectimin)()()(nsspnsnsnnnnSuccessorssnSuccessorssnSuccessorss在保持顺序不变的情况下，叶节点赋值的在保持顺序不变的情况下，叶节点赋值的变换导致了最佳招数的改变。变换导致了最佳招数的改变。argmax( )( , )aP s MINIMAX RESULT s a11argmax( )( , )naiP s MINIMAX RESULT s aN