一个看起来像是博弈的问题能够使用本章的算法来解吗？我们现在将要描述一下能够使用本章所述算法的问题的关键思想。
表示状态
显然地，我们需要能够从当前位置中获取这个位置的所有状态信息。例如，在国际象棋中，王车移位的条件是（a）王与车从来没有动过，（b）自己的王与车之间没有棋子，以及王车之间的格子没有被对方的棋子威胁，（c）王没有被对方将军。注意（b）和（c）能够直接从当前棋面状态中推导出来，因此不需要存储，但是，我们需要存储王和车哪个已经移动过。
搜索树中的每个节点都是存储的相关局面状态信息。如果一个游戏能够产生一个指数级规模的博弈树，那么状态必须紧凑地存储。如果局面状态存在对称，例如四子棋、黑白棋或者十五数码游戏，那么搜索树的规模将会大幅减少，因为可以检测并且删除掉可以通过其他状态旋转或者翻转得到的状态。在国际象棋，跳棋或者黑白棋中，我们使用了一种叫做位棋盘的复杂表示方法来管理大量的状态，这样做的好处是性能能够得到令人印象深刻的改进。
计算可行走法
在每个局面状态，必须要计算出一些可行走法。术语分支因子是指在任何局面下可行走法的总数。例如一字棋，在画标记之后，分支因子将会小于9（初始状态的分支因子）。3×3的魔方初始状态分支因子（平均）是13.5（Korf，1985），而四子棋大多数情况下分支因子为7。国际跳棋（不同于我们经常见到的那种）则复杂得多，因为玩家下棋需要遵守的规则比较复杂。分析过大量跳棋数据库之后，吃子位置的分支因子大概是1.20，而非吃子位置的分支因子是7.94，Schaeffer计算出整个比赛中，平均的分支因子为6.14（Schaeffer，2008）。而围棋的初始分支因子超过360（Berlekamp和Wolfe,1997）。
许多算法对于走法的顺序是非常敏感的。事实上，如果某个游戏的分支因子非常高，而且走法由于某些原因没有被正确地排序，那么盲目地搜索博弈树是得不到解的。
使用启发式信息
如果盲目搜索的算法不可能利用局面状态的信息，它仅仅是根据固定的策略。深度优先盲目搜索简单地迭代所有可行的走法，直到找到一个解法。而广度优先盲目搜索将会尝试完k步是否能够得到可行解之后再去尝试k+1步是否能够得到。
我们可以通过如下几种方法来得到智能搜索（Barr和Feigenbaum，1981）。
根据棋面状态选择如何扩展而不是使用固定的策略
并不一直使用深度优先或者广度优先结构，算法将根据当前需要在这两种策略中灵活转换。
选择适当数目的可行走法，以及走的顺序
当考虑当前棋面状态下可行走法时，玩家必须评估一下这些走法，哪些走法看起来能够赢得比赛，而哪些看起来不会。另外，玩家可能会抛弃那些看起来不会赢得比赛的走法。
选择棋面状态，剪枝搜索树
在搜索过程中，可能会获得新的知识，利用这些新知识，我们可以从选择列表中删除不必要的棋面状态。
最通用的方法是定义一个静态的评价函数，在计算的过程中评价局面状态，排序可行走法。评价函数对寻路算法的性能影响非常大。事实上，使用了坏的评估函数的寻路算法将不可能在每一步选择到最优走法。有句谚语说得好：“错误的输入必然导致错误的输出。”
我们不会限制评价当前局面状态，一个评价函数能够短暂地扩展博弈树，插入一些走法，然后从中选择看起来能够为玩家带来更多好处的走法。但是现实往往不尽如人意，因为（a）这些操作的开销，以及（b）通用的选择逻辑。在A*搜索的讨论中，我们将会给出一个搜索八数码的样例，这个样例使用了不同的评价函数，我想你将会非常高兴地看到设计高效函数是一门含蓄的艺术。
静态函数必须考虑到当前所出位置的各种特征，返回一个整数得分，这个得分反映了玩家对当前位置的一个看法。例如，第一个成功的国际跳棋程序是由Arthur Samuel（1959）开发的，它评价每个棋盘位置，考虑游戏的多达24个特征，例如“棋子优势特性”（比较玩家和其对手的棋子数目）以及“获胜交换特性”（在胜利时交换棋子而不是在将要失败时）。很明显，如果评价函数能够做得足够好，那么一个下棋引擎可以看做是一名优秀的玩家。
最大扩展深度
由于内存资源的限制，一些搜索算法在扩展搜索树和博弈树时会选择扩展到一定程度为止。这个方法有自己的局限性，例如一个玩家需要走很多步来布一个局。例如，在国际象棋中，经常会出现丢卒保车这样的现象，为了获得更多的利益而牺牲掉某些棋子，如果恰好在最大扩展深度的边界处牺牲掉某些棋子，那么我们做出的牺牲将不会得到任何回报。使用固定的扩展深度，程序不会搜索某条水平线以下的状态，这样就对成功搜索造成了不利的影响。