飞机对战游戏的策略问题

1飞机对战游戏的策略问题摘要本文研究怎样构造策略使得在人机对战中计算机在比赛采用19局10胜制情况下最容易取得胜利。模型一：针对问题一，使问题简单化（考虑飞机头朝上的情况），利用概率和折半查找法确定第一次攻击坐标，考虑飞机头朝向的四个方向，依据飞机头在不同方向坐标之间的函数关系即对称性，飞机头朝上时策略中使用的坐标可以转化为飞机头朝下，左，右时策略中要使用的坐标，每个方向的策略相同，这样计算机最多要16次击中机头。模型二：改进模型一，采用概率模型、折半查找法、动态决策法对模型进行优化求解使击中机头的次数更优化。模型三：针对问题二，建立概率模型，利用折半查找法、动态决策法对由7×7的方格变换成11×11的方格且有两架飞机的情况进行决策，最后给出计算机取得胜利的游戏策略。关键字：飞机对战游戏概率折半查找动态决策21、问题重述有一种双方对战游戏，在游戏前双方各准备一张坐标纸，在上面分别制作7×7的方格，在自己的方格中画一架飞机，飞机呈“士”字形，其中上面的一长横占5个格子，下面的短横占3个格子，一竖占4个格子，最上面突出的一个格子代表机头。所画飞机的位置以及机头的指向由游戏者自己决定，游戏结束前双方不能互看对方的坐标纸。游戏时双方交替用“炮弹”打击对方，攻击的一方报告“炮弹”打击的位置，被攻击的一方报告是否命中飞机。如果某一方被命中机头，游戏结束，被命中机头的一方失败。游戏双方都在通过打击后对方的反馈信息来猜测对方飞机的位置。游戏比赛采用19局10胜制。问题一：设计一个人机对战的“飞机对战”游戏。要求先由计算机进行攻击，以取胜为目标，给出进行游戏的策略。问题二：考虑在11×11坐标纸上画两架飞机的游戏方式，两架飞机所占的格子不能重合，游戏方法同上。其中一架飞机被命中机头时要报告有一架飞机被击落。当某方的两架飞机都被击落时游戏结束，被击落方失败。分析这种游戏方式与只画一架飞机的游戏方式在策略上的不同点。32、问题分析问题一：我们的分析建立在概率模型的基础上，将7×7的方格转化成对应坐标系里的点。由于飞机形式固定，因此，将对飞机的研究转化成对机头的研究。由对称性，再将问题转化成机头向上的情况。综上所述，我们将飞机对战游戏转化为通过概率，寻找单一方向上的机头所在点的坐标的问题。问题二：建立在问题一的数学模型的基础上，将7×7方格扩大到11×11方格，用类似的方法，先查找出第一个机头的位置。由于第二个机头的位置在第一个机头位置确定的前提下，可以确定具体范围。再用类似的办法，结合此前过程中的反馈信息，继续查找。直至查找到第二架飞机的机头。即可取得游戏的胜利。43、模型假设及符号说明3.1模型假设根据问题建立如下合理假设：1、计算机以取胜为目标，尽可能取得游戏的胜利。2、人机摆设飞机的位置都是随机的。3、人和计算机在游戏中是公平的，都不知道对方飞机头的位置坐标。4、多局比赛中计算机安排飞机不会因为前次游戏进行情况而影响下一次飞机的摆放方式。5、计算机安排飞机在所有可能出现的位置的概率相等。6、模型中,考虑到以计算机取胜为目标，则仅给出计算机的攻击策略，不考虑计算机被攻击的情况。3.2符号术语说明M：击中时可判断出机身可能出现位置的情况数量N：击中时可判断出机身不可能出现位置的情况数量L：飞机头出现情况飞机头朝上是指飞机头朝Y轴正方向飞机头朝下是指飞机头朝Y轴负方向飞机头朝右是指飞机头朝X轴正方向飞机头朝左是指飞机头朝X轴负方向54、问题一模型的建立和求解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当飞机头在（4，6）时，为情况5当飞机头在（5，6）时，为情况6当飞机头在（3，5）时，为情况7当飞机头在（4，5）时，为情况8当飞机头在（5，5）时，为情况9当飞机头在（3，4）时，为情况10当飞机头在（4，4）时，为情况11当飞机头在（5，4）时，为情况1271236456578941011123211234567图4.116五、若以取胜为目的，即用最少的次数击中对方的飞机头。则M和N的值越接近越好。计算出49个坐标点相对应的M和N的值。M，N的值如图4.12所示（M+N=12）：M-N70-120-121-111-111-110-120-1261-112-104-84-84-82-101-1151-112-105-75-75-72-101-1141-113-97-58-47-53-91-1131-113-96-67-56-63-91-1120-121-113-94-83-91-110-1210-121-112-103-92-81-110-121234567图4.12由图4.12可知，在坐标点（3，3）和（5，3）M=N=6时，M、N最为相近。所以第一次应该攻击（3，3）点或（5，3）点。六、假设先攻击（3，3）点。图4.13(3,5)L=47(4,4)L=51112(3,6)L=4(4,6)L=5(5,4)L=12(5,7)L=36(4,5)L=128(5,6)L=6(4,7)L=2(3,7)L=1gameover(3,3)L=123456789101112(3,4)L=457101112(5,5)L=1236897图4.13是飞机头朝上时计算机的策略表示图。可以看出,计算机最多通过4次反馈信息就可以判断出飞机头的坐标。但是,我们不知道飞机头的朝向。所以我们根据此方法，算出在飞机头朝下，朝左，朝右时的对策。依据对称性，在飞机头朝下时，我们根据函数法则：X=X,Y=8-Y,将飞机头朝上时策略中使用的坐标转化为飞机头朝下时策略中要使用的坐标。例如：（2，5）——〉（2，3）（6，2）——〉（6，6）在飞机头朝左时，我们根据函数法则：X=8-Y,Y=8-X,将飞机头朝上时策略中使用的坐标转化为飞机头朝左时策略中要使用的坐标。例如：（3，6）——〉（2，5）（2，5）——〉（3，6）在飞机头朝右时，我们根据函数法则：X=Y,Y=X，将飞机头朝上时策略中使用的坐标转化为飞机头朝右时策略中要使用的坐标。例如：（3，4）——〉（4，3）（2，5）——〉（5，2）所以，重复操作，最多通过16次，就可以击中对方的飞机头，取得胜利。按此方法进行游戏，直到游戏分出该局胜负。然后重复该过程，当有一方胜利数达到10时，结束游戏。4.2模型二一、由于飞机形状是固定的，飞机的移动的范围有限，我们可以初步判断出飞机头及机身可能出现的位置。在7×7的方格中飞机头的指向有上下左右四个方向，在这四个方向中每个方向飞机头有12种不同的位置，所以7×7的方格中飞机的位置共有48种。我们分析飞机机头在7×7的方格上出现的情况如图4.21：0011100001110011232111134311112321100111000011100图4.218二、由次数分布图可得，对于7×7的方格而言，中心的十字形区域是飞机机头出现的概率最大点和次概率最大点，即点(4,4)概率最大；(4,5),(5,4),(3,4),(4,3)为次最大概率点。则对这五个点首要考虑，进行如下步骤：首先攻击概率最大点（4，4）；然后攻击次概率最大点，通过反馈信息分析,进行下面一步。攻击（4,4）点得到反馈：1、击中机头，游戏结束2、击中机身，攻击(4,5),(5,4),(3,4),(4,3)，考虑上下方向的中机情况，反馈如图4.22（√表示击中机头或机身）（3,4）（4,3）（4,5）（5,4）1√2√√√3√4√√5√√6√√√√7√√8√9√√√10√11√√12√√13√√√√14√√图4.22发现四点中一点的情况为4种，考虑左右方向可知8种情况，最大游戏时间是1+4+3=8次。发现四点中三点的情况为2种，考虑左右方向可知4种情况，最大游戏时间是1+4+1=6次。9发现四点均中的情况为2种，考虑左右方向仍为2，最大游戏时间是1+4=5次。发现四点中二点（4,3）（4,5）的情况为2种，考虑左右方向可知4种情况，最大游戏时间是1+4+3=8次。发现四点中二点（3,4）（5,4）的情况为4种，考虑左右方向仍为4，最大游戏时间是1+4+3=8次。3、未击中机身，攻击（3,4）（5,4）（4,3）（4,5），类似上一步骤得到信息反馈，最大游戏时间是1+2+3=6次。4.3模型检验例如飞机头为（6,3）朝右方向:攻击（4,4）未中，攻击次概率最大点得到反馈击中（3,4）（4,3）（5,4）未击中（4,5），考虑左右方向（2,3）（6,3）选择攻击一点则可知。例如飞机头为（3,1）朝下方向：攻击（4,4）机身，攻击次概率最大点得到反馈击中（3,4）未击中（4,3）（5,4）（4,5），考虑上下方向（3,7）（3,1）选择攻击一点则可知。105、问题二模型的建立和求解一、在模型二的基础上增加一架飞机，坐标纸扩大为11×11方格。同第一问可知在11×11方格中飞机机头出现的最大概率点为（6，6），次最大概率点为其上下左右四点。二、类似模型二，逐次攻击概率大的点。若两架飞机为上下方向，设飞机头的坐标分别为（x,y），（m,n），则机身上其他所有点的坐标分别为（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）。（m-2,n+1),(m-1,n+1),(m,n+1),(m+1,n+1),(m+2,n+1),(m,n+2),(m-1,n+3),(m,n+3),(m+1,n+3)。三、先攻击最大概率点和次最大概率点，若中飞机机身，则可找出与之有关的一切飞机机头坐标的集合。若不中，那么以之为机头的周围4架飞机所经过的点都不可能存在，如图5.11：2222221112211111111111111111111111111111111111111111111111111122111222222图5.11然后攻击（3,9）、（9,9）、(3,3)、（9,3）点，依次判断，最后可知飞机机头的具体位置。116、模型的评价与推广6.1模型的评价模型一采用折半查找法寻找飞机头，大大减少了击中对方飞机头所需要的次数，可以使攻击次数降到理论最少，提高了击中对方的可能性。分析比较全面，对待各种可能都能很好的分析。且对于方格数变多照样可以使用这种模型处理。但在这个模型中，开始时没有办法对飞机头的方向进行判断，这样就不得不进行4遍相似的操作，最多需要16次才能击中，容易出现很多攻击相同点重复考虑的情况。模型二是模型一的改进，结合概率模型对问题一进行了综合考虑和动态决策。模型三由7×7的格子变成11×11的格子，飞机架数由一架变成两架,基本方法同模型二。模型一是低级游戏,由设计模型一的难度级别可知,玩家不用很长时间,凭经验就可以获得攻击飞机头的最佳策略。玩家在获得最佳策略后因为形势固定单一将不愿意继续玩,因此模型一的耐玩程度低.模型二是中级游戏,难度有所增加。玩家在判断飞机位置的基础上,还需要考虑飞机机头的朝向,比游戏模型一增加了难度,为中级难易程度。模型三是高级游戏,飞机的方格比模型设计一,二有所增加,由