PAGEPAGE12飛機(jī)對(duì)戰(zhàn)游戲的策略問(wèn)題摘要本文研究怎樣構(gòu)造策略使得在人機(jī)對(duì)戰(zhàn)中計(jì)算機(jī)在比賽采用19局10勝制情況下最容易取得勝利。模型一：針對(duì)問(wèn)題一，使問(wèn)題簡(jiǎn)單化（考慮飛機(jī)頭朝上的情況），利用概率和折半查找法確定第一次攻擊坐標(biāo)，考慮飛機(jī)頭朝向的四個(gè)方向，依據(jù)飛機(jī)頭在不同方向坐標(biāo)之間的函數(shù)關(guān)系即對(duì)稱性，飛機(jī)頭朝上時(shí)策略中使用的坐標(biāo)可以轉(zhuǎn)化為飛機(jī)頭朝下，左，右時(shí)策略中要使用的坐標(biāo)，每個(gè)方向的策略相同，這樣計(jì)算機(jī)最多要16次擊中機(jī)頭。模型二：改進(jìn)模型一，采用概率模型、折半查找法、動(dòng)態(tài)決策法對(duì)模型進(jìn)行優(yōu)化求解使擊中機(jī)頭的次數(shù)更優(yōu)化。模型三：針對(duì)問(wèn)題二，建立概率模型，利用折半查找法、動(dòng)態(tài)決策法對(duì)由7×7的方格變換成11×11的方格且有兩架飛機(jī)的情況進(jìn)行決策，最后給出計(jì)算機(jī)取得勝利的游戲策略。關(guān)鍵字：飛機(jī)對(duì)戰(zhàn)游戲概率折半查找動(dòng)態(tài)決策

1、問(wèn)題重述有一種雙方對(duì)戰(zhàn)游戲，在游戲前雙方各準(zhǔn)備一張坐標(biāo)紙，在上面分別制作7×7的方格，在自己的方格中畫一架飛機(jī)，飛機(jī)呈“士”字形，其中上面的一長(zhǎng)橫占5個(gè)格子，下面的短橫占3個(gè)格子，一豎占4個(gè)格子，最上面突出的一個(gè)格子代表機(jī)頭。所畫飛機(jī)的位置以及機(jī)頭的指向由游戲者自己決定，游戲結(jié)束前雙方不能互看對(duì)方的坐標(biāo)紙。游戲時(shí)雙方交替用“炮彈”打擊對(duì)方，攻擊的一方報(bào)告“炮彈”打擊的位置，被攻擊的一方報(bào)告是否命中飛機(jī)。如果某一方被命中機(jī)頭，游戲結(jié)束，被命中機(jī)頭的一方失敗。游戲雙方都在通過(guò)打擊后對(duì)方的反饋信息來(lái)猜測(cè)對(duì)方飛機(jī)的位置。游戲比賽采用19局10勝制。問(wèn)題一：設(shè)計(jì)一個(gè)人機(jī)對(duì)戰(zhàn)的“飛機(jī)對(duì)戰(zhàn)”游戲。要求先由計(jì)算機(jī)進(jìn)行攻擊，以取勝為目標(biāo)，給出進(jìn)行游戲的策略。問(wèn)題二：考慮在11×11坐標(biāo)紙上畫兩架飛機(jī)的游戲方式，兩架飛機(jī)所占的格子不能重合，游戲方法同上。其中一架飛機(jī)被命中機(jī)頭時(shí)要報(bào)告有一架飛機(jī)被擊落。當(dāng)某方的兩架飛機(jī)都被擊落時(shí)游戲結(jié)束，被擊落方失敗。分析這種游戲方式與只畫一架飛機(jī)的游戲方式在策略上的不同點(diǎn)。

2、問(wèn)題分析問(wèn)題一：我們的分析建立在概率模型的基礎(chǔ)上，將7×7的方格轉(zhuǎn)化成對(duì)應(yīng)坐標(biāo)系里的點(diǎn)。由于飛機(jī)形式固定，因此，將對(duì)飛機(jī)的研究轉(zhuǎn)化成對(duì)機(jī)頭的研究。由對(duì)稱性，再將問(wèn)題轉(zhuǎn)化成機(jī)頭向上的情況。綜上所述，我們將飛機(jī)對(duì)戰(zhàn)游戲轉(zhuǎn)化為通過(guò)概率，尋找單一方向上的機(jī)頭所在點(diǎn)的坐標(biāo)的問(wèn)題。問(wèn)題二：建立在問(wèn)題一的數(shù)學(xué)模型的基礎(chǔ)上，將7×7方格擴(kuò)大到11×11方格，用類似的方法，先查找出第一個(gè)機(jī)頭的位置。由于第二個(gè)機(jī)頭的位置在第一個(gè)機(jī)頭位置確定的前提下，可以確定具體范圍。再用類似的辦法，結(jié)合此前過(guò)程中的反饋信息，繼續(xù)查找。直至查找到第二架飛機(jī)的機(jī)頭。即可取得游戲的勝利。

3、模型假設(shè)及符號(hào)說(shuō)明3.1模型假設(shè)根據(jù)問(wèn)題建立如下合理假設(shè)：1、計(jì)算機(jī)以取勝為目標(biāo)，盡可能取得游戲的勝利。2、人機(jī)擺設(shè)飛機(jī)的位置都是隨機(jī)的。3、人和計(jì)算機(jī)在游戲中是公平的，都不知道對(duì)方飛機(jī)頭的位置坐標(biāo)。4、多局比賽中計(jì)算機(jī)安排飛機(jī)不會(huì)因?yàn)榍按斡螒蜻M(jìn)行情況而影響下一次飛機(jī)的擺放方式。5、計(jì)算機(jī)安排飛機(jī)在所有可能出現(xiàn)的位置的概率相等。6、模型中,考慮到以計(jì)算機(jī)取勝為目標(biāo)，則僅給出計(jì)算機(jī)的攻擊策略，不考慮計(jì)算機(jī)被攻擊的情況。3.2符號(hào)術(shù)語(yǔ)說(shuō)明M：擊中時(shí)可判斷出機(jī)身可能出現(xiàn)位置的情況數(shù)量N：擊中時(shí)可判斷出機(jī)身不可能出現(xiàn)位置的情況數(shù)量L：飛機(jī)頭出現(xiàn)情況飛機(jī)頭朝上是指飛機(jī)頭朝Y軸正方向飛機(jī)頭朝下是指飛機(jī)頭朝Y軸負(fù)方向飛機(jī)頭朝右是指飛機(jī)頭朝X軸正方向飛機(jī)頭朝左是指飛機(jī)頭朝X軸負(fù)方向

4、問(wèn)題一模型的建立和求解4.1模型一一、由于飛機(jī)形狀是固定的，飛機(jī)的移動(dòng)的范圍是有限的，我們可以初步判斷出飛機(jī)頭及機(jī)身可能出現(xiàn)的位置。二、當(dāng)飛機(jī)頭坐標(biāo)確定時(shí),能確定整個(gè)飛機(jī)上所有其他點(diǎn)的坐標(biāo)。例如當(dāng)飛機(jī)頭朝上，飛機(jī)頭的坐標(biāo)為(x,y)時(shí)，機(jī)身上其他所有點(diǎn)的坐標(biāo)為(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）。三、由于飛機(jī)和飛機(jī)的活動(dòng)空間具有對(duì)稱性，飛機(jī)頭朝上、朝下、朝左、朝右的情況之間具有一定函數(shù)關(guān)系。當(dāng)飛機(jī)頭朝上時(shí)，飛機(jī)頭的坐標(biāo)為（x,y），則類似于此的情況，當(dāng)飛機(jī)頭朝下時(shí)，該飛機(jī)頭的坐標(biāo)為（x,8-y）當(dāng)飛機(jī)頭朝左時(shí)，該飛機(jī)頭的坐標(biāo)為（8-y,8-x）當(dāng)飛機(jī)頭朝右時(shí)，該飛機(jī)頭的坐標(biāo)為（y,x）四、以飛機(jī)頭朝上為例，機(jī)頭的位置共有12種情況（如圖4.11）。當(dāng)飛機(jī)頭在（3，7）時(shí)，為情況1當(dāng)飛機(jī)頭在（4，7）時(shí)，為情況2當(dāng)飛機(jī)頭在（5，7）時(shí)，為情況3當(dāng)飛機(jī)頭在（3，6）時(shí)，為情況4當(dāng)飛機(jī)頭在（4，6）時(shí)，為情況5當(dāng)飛機(jī)頭在（5，6）時(shí)，為情況6當(dāng)飛機(jī)頭在（3，5）時(shí)，為情況7當(dāng)飛機(jī)頭在（4，5）時(shí)，為情況8當(dāng)飛機(jī)頭在（5，5）時(shí)，為情況9當(dāng)飛機(jī)頭在（3，4）時(shí)，為情況10當(dāng)飛機(jī)頭在（4，4）時(shí)，為情況11當(dāng)飛機(jī)頭在（5，4）時(shí)，為情況1271236456578941011123211234567圖4.11五、若以取勝為目的，即用最少的次數(shù)擊中對(duì)方的飛機(jī)頭。則M和N的值越接近越好。計(jì)算出49個(gè)坐標(biāo)點(diǎn)相對(duì)應(yīng)的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可知，在坐標(biāo)點(diǎn)（3，3）和（5，3）M=N=6時(shí)，M、N最為相近。所以第一次應(yīng)該攻擊（3，3）點(diǎn)或（5，3）點(diǎn)。六、假設(shè)先攻擊（3，3）點(diǎn)。(3,4)L=457101112(3,3)L=123456789101112(5,5)L=123689(3,5)L=47(3,4)L=457101112(3,3)L=123456789101112(5,5)L=123689(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圖4.13

圖4.13是飛機(jī)頭朝上時(shí)計(jì)算機(jī)的策略表示圖?？梢钥闯?計(jì)算機(jī)最多通過(guò)4次反饋信息就可以判斷出飛機(jī)頭的坐標(biāo)。但是,我們不知道飛機(jī)頭的朝向。所以我們根據(jù)此方法，算出在飛機(jī)頭朝下，朝左，朝右時(shí)的對(duì)策。依據(jù)對(duì)稱性，在飛機(jī)頭朝下時(shí)，我們根據(jù)函數(shù)法則：X=X,Y=8-Y,將飛機(jī)頭朝上時(shí)策略中使用的坐標(biāo)轉(zhuǎn)化為飛機(jī)頭朝下時(shí)策略中要使用的坐標(biāo)。例如：（2，5）——〉（2，3）（6，2）——〉（6，6）在飛機(jī)頭朝左時(shí)，我們根據(jù)函數(shù)法則：X=8-Y,Y=8-X,將飛機(jī)頭朝上時(shí)策略中使用的坐標(biāo)轉(zhuǎn)化為飛機(jī)頭朝左時(shí)策略中要使用的坐標(biāo)。例如：（3，6）——〉（2，5）（2，5）——〉（3，6）在飛機(jī)頭朝右時(shí)，我們根據(jù)函數(shù)法則：X=Y,Y=X，將飛機(jī)頭朝上時(shí)策略中使用的坐標(biāo)轉(zhuǎn)化為飛機(jī)頭朝右時(shí)策略中要使用的坐標(biāo)。例如：（3，4）——〉（4，3）（2，5）——〉（5，2）所以，重復(fù)操作，最多通過(guò)16次，就可以擊中對(duì)方的飛機(jī)頭，取得勝利。按此方法進(jìn)行游戲，直到游戲分出該局勝負(fù)。然后重復(fù)該過(guò)程，當(dāng)有一方勝利數(shù)達(dá)到10時(shí)，結(jié)束游戲。4.2模型二一、由于飛機(jī)形狀是固定的，飛機(jī)的移動(dòng)的范圍有限，我們可以初步判斷出飛機(jī)頭及機(jī)身可能出現(xiàn)的位置。在7×7的方格中飛機(jī)頭的指向有上下左右四個(gè)方向，在這四個(gè)方向中每個(gè)方向飛機(jī)頭有12種不同的位置，所以7×7的方格中飛機(jī)的位置共有48種。我們分析飛機(jī)機(jī)頭在7×7的方格上出現(xiàn)的情況如圖4.21：0011100001110011232111134311112321100111000011100圖4.21

二、由次數(shù)分布圖可得，對(duì)于7×7的方格而言，中心的十字形區(qū)域是飛機(jī)機(jī)頭出現(xiàn)的概率最大點(diǎn)和次概率最大點(diǎn)，即點(diǎn)(4,4)概率最大；(4,5),(5,4),(3,4),(4,3)為次最大概率點(diǎn)。則對(duì)這五個(gè)點(diǎn)首要考慮，進(jìn)行如下步驟：首先攻擊概率最大點(diǎn)（4，4）；然后攻擊次概率最大點(diǎn)，通過(guò)反饋信息分析,進(jìn)行下面一步。攻擊（4,4）點(diǎn)得到反饋：1、擊中機(jī)頭，游戲結(jié)束2、擊中機(jī)身，攻擊(4,5),(5,4),(3,4),(4,3)，考慮上下方向的中機(jī)情況，反饋如圖4.22（√表示擊中機(jī)頭或機(jī)身）（3,4）（4,3）（4,5）（5,4）1√2√√√3√4√√5√√6√√√√7√√8√9√√√10√11√√12√√13√√√√14√√圖4.22發(fā)現(xiàn)四點(diǎn)中一點(diǎn)的情況為4種，考慮左右方向可知8種情況，最大游戲時(shí)間是1+4+3=8次。發(fā)現(xiàn)四點(diǎn)中三點(diǎn)的情況為2種，考慮左右方向可知4種情況，最大游戲時(shí)間是1+4+1=6次。發(fā)現(xiàn)四點(diǎn)均中的情況為2種，考慮左右方向仍為2，最大游戲時(shí)間是1+4=5次。發(fā)現(xiàn)四點(diǎn)中二點(diǎn)（4,3）（4,5）的情況為2種，考慮左右方向可知4種情況，最大游戲時(shí)間是1+4+3=8次。發(fā)現(xiàn)四點(diǎn)中二點(diǎn)（3,4）（5,4）的情況為4種，考慮左右方向仍為4，最大游戲時(shí)間是1+4+3=8次。3、未擊中機(jī)身，攻擊（3,4）（5,4）（4,3）（4,5），類似上一步驟得到信息反饋，最大游戲時(shí)間是1+2+3=6次。4.3模型檢驗(yàn)例如飛機(jī)頭為（6,3）朝右方向:攻擊（4,4）未中，攻擊次概率最大點(diǎn)得到反饋擊中（3,4）（4,3）（5,4）未擊中（4,5），考慮左右方向（2,3）（6,3）選擇攻擊一點(diǎn)則可知。例如飛機(jī)頭為（3,1）朝下方向：攻擊（4,4）機(jī)身，攻擊次概率最大點(diǎn)得到反饋擊中（3,4）未擊中（4,3）（5,4）（4,5），考慮上下方向（3,7）（3,1）選擇攻擊一點(diǎn)則可知。

5、問(wèn)題二模型的建立和求解一、在模型二的基礎(chǔ)上增加一架飛機(jī)，坐標(biāo)紙擴(kuò)大為11×11方格。同第一問(wèn)可知在11×11方格中飛機(jī)機(jī)頭出現(xiàn)的最大概率點(diǎn)為（6，6），次最大概率點(diǎn)為其上下左右四點(diǎn)。二、類似模型二，逐次攻擊概率大的點(diǎn)。若兩架飛機(jī)為上下方向，設(shè)飛機(jī)頭的坐標(biāo)分別為（x,y），（m,n），則機(jī)身上其他所有點(diǎn)的坐標(biāo)分別為（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)。三、先攻擊最大概率點(diǎn)和次最大概率點(diǎn)，若中飛機(jī)機(jī)身，則可找出與之有關(guān)的一切飛機(jī)機(jī)頭坐標(biāo)的集合。若不中，那么以之為機(jī)頭的周圍4架飛機(jī)所經(jīng)過(guò)的點(diǎn)都不可能存在，如圖5.11：2222221112211111111111111111111111111111111111111111111111111122111222222圖5.11然后攻擊（3,9）、（9,9）、(3,3)、（9,3）點(diǎn)，依次判斷，最后可知飛機(jī)機(jī)頭的具體位置。

6、模型的評(píng)價(jià)與推廣6.1模型的評(píng)價(jià)模型一采用折半查找法尋找飛機(jī)頭，大大減少了擊中對(duì)方飛機(jī)頭所需要的次數(shù)，可以使攻擊次數(shù)降到理論最少，提高了擊中對(duì)方的可能性。分析比較全面，對(duì)待各種可能都能很好的分析。且對(duì)于方格數(shù)變多照樣可以使用這種模型處理。但在這個(gè)模型中，開(kāi)始時(shí)沒(méi)有辦法對(duì)飛機(jī)頭的方向進(jìn)行判斷，這樣就不得不進(jìn)行4遍相似的操作，最多需要16次才能擊中，容易出現(xiàn)很多攻擊相同點(diǎn)重復(fù)考慮的情況。模型二是模型一的改進(jìn)，結(jié)合概率模型對(duì)問(wèn)題一進(jìn)行了綜合考慮和動(dòng)態(tài)決策。模型三由7×7的格子變成11×11的格子，飛機(jī)架數(shù)由一架變成兩架,基本方法同模型二。模型一是低級(jí)游戲,由設(shè)計(jì)模型一的難度級(jí)別可知,玩家不用很長(zhǎng)時(shí)間,憑經(jīng)驗(yàn)就可以獲得攻擊飛機(jī)頭的最佳策略。玩家在獲得最佳策略后因?yàn)樾蝿?shì)固定單一將不愿意繼續(xù)玩,因此模型一的耐玩程度低.模型二是中級(jí)游戲,難度有所增加。玩家在判斷飛機(jī)位置的基礎(chǔ)上,還需要考慮飛機(jī)機(jī)頭的朝向,比游戲模型一增加了難度,為中級(jí)難易程度。模型三是高級(jí)游戲,飛機(jī)的方格比模型設(shè)計(jì)一,二有所增加,由7×7的格子變成11×11的格子,飛機(jī)架數(shù)由一架變成兩架,這個(gè)游戲有兩架飛機(jī),由于攻擊飛機(jī)時(shí),玩家不知道自