先弄明白數(shù)據(jù)的結(jié)構(gòu)：
創(chuàng)新互聯(lián)建站主營(yíng)濟(jì)寧網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,成都app軟件開發(fā)公司,濟(jì)寧h5成都微信小程序搭建,濟(jì)寧網(wǎng)站營(yíng)銷推廣歡迎濟(jì)寧等地區(qū)企業(yè)咨詢
MantisChessDef.h里的東西一定要先看一下， 否則會(huì)摸不到頭腦的。
還有棋盤坐標(biāo)：
象棋棋盤大小9x10,為了便于編程，規(guī)定棋盤每條邊留有一個(gè)元素的邊界。
這樣棋盤大?。òㄟ吔纾┳兂?1x12。棋盤x坐標(biāo)軸向右，y軸向下。
黑棋永遠(yuǎn)在上方，在標(biāo)準(zhǔn)開局時(shí)左上角的黑車坐標(biāo)是（1，1）。
局面用這三個(gè)變量表示:
static POINT g_pointChessman[32]; //棋子坐標(biāo)
static int g_iChessmanMap[11][12]; //棋位狀態(tài)
static int g_iSide; //輪到哪方走
智能部分有幾個(gè)函數(shù)的前三個(gè)參數(shù)就是這個(gè)東西, 應(yīng)該不難理解吧?
---------------------------------------------------------------------------------------
search函數(shù):
先說(shuō)明一下， 經(jīng)常有朋友問(wèn)我要原理, 但我公開源代碼是給大家一個(gè)參考， 而不是什么教程，所以我不想說(shuō)那些理論的東西。
基本原理是α-β搜索， 很多人工智能的教科書上都有講到， 沒看過(guò)的的趕快去找一本來(lái)啃一啃；
雖然這些書上的文字大多晦澀難懂，但畢竟講得明明白白。
沒有書的朋友請(qǐng)發(fā)揮一下主觀能動(dòng)性， 去找一找，不要來(lái)問(wèn)我要， 因?yàn)槲乙矝]有。
我在這里只分析一下search函數(shù):
弄懂α-β搜索后來(lái)看看這個(gè)博弈樹， 看怎么編程實(shí)現(xiàn)它。
先規(guī)定一下， 我們用一個(gè)整數(shù)表示局面的好壞.
這個(gè)數(shù)越大說(shuō)明局面對(duì) "走棋方" 越有利，0表示雙方實(shí)力相等。
1a( 1) ┬ 2a(-1) ┬ 3a(-1)
│ └ 3b( 1)
└ 2b(-5) ┬ 3c( 2)
├ 3d(-4)
└ 3e( 5)
分析一下這棵樹，有這么個(gè)特點(diǎn): 父結(jié)點(diǎn)的值 = -MAX(子結(jié)點(diǎn)的值)
我們還知道1、每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)局面。2、底層的結(jié)點(diǎn)的值是"估"出來(lái)的。
于是我們可以寫出偽代碼了:
偽代碼: 搜索一個(gè)結(jié)點(diǎn)下的分支， 得到這個(gè)結(jié)點(diǎn)的值。
參數(shù): 局面，搜索深度
返回值:結(jié)點(diǎn)的值
int search(局面，int depth)
{
if(depth!=0)//不是底層結(jié)點(diǎn)
{
枚舉出所有子結(jié)點(diǎn)(列出所有走法);
int count=子結(jié)點(diǎn)數(shù)；
int maxvalue= -∞;
for(int i=0;icount;i++)//遍歷所有結(jié)點(diǎn)
{
算出子結(jié)點(diǎn)局面;
maxvalue=max(maxvalue，search(子結(jié)點(diǎn)局面,depth-1));
}
return -maxvalue;
}
else //是底層結(jié)點(diǎn)
{
return 估計(jì)值;
}
}
這就是搜索算法的框架， 用到了遞歸。
MantisChess的智能部分函數(shù)都在MantisChessThink.cpp里， 其中search是搜索， 跟上面的這個(gè)search差不多，我把它c(diǎn)opy出來(lái)注釋一下：
int Search(int tmap[11][12],POINT tmanposition[32],int tside,int man, POINT point,int upmax,int depth)
{
//前面的三個(gè)參數(shù)就是局面。
//man 和point 是走法，用來(lái)計(jì)算本結(jié)點(diǎn)的局面。 這里是把計(jì)算局面放在函數(shù)的開頭，跟上面的偽代碼不太一樣。
//upmax: up - 上一層， max - 最大值， 這是α-β的剪枝用到的東西， 后面再講。
//depth: 搜索深度
int ate,cur,maxvalue,curvalue,xs,ys;
int count;
//#####################這一段是計(jì)算本結(jié)點(diǎn)的局面#########################################
ate=32;
//移動(dòng)棋子:
xs=tmanposition[man].x;ys=tmanposition[man].y; //原坐標(biāo)
if (SideOfMan[tmap[point.x][point.y]]==!tside) //目標(biāo)點(diǎn)有對(duì)方的棋子
{
ate=tmap[point.x][point.y]; //記錄下被吃掉的棋子
if(ate==0 || ate==16)
{
return 9999;
}
tmanposition[ate].x=0; //目標(biāo)點(diǎn)的棋子被吃掉
}
tmap[point.x][point.y]=man; //這兩行是:
tmap[xs][ys]=32; //在map上的移動(dòng)
tmanposition[man]=point;
tside=!tside;
//####################################################################################
depth--;
if(depth0) //不是底層結(jié)點(diǎn)
{
int chessman[125];
POINT targetpoint[125];
if(EnumList(tmap,tmanposition,tside,chessman,targetpoint,count)) //枚舉出所有子結(jié)點(diǎn)(列出所有走法)
{
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//這里是剪枝(不是α-β剪枝), 原理是在正式搜索之前先用較淺的搜索來(lái)得到誤差較大的值
//然后根據(jù)這些值來(lái)對(duì)子結(jié)點(diǎn)排序， 只保留最好的S_WIDTH個(gè)結(jié)點(diǎn)進(jìn)行正式搜索。
//顯然，這個(gè)剪枝有一定的風(fēng)險(xiǎn)
if(depth=2 countS_WIDTH+2)
{
int value[125];
cur=0;
maxvalue=-10000;
while(cur count)
{
curvalue=Search(tmap,tmanposition,tside,chessman[cur],targetpoint[cur],-10000,depth-2);
value[cur]=curvalue;
if(curvaluemaxvalue)maxvalue=curvalue;
cur ++;
}
::Mantis_QuickSort(value,chessman,targetpoint,0,count-1); //排序
count=S_WIDTH;//剪枝
}
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
maxvalue=-10000;
cur=0;
while(cur count)
{
curvalue=Search(tmap,tmanposition,tside,chessman[cur],targetpoint[cur],maxvalue,depth);
if(curvaluemaxvalue)maxvalue=curvalue;
if(curvalue=-upmax)goto _ENDSUB; //α-β剪枝, 符合剪枝條件的就Cut掉。 這里用了goto語(yǔ)句了， 千萬(wàn)別學(xué)我。
cur ++;
}
}
else maxvalue=9800;
}
else //是底層結(jié)點(diǎn)
{
maxvalue=Value(tmap,tmanposition,tside); //估值
}
_ENDSUB:
//返回之前要恢復(fù)父結(jié)點(diǎn)的局面
//####################################################################################
tmanposition[man].x=xs; //這兩行是:
tmanposition[man].y=ys; //在face上的恢復(fù)
tmap[xs][ys]=man; //在map上的恢復(fù)
if(ate!=32)
{
tmanposition[ate]=point;
tmap[point.x][point.y]=ate;
}
else tmap[point.x][point.y]=32;
tside=!tside;
//####################################################################################
return -maxvalue;
}
上面的代碼用到了α-β剪枝, 舉個(gè)例子就明白了:
還是這個(gè)博弈樹，從上往下遍歷。
1a( 1) ┳ 2a(-1) ┳ 3a(-1)
┃ ┗ 3b( 1)
┗ 2b(-5) ┯ 3c( 2)
├ 3d(-4)
└ 3e( 5)
2a遍歷完后 upmax=-1, 繼續(xù)遍歷完3c后返回2b， 發(fā)現(xiàn)3c=2-upmax, 這時(shí)就不用管3d和3e了, 因?yàn)闊o(wú)論他們的值是多少 2b=-max(3c,3d,3e)2a 一定成立,
也就是說(shuō)2b可以安全地剪掉。這就是α-β剪枝。
從上面的代碼來(lái)看我的MantisChess算法與標(biāo)準(zhǔn)的α-β剪枝搜索并沒有什么不同， 只不過(guò)加了排序和剪枝而已。
package com.plague.math;
import java.lang.Math;
public class Chess {
private final static int CHESS_NUMBER = 64;
private int total;
public Chess () {
System.out.println("國(guó)王的賞賜，其實(shí)，問(wèn)題是這樣的：" +
"在國(guó)際象棋的棋盤上，第一格放一粒米，第二格放2粒米，第三個(gè)放四粒米。。。最后國(guó)王要賞賜多少米");
for (int i = 0; i CHESS_NUMBER; i++) {
total += Math.pow(2.0,(double)i);
}
System.out.println("國(guó)王的賞賜是："+total);
}
public static void main(String[] args) {
Chess c1 = new Chess();
}
}
呵呵，開始我也覺得沒有破綻，后來(lái)發(fā)現(xiàn)了軟件也會(huì)出昏招。原來(lái)原理很簡(jiǎn)單，只是把基本的開局定式以及常見的對(duì)弈拆解局面轉(zhuǎn)換成數(shù)據(jù)庫(kù)函數(shù)，當(dāng)出現(xiàn)數(shù)據(jù)庫(kù)招數(shù)，便調(diào)出同類型的宏功能。說(shuō)到底，只是電腦軟件做到了更多的對(duì)弈棋局收集，把相關(guān)的招數(shù)進(jìn)行了數(shù)碼匯編。比如：仙人指路開局，軟件就會(huì)自動(dòng)把存儲(chǔ)在數(shù)據(jù)庫(kù)中的符合這一定式類型的所有函數(shù)自動(dòng)調(diào)出，選擇基本應(yīng)招（根據(jù)用戶選手游戲難度不同，軟件也會(huì)選擇相應(yīng)招數(shù)致勝比率和復(fù)雜程度）。所以按一般局面和軟件玩，就等于和一個(gè)熟讀兵法的謀士作戰(zhàn)，很難贏。你會(huì)有看不透，想不到的時(shí)候，軟件按步就班，數(shù)據(jù)庫(kù)就是它的眼睛和腦袋。但是編制軟件的并不是一流大師，他們手頭上有的都是找得到的棋局，但是棋盤千變?nèi)f化，有很多招式不可能存在軟件中，所以軟件也會(huì)碰到出昏招的時(shí)候。我們可以做一個(gè)小實(shí)驗(yàn)，兩臺(tái)電腦玩相同的象棋游戲，如果以A電腦進(jìn)行先手，B電腦進(jìn)行后手，以B電腦的招式來(lái)和A電腦下。百分之九十九的機(jī)率是和棋。如果我們用自己的方式操作B電腦和A電腦進(jìn)行至中局（有一方有多子優(yōu)勢(shì)），然后再讓兩臺(tái)電腦自己下，肯定有一臺(tái)電腦是輸?shù)?。你就?huì)發(fā)現(xiàn)輸?shù)碾娔X下的棋局很一般，因?yàn)樗€是在以應(yīng)對(duì)的形式開展，試問(wèn)沒有優(yōu)勢(shì)的情況下，那臺(tái)數(shù)據(jù)庫(kù)一樣的電腦軟件會(huì)出現(xiàn)奇招嘛？也就是說(shuō)軟件也是會(huì)輸?shù)摹Ｎ矣浀脟?guó)際象棋那個(gè)深藍(lán)也輸給過(guò)卡斯帕羅夫，然后那個(gè)更深的藍(lán)贏了卡斯帕羅夫。還是贏在數(shù)據(jù)采集啊。
import java.awt.*;
import javax.swing.*;
public class Chessboard extends JApplet {
int baseXPosition, baseYPosition;
int currentXPosition, currentYPosition;
public void init() {
baseXPosition = 40; // 棋盤的開始x位置
baseYPosition = 40; // 棋盤的開始y位置
setBackground(Color.black); // 設(shè)置背景顏色黑色
}
public void paint(Graphics g) { // 繪制棋盤
currentXPosition = baseXPosition; // currentXPosition當(dāng)前的x位置
currentYPosition = baseYPosition; // currentYPosition當(dāng)前的y位置
for (int row = 0; row 8; row++) {
currentXPosition = baseXPosition + row * 40;
for (int column = 0; column 8; column++) {
if ((column + row) % 2 == 0)
g.setColor(Color.white); // 設(shè)置棋盤格子的顏色
else
g.setColor(Color.red); // 設(shè)置棋盤格子的顏色
currentYPosition = baseXPosition + column * 40;
g.drawRect(currentXPosition,currentYPosition,40,40);//;代碼4 //在當(dāng)前位置繪制棋盤的格子；每個(gè)格子的大小是40*40像
g.fillRect(currentXPosition,currentYPosition,40,40);
}
}
}
}
import java.awt.Color;
import javax.swing.*;
public class Chess extends JPanel
{// 繼承面板類
public Chess(int grids,int gridsize)
{//grids:行數(shù)和列數(shù), gridsize:單元格的高和寬
super(null);
for(int i=0; igrids; i++)
{
for(int j=0; jgrids; j++)
{
JLabel l = new JLabel();//生成標(biāo)簽實(shí)例
l.setSize(gridsize,gridsize);
l.setLocation(i*gridsize,j*gridsize);
if((i+j)%2==0)
{ //當(dāng)小方格的坐標(biāo)和剛好是偶數(shù)時(shí)，
l.setBackground(Color.black); //設(shè)置為方格為黑色
l.setOpaque(true); //設(shè)置為不透明
}
l.setBorder(BorderFactory.createLineBorder(Color.black)); //設(shè)置邊界為黑色
add(l);//將l標(biāo)簽添加到面板
}
}
}
public static void main(String[] args)
{
JFrame f = new JFrame();
f.setSize(658,677); //邊框的長(zhǎng)和寬
f.setLocationRelativeTo(null); //設(shè)置窗口相對(duì)于指定組件的位置
f.add(new Chess(8,80));
f.setVisible(true);
}
}
重慶分公司
重慶分公司
