周子龙

（同济大学 软件学院，上海201804）

1 概述

在一般的搜索过程中，总是会有一个限定的、有限的搜索内容集。一般的搜索算法也仅仅限于在该固定集中进行查找操作，返回是否查找成功，即待查找的元素是否属于该集合。而在许多情境中，该类搜索并不能满足用户的全部需要，有时候，我们并不是搜索某一特定的元素，而是给出集合中最符合用户需求的元素。这些元素并不是绝对确定的，当一定是在某一些特定要求下，根据某种评估，所能在有限的搜索集合中给出最有元素；同时，搜索的集合可能在需要执行搜索的时候还未产生，需要一边搜索一边动态的产生新的元素。一般地，我们把符合上述描述的搜索称为动态博弈搜索。相较于普通搜索，博弈搜索的搜索集合并不是可以立即确定的，它可能需要根据不同局中人的不同行为生成不同元素进行不断补充；以及，该过程也涉及到多个参与者，即上文提到的多个局中人，每一局中人均假设为理性博弈者，即其所作出的任何行为均是符合一定标准下利益最大化原则。综上，动态博弈搜索树是一种对动态决策的过程模拟，它在搜索的过程中同时产生许多新的可能的结果，依据利益最大化原则，为每一为局中人进行操作，搜索出来的最优行为即应当满足如下要求：通过该最优行为，当所有局中人按照自己利益最大化原则进行后续行为后，该行为为己方带来最大收益。

在理想情况下，总是认为考虑到的情况越多越好，但计算机的算力总是有限的，在现实生活中，局中人的思考能力以及思考时间也是有限的，故搜索不能无限制的进行下去，只可能在有限的搜索深度下，得到当前局面的最优行为。……