自博弈演算法

㈠ 巴什博弈必勝策略演算法

巴什博弈公式是：(m+1)|n
理解是如果n=m+1,那麼由於一次最多隻能取m個,所以,無論先取者拿走多少個,後取者都能夠一次拿走剩餘的物品,後者取勝。
因此我們發現了如何取勝的法則是：如果n=(m+1)r+s,(r為任意自然數,s≤m)，那麼先取者要拿走s個物品，如果後取者拿走k(≤m)個，那麼先取者再拿走m+1-k個。結果剩下(m+1)(r-1)個，以後保持這樣的取法，那麼先取者肯定獲勝總之，要保持給對手留下(m+1)的倍數，就能最後獲勝。
同餘定理：n=k_(m+1)+r，先者拿走r個，那麼後者無論拿走1m個先者只要的數目使和為m+1，那麼先手必贏。
博弈論是ACM比賽中的一個很重要的理論，雖然很多情況可以套用公式。
博弈論題目特點:兩名選手，交替進行預先規定好的操作,在任何情況下，合法操作只取決於情況本身，與選手無關。游戲失敗的最終判定往往是選手無法進行合法操作了。

㈡ 博弈樹演算法是啥

就是用樹的節點來表示博弈過程中的每一步，比如在象棋里，雙方棋手獲得相同的棋盤信息。他們輪流走棋，目的就是將死對方，或者避免被將死。
由此，我們可以用一棵「博弈樹」（一棵n叉樹）來表示下棋的過程——樹中每一個結點代表棋盤上的一個局面，對每一個局面（結點）根據不同的走法又產生不同的局面（生出新的結點），如此不斷直到再無可選擇的走法，即到達葉子結點（棋局結束）。

㈢ 棋類游戲的演算法有哪些

棋類游戲的演算法有哪些

棋類游戲通常包含三大要素：棋盤、棋子和游戲規則，其中游戲規則又包括勝負判定規則、落子的規則以及游戲的基本策略。下面我來給大家講講各類棋類游戲的演算法。

除了棋盤和棋子的建模，棋類游戲最重要的部分就是AI演算法的設計。目前棋類游戲的AI基本上就是帶啟發的搜索演算法，那麼常用的搜索演算法有哪些呢?

1. 博弈與博弈樹

博弈可以理解為有限參與者進行有限策略選擇的競爭性活動，比如下棋、打牌、競技、戰爭等。根據參與者種類和策略選擇的方式可以將博弈分成很多種，比如“二人零和、全信息、非偶然”博弈，也就是我們常說的零和博弈(Zero-sum Game)。所謂“零和”，就是有贏必有輸，不存在雙贏的結果。所謂“全信息”，是指參與博弈的雙方進行決策時能夠了解的信息是公開和透明的，不存在信息不對稱的情況。比如棋類游戲的棋盤和棋子狀態是公開的，下棋的雙方都可以看到當前所有棋子的位置，但是很多牌類游戲則不滿足全信息的條件，因為牌類游戲都不會公開自己手中的牌，也看不到對手手中的牌。所謂的“非偶然”，是指參與博弈的雙方的決策都是“理智”的行為，不存在失誤和碰運氣的情況。

在博弈過程中，任何一方都希望自己取得勝利，當某一方當前有多個行動方案可供選擇時，他總是挑選對自己最為有利同時對對方最為不利的那個行動方案。當然，博弈的另一方也會從多個行動方案中選擇一個對自己最有利的方案進行對抗。參與博弈的雙方在對抗或博弈的過程中會遇到各種狀態和移動(也可能是棋子落子)的選擇，博弈雙方交替選擇，每一次選擇都會產生一個新的棋局狀態。

假設兩個棋手(可能是兩個人，也可能是兩台計算機)MAX和MIN正在一個棋盤上進行博弈。當MAX做選擇時，主動權在MAX手中，MAX可以從多個可選決策方案中任選一個行動，一旦MAX選定某個行動方案後，主動權就轉移到了MIN手中。MIN也會有若干個可選決策方案，MIN可能會選擇任何一個方案行動，因此MAX必須對做好應對MIN的每一種選擇。如果把棋盤抽象為狀態，則MAX每選擇一個決策方案就會觸發產生一個新狀態，MIN也同樣，最終這些狀態就會形成一個狀態樹，這個附加了MAX和MIN的決策過程信息的狀態樹就是博弈樹(Game Tree)。

2. 極大極小值搜索演算法

極大極小值(Min-Max)搜索演算法是各種博弈樹搜索演算法中最基礎的搜索演算法。假如MAX和MIN兩個人在下棋，MAX會對所有自己可能的落子後產生的局面進行評估，選擇評估值最大的局面作為自己落子的選擇。這時候就該MIN落子，MIN當然也會選擇對自己最有利的局面，這就是雙方的博弈，即總是選擇最小化對手的'最大利益(令對手的最大利益最小化)的落子方法。作為一種博弈搜索演算法，極大極小值搜索演算法的名字就由此而來。

3. 負極大值搜索演算法

博弈樹的搜索是一個遞歸的過程，極大極小值演算法在遞歸搜索的過程中需要在每一步區分當前評估的是極大值節點還是極小值節點。1975年Knuth和Moore提出了一種消除MAX節點和MIN節點區別的簡化的極大極小值演算法，稱為負極大值演算法Negamax。該演算法的理論基礎是：

max(a,b) = -min(-a, -b)

簡單地將遞歸函數MiniMax()返回值取負再返回，就可以將所有的MIN 節點都轉化為MAX節點，對每個節點的搜索都嘗試讓節點值最大，這樣就將每一步遞歸搜索過程都統一起來。

4. “α-β”剪枝演算法

有很多資料將“α-β”剪枝演算法稱為“α-β”搜索演算法，實際上，它不是一種獨立的搜索演算法，而是一種嫁接在極大極小值演算法和負極大值演算法上的一種優化演算法。“α-β”剪枝演算法維護了一個搜索的極大極小值窗口：[α,β]。其中α表示在搜索進行到當前狀態時，博弈的MAX一方所追尋的最大值中最小的那個值(也就是MAX的最壞的情況)。在每一步的搜索中，如果MAX所獲得的極大值中最小的那個值比α大，則更新α值(用這個最小值代替α)，也就是提高α這個下限。

而β表示在搜索進行到當前狀態時，博弈的MIN一方的最小值中最大的那個值(也就是MIN的最壞的情況)。在每一步的搜索中，如果MIN所獲得的極小值中最大的那個值比β小，則更新β值(用這個最大值代替β)，也就是降低β這個上限。當某個節點的α≥β時，說明該節點的所有子節點的評估值既不會對MAX更有利，也不會對MIN更有利，也就是對MAX和MIN的選擇不會產生任何影響，因此就沒有必要再搜索這個節點及其所有子節點了。

5. 估值函數

對於很多啟發式搜索演算法，其“智力”的高低基本上是由估值函數(評估函數)所決定，棋類游戲的博弈樹搜索演算法也不例外。

估值函數的作用是把一個棋局量化成一個可直接比較的數字，這個數字在一定程度上能反映取勝的概率。棋局的量化需要考慮很多因素，量化結果是這些因素按照各種權重組合的結果。這些因素通常包括棋子的戰力(棋力)、雙方棋子佔領的空間、落子的機動性、威脅性(能吃掉對方的棋子)、形和勢等。

6. 置換表與哈希函數

置換表(transposition table)也是各種啟發式搜索演算法中常用的輔助演算法，它是一種以空間換時間的策略，使用置換表的目的就是提高搜索效率。一般情況下，置換表中的每一項代表者一個棋局中最好的落子方法，直接查找置換表獲得這個落子方法能避免耗時的重復搜索，這就是使用置換表能大幅提高搜索效率的原理。

使用置換表最大的問題是置換表的組織和查找的效率。一般來說，置換表越大，查找的命中率就越高。但這個關系不是絕對的，當置換表大小達到一定規模後，不僅不會再提高命中率，反而會因為耗時的查找操作影響演算法的效率。所以置換表不是越大越好，需要根據計算機的性能以及搜索的深度選擇一個合適的大小。此外，為了查找操作更高效，通常都會用可直接訪問的哈希表方式組織置換表，哈希函數的性能就成為影響置換表性能的重要因素。棋類游戲普遍採用Zobrist哈希演算法。

㈣ 博弈演算法的研究意義

博弈演算法的研究意義是可作為研究價格競爭問題的最有力的武器和有效的工具。根據查詢相關資料得知，博弈論是研究各方策略相互影響的條件下，理性決策人的決策行為的一種理論，通過利用博弈均衡理論在企業價格競爭當中的應用來研究企業應該正確的運用價格競爭策略。

㈤ 博弈論中各公式及演算法 數學渣，看書里的運算發暈。

學博弈論不能背公式，分析SG函數才是正道= =。

另外，網路知道不會有人幫你整理公式的。

㈥ 博弈均衡的進化穩定策略的演算法

計算進化穩定策略的方法主要有兩大類：一是從動態過程出發，求出系統的平衡點，然後，再根據進化穩定策略的定義進行驗證就可以了；另一種方法就是直接用進化穩定策略定義來求。第一種方法涉及到具體的動態過程，並且只要知道動態過程就很容易求出進化穩定策略，本文略（可以參考張良橋2001）。第二種方法就是通過定義來求，下面給出一種簡單的處理方法。
根據納什均衡的定義可以知道，如果策略 是博弈的納什均衡，那麼，所有以正概率進入最優混合策略的純策略都是最優的，參與人在所有這些純策略所得的支付都是無差異的（見《博弈論與信息經濟學》102-103頁，張維迎），即有：
表示混合策略中非零概率的純策略。假定存在 且下標為 的純策略滿足 ，令B是矩陣A中對應於非零純策略的 階子矩陣。且令C為 矩陣，其中代表元素為： 。那麼當且僅當C是負定的， 就是進化穩定策略(見John Haigh 1974)。
證明：假定 ，並且存在 ，有 ，那麼很明顯有 ，其中 是第 個純策略，即在與穩定策略者群體博弈時，突變策略者得到的支付比穩定策略者還要大，所以策略 不是進化穩定策略，所以式（6）是進化穩定策略的必要條件。因此，對應於非零概率的純策略滿足： ，對滿足條件的策略 有（注意 ）：
對任意 ，當且僅當
有： 。綜上所述，利用該方法來求進化穩定策略的步驟如下：
首先，令 個非零混合策略，然後解 個方程： ，定義B，C再考察矩陣C的所有特徵根是否都為負，若都是負則所得的策略就是進化穩定策略。
如求對稱博弈 ，它有兩個進化穩定策略： 。
如果某策略組合是嚴格納什均衡策略，那麼就可以直接得出它就是進化穩定策略，但如果是弱納什均衡策略，那麼就可運用上述的方法來進行判定。由此，可得到求博弈的進化穩定策略步驟：一是求出博弈所有的納什均衡；二是由支付判斷出其中的嚴格納什均衡；三對非嚴格納什均衡而言就代入上述方程，並判斷是否為負定即可以求出博弈中所有進化穩定策略。

㈦ c語言 五子棋 博弈樹演算法 葉子節點的分值是如何計算的

其實這個不是難點的，那個分數是當前落子後所形成的以這個棋子為中心的9x9矩陣中所形成的棋型，計算其他地方的棋型顯然沒有什麼意義，再有就是不是C語言才可以寫演算法的，對於極大極小原理，博弈樹和alpha-beta剪枝演算法都是基於這個原理的，如果你是剛學編程不久，而且沒有數據結構的基礎是寫不出來運用博弈樹演算法的五子棋的，先把基礎打好再說。。

㈧ 博弈演算法里的剪枝怎麼用（具體的）

極大極小過程，以及阿爾法-貝塔剪紙。極小極大搜索方法是博弈樹搜索的基本方法，現在博弈樹搜索中最常用的α-β剪枝搜索方法，就是從這一方法發展而來的。
首先假定，有一個評價函數可以對所有的棋局進行評估。當評價函數值大於0時，表示棋局對我方有利，對對方不利。當評價函數小於0時，表示棋局對我方不利，對對方有利。而評價函數值越大，表示對我方越有利。當評價函數值等於正無窮大時，表示我方必勝。評價函數值越小，表示對我方越不利。當評價函數值等於負無窮大時，表示對方必勝。假設雙方都是對弈高手，在只看一步棋的情況下，我方一定走評價函數值最大的一步棋，而對方一定走評價函數值最小的一步棋。會下棋的讀者都知道，在只看一步的情況下最好的棋，從全局來說不一定就好，還可能很不好。因此為了走出好棋，必須多看幾步，從多種可能狀態中選擇一步好棋。
想一想人是如何下棋的呢？人實際上採用的是一種試探性的方法。首先假定走了一步棋，看對方會有那些應法，然後再根據對方的每一種應法，看我方是否有好的回應......這一過程一直進行下去，直到若干步以後，找到了一個滿意的走法為止。初學者可能只能看一、兩個輪次，而高手則可以看幾個，甚至十幾個輪次。
極小極大搜索方法，模擬的就是人的這樣一種思維過程。當輪到我方走棋時，首先按照一定的搜索深度生成出給定深度d以內的所有狀態，計算所有葉節點的評價函數值。然後從d-1層節點開始逆向計算：對於我方要走的節點（用MAX標記，稱為極大節點）取其子節點中的最大值為該節點的值（因為我方總是選擇對我方有利的棋）；對於對方要走的節點（用MIN標記，稱為極小節點）取其子節點中的最小值為該節點的值（對方總是選擇對我方不利的棋）。一直到計算出根節點的值為止。獲得根節點取值的那一分枝，即為所選擇的最佳走步。
在圖3.5所示的例子中，假定搜索深度為2，D～J是7個葉節點，在它們下邊括弧中的數字是這些節點的評價函數值（假定可以計算得到）。A、B、C是三個極小節點，它們分別取各自子節點最小值為自己的值，得到三個節點的值分別為-6、-2和-4。s是極大節點，從A、B、C三個節點的值中取最大值，得到-2。由於-2來自於節點B，所以搜索的結果是應選擇B作為我方的走步。對於我方來說，-2並不是一個好的結果，但卻是在對方不犯錯誤的情況下，對我方最有利的結果。因為從圖中可以看出，如果選擇A為我方的走步，如果對方回應D的話，我方可以得到評價值9，固然對我方有利。但是如果對方是一個高手的話，他一定回選擇E，而不是D。在這種情況下，我方只能得到-6，結果豈不是更差。因此，極小極大過程是一種假定對手每次回應都正確的情況下，如何從中找出對我方最有利的走步的搜索方法。
值得注意的是，不管設定的搜索深度是多少層，經過一次搜索以後，只決定了我方一步棋的走法。等到對方回應一步棋之後，需要在新的棋局下重新進行搜索，來決定下一步棋如何走。極小極大搜索策略是考慮雙方對弈若干步之後，從可能的走步中選一步相對好棋的著法來走，即在有限的搜索深度范圍內進行求解。為此要定義一個靜態估計函數f，以便對棋局的勢態（節點）作出優劣估值，這個函數可根據勢態優劣特徵來定義（主要用於對端節點的"價值"進行度量）。一般規定有利於MAX的勢態，f（p）取正值，有利於MIN的勢態，f（p）取負值，勢均力敵的勢態，f（p）取0值。若f（p）＝＋∞，則表示MAX贏，若f（p）＝－∞，則表示MIN贏。下面的討論規定：頂節點深度d＝0，MAX代表程序方，MIN代表對手方，MAX先走。
圖3.5是一個表示考慮兩步棋的例子，圖中端節點給出的數字是用靜態函數f（p）計算得到，其他節點不用f（p）估計，因為不夠精確，而應用倒推的辦法取值。例如A、B、C是MIN走步的節點，MAX應考慮最壞的情況，故其估值應分別取其子節點f（p）估值中最小者，而s是MAX走步的節點，可考慮最好的情況，故估值應取A、B、C值中的最大者。這樣求得f（s）＝－2，依此確定了相對較優的走步應是走向B，因為從B出發，對手不可能產生比f（s）＝－2更差的效果。實際上可根據資源條件，考慮更多層次的搜索過程，從而可得到更准確的倒推值，供MAX選取更正確的走步。當用端節點的靜態估計函數f（p）求倒推值時，兩位選手應採取不同的策略，從下往上逐層交替使用極小和極大的選值方法，故稱極小極大過程。

㈨ 人工智慧研究博弈演算法的意義是什麼

通過對博弈問題的研究來促進人工智慧技術在規劃、決策等方面的應用。人工智慧研究博弈起初是通過讓計算機與人進行下棋、打牌之類的游戲來測驗博弈演算法，而人工智慧研究博弈演算法的意義是通過對博弈問題的研究來促進人工智慧技術在規劃、決策等方面的應用。從而讓博弈演算法可以應用在更多方面。

㈩ c語言的五子棋代碼（博弈演算法）

#include<stdio.h>
#include<bios.h>
#include<ctype.h>
#include<conio.h>
#include<dos.h>
#defineCROSSRU0xbf/*右上角點*/
#defineCROSSLU0xda/*左上角點*/
#defineCROSSLD0xc0/*左下角點*/
#defineCROSSRD0xd9/*右下角點*/
#defineCROSSL0xc3/*左邊*/
#defineCROSSR0xb4/*右邊*/
#defineCROSSU0xc2/*上邊*/
#defineCROSSD0xc1/*下邊*/
#defineCROSS0xc5/*十字交叉點*/

/*定義棋盤左上角點在屏幕上的位置*/
#defineMAPXOFT5
#defineMAPYOFT2

/*定義1號玩家的操作鍵鍵碼*/
#definePLAY1UP0x1157/*上移--'W'*/
#definePLAY1DOWN0x1f53/*下移--'S'*/
#definePLAY1LEFT0x1e41/*左移--'A'*/
#definePLAY1RIGHT0x2044/*右移--'D'*/
#definePLAY1DO0x3920/*落子--空格鍵*/

/*定義2號玩家的操作鍵鍵碼*/
#definePLAY2UP0x4800/*上移--方向鍵up*/
#definePLAY2DOWN0x5000/*下移--方向鍵down*/
#definePLAY2LEFT0x4b00/*左移--方向鍵left*/
#definePLAY2RIGHT0x4d00/*右移--方向鍵right*/
#definePLAY2DO0x1c0d/*落子--回車鍵Enter*/

/*若想在游戲中途退出,可按Esc鍵*/
#defineESCAPE0x011b

/*定義棋盤上交叉點的狀態,即該點有無棋子*/
/*若有棋子,還應能指出是哪個玩家的棋子*/
#defineCHESSNULL0/*沒有棋子*/
#defineCHESS1'O'/*一號玩家的棋子*/
#defineCHESS2'X'/*二號玩家的棋子*/

/*定義按鍵類別*/
#defineKEYEX99v0/*退出鍵*/
#defineKEYFALLCHESS1/*落子鍵*/
#defineKEYMOVECURSOR2/*游標移動鍵*/
#defineKEYINVALID3/*無效鍵*/

/*定義符號常量:真,假---真為1,假為0*/
#defineTRUE1
#defineFALSE0

/**********************************************************/
/*定義數據結構*/

/*棋盤交叉點坐標的數據結構*/
structpoint
{
intx,y;
};


或者下面這個：
#include<graphics.h>
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#defineN15
#defineB7
#defineSTOP-10000
#defineOK1
#defineNO0
#defineUP328
#defineDOWN336
#defineLEFT331
#defineRIGHT333

inta[N+1][N+1];
intzx,zy;
intwrite=1,biaoji=0;
structzn{
longsum;

inty;

intx;

}w[N+1][N+1],max,max1;


voidcbar(inti,intx,inty,intr);
voidmap(inta[][]);
intgetkey();
intkey();
voidzuobiao(intx,inty,inti);
inttu(inta[][],intwrite);
intwtu(inta[][],intwrite);
intneng(inta[][]);
intzh5(inty,intx,inta[][]);
longzzh5(intb[][],inti);
main()
{
inti,j;
intgdriver=DETECT;
intgmode;
initgraph(&gdriver,&gmode,"");
zx=(N+1)/2;
zy=(N+1)/2;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
a[i][j]=0;
map(a);
i=1;
while(i)
{
intk,n;
k=wtu(a,write);
if(k==STOP)gotoend;
map(a);
n=neng(a);
if(n==STOP)gotoend;
map(a);
}
end:
;
}


intneng(inta[N+1][N+1])

{
inti,j;
intk;
max.sum=-1;

for(i=0;i<=N;i++)
for(j=0;j<+N;j++)

{
w[i][j].sum=0;
w[i][j].x=i;
w[i][j].y=j;
}
for(i=1;i<=N-4;i++)
for(j=1;j<=N-4;j++)
{
k=zh5(i,j,a);
if(k==STOP)return(STOP);
}

for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
{

if(max.sum<w[i][j].sum)
{

max.sum=w[i][j].sum;
max.y=i;
max.x=j;
}

elseif(max.sum==w[i][j].sum)
{

if(((max.y-zy)*(max.y-zy)+(max.x-zx)*(max.x-zx))>((i-zy)*(i-zy)+(j-zx)*(j-zx)))
max.sum=w[i][j].sum;
max.y=i;
max.x=j;
}
}
if(a[max.y][max.x]==0)

{
a[max.y][max.x]=-1;
zy=max.y;
zx=max.x;
}

}


intzh5(inty,intx,inta[N+1][N+1])
{

inti,j;
intb[6][6];
longc[13];

longd[6][6];
longtemp;
for(i=y;i<=y+4;i++)
for(j=x;j<=x+4;j++)
b[i+1-y][j+1-x]=a[i][j];
c[1]=b[1][1]+b[1][2]+b[1][3]+b[1][4]+b[1][5];
c[2]=b[2][1]+b[2][2]+b[2][3]+b[2][4]+b[2][5];
c[3]=b[3][1]+b[3][2]+b[3][3]+b[3][4]+b[3][5];
c[4]=b[4][1]+b[4][2]+b[4][3]+b[4][4]+b[4][5];
c[5]=b[5][1]+b[5][2]+b[5][3]+b[5][4]+b[5][5];
c[6]=b[1][1]+b[2][1]+b[3][1]+b[4][1]+b[5][1];
c[7]=b[1][2]+b[2][2]+b[3][2]+b[4][2]+b[5][2];
c[8]=b[1][3]+b[2][3]+b[3][3]+b[4][3]+b[5][3];
c[9]=b[1][4]+b[2][4]+b[3][4]+b[4][4]+b[5][4];
c[10]=b[1][5]+b[2][5]+b[3][5]+b[4][5]+b[5][5];
c[11]=b[1][1]+b[2][2]+b[3][3]+b[4][4]+b[5][5];
c[12]=b[1][5]+b[2][4]+b[3][3]+b[4][2]+b[5][1];


for(i=1;i<=12;i++)
{
switch(c[i])

{

case5:biaoji=1;return(STOP);

case-5:biaoji=-1;return(STOP);

case-4:c[i]=100000;break;

case4:c[i]=100000;break;

case-3:c[i]=150;break;

case3:c[i]=150;break;

case-2:c[i]=120;break;

case2:c[i]=100;break;

case-1:c[i]=1;break;

case1:c[i]=1;break;

default:c[i]=0;

}

}

for(i=1;i<=12;i++)

{

if(c[i]==150)

c[i]+=zzh5(b,i);

}

for(i=1;i<=5;i++)

for(j=1;j<=5;j++)

d[i][j]=0;

for(i=1;i<=5;i++)

for(j=1;j<=5;j++)

{

if(i==j)d[i][j]+=c[11];

if((i+j)==6)d[i][j]+=c[12];

d[i][j]+=c[i]+c[j+5];

}

for(i=1;i<=5;i++)

for(j=1;j<=5;j++)

{

if(b[i][j]!=0)

d[i][j]=-2;

}

max1.sum=-1;

max1.y=0;

max1.x=0;

for(i=1;i<=5;i++)

for(j=1;j<=5;j++)

{

if(max1.sum<d[i][j])

{

max1.sum=d[i][j];

max1.y=i;

max1.x=j;

w[i+y-1][j+x-1].sum+=max1.sum;

}

elseif(max1.sum==d[i][j])

{

if(((i+y-1-zy)*(i+y-1-zy)+(j+x-1-zx)*(j+x-1-zx))>((max1.y+y-1-zy)*(max1.y+y-1-zy)+(max1.x+x-1-zx)*(max1.x+x-1-zx)))

{

max1.sum=d[i][j];

max1.y=i;

max1.x=j;

}

}

}

}

longzzh5(intb[6][6],intn)

{

inti,j,k,l,m;

switch(n)

{

case1:i=b[1][1];j=b[1][2];k=b[1][3];l=b[1][4];m=b[1][5];break;

case2:i=b[2][1];j=b[2][2];k=b[2][3];l=b[2][4];m=b[2][5];break;

case3:i=b[3][1];j=b[3][2];k=b[3][3];l=b[3][4];m=b[3][5];break;

case4:i=b[4][1];j=b[4][2];k=b[4][3];l=b[4][4];m=b[4][5];break;

case5:i=b[5][1];j=b[5][2];k=b[5][3];l=b[5][4];m=b[5][5];break;

case6:i=b[1][1];j=b[2][1];k=b[3][1];l=b[4][1];m=b[5][1];break;

case7:i=b[1][2];j=b[2][2];k=b[3][2];l=b[4][2];m=b[5][2];break;

case8:i=b[1][3];j=b[2][3];k=b[3][3];l=b[4][3];m=b[5][3];break;

case9:i=b[1][4];j=b[2][4];k=b[3][4];l=b[4][4];m=b[5][4];break;

case10:i=b[1][5];j=b[2][5];k=b[3][5];l=b[4][5];m=b[5][5];break;

case11:i=b[1][1];j=b[2][2];k=b[3][3];l=b[4][4];m=b[5][5];break;

case12:i=b[1][5];j=b[2][4];k=b[3][3];l=b[4][2];m=b[5][1];break;

}

if((i==0&&j==1&&k==1&&l==1&&m==0))

return(900);

if((i==0&&j==-1&&k==-1&&l==-1&&m==0))

return(1000);

if((i==0&&j==0&&k==1&&l==1&&m==1)||(i==1&&j==1&&k==1&&l==0&&m==0))

return(20);

if((i==0&&j==0&&k==-1&&l==-1&&m==-1)||(i==-1&&j==-1&&k==-1&&l==0&&m==0))

return(20);

if((i==-1&&j==1&&k==1&&l==1&&m==1)||(i==1&&j==-1&&k==1&&l==1&&m==1)||(i==1&&j==1&&k==-1&&l==1&&m==1)||(i==1&&j==1&&k==1&&l==-1&&m==1)||(i==1&&j==1&&k==1&&l==1&&m==-1))

return(-60);

if((i==1&&j==-1&&k==-1&&l==-1&&m==-1)||(i==-1&&j==1&&k==-1&&l==-1&&m==-1)||(i==-1&&j==1&&k==-1&&l==-1&&m==-1)||(i==-1&&j==-1&&k==-1&&l==1&&m==-1)||(i==-1&&j==-1&&k==-1&&l==-1&&m==1))

return(-60);

}


intwtu(inta[N+1][N+1],intwrite)

{

inti=1;

map(a);

zuobiao(zx,zy,1);

while(i)

{

intk;

k=tu(a,write);

if(k==OK)i=0;

if(k==STOP)return(STOP);

}

}


intgetkey()

{

intkey,lo,hi;

key=bioskey(0);

lo=key&0x00ff;

hi=(key&0xff00)>>8;

return((lo==0)?hi+256:lo);

}


intkey()

{

intk;

k=getkey();

switch(k)

{

case27:return(STOP);

case13:

case'':return(OK);

case328:return(UP);

case336:return(DOWN);

case331:return(LEFT);

case333:return(RIGHT);

default:return(NO);

}

}


voidzuobiao(intx,inty,inti)

{

intr;

if(i!=0)

{

setcolor(GREEN);

for(r=1;r<=5;r++)

circle(75+25*x,25+25*y,r);


}

else

{

if(a[zy][zx]==1)

{

setcolor(8);

for(r=1;r<=5;r++)

circle(75+25*x,25+25*y,r);

}

elseif(a[zy][zx]==-1)

{

setcolor(WHITE);

for(r=1;r<=5;r++)

circle(75+25*x,25+25*y,r);

}

else

{

setcolor(B);

for(r=1;r<=5;r++)

circle(75+25*x,25+25*y,r);

setcolor(RED);line(75+25*zx-5,25+25*zy,75+25*x+5,25+25*zy);

line(75+25*zx,25+25*zy-5,75+25*zx,25+25*zy+5);

}

}

}


inttu(inta[N+1][N+1],intwrite)

{

intk;

re:

k=key();

if(k==OK)

{

if(a[zy][zx]==0)

{

a[zy][zx]=write;

}

else

gotore;

}

if(k==STOP)return(STOP);

if(k==NO)gotore;

if(k==UP)

{

inti,j;

if(zy==1)j=zy;

elsej=zy-1;

zuobiao(zx,zy,0);

zuobiao(zx,j,1);

zy=j;

gotore;

}

if(k==DOWN)

{

inti,j;

if(zy==N)j=zy;

elsej=zy+1;

zuobiao(zx,zy,0);

zuobiao(zx,j,1);

zy=j;

gotore;

}

if(k==LEFT)

{

inti,j;

if(zx==1)i=zx;

elsei=zx-1;

zuobiao(zx,zy,0);

zuobiao(i,zy,1);

zx=i;

gotore;

}

if(k==RIGHT)

{

inti,j;

if(zx==N)i=zx;

elsei=zx+1;

zuobiao(zx,zy,0);

zuobiao(i,zy,1);

zx=i;

gotore;

}

}


voidcbar(inti,intx,inty,intr)

{

if(i!=0)

{

if(i==1)

setcolor(8);

elseif(i==-1)

setcolor(WHITE);

for(i=1;i<=r;i++)

{

circle(x,y,i);

}

}

}


voidmap(inta[N+1][N+1])

{

inti,j;

cleardevice();

setbkcolor(B);

setcolor(RED);

for(i=0;i<N;i++)

{

line(100,50+25*i,75+N*25,50+25*i);

line(100+25*i,50,100+25*i,25+N*25);

}

for(i=1;i<=N;i++)

for(j=1;j<=N;j++)

cbar(a[i][j],75+25*j,25+25*i,10);

}