Ⅰ 中國象棋演算法
對於中國象棋，每一個字都有自己的規則，正所謂無規矩不成方圓。
棋盤先設定好，a:array[1..10][1..9] of MapStruct;
是個二維數組，每個單元符全自定義的棋盤結構
不要定義一個棋字結構
int StepJudge(int oldx,int oldy,int nowx,int nowy)
/* oldx,oldy 棋字原來位置 */
/* oldx,oldy 棋字新位置 */
/* 判斷從原位置到新位置的合法性 */
{
int index,count=0;
int nox,noy;
int x,y,x1,x2,y1,y2;
BYTE ChessId; /* 棋字是哪一方的，有RED，BLUE，NONE三種值 */
ChessId=map[oldx][oldy].Id;
if(ChessId==NONE) return 0;
if(oldx==nowx&&oldy==nowy) return 0;
if(nowx>8||nowx<0||nowy<0||nowy>9) return 0;
nox=nowx-oldx;noy=nowy-oldy;
switch(map[oldx][oldy].num)
{
case 0:/*HeaderCapital*/將或帥
{
if(map[nowx][nowy].num==0&&map[nowx][nowy].Id!=NONE&&oldx==nowx)
{
/*Face to Face*/
y1=oldy;y2=nowy;
if(nowy<oldy) Swap(&y1,&y2);
for(y=y1+1;y<y2;y++) if(map[nowx][y].Id!=NONE) count++;
if(count==0) return 1;
}
if(abs(nox)>1||abs(noy)>1||abs(nox)==1&&abs(noy)==1) return 0;
if(nowy>2&&nowy<7||nowx<3||nowx>5) return 0;
break;
}
case 14: case 15:/*Genaral*/車
{
if(abs(nox)!=0&&abs(noy)!=0) return 0;
if(abs(nox)>1&&noy==0)
{
x1=oldx;x2=nowx;
if(nowx<oldx) Swap(&x1,&x2);
for(x=x1+1;x<x2;x++) if(map[x][nowy].Id!=NONE) return 0;
}
if(nox==0&&abs(noy)>1)
{
y1=oldy;y2=nowy;
if(nowy<oldy) Swap(&y1,&y2);
for(y=y1+1;y<y2;y++) if(map[nowx][y].Id!=NONE) return 0;
}
break;
}
case 10: case 11:/*Horse*/馬
{
if(abs(nox)==2&&abs(noy)==1||abs(nox)==1&&abs(noy)==2)
{
if(abs(nox)==1&&map[oldx][oldy+noy/2].Id!=NONE) return 0;
if(abs(nox)==2&&map[oldx+nox/2][oldy].Id!=NONE) return 0;
break;
}
else return 0;
}
case 12: case 13:/*Gun*/炮
{
if(abs(nox)>0&&abs(noy)>0) return 0;
if(abs(nox)>0&&noy==0)
{
x1=oldx;x2=nowx;
if(nowx<oldx) Swap(&x1,&x2);
for(x=x1+1;x<x2;x++) if(map[x][nowy].Id!=NONE) count++;
}
else if(nox==0&&abs(noy)>0)
{
y1=oldy;y2=nowy;
if(nowy<oldy) Swap(&y1,&y2);
for(y=y1+1;y<y2;y++) if(map[nowx][y].Id!=NONE) count++;
}
if(count==0&&map[nowx][nowy].Id!=NONE) return 0;
if(count==1&&map[nowx][nowy].Id==NONE) return 0;
if(count>1) return 0;
break;
}
case 3: case 4:/*Minister*/象或相
{
if(abs(nox)!=2||abs(noy)!=2) return 0;
else if(map[oldx+nox/2][oldy+noy/2].Id!=NONE) return 0;
if(nowy==0||nowy==4||nowy==5||nowy==9)
if(nowx==2||nowx==6) break;
if(nowy==2||nowy==7)
if(nowx==0||nowx==4||nowx==8) break;
}
case 1: case 2:/*Shi*/士或仕
{
if(abs(nox)!=1||abs(noy)!=1) return 0;
if(nowy>2&&nowy<7||nowx<3||nowx>5) return 0;
break;
}
case 5: case 6: case 7: case 8: case 9: /*Soldier*/兵或卒
{
if(abs(nox)>0&&abs(noy)>0) return 0;
if(ChessId==GREEN&&GreenChess[0].y<3||ChessId==RED&&RedChess[0].y<3)
{
if(oldy>4)
{
if(nox==0&&noy!=1) return 0;
if(abs(nox)!=1&&noy==0) return 0;
}
if(oldy<5) if(nox!=0||noy!=1) return 0;
}
if(ChessId==GREEN&&GreenChess[0].y>6||ChessId==RED&&RedChess[0].y>6)
{
if(oldy<5)
{
if(nox==0&&noy!=-1) return 0;
if(abs(nox)!=1&&noy==0) return 0;
}
if(oldy>4) if(nox!=0||noy!=-1) return 0;
}
index=map[oldx][oldy].num;
if(ChessId==GREEN)
if(GreenChess[0].y<3&&GreenChess[index].y>4||GreenChess[0].y>6&&GreenChess[index].y<5)
GreenChess[index].FixLevel=ADVANCED_SOLDIER_LEVEL;
if(ChessId==RED)
if(RedChess[0].y<3&&RedChess[index].y>4||RedChess[0].y>6&&RedChess[index].y<5)
RedChess[index].FixLevel=ADVANCED_SOLDIER_LEVEL;//兵過河後等級值加1
break;
}
}
if(ChessId==map[nowx][nowy].Id) return 2;
else return 1;
}
用c語言寫的
Ⅱ 象棋對弈軟體是如何編制出來的
呵呵，開始我也覺得沒有破綻，後來發現了軟體也會出昏招。原來原理很簡單，只是把基本的開局定式以及常見的對弈拆解局面轉換成資料庫函數，當出現資料庫招數，便調出同類型的宏功能。說到底，只是電腦軟體做到了更多的對弈棋局收集，把相關的招數進行了數碼匯編。比如：仙人指路開局，軟體就會自動把存儲在資料庫中的符合這一定式類型的所有函數自動調出，選擇基本應招（根據用戶選手游戲難度不同，軟體也會選擇相應招數致勝比率和復雜程度）。所以按一般局面和軟體玩，就等於和一個熟讀兵法的謀士作戰，很難贏。你會有看不透，想不到的時候，軟體按步就班，資料庫就是它的眼睛和腦袋。但是編制軟體的並不是一流大師，他們手頭上有的都是找得到的棋局，但是棋盤千變萬化，有很多招式不可能存在軟體中，所以軟體也會碰到出昏招的時候。我們可以做一個小實驗，兩台電腦玩相同的象棋游戲，如果以A電腦進行先手，B電腦進行後手，以B電腦的招式來和A電腦下。百分之九十九的機率是和棋。如果我們用自己的方式操作B電腦和A電腦進行至中局（有一方有多子優勢），然後再讓兩台電腦自己下，肯定有一台電腦是輸的。你就會發現輸的電腦下的棋局很一般，因為它還是在以應對的形式開展，試問沒有優勢的情況下，那台資料庫一樣的電腦軟體會出現奇招嘛？也就是說軟體也是會輸的。我記得國際象棋那個深藍也輸給過卡斯帕羅夫，然後那個更深的藍贏了卡斯帕羅夫。還是贏在數據採集啊。
Ⅲ 象棋人機對戰怎麼設計的
象棋人機對戰可以使用搜索演算法來設計，如果使用貪心演算法或者minimax演算法。
貪心演算法：每次總是選擇最優先的走法。
minimax演算法：將游戲局面建立搜索樹，在搜索樹中搜索最優解。
還有其他演算法如alpha-beta剪枝演算法等，都是在minimax基礎上進行優化。
另外，象棋人機對戰還需要設計各種規則和評估函數來確定最優解。
Ⅳ 關於象棋殘局編程問題,怎麼實現對使用者下的棋的應對方法呢
樓上說的根本不對，沒有這么簡單，怎麼能靠隨機來讓電腦下棋呢！
象棋、圍棋、國際象棋等競技類棋類的電腦思維編程採用的是CBR基於案例推理（case based reasoning -- CBR）以及啟發搜索演算法（heuristic search algorithm）。
CBR應用在棋局的開始階段，一般是將開局棋譜作為case先進行數據化預處理，在人類對手下了一跡模手棋之後，電腦要搜索所有保存的case開局，找到最接近的幾種開局。然後需要運用啟發搜索演算法根據預定義的效用函數（utility function）來計算最有效的一種開局。
進入中局和你提到的殘局階段，電腦不再參考CBR數據，而是直接根據當前棋局形式，使用啟發搜索演算法查找效率值最高的下一步。這個過程中要考慮的東西非常多，比如啟發搜索演算法的目的函數定義（吃子、換子、平局、獲勝）、效用函數變化（每個子的效用值在不同的盤面下是會變的，比如象棋中的炮在子力越少的殘局中效用越小）、搜索寬度（當前棋局形勢的多少種下一手變化）以及搜索深度（每個搜索寬度中的下一手變化還要涉及的下面幾手變化）、計算順序（橫向搜索計算順序--Breadth-first search，縱向搜索計算順序--Depth-first search）等等等等。對於象棋和國際象棋的殘局來說其實姿虛緩是比較簡單的，因為目的函數是確定的、盤面所剩棋子不多導致搜索寬度不大。但是怎麼定義目的函數和效用函數是關鍵的問題。
一款棋類游戲的好壞，電腦對手的棋力高低，往往是由上述這些演算法因素決定的。比如在一款象棋游戲里，把電腦等級調成"簡單"，那麼就是把電腦的搜索深度調低，讓電腦不考慮很多步之後的盤面情況，或者調低電腦的效用函數值，讓電腦選擇效率低的下法。當年深藍的成功，就在於為國際象棋定義了精確的目的函數和效用函數，以及恰當的運用了大型計算機的並行計算能力來提高搜索寬度和搜索深度，從而保證了電腦的棋招給卡斯帕洛夫帶來了很大的挑戰。
以上提到的CBR和啟發搜索演算法只是兩種曾運用到棋類編程的演算法，除此之外還有很多演算法可以用到競技棋類編程中來，譽賀比如神經網路演算法等等。國際上，在人工智慧領域有很多類似的棋類編程演算法研究，相關論文不計期數，有興趣可以查閱有關期刊文獻。
Ⅳ 關於國際象棋中馬的貪心演算法證明 嚴重頭痛啊
【問題描述】
馬的遍歷問題。在8×8方格的棋盤上，從任意指定方格出發，為馬尋找一條走遍棋盤每一格並且只經過一次的一條路徑。
【初步設計】
首先這是一個搜索問題，運用深度優先搜索進行求解。演算法如下：
1、 輸入初始位置坐標x,y；
2、 步驟 c:
如果c>64輸出一個解，返回上一步驟c--
(x,y) ← c
計算(x,y)的八個方位的子結點，選出那此可行的子結點
循環遍歷所有可行子結點，步驟c++重復2
顯然（2）是一個遞歸調用的過程，大致如下：
void dfs(int x,int y,int count)
{
int i,tx,ty;
if(count>N*N)
{
output_solution();//輸入一個解
return;
}
for(I=0;i<8;++i)
{
tx=hn[i].x;//hn[]保存八個方位子結點
ty=hn[i].y;
s[tx][ty]=count;
dfs(tx,ty,count+1);//遞歸調用
s[tx][ty]=0;
}
}
這樣做是完全可行的，它輸入的是全部解，但是馬遍歷當8×8時解是非常之多的，用天文數字形容也不為過，這樣一來求解的過程就非常慢，並且出一個解也非常慢。
怎麼才能快速地得到部分解呢？
【貪心演算法】
其實馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個有名的演算法。在每個結點對其子結點進行選取時，優先選擇『出口』最小的進行搜索，『出口』的意思是在這些子結點中它們的可行子結點的個數，也就是『孫子』結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現『死』結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。這種演算法稱為為貪心演算法，也叫貪婪演算法或啟發示演算法，它對整個求解過程的局部做最優調整，它只適用於求較優解或者部分解，而不能求最優解。這樣的調整方法叫貪心策略，至於什麼問題需要什麼樣的貪心策略是不確定的，具體問題具體分析。實驗可以證明馬遍歷問題在運用到了上面的貪心策略之後求解速率有非常明顯的提高，如果只要求出一個解甚至不用回溯就可以完成，因為在這個演算法提出的時候世界上還沒有計算機，這種方法完全可以用手工求出解來，其效率可想而知。
在前面的演算法基礎之上，增添一些程序加以實現：
函數1：計算結點出口多少
int ways_out(int x,int y)
{
int i,count=0,tx,ty;
if(x<0||y<0||x>=N||y>=N||s[x][y]>0)
return -1;//-1表示該結點非法或者已經跳過了
for(i=0;i<8;++i)
{
tx=x+dx[i];
ty=y+dy[i];
if(tx<0||ty<0||tx>=N||ty>=N)
continue;
if(s[tx][ty]==0)
++count;
}
return count;
}
函數2：按結點出口進行排序
void sortnode(h_node *hn,int n)//採用簡單排序法，因為子結點數最多隻有8
{
int i,j,t;
h_node temp;
for(i=0;i<n;++i)
{
for(t=i,j=i+1;j<n;++j)
if(hn[j].waysout<hn[t].waysout)
t=j;
if(t>i)
{
temp=hn[i];
hn[i]=hn[t];
hn[t]=temp;
}
}
}
函數3：修改後的搜索函數
void dfs(int x,int y,int count)
{
int i,tx,ty;
h_node hn[8];
if(count>N*N)
{
output_solution();
return;
}
for(i=0;i<8;++i)//求子結點和出口
{
hn[i].x=tx=x+dx[i];
hn[i].y=ty=y+dy[i];
hn[i].waysout=ways_out(tx,ty);
}
sortnode(hn,8);
for(i=0;hn[i].waysout<0;++i);//不考慮無用結點
for(;i<8;++i)
{
tx=hn[i].x;
ty=hn[i].y;
s[tx][ty]=count;
dfs(tx,ty,count+1);
s[tx][ty]=0;
}
}
函數4：主調函數
void main()
{
int i,j,x,y;
for(i=0;i<N;++i)//初始化
for(j=0;j<N;++j)
s[i][j]=0;
printf("Horse jump while N=%d\nInput the position to start:",N);
scanf("%d%d",&x,&y);//輸入初始位置
while(x<0||y<0||x>=N||y>=N)
{
printf("Error! x,y should be in 0~%d",N-1);
scanf("%d%d",&x,&y);
}
s[x][y]=1;
dfs(x,y,2);//開始搜索
}
Ⅵ ai象棋原理ai象棋
在AI象棋原理是指人工智慧在象棋領域的應用原理。AI象棋的原理主要包括以下幾個方面：
搜索演算法：AI象棋通過搜索演算法來尋找最優的下棋策略。常用的搜索演算法包括極小化極大演算法（Minimax）、Alpha-Beta剪枝演算法等。這些演算法通過遍歷棋盤上可能的走法，評估每個走法的得分，並選擇得分最高的走法作為下一步的決策。
評估函數：AI象棋通過評估函數來評估當前棋局的好壞。評估函數會考慮棋子的位置、棋子的價值、棋局的控制力等因素，從而給出一個分數來表示當前棋局的優劣。搜索演算法會根據評估函數的分數來選擇最優的下棋策略。
學習演算法：AI象棋可以通過機器學習演算法來提高自己的下棋水平。例如，可以使用強化學習演算法來讓AI象棋與自己進行對弈，通過不斷的對弈和反饋，AI象棋可以逐漸學習到更好的下棋策略。
資料庫和開局庫：AI象棋可以利用大量的開局庫和資料庫來提高自己的下棋水平。開局庫包含了各種開局的走法和變化，AI象棋可以通過學習和記憶這些開局庫來在開局階段做出更好的決策。資料庫則包含了大量的棋局和對弈記錄，AI象棋可以通過分析這些數據來提高自己的下棋水平。
綜上所述，AI象棋的原理主要包括搜索演算法、評估函數、學習演算法以及資料庫和開局庫的應用。通過這些原理的結合，AI象棋可以在象棋領域表現出較高的水平。
象棋AI的原理主要基於兩個核心思想：博弈論和機器學習。
博弈論是一種研究決策過程的數學理論，它考慮了決策者之間的相互影響和策略選擇，通過預測不同決策可能產生的結果，來幫助決策者做出更好的選擇。在象棋AI中，博弈論被用來模擬人類棋手的思維過程，通過推演棋局的變化，找到最優的走法。
機器學習則是通過大量數據的訓練，讓AI學會如何在下棋時進行決策。通過學習人類棋譜和自對弈的數據，AI可以逐漸優化自己的下棋策略，提高自己的勝率。
具體來說，象棋AI的實現通常包括以下步驟：
1. 數據收集：收集大量的象棋對局數據，包括人類棋譜和AI訓練的數據。
2. 特徵工程：將每一局棋的走法、當前局面、歷史信息等作為特徵，用於後續模型的訓練。
3. 模型訓練：使用深度學習演算法（如神經網路）對特徵進行訓練，讓AI逐漸學習到更優的下棋策略。
4. 模型評估：通過與人類棋手對弈或者與其他AI進行對戰，評估AI的棋力水平。
通過以上步驟，象棋AI可以在不斷的學習和優化中，逐漸提高自己的棋力水平。
傳統ai使用的是阿爾法貝塔剪枝演算法和啟發式搜索函數，現在ai用的神經網路演算法審局