飞机对战游戏的策略问题.doc

PAGE PAGE 12 飞机对战游戏的策略问题 摘要 本文研究怎样构造策略使得在人机对战中计算机在比赛采用19局10胜制情况下最容易取得胜利。 模型一：针对问题一，使问题简单化（考虑飞机头朝上的情况），利用概率和折半查找法确定第一次攻击坐标，考虑飞机头朝向的四个方向，依据飞机头在不同方向坐标之间的函数关系即对称性，飞机头朝上时策略中使用的坐标可以转化为飞机头朝下，左，右时策略中要使用的坐标，每个方向的策略相同，这样计算机最多要16次击中机头。 模型二：改进模型一，采用概率模型、折半查找法、动态决策法对模型进行优化求解使击中机头的次数更优化。 模型三：针对问题二，建立概率模型，利用折半查找法、动态决策法对由7×7的方格变换成11×11的方格且有两架飞机的情况进行决策，最后给出计算机取得胜利的游戏策略。 关键字：飞机对战游戏 概率 折半查找 动态决策 1、问题重述 有一种双方对战游戏，在游戏前双方各准备一张坐标纸，在上面分别制作7×7的方格，在自己的方格中画一架飞机，飞机呈“士”字形，其中上面的一长横占5个格子，下面的短横占3个格子，一竖占4个格子，最上面突出的一个格子代表机头。所画飞机的位置以及机头的指向由游戏者自己决定，游戏结束前双方不能互看对方的坐标纸。游戏时双方交替用“炮弹”打击对方，攻击的一方报告“炮弹”打击的位置，被攻击的一方报告是否命中飞机。如果某一方被命中机头，游戏结束，被命中机头的一方失败。游戏双方都在通过打击后对方的反馈信息来猜测对方飞机的位置。 游戏比赛采用19局10胜制。 问题一：设计一个人机对战的“飞机对战”游戏。要求先由计算机进行攻击，以取胜为目标，给出进行游戏的策略。 问题二：考虑在11×11坐标纸上画两架飞机的游戏方式，两架飞机所占的格子不能重合，游戏方法同上。其中一架飞机被命中机头时要报告有一架飞机被击落。当某方的两架飞机都被击落时游戏结束，被击落方失败。分析这种游戏方式与只画一架飞机的游戏方式在策略上的不同点。 2、问题分析 问题一：我们的分析建立在概率模型的基础上，将7×7的方格转化成对应坐标系里的点。由于飞机形式固定，因此，将对飞机的研究转化成对机头的研究。由对称性，再将问题转化成机头向上的情况。综上所述，我们将飞机对战游戏转化为通过概率，寻找单一方向上的机头所在点的坐标的问题。 问题二：建立在问题一的数学模型的基础上，将7×7方格扩大到11×11方格，用类似的方法，先查找出第一个机头的位置。由于第二个机头的位置在第一个机头位置确定的前提下，可以确定具体范围。再用类似的办法，结合此前过程中的反馈信息，继续查找。直至查找到第二架飞机的机头。即可取得游戏的胜利。 3、模型假设及符号说明 3.1模型假设 根据问题建立如下合理假设： 1、计算机以取胜为目标，尽可能取得游戏的胜利。 2、人机摆设飞机的位置都是随机的。 3、人和计算机在游戏中是公平的，都不知道对方飞机头的位置坐标。 4、多局比赛中计算机安排飞机不会因为前次游戏进行情况而影响下一次飞机的摆放方式。 5、计算机安排飞机在所有可能出现的位置的概率相等。 6、模型中,考虑到以计算机取胜为目标，则仅给出计算机的攻击策略，不考虑计算机被攻击的情况。 3.2符号术语说明 M：击中时可判断出机身可能出现位置的情况数量 N：击中时可判断出机身不可能出现位置的情况数量 L：飞机头出现情况 飞机头朝上是指飞机头朝Y轴正方向 飞机头朝下是指飞机头朝Y轴负方向 飞机头朝右是指飞机头朝X轴正方向 飞机头朝左是指飞机头朝X轴负方向 4、问题一模型的建立和求解 4.1模型一 一、由于飞机形状是固定的，飞机的移动的范围是有限的，我们可以初步判断出飞机头及机身可能出现的位置。 二、当飞机头坐标确定时,能确定整个飞机上所有其他点的坐标。 例如当飞机头朝上，飞机头的坐标为(x,y)时，机身上其他所有点的坐标为 (x-2,y-1),(x-1,y-1),(x,y-1),(x+1,y-1),(x+2,y-1),(x,y-2),(x-1,y-3), (x,y-3)，（x+1，y-3）。 三、由于飞机和飞机的活动空间具有对称性，飞机头朝上、朝下、朝左、朝右的情况之间具有一定函数关系。当飞机头朝上时，飞机头的坐标为（x,y），则类似于此的情况， 当飞机头朝下时，该飞机头的坐标为（x,8-y） 当飞机头朝左时，该飞机头的坐标为（8-y,8-x） 当飞机头朝右时，该飞机头的坐标为（y,x） 四、以飞机头朝上为例，机头的位置共有12种情况（如图4.11）。 当飞机头在（3，7）时，为情况1 当飞机头在（4，7）时，为情况2 当飞机头在（5，7）时，为情况3 当飞机头在（3，6）时，为情况4 当飞机头在