【正文】 在一個具有完美信息的動態(tài)博弈中，若各方的策略組合在整個博弈及其子博弈中都構(gòu)成納什均衡，則該策略組合稱為該動態(tài)博弈的一個子博弈完美納什均衡。 ? 納什均衡理論的關(guān)鍵是在各種條件下，局中人都可以通過向其他局中人提出威脅和要求，尋求所有局中人都能夠接受的解決方案。 開局分析 ? 研究亞馬遜棋的棋局狀態(tài)的性質(zhì)，就要研究每方棋子的位置關(guān)系及棋子的自由度，其行棋目的是用障礙或自身棋子將對方棋子堵死，使其不能移動或為己方圈地盤，所以棋盤上具體哪個格子被哪個游戲者占有并不重要，重要的是棋子對棋盤的控制力。 ? 在亞馬遜棋的開局階段，每個棋子的自由度都非常高，可行著法非常多。在開局階段著法的主要目標是將己方棋子擴散分布在棋盤上，而避免集中，這種布局有益于自己在殘局階段有最大的地盤。在開局的布局過程中，要求己方著法一定要對自己有利，盡量避免在邊框，障礙等附近。中局可行區(qū)域變小，有的棋子的自由度也變小，主要兩種途徑“逃”和“圍”，逃出自由度小的區(qū)域，而將對方圍在自由度小的區(qū)域。 殘局分析 ? (1) 棋局分解 ? 隨著雙方不斷設(shè)障，活動余地越來越小，亞馬遜棋博弈到一定階段，棋面就會出現(xiàn)被棋子和障礙分割出來的區(qū)域，這些區(qū)域都是獨立的，棋子不能移動到而且也不能再將障礙設(shè)到其他區(qū)域。 ? 圖 (a)為一個棋局， (b)為去掉設(shè)障礙部分后它的基本分解。我們可以利用棋的著法與設(shè)障礙圈出屬于己方的地盤。 (c)是將 (b)的細分， (b)中 c區(qū)域被細分成 c和 d兩個區(qū)域，其中 c被黃方控制，也就是 c屬于黃方的地盤， d被藍方控制就屬于藍方地盤。 ? 區(qū)域 a被細分為區(qū)域 a和 e， a為黃方地盤，而 e屬于藍方地盤，顯然占有 e的藍方棋子已經(jīng)無格子可走，也就是死棋。而 b區(qū)域是屬于藍黃兩方的區(qū)域，需要再進行幾步才能分出地盤。此時，藍黃雙方的最佳選擇就是先不在區(qū)域 a， c， d中行棋，而是選擇首先在 b中占領(lǐng)更大的屬于自己的地盤。 ? (2) 亞馬遜棋中的線段圖表示 ? 如果將亞馬遜棋棋盤的格子看成點，相鄰的格子之間用線段連結(jié)，就可以將當前棋局用線段圖代表，不同的棋局可能有著相同的線段圖，稱為同構(gòu)線段圖。 ? (3) 亞馬遜棋的棋局處理技術(shù) ? 地盤處理技術(shù)分析： ? 當棋子已經(jīng)在地盤中，則不在地盤中行棋，而考慮先在其它區(qū)域行棋，直到己方的每個棋子都在某一地盤中。 ? 死局的處理技術(shù)分析： ? 放棄數(shù)目少的格子，爭取數(shù)目多的格子，棋子向空格子多的路徑行棋，并將障礙設(shè)在現(xiàn)棋子所在位置。 一個死局局勢 納什均衡 ? 零和博弈，是博弈論里的一個概念，意思是雙方博弈，一方得益必然意味著另一方吃虧，一方得益多少，另一方就吃虧多少，顯然亞馬遜棋為二人零和動態(tài)博弈。 ? 亞馬遜棋的每個回合都是整個博弈過程的一個子博弈，由于雙方都是理性的，所以最后最好的結(jié)果是終局雙方均無格子可走。 ? 在弈棋過程中，雙方追求的都是己方地盤的最大化，雖然在博弈中我們會處于一種均衡的狀態(tài)，但博弈雙方的目的都不是尋找這種均衡點，而是要抓住機會打破這種均衡，占得優(yōu)勢地位，以達到贏棋的目的，所以最后的結(jié)果往往并不是雙方的最優(yōu)收益。 ? 雙方雖然不會將達到均衡狀態(tài)的策略集放在首先要考慮的范疇，但是這一納什均衡在著法選擇的過程中起著指導(dǎo)作用。在搜索策略時，往往不去選擇導(dǎo)致雙方收益瞬間變大的著法，而是穩(wěn)中求變。在棋局不發(fā)生劇烈震蕩的前提下，選擇最有利于己方的策略。 ? 在亞馬遜棋中雙方在不同的對弈階段，需要從不同的角度對它的棋局進行評估，對實施的著法做出合理的評價。 ? 開局階段： ? 雙方對弈過程中，均為己方布局，用納什均衡理論來分析開局的布局方法，可以得出著法的選擇要盡量保持雙方所得的價值大致相當，將棋子分散地布在棋盤上，爭取在開局階段棋子對棋盤的掌控程度與對方保持相當，不至于使對方在開局階段便獲得主動權(quán)。如果雙方對棋盤的掌控程度相當，雙方均覺得己方不錯，可以說是一系列納什均衡的累計使棋局達到穩(wěn)定。按照納什均衡理論來對這種均衡的下法進行改進，在對方?jīng)]有改變策略時，靈活地進行己方著法的改進，進行出招，使己方占有更大范圍的地盤，占得優(yōu)勢。 ? 中局階段： ? 雖然雙方的最終目的是使在終局對方無路可走而取得勝利，但在中局不能冒不必要的風(fēng)險，本來想通過某一走棋設(shè)障礙的行動來達到圍困對方的目的，反而被對方圍困。 ? 在選擇著法的過程中，要把雙方最強的著法考慮進去，形成一個雙方都能夠接受的策略集，這也正是納什均衡理論所提議的。即在雙方棋子分布均衡的情況下，先考慮己方活棋的方法，采取攻擊時要確保對方圍困時不致因為自由度小而無法逃脫，然后才能開始攻擊對方。相反地，在采取防守著法時，首先要考慮對方是否有活棋的著法，要是對方?jīng)]有較好的著法，那么我們就先走對己方有利的著法，再找合適的機會反攻對方。 ? 殘局階段： ? 亞馬遜棋對弈的最后階段是殘局階段，殘局階段的每一步棋的價值都很大，足以影響整個棋局的勝負。 ? 對殘局的改進可以應(yīng)用納什均衡理論，我們首先搜索相應(yīng)的能夠?qū)е缕寰质テ胶獾闹?，并將它的價值權(quán)數(shù)增大。如果對方走棋放箭之后使得己方的某棋子的自由度非常小甚至堵死，而己方棋子沒有合適的著法逃離這種攻勢，這時的對方的著法的價值就應(yīng)該被高估。 第 5章機器博弈系統(tǒng)設(shè)計 ? ? 亞馬遜棋博弈系統(tǒng)分為界面和引擎兩大部分，在進行系統(tǒng)設(shè)計時將整個軟件分成幾個模塊，對每個模塊分別進行設(shè)計，最后組合成為一個完整的系統(tǒng)。 ? 分為五個模塊：數(shù)據(jù)結(jié)構(gòu)模塊，著法生成模塊，搜索模塊，評估模塊，界面模塊。 ? 亞馬遜棋流程分析如下： ? (1) 開始一個新的棋局； ? (2) 判斷人和計算機哪方先走棋，如果人先走棋那么執(zhí)行 (3)，如果計算機先走棋那么跳轉(zhuǎn)到 (5)； ? (3) 人在棋盤上走棋，設(shè)障礙； ? (4) 判斷游戲是否結(jié)束，如果游戲結(jié)束那么顯示雙方輸贏情況并退出程序，否則執(zhí)行 (5)； ? (5) 判斷棋子是否全在區(qū)域內(nèi)，然后根據(jù)著法生成函數(shù)生成的所有可能的著法展開博弈樹，同時啟動搜索引擎，調(diào)用評估函數(shù)進行估值； ? (6) 計算機走出最佳著法； ? (7) 判斷游戲是否結(jié)束，如果游戲結(jié)束那么顯示雙方輸贏情況并退出程序，否則轉(zhuǎn)到 (3)。 數(shù)據(jù)結(jié)構(gòu)設(shè)計 ? 讓計算機下棋，首先要選用一種合適的方法記錄棋局，以計算機能接收的數(shù)據(jù)格式表示棋盤、棋子、障礙等相關(guān)信息。這些信息是以后進行搜索和估值等算法操作的基礎(chǔ)。 ? 實際上因為棋盤是 10行 10列的格子，恰好100個位置，因此用數(shù)字 099對棋盤進行編碼，用來表示 100個格子 ? 具體定義雙方的八顆棋子。這里定義每顆棋子的初始位置如下： B [0].Situation=03； B [1].Situation=06； B [2].Situation=30； B [3].Situation=39； 棋子 甲棋 乙棋 空格 障礙 編碼 0 1 1 2 Y [0].Situation=60； Y [1].Situation=69； Y [2].Situation=93； Y [3].Situation=96； ? 亞馬遜棋的棋局狀態(tài)數(shù)據(jù)由一個長度為 100的一維數(shù)組表示，對應(yīng)表示棋盤上的棋子、障礙和空格的信息。初始棋盤狀態(tài)數(shù)組形式如下： Amazon[100]={ 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 0, 1, 1,1, 1, 1, 1, 1, 1, 0, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, } ? 亞馬遜棋走棋與提子位置、落子位置、設(shè)障礙位置有關(guān)，定義如下： ? struct Go{ ? int f； //提子點 ? int t； //落子點 ? int p； } //放箭點 ? 這里的 f、 t、 p指 0099的棋盤位置編碼。 ? 當棋盤上有變化時就需要更新一些數(shù)據(jù)信息。通過消息響應(yīng)函數(shù)確定提子位置，落子位置和設(shè)障礙位置的坐標，并將位置坐標傳入后臺棋盤，后臺中相應(yīng)的處理函數(shù)將在棋盤數(shù)組相應(yīng)位置上置 0 或 1，更新存儲棋局狀態(tài)的數(shù)組。在計算機搜索最佳著法的過程中，搜索完一個節(jié)點后，如果需要