计算机博弈软件开发简介——亚马逊棋实现

计算机博弈软件开发简介——亚马逊棋实现内容摘要：

继续搜索同一层的下一个节点时，必须要恢复棋盘为原来的棋局状态。 着法生成模块的设计  着法生成是博弈树展开的依据，它是根据当前的棋局和走棋方信息，给出所有可能着法的那一部分程序，也就是用来告诉引擎的其他部分下一步可以怎么走的模块，从而不断扩展博弈树。 不同的棋类有不同的规则，不同的复杂程度，所以要有一个相应的走法产生机制。  在亚马逊棋对弈中，着法生成是一个很关键的问题。 扫描棋盘寻找所有的可行棋位，罗列出所有符合规则的下一步着法。  亚马逊棋着法生成步骤：  (1) 确定走动的棋子的位置；  (2) 根据规则，扫描棋盘，找到全部合理落子位置；  (3) 根据落子位置，扫描棋盘，找到全部合理的设障碍的位置。  定义着法函数：  makemove(Ifrom, Ito, Iput, Lmyturn)  函数包括 4个参数：  int Ifrom //提子位置  int Ito //落子位置  int Iput //放箭位置  bool Lmyturn //是黑方还是白方 搜索算法的研究  选择着法时要充分考虑到对手的存在，考虑己方和对方以后几步棋的可能下法，需要展开博弈树，搜索最佳着法。  在博弈过程中，按照博弈规则和着法状态过程分析，客观评判博弈双方在各自分枝节点上所获得的分数估计值，并以其中任何一方的角度而依次生成具有得分值表示的与或搜索树，称为博弈树。 博弈树是根在上部，然后向下递归产生的一棵包含着所有可能的对弈过程的搜索树，是完全搜索树，包含了下棋者和计算机所有可能的着法和局面。 搜索算法是计算机“思维”的核心。  一般，计算机直接通过棋盘信息判断某个着法的好坏并不精确。 棋类程序中，通常通过使用“搜索”函数来寻找可能着法。 搜索函数获得棋局信息，然后寻找对于计算机来说最好的着法。 判断着法好坏的一个办法就是考察棋局走下去的结果，可以由博弈树向下搜索几步，然后比较发展下去的结果。  双方进行对弈，假设轮到白方走棋，对其任何一种走法，黑方也有若干种与之相对应的走法，对黑方的任何一种走法白方又有若干种与之相对应的走法，如此往复，构造出一棵博弈树，将所有的走法罗列出来。 在博弈树中，节点为局面，树枝为着法，其中根结点为当前时刻的棋局，它的儿子节点是假设再行棋一步之后的各种棋局，孙子节点是从儿子节点的棋局再行棋一步的各种棋局，以此类推。 双方轮流出手，偶数层节点属于白方，奇数层节点属于黑方。 如果叶节点还不能给出胜负的最终局面，则要对叶节点进行评估，以便从有利局面选择当前着法，这便是博弈搜索的职能。 极小值搜索  极大极小值算法是香侬教授在 1950年首先提出来的，极大极小值算法也是当代计算机博弈各种搜索算法的基础。 由于对弈双方都是理智的，都想赢棋，在选择着法的时候都尽量让棋局朝着有利于自己的方面转化，所以在博弈树上，在不同层上就要有不同的选择标准。  极大极小搜索算法的基本思想：  (1) 在偶数层节点的着法即轮到 Max走棋的节点时， Max应考虑最好的情况，选择其全部子节点中评估值最大的一个，即  F(v) = max{F(v1), F(v2), ……, F(v n)}  其中， F ( ) 为节点估值， v1， v2， …… … vn为节点 v的子节点。  (2) 在奇数层节点的着法即轮到 Min走棋的节点时， Max应考虑最坏的情况，选择其全部子节点中评估值最小的一个，即  F(v) = min{F(v1), F(v2), ……, F(v n)}  其中， F ( ) 为节点估值， v1， v2， …… … vn为节点 v的子节点。  (3) 评价往回倒推时，相当于两个局中人的对抗策略，交替使用 (1)、 (2)两种方法传递倒推值。  在进行极大 极小搜索的时候，首先要在有限深度内展开全部叶子节点，并进行评估，然后自下而上地进行搜索计算，一直反推到根结点。 在反推的过程中始终要记住算出该值的子节点是谁，这样就可以得到一个从根结点到叶子节点的一条路径，这就是最佳路径，它是双方表现最佳的对弈着法序列。 如图所示的博弈树， MAX层取下一层的极大值， MIN层取下一层的极小值。 极大极小算法伪代码  int minimax(position p,int depth) {  int bestvalue,value。  if(gameover) // 检查棋局是否结束  return evaluation(p)。 // 棋局结束，返回估值  if depth=0) // 是否是叶子节点  return evaluation(p)。 // 叶子节点，返回估值  if(==RED) // 是否轮到红方走棋  bestvalue=INFINITY。 // 是，令初值最大值为极小  else  bestvalue=INFINITY。 // 否，令初值最小值为极大  for(each possibly move m) { // 对每一可能的走法 m  makemove(m)。 // 产生第 i 个棋面（子节点）  value=minimax(p, depth 1)。 // 递归调用向下搜索子节点  unmakemove(m)。 // 恢复当前棋面  if(==RED)  bestval ue=max(value,bestvalue)。 // 取最大值  else  bestval ue=min(value,bestvalue)。 // 取最小值  }  return bestvalue。 // 返回最大值或最小值  }  极大极小搜索是一种“变性”搜索，在偶数层进行 Max搜索，而在奇数层进行 Min搜索。 如果把极大极小值算法稍做变形，就是负极大值算法。 负极大值算法是 Knuth和Moore在 1975年提出的，是对极大极小算法的优化。  负极大值算法的思想在于：父节点的值是各子节点的值的负数的极大值，如图所示。 在负极大值算法下，无论轮到人或者电脑走棋，选取的都是子节点负数最大的分枝，即  F(v) = max{F(v1), F(v2), ……, F(vn)}  其中， F ( ) 为节点估值， v1， v2， …… … vn为节点 v的子节点。 负极大值搜索算法伪代码  int negamax(position p,int depth) {  int n, value, bestvalue=INFINITY。  if(gameover) // 检查棋局是否结束  return evaluation(p)。 // 棋局结束，返回估值  if depth=0) // 是否叶子节点  return evaluation(p)。 // 叶子节点，返回估值  for(each possibly move m) { // 对每一可能的走法 m  makemove(m)。 // 产生第 i 个局面（子节点）  value=negamax(p, depth 1)。 // 递归调用 minimax 向下搜索子节点  unmakemove(m)。 // 恢复当前局面  if(value = bestvalue)  bestvalue= value。 // 取最小值  }  return bestvalue。 // 返回最大值或最小值  }  宽度优先搜索的基本思想是从初始节点开始，逐层地对节点进行扩展并考查它是否为目标节点。 在第 n层的节点没有全部扩展并考查之前，不对第 1 + n 层的节点进行扩展。 宽度优先搜索是一种盲目搜索，时间和空间复杂度都比较高。  深度优先搜索的基本思想是从初始节点开始扩展，沿着树的最大深度方向进行的。 只有当上次访问的节点不是目标节点且没有其它节点生成的时候才转到上次访问节点的父节点。 深度优先搜索的优点是比宽度优先搜索算法需要较少的空间，该算法只需保存搜索树的一部分，它由当前正在搜索的路径和该路径上还没有完全展开的节点标志所组成。  在复杂度很高的机器博弈搜索中，比较适合选择深度优先搜索方法，可以在搜索过程中的任何时候仅仅生成整棵树的一小部分，搜索过的部分被立即删去。 αβ剪枝算法  在极大极小搜索过程中，遍历了整棵博弈树，每个节点都访问了一次，这样做的缺点是效率低下。 在极大 极小搜索的基础上，以窗口的形式引进αβ 剪枝技术，使得搜索的效率显著提高。  αβ 剪枝把生成的搜索树和估值格局这两个过程结合起来，再根据一定的条件判定，有可能尽早剪掉一些无。