上海公司网站建设电话,大连网站建设方案咨询,东莞服务好的营销型网站建设,织梦小说网站模板第二章 计算机是如何学会下棋的
人类棋手在下棋时#xff0c;会根据自己的经验只考虑在当前棋局下最重要的几个可能的走法#xff0c;但是计算机没有这种经验。
知识太复杂了#xff0c;需要考虑很多具体的情况#xff0c;一旦知识总结的不到位#xff0c;可能就会出现大…第二章 计算机是如何学会下棋的
人类棋手在下棋时会根据自己的经验只考虑在当前棋局下最重要的几个可能的走法但是计算机没有这种经验。
知识太复杂了需要考虑很多具体的情况一旦知识总结的不到位可能就会出现大的差错总结知识让计算机使用应该是走不通的。
三、 α \alpha α- β \beta β 剪枝算法
1. 极小-极大模型存在的问题 2. 人如何处理这个问题呢 3. α \alpha α- β \beta β 剪枝算法
假设并不是一开始就将整个搜索图生成出来而是按照一定的原则一点一点地产生。比如下图是一个搜索图我们假设一开始并没有这个图而是按照从上到下从左到右的优先顺序来生成这个图。我们先从最上边一个节点开始按顺序产生 a、c、g、r 四个节点假设就考虑 4 步棋这时就不再向下生成节点了。由于 r 的分值为 0而 g 是极小节点所以我们知道 g 的分值应该 ≤0。接下来再生成 s 节点由于 s 的分值为 5g 是极小节点且没有其他子节点了所以 g 的分值等于 0。由于 c 是极大节点根据 g 的分值为 0我们有 c 的分值 ≥0。再看 c 的其他后辈节点情况生成 h 和 t 两个节点由于 t 的分值为-3而 h 是极小节点所以有 h 的分值 ≤-3。 c 的分值 ≥0而 h 的分值 ≤-3这时 u 的分值是多少都无关紧要了。图中 u 的分值如果大于 h 的当前分值-3则不影响 h 的分值即便 u 的分值小于-3比如-5虽然改变了 h 的分值为 ≤-5但是由于 c 是极大节点c 的当前分值已经至少为 0 了所以 h 的分值变小也不会改变 c 的分值。这样的话遇到图中这种 h 的当前分值小于 c 的当前分值这种情况时由于 u 的分值是多少都不会影响 c 的分值了所以就没有必要生成 u 这个节点了。这种情况我们称之为剪枝其剪枝条件是如果一个后辈的极小节点如图中的 h其当前的分值小于等于其祖先极大节点的分值时如图中的 c则该后辈节点的其余子节点如图中的 u就没有必要生成了可以被剪掉。注意这里用的是后辈节点和祖先节点这是一种推广因为这种剪枝并不局限于父节点和子节点的关系。在确认了 c 的分值为 0 之后同样的理由我们可以确认 a 的分值 ≤0。生成 a 的后辈节点 d、i、v由于 v 的分值为 3且 d 向下就一条路所以有 d 的分值 ≥3。由于 a 的分值最大为 0而 d 的分值最小为 3所以大的红圈圈起来的那些分支的分值是多少又没有意义了a 取 c 和 d 中分值最小的最终 a 取值为 0大红圈圈起来的部分都没有必要生成了又可以被剪掉。这里我们又发现了另外一个剪枝条件如果一个后辈的极大节点的分值如图中节点 d大于等于其祖先极小节点的分值时如图中节点 a则该后辈节点还没有被生成的节点可以被剪掉如图中大红圈圈起来的那些节点。a 的分值被确定为 0 之后就可以确定 R 的分值 ≥0继续向下生成节点 b、e、n、E由于 E 的分值为 0所以有 n 的分值 ≤0。n 是极小节点其极大节点祖先有 e 和 Re 这时还没有值但是 R 的分值 ≥0所以满足后辈极小节点的分值小于等于其祖先极大节点分值的剪枝条件n 的两个子节点 F 和 G 都没有生成的必要又可以被剪掉了。n 的分值被确定为 0从而有 e 的分值 ≥0。接着生成节点 o 和 H由于 H 的分值为 1有 o 的分值 ≤1不满足剪枝条件生成节点 II 的分值为 2o 是极小节点所以 o 的分值确定为 1。e 是极大节点从 n 和 o 的分值中选取最大的从而更新 e 的取值由原来的 0 修改为 1。e 的分值确定为 1 后有 b 的分值 ≤1。继续生成 b 的后辈节点 f、P、JJ 的分值为 6得到 P 的分值 ≤6不满足剪枝条件继续生成子节点 K得到 K 的分值为 8P 是极小节点选取子节点中最小的值 6从而确定 f 的分值 ≥6。后辈极大节点 f 的分值 6 大于等于其前辈极小节点 b 的分值 1满足剪枝条件q、M、N 三个节点被剪枝从而确定 b 的分值为 1。R 的分值取 a、b 中最大者从而用从节点 b 得到的 1 代替原来从 a 得到的 0。搜索过程到此结束按照刚才的搜索结果甲方应该选择 b 作为行棋的最佳走步如图中的红色箭头所示。这种方法就是 α-β 剪枝算法可以利用已有的搜索结果剪掉一些不必要的分枝有效提高了搜索效率。 深蓝就是用了 α-β 剪枝算法从而可以在规定的时间内完成一次行棋过程。这种 α-β 剪枝算法得到的最佳走步跟极小-极大模型得到的结果是一样的。α-β 剪枝只是剪掉了那些不改变结果的分枝所以不影响最终选择的走步。那些分值是如何得到的何处发生剪枝完全取决于那些分值如果分值不准确则得到的结果也就值得怀疑了。
4. 如何估值 这些分值是非常重要的。据深蓝的研发者介绍说他们聘请了好几位国际象棋大师帮助他们整理知识用于估算分值。但是基本思想并不复杂大概就是根据甲乙双方剩余棋子进行加权求和比如一个皇后算 10 分一个车算 7 分一个马算 4 分等。然后还要考虑棋子是否具有保护比如两个相互保护的马分数会更高一些其他棋子也是大体如此。然后再考虑各种残局等按照残局的结果进行估分。当然这里给出的各个棋子的分数只是大概而已。最后甲方得分减去乙方得分就是该棋局的分值。这个估值虽然看起来有些粗糙但是由于在剪枝过程中探索的比较深对于象棋来说无论是国际象棋还是中国象棋在探索的比较深的情况下凭借棋子的多少基本就可以评判局面的优劣了所以可以得到比较准确的估值。所以对于计算机下棋来说探索的越深其棋力也就越强在可能的情况下应该尽可能探索的更深一些。
5. α \alpha α- β \beta β 剪枝效果如何 6. 几点注意 α-β 剪枝的关键点 在判断是否剪枝时都是后辈极小节点与祖先极大节点进行比较、后辈极大节点与祖先极小节点做比较。当后辈极小节点的值小于等于祖先极大节点的值时发生剪枝当后辈极大节点的值大于等于前辈极小节点的值时发生剪枝。 在判断是否剪枝时一定要注意不只是与父节点做比较还要考虑祖先节点。 在完成一次 α-β 剪枝后只是选择了一次行棋下一次应该走什么棋应该在对方走完一步棋后根据棋局变化进行 α-β 剪枝过程再次根据搜索结果确定走什么棋。
7. 总结 对于真实的棋类游戏由于其状态数过于庞大不可能通过穷举所有状态的方法获得最佳走步。受人类下棋时思考过程的启发提出了计算机下棋的极小-极大模型。该模型只在有限步内搜索获得有限范围内的最佳走步。但同样由于棋类变化太多即便是有限范围的搜索也是非常花费时间的。人类棋手在做极小-极大搜索的时候并不是考虑有限范围内的每一种可能的走法而是根据经验砍掉大量的不合理分枝从而极大地缩小了搜索范围。受此启发提出了 α-β 剪枝算法与人类利用经验砍掉大量不合理分枝不同计算机并没有这种经验而是利用已有的搜索结果砍掉没有必要产生的分枝有效地提高了搜索效率。深蓝就是采用的这种方法。 α-β 剪枝条件 当后辈的极小节点值小于等于其祖先的极大节点值时发生剪枝。 当后辈的极大节点值大于等于其祖先的极小节点值时发生剪枝。 注意比较时不只是与其父节点做比较还要与其祖先节点做比较只要有一个祖先节点满足比较的条件就发生剪枝。 α-β 剪枝算法所得到的最佳走步质量严重依赖于最底层节点估值的准确性搜索的越深估值越准确。这是因为越深的节点其对应的棋局中棋子越少而棋子比较少的情况下其局面的估值也就会比较准确。这与人下棋时的思考也是一致的。 α-β 剪枝算法结束时得到的只是当前棋局下的一步走法相当于我们思考了半天决定了一步棋如何走后面如何进行需要待对方走完一步棋后再次进行 α-β 剪枝搜索获得下一步棋的走法。也就是说每行棋一次都需要进行一次 α-β 剪枝搜索。
