公开(公告)号：CN111176892A

公开(公告)日：2020-05-19

申请号：CN201911333317.6

申请日：2019-12-23

Applicant: 大连理工大学

Inventor： 刘婵娟 ,  闫俊名 ,  张强 ,  魏小鹏

IPC: G06F11/14

Abstract: 本发明公开一种基于备份策略的对抗式搜索方法，属于零和博弈策略搜索领域。本发明通过优化经典极大极小算法的备份规则，提出了一种迭代最优极大极小(IOM)算法。该方法包括如下步骤：首先，利用静态评估函数计算任一给定节点的评估值。然后，根据备份规则以反向传播的方式更新每个节点的最终值，即，每个节点的最终备份值等于其评估值减去其子节点中的最大备份值的两倍。本发明在计算中间节点最终状态值时所使用的备份规则，为减小博弈树中病态节点对决策质量的影响提供了一种解决方法。与误差最小化极大极小算法以及经典的极大极小算法相比，本发明所述的迭代最优极大极小算法在搜索深度有限的条件下提高了决策质量。

公开(公告)号：CN111176892B

公开(公告)日：2023-06-09

申请号：CN201911333317.6

申请日：2019-12-23

Applicant: 大连理工大学

Inventor： 刘婵娟 ,  闫俊名 ,  张强 ,  魏小鹏

IPC: G06F11/14

Abstract: 本发明公开一种基于备份策略的对抗式搜索方法，属于零和博弈策略搜索领域。本发明通过优化经典极大极小算法的备份规则，提出了一种迭代最优极大极小(IOM)算法。该方法包括如下步骤：首先，利用静态评估函数计算任一给定节点的评估值。然后，根据备份规则以反向传播的方式更新每个节点的最终值，即，每个节点的最终备份值等于其评估值减去其子节点中的最大备份值的两倍。本发明在计算中间节点最终状态值时所使用的备份规则，为减小博弈树中病态节点对决策质量的影响提供了一种解决方法。与误差最小化极大极小算法以及经典的极大极小算法相比，本发明所述的迭代最优极大极小算法在搜索深度有限的条件下提高了决策质量。