博弈树和搜索树的一个不同就是搜索树必须在搜索中存储棋面状态的副本（在开放集和闭合集中）。基于博弈树的搜索算法在搜索过程中只需要执行或者撤销走法。
没有任何条件限制的深度优先搜索将会在搜索树中盲目地搜索，我们可以预见到它将会搜索巨量的节点，而不是有目标地尝试找到一条可行路。更加讽刺的是，使用固定的搜索深度限制在巨型搜索树中显得微不足道，无法在所限制的深度中找到解。
我们存储棋面状态，避免重复访问同一状态。为了改进算法的性能，我们假设存在一个高效函数，能够为每个棋面状态生成一个唯一键值，也就是说，如果两个棋面状态有着相同的键值，那么这两个棋面状态是等价的。等价的意思也包括其他的相等情况，比如对称。例如棋面状态：
旋转90°得到如下棋面状态：
这两个棋面状态可以认为是等价的。
相比广度优先搜索，深度优先搜索在开放集中存储更少的信息，因此需要的空间更少。