自然演绎推理常用的规则:自然演绎推理是从一组已知的事实出发，直接运用命题逻辑或谓词逻辑中的推理模式推导出结论的过程，其中推理模式被称为推理规则。最基本的规则是三段论推理，包括假言推理、拒取式推理。假言推理的一般形式：拒取式推理的一般形式：

蒙特卡洛树搜索算法概念：我们经常会听到“蒙特卡洛树搜索”这个概念，事实上，蒙特卡洛树搜索是在完美信息博弈场景中进行决策的一种通用技术，除游戏之外，它还在很多现实世界的应用中有着广阔前景。蒙特卡洛树搜索（MonteCarloTreeSearch）并不是一种"模拟人"的算法。而是通过随机的对游戏进行推演来逐渐建立一棵不对称的搜索树的过程。可以看成是某种意义上的强化学习，当然这一点学界还有一些争议。蒙特卡洛树搜索可以分为哪四个过程蒙特卡洛树搜索大概可以被分成四步。选择（Selection），拓展（Expansion），模拟（Simulation），反向传播（Backpropagation）。在开始阶段，搜索树只有一个节点，也就是我们需要决策的局面。搜索树中的每一个节点包含了三个基本信息：代表的局面，被访问的次数，累计评分。1.选择（Selection）在选择阶段，需要从根节点，也就是要做决策的局面R出发向下选择出一个最急迫需要被拓展的节点N，局面R是是每一次迭代中第一个被检查的节点；对于被检查的局面而言，他可能有三种可能：1)该节点所有可行动作都已经被拓展过。2)该节点有可行动作还未被拓展过。3)这个节点游戏已经结束了。对于这三种可能：1)如果所有可行动作都已经被拓展过了，那么我们将使用UCB公式计算该节点所有子节点的UCB值，并找到一个值最大的子节点继续检查。反复向下迭代。2)如果被检查的局面依然存在没有被拓展的子节点(例如说某节点有20个可行动作，但是在搜索树中才创建了19个子节点)，那么我们认为这个节点就是本次迭代的目标节点N，并找出N还未被拓展的动作A。执行步骤23)如果被检查到的节点是一个游戏已经结束的节点。那么从该节点直接执行步骤4。每一个被检查的节点的被访问次数在这个阶段都会自增。在反复的迭代之后，我们将在搜索树的底端找到一个节点，来继续后面的步骤。2.拓展（Expansion）在选择阶段结束时候，我们查找到了一个最迫切被拓展的节点N，以及他一个尚未拓展的动作A。在搜索树中创建一个新的节点〖N〗_(n)作为N的一个新子节点。〖N〗_(n)的局面就是节点N在执行了动作A之后的局面。3.模拟（Simulation）为了让〖N〗_(n)得到一个初始的评分。我们从〖N〗_(n)开始，让游戏随机进行，直到得到一个游戏结局，这个结局将作为〖N〗_(n)的初始评分。一般使用胜利或者失败作为评分，只有1或者0。4.反向传播（Backpropagation）在〖N〗_(n)的模拟结束之后，它的父节点N以及从根节点到N的路径上的所有节点都会根据本次模拟的结果来添加自己的累计评分。如果在步骤1的选择中直接发现了一个游戏结局的话，根据该结局来更新评分。每一次迭代都会拓展搜索树，随着迭代次数的增加，搜索树的规模也不断增加。当到了一定的迭代次数或者时间之后结束，选择根节点下最好的子节点作为本次决策的结果。

a-b剪枝技术是什么：a-b剪枝算法是一个搜索算法旨在减少在其搜索树中，被极大极小算法评估的节点数。这是一个常用人机游戏对抗的搜索算法。它的基本思想是根据上一层已经得到的当前最优结果，决定目前的搜索是否要继续下去。a-b剪枝算法是对Minimax方法的优化，它们产生的结果是完全相同的，只不过运行效率不一样。这种方法的前提假设与Minimax也是一样的：1）双方都按自己认为的最佳着法行棋。2）对给定的盘面用一个分值来评估，这个评估值永远是从一方（搜索程序）来评价的，红方有利时给一个正数，黑方有利时给一个负数。（如果红方有利时返回正数，当轮到黑方走棋时，评估值又转换到黑方的观点，如果认为黑方有利，也返回正数，这种评估方法都不适合于常规的算法描述）。3）从我们的搜索程序（通常把它称为Max）看来，分值大的数表示对己方有利，而对于对方Min来说，它会选择分值小的着法。a-b剪枝技术只能用递归来实现。这个思想是在搜索中传递两个值，第一个值是a，即搜索到的最好值，任何比它更小的值就没用了，因为策略就是知道a的值，任何小于或等于a的值的合理着法都不会对整个局面的获胜率有更高的提高。第二个值是b，即对于对手来说最坏的值。这是对手所能承受的最坏的结果，因为我们知道在对手看来，他总是会找到一个对策不比b更坏的。如果搜索过程中返回b或比b更好的值，那就够好的了，走棋的一方就没有机会使用这种策略。在搜索着法时，每个搜索过的着法都返回跟a和b有关的值，它们之间的关系非常重要，或许意味着搜索可以停止并返回。如果某个着法的结果小于或等于a，那么它就是很差的着法，因此可以抛弃。因为我前面说过，在这个策略中，局面对走棋的一方来说是以a为评价的。如果某个着法的结果大于或等于b，那么整个节点就作废了，因为对手不希望走到这个局面，而它有别的着法可以避免到达这个局面。因此如果我们找到的评价大于或等于b，就证明了这个结点是不会发生的，因此剩下的合理着法没有必要再搜索。如果某个着法的结果大于a但小于b，那么这个着法就是走棋一方可以考虑走的，除非以后有所变化。因此a会不断增加以反映新的情况。有时候可能一个合理着法也不超过a，这在实战中是经常发生的，此时这种局面是不予考虑的，为了避免这样的局面，我们必须在博弈树的上一个层局面中选择另外一个着法。下图中第四层的4的b值为4比其父节点的a值5要小，所以将其剩余的枝剪去。

极小极大分析法的原理：Max局面：假设这个局面轮到己方走，有多种决策可以选择，其中每种决策都会形成一种子局面（Sub-State）。由于决策权在我们手中，当然是选择估价函数值f最大的子局面，因此该局面的估价函数值等于其子局面f的最大值，把这样的局面称为Max局面。Min局面：假设这个局面轮到对方走，它也有多种决策可以选择，其中每种决策都形成一种子局面（Sub-State）。但由于决策权在对方手中，在最坏的情况下，对方当然是选择估价函数值f最小的子局面，因此该局面的估价函数值等于其子局面f值的最小值，把这样的局面称为Min局面。终结局面：胜负已分（假设没有和局）假如有如上图的博弈树，设先手为A，后手为B；则A为Max局面，B为Min局面。上图中A一开始有2种走法（〖W〗_(2)和〖W〗_(3)，W表示节点记号），它走〖W〗_(2)还是〖W〗_(3)取决于〖W〗_(2)和〖W〗_(3)的估价函数值f(W_x)，因为A是Max局面，所以它会取f(W_2)和f(W_3)中大的那个。而f(x)怎么求呢？一般是以递归的方式对博弈树进行搜索，我们通常可以设定叶子结点局面的估价值。如上图的搜索过程为〖W〗_(1)〖W〗_(2)〖W〗_(4)，然后回溯到〖W〗_(1)〖W〗_(2)得到f(W_2)=3，接着〖W〗_(1)〖W〗_(2)〖W〗_(5)得到f^′(W_2)=1，因为〖W〗_(2)在第二层为Min局面，所以它会选择得到的结果中小的那个，即f^′(W_2)替代f(W_2)，即f(W_2)=1。随后搜索〖W〗_(1)〖W〗_(2)〖W〗_(6)得到f^′(W_2)=6>f(W_2)可直接忽略。因此如果A往〖W〗_(2)走的话将会得到一个估价值为f(W_2)=1的局面；如果往〖W〗_(3)走的话将会得到一个估价值为f(W_3)=-3的局面。而因为A是Max局面会选择估价值大的走法，而f(W_2)=1>f(W_3)=-3，因此它下一步走〖W〗_(2)。但是，实际问题中的所有局面所产生的博弈树一般都是非常庞大，非常庞大的多叉树，并不能依靠暴力搜索来寻找最佳解法。因此需要用到一些剪枝手段，常用的比较初级的有a-b剪枝技术。

博弈的定义：博弈本意是：下棋。引申义是：在一定条件下，遵守一定的规则，一个或几个拥有绝对理性思维的人或团队，从各自允许选择的行为或策略进行选择并加以实施，并从中各自取得相应结果或收益的过程。有时候也用作动词，特指对选择的行为或策略加以实施的过程。一个完整的博弈应当包括五个方面的内容：1.博弈的参加者，即博弈过程中独立决策、独立承担后果的个人和组织。2.博弈信息，即博弈者所掌握的对选择策略有帮助的情报资料。3.博弈方可选择的全部行为或策略的集合。4.博弈的次序，即博弈参加者做出策略选择的先后。5.博弈方的收益，即各博弈方做出决策选择后的所得和所失。博弈树是一种与/或树的一种，为了方便博弈树的研究，我们使用一种简单的博弈作为研究的对象。具体的说这样的博弈具有如下的特点：（1）对垒的A，B双方轮流采取行动(这就比同时采取行动在分析上方便的许多)，博弈的结果只有三种情况：A方胜，B方败；A方败，B方胜；双方战成平局。（2）在对垒过程中，任何一方都了解当前的格局及过去的历史。（3）任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自己最为有利而对对方最为不利的对策,不存在“碰运气”的偶然因素。即双方都是十分理智地决定自己的行动。在博弈过程中，任何一方都希望自己取得胜利。因此,在某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时，如果我们站在A方的立场上，则可供A方选择的若干行动方案之间是“或”关系，因为主动权操在A方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由A方决定。但是，若B方也有若干个可供选择的行动方案，则对A方来说这些行动方案之间是“与”关系，因为这时主动权操在B方手里，这些可供选择的行动方案中地任何一个都可能被B方选中，A方必须考虑到对自己最不利的情况发生。若把上述博弈过程用图表示出来，得到的是一棵“与/或”树。这里要特别指出，该“与/或”树是始终站在某一方（例如A方）的立场上得出的，决不可一会儿站在这一方的立场上,一会儿又站在另一方的立场上。

有序搜索的原理特点：有序搜索（OrderedSearch）又称之为最佳优先搜索（BestFirstSearch），是一种启发式搜索算法，我们也可以将它看作广度优先搜索算法的一种改进；最佳优先搜索算法在广度优先搜索的基础上，用启发估价函数对将要被遍历到的点进行估价，然后选择代价小的进行遍历，直到找到目标节点或者遍历完所有的点，算法结束。要实现最佳优先搜索我们必须使用一个优先队列（PriorityQueue）来实现，通常采用一个open优先队列和一个closed集open优先队列用来储存还没有遍历将要遍历的节点，而closed集用来储存已经被遍历过的节点。我们用下面图作为一个示例图来描述最佳优先搜索过程。有序搜索的例子：最佳优先搜索的过程如下图所示，可以被描述为：搜索出的路径为：A-H-G-D-E，整条路径的代价和为16。（1）将根节点放入优先队列open中。（2）从优先队列中取出优先级最高的节点X。（3）根据节点X生成子节点Y：X的子节点Y不在open队列或者closed中，由估价函数计算出估价值，放入open队列中。X的子节点Y在open队列中，且估价值优于open队列中的子节点Y，将open队列中的子节点Y的估价值替换成新的估价值并按优先值排序。X的子节点Y在closed集中，且估价值优于closed集中的子节点Y，将closed集中的子节点Y移除，并将子节点Y加入open优先队列。（4）将节点X放入closed集中。（5）重复过程2,3,4直到目标节点找到，或者open为空，程序结束。

启发式搜索策略特点：启发式搜索(HeuristicallySearch)又称为有信息搜索(InformedSearch)，它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。如果能够利用搜索过程所得到的问题自身的一些特征信息来指导搜索过程，则可以缩小搜索范围，提高搜索效率。像这样利用问题自身特征信息来引导搜索过程的方法成为启发式方法。启发式策略可以通过指导搜索向最有希望的方向前进，降低了复杂性。通过删除某些状态及其延伸，启发式算法可以消除组合爆炸，并得到令人能接受的解(通常并不一定是最优解)。然而，启发式策略是极易出错的。在解决问题的过程中启发仅仅是下一步将要采取措施的一个猜想，常常根据经验和直觉来判断。由于启发式搜索只有有限的信息(比如当前状态的描述)，要想预测进一步搜索过程中状态空间的具体行为则很难。一个启发式搜索可能得到一个次优解，也可能一无所获。这是启发式搜索固有的局限性。这种局限性不可能由所谓更好的启发式策略或更有效的搜索算法来消除。一般说来，启发信息越强，扩展的无用节点就越少。引入强的启发信息，有可能大大降低搜索工作量，但不能保证找到最小耗散值的解路径(最佳路径)。因此，在实际应用中，最好能引入降低搜索工作量的启发信息而不牺牲找到最佳路径的保证。启发式搜索策略特点以及例子：以下为一个启发式搜索的八数码游戏例子：如下图所示，在一个九宫格里面放入8个数字，数字只能上下左右移动，并且只能移动到空白处。通过若干次这样的移动后，把左图数字位置移动成右图数字位置。解决此问题的启发策略：每次移动的时候，正确位置数码的个数要大于交换前正确位置数码个数。正确位置数码的个数是指每个数码的位置与最终格局的对比，如果位置相同，则说明此数码在正确位置。图3-8中红色字体标识的数码为正确位置数码，由此我们可以发现下图中左边初始图案正确位置的数码个数为4个。由下图所示可得，正确位置数码个数大于等于4的只有左下方的格局，那么下一步选择的就是左下方的格局。再次调用次算法如下图所示：这样一步一步地进行，最终即可得到最终格局。

深度优先搜索算法特点：深度优先搜索（DepthFirstSearch，DFS）属于图算法的一种。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。深度优先搜索所使用的策略就如其名字一样，只要可能，就在图中尽量的深入。深度优先搜素总是对最近才发现的结点V的出发边进行探索，直到该结点的所有出发边都被发现为止。一旦结点V的所有出发边都被发现，搜索则回溯到V的前驱结点（V是经过该点才被发现的），来探索该前驱结点的出发边。该过程一直持续到从源结点可以到达的所有结点都被发现为止。如果还存在尚未发现的结点，则深度优先搜索将从这些未被发现的结点中任选一个作为新的源节点，并重复同样的搜索过程。深度优先搜索遍历图：深度优先遍历图的基本思路是，从图中某顶点V出发：（1）访问顶点V。（2）依次从V的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问。（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。下面采用一个示例图来说明这个过程。如图3-6所示，示例图是一个无向图，如果我们从A点发起深度优先搜索（以下的访问次序并不是唯一的，第二个点既可以是B也可以是C，D），则我们可能得到如下的一个访问过程：ABE（没有路了！回溯到A)CFHGD（没有路，最终回溯到A，A也没有未访问的相邻节点，本次搜索结束）。

宽度优先搜索定义概念：宽度优先搜索（BreadthFirstSearch，BFS）又称广度优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。宽度优先搜索的特点：宽度优先搜索属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。所谓广度，就是一层一层的，向下遍历，层层堵截，如对下图3-4进行一次宽度优先遍历的话，我们的结果是：v_1→v_2→v_3→v_4→v_5→v_6→v_7→v_81、访问顶点v_i2、访问v_i的所有未被访问的邻接点v_1,v_2......v_k。3、依次从这些邻接点（在步骤2中访问的顶点）出发，访问它们的所有未被访问的邻接点，依此类推，直到图中所有访问过的顶点的邻接点都被访问。我们采用另一个示例图来说明这个过程，假设我们需要用宽度搜索的方法找到一条从v_0到v_6的最短的路径（一个节点算一步）。1、在搜索的过程中，初始所有节点是白色（代表了所有点都还没开始搜索），如图3-5(a)所示2、把起点v_0标志成灰色（表示即将探索v_0），如图3-5(b)所示3、下一步搜索的时候，我们把所有的灰色节点访问一次，然后将其变成黑色（表示已经被探索过了）。进而再将它们所能到达的节点标志成灰色（因为那些节点是下一步探索的目标点了），但是这里有个判断，当访问到v_1节点的时候，它的下一个节点应该是v_0和v_4，但是v_0已经在前面被染成黑色了，所以不会将它染灰色（即不会回头去探索它），如图3-5(c)所示4、循环执行步骤3，直到目标节点v_6被染灰色，说明了下一步就到终点了，没必要再搜索（染色）其他节点了，此时可以结束搜索了，整个搜索就结束了，如图3-5(d)所示。然后根据搜索过程，反过来把最短路径找出来，图中把最终路径上的节点标志成绿色，如图3-5(e)所示。

盲目搜索定义：盲目搜索（BlindSearch）又叫非启发式搜索（UninformedSearch），它只会按预定的搜索策略进行搜索，而不会考虑问题本身的特性而做变通，它唯一能区分的就是，下一个状态是目标状态（即问题的解）还是非目标状态。盲目搜索的方法有哪些：因此，盲目搜索一般只适用于求解比较简单的问题。我们将学习的宽度优先搜索和深度优先搜索，属于盲目搜索方法。