站内seo和站外seo区别,wordpress演示数据,逆思维服装设计公司,北京网站建设z亿玛酷1专注[2018年最新整理]实验二#xff1a;利用α-β搜索过程的博弈树搜索算法编写一字棋游戏实验二#xff1a;利用α-β搜索过程的博弈树搜索算法编写一字棋游戏一、实验目的与要求(1)了解极大极小算法的原理和使用方法#xff0c;并学会用α-β剪枝来提高算法的效率。(2)使用C语…[2018年最新整理]实验二利用α-β搜索过程的博弈树搜索算法编写一字棋游戏实验二利用α-β搜索过程的博弈树搜索算法编写一字棋游戏一、实验目的与要求(1)了解极大极小算法的原理和使用方法并学会用α-β剪枝来提高算法的效率。(2)使用C语言平台编写一个智能井字棋游戏。(3)结合极大极小算法的使用方法和α-β剪枝让机器与人对弈时不但有智能的特征而且计算的效率也比较高。二、实验原理一字棋游戏是一个流传已久的传统游戏。游戏由两个人轮流来下分别用“X”和“O”来代替自身的棋子。棋盘分9个格双方可以在轮到自己下的时候可以用棋子占领其中一个空的格子。如果双方中有一方的棋子可以连成一条直线则这一方判胜对方判负。当所有的格子都被占领但双方都无法使棋子连成一条直线的话则判和棋。这是一个智能型的一字棋游戏机器可以模拟人与用户对弈。当轮到机器来下的时候机器会根据当前棋局的形势利用极大极小算法算出一个评价值判断如何下才对自身最有利同时也是对方来说对不利的然后下在评价值最高的地方。另外利用α-β剪枝使机器在搜索评价值的时候不用扩展不必要的结点从而提高机器计算的效率。在用户界面方法用一个3×3的井字格来显示用户与机器下的结果。当要求用户输入数据的时候会有提示信息。用户在下的过程中可以中途按下“0”退出。当用户与计算机分出了胜负后机器会显示出比赛的结果并按任意键退出。如果用户在下棋的过程中输入的是非法字符机器不会做出反应。三、实验步骤和过程1.α-β搜索过程 在极小极大搜索方法中由于要先生成指定深度以内的所有节点其节点数将随着搜索深度的增加承指数增长。这极大地限制了极小极大搜索方法的使用。能否在搜索深度不变的情况下利用已有的搜索信息减少生成的节点数呢MINIMAX过程是把搜索树的生成和格局估值这两个过程分开来进行即先生成全部搜索树然后再进行端节点静态估值和倒推值计算这显然会导致低效率。如图中其中一个MIN节点要全部生成A、B、C、D四个节点然后还要逐个计算其静态估值最后在求倒推值阶段才赋给这个MIN节点的倒推值∞。其实如果生成节点A后马上进行静态估值得知f(A)∞之后就可以断定再生成其余节点及进行静态计算是多余的可以马上对MIN节点赋倒推值∞而丝毫不会影响MAX的最好优先走步的选择。这是一种极端的情况实际上把生成和倒推估值结合起来进行再根据一定的条件判定有可能尽早修剪掉一些无用的分枝同样可获得类似的效果这就是α-β过程的基本思想。α-β搜索过程一字棋的图一字棋第一阶段α-β剪枝方法为了使生成和估值过程紧密结合采用有界深度优先策略进行搜索这样当生成达到规定深度的节点时就立即计算其静态估值函数而一旦某个非端节点有条件确定其倒推值时就立即计算赋值。从图中标记的节点生成顺序号(也表示节点编号)看出生成并计算完第6个节点后第1个节点倒推值完全确定可立即赋给倒推值1。这时对初始节点来说虽然其他子节点尚未生成但由于s属极大值层可以推断其倒推值不会小于1我们称极大值层的这个下界值为α即可以确定s的α1。这说明s实际的倒推值决不会比1更小还取决于其他后继节点的倒推值因此继续生成搜索树。当第8个节点生成出来并计算得静态估值为1后就可以断定第7个节点的倒推值不可能大于1我们称极小值层的这个上界值为β即可确定节点的β1。有了极小值层的β值很容易发现若α≥β时节点7的其他子节点不必再生成这不影响高一层极大值的选取因s的极大值不可能比这个β值还小再生成无疑是多余的因此可以进行剪枝。这样一来只要在搜索过程记住倒推值的上下界并进行比较就可以实现修剪操作称这种操作为α剪枝。类似的还有β剪枝统称为α-β剪枝技术。在实际修剪过程中α、β还可以随时修正但极大值层的倒推值下界α永不下降实际的倒推值取其后继节点最终确定的倒推值中最大的一个倒推值。而极小值层的倒推值上界β永不上升其倒推值则取后继节点最终确定的倒推值中最小的一个倒推值。在进行α-β剪枝时应注意以下几个问题 (1)比较都是在极小节点和极大节点间进行的极大节点和极大节点的比较或者极小节点和极小节点间的比较是无意义的。 (2)在比较时注意是与先辈层节点比较不只是与父辈节点比较。当然这里的先辈层节点指的是那些已经有了值的节点。 (3)当只有一个节点的固定以后其值才能够向其父节点传递。 (4)α-β剪枝方法搜索得到的最佳走步与极小极大方法得到的结果是一致的α-β剪枝并没有因为提高效率而降低得到最佳走步的可能性。 (5)在实际搜索时并不是先生成指定深度的搜索图再在搜索图上进行剪枝。如果这样就失去了α-β剪枝方法的意义。在实际程序实现时首先规定一个搜索深度然
