一、? 問題介紹

實(shí)現(xiàn)交互式五子棋

采用博弈算法

二、? 程序設(shè)計(jì)與算法分析

l?? 博弈問題簡介：

– 雙人對弈,輪流走步。

– 信息完備,雙方所得到的信息是一樣的。

– 零和,即對一方有利的棋,對另一方肯定是不利的,不存在對雙方均有利或無利的棋。

l?? 博弈的特性：

– 兩個(gè)棋手交替地走棋 ;

– 比賽的最終結(jié)果,是贏、輸和平局中的一種;

– 可用圖搜索技術(shù)進(jìn)行,但效率很低;?

– 博弈的過程,是尋找置對手于必?cái)B(tài)的過程;

– 雙方都無法干預(yù)對方的選擇。

l?? 結(jié)論：五子棋問題屬于博弈問題。

l?? 博弈問題的兩種常用算法思路：

– 與或圖直接搜索法：搜索枚舉雙方棋手的下棋方法，構(gòu)建與或圖直接搜索出答案 ;

u? 與或圖簡介：

與或圖是一個(gè)超圖,節(jié)點(diǎn)間通過連接符連接。

u? 與或圖節(jié)點(diǎn)分類：

n??能解節(jié)點(diǎn)：

???終節(jié)點(diǎn)是能解節(jié)點(diǎn) ?

???若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)時(shí),當(dāng)且僅當(dāng)其子節(jié)點(diǎn)至少有一能解時(shí),該非終結(jié)點(diǎn)才能解。

???若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí),當(dāng)且僅當(dāng)其子節(jié)點(diǎn)均能解時(shí), 該非終節(jié)點(diǎn)才能解。

n??不能解節(jié)點(diǎn)

???沒有后裔的非終節(jié)點(diǎn)是不能解節(jié)點(diǎn)。?

???若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn),當(dāng)且僅當(dāng)所有子節(jié)點(diǎn)均不能解時(shí), ?該非終節(jié)點(diǎn)才不能解。 ?

???若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí),當(dāng)至少有一個(gè)子節(jié)點(diǎn)不能解時(shí), 該非終節(jié)點(diǎn)才不能解。

u? 與或圖搜索算法：

n??1.建立搜索圖G:=s,計(jì)算q(s)=h(s), If Goal(s)Then M(s, Solved) ?

n??2.Until S 被標(biāo)記為Solved, Do: ?

n??3.Begin ;擴(kuò)展 ?

n??4.G’:= Find(g) ; G’為根據(jù)連接符找到的待擴(kuò)展局部解圖 ?

n??5.n := G’中任一非終結(jié)點(diǎn) ?

n??6.{nj}:=Expand(n), 計(jì)算q(nj)=h(nj),If Goal(nj) Then M(nj,solved) ?

n??7.S:={n} ;回溯,修改指針和耗散值 ?

n??8.Until S為空, Do: ?

n??9.Begin ?

n??10.Remove(m, S) If m的子結(jié)點(diǎn)不在s中 ;子結(jié)點(diǎn)耗散值已確定 3/21/2014 第二章 與或圖搜索

n??11.修改m的耗散值:?對m的每個(gè)連接符i{n1i,n2i,...,nki},計(jì)算qi(m)=Ci+q(n1i)+...+q(nki)q(m):=min qi (m)?修改m的指針到min qi (m)對應(yīng)的連接符上?If(nji,Solved) THEN M(m,Solved) ;某一個(gè)連接符已解決

n??12.If M(m,Solved) or q(m)被修改 Then Add(ma,S), ma為m的所有先輩節(jié)點(diǎn)

n??13.End

n??14.End

u? 兩個(gè)過程：

n??圖生成過程，即擴(kuò)展節(jié)點(diǎn)，從最優(yōu)的局部途中選擇一個(gè)節(jié)點(diǎn)擴(kuò)展

n??計(jì)算耗散值的過程?– 對當(dāng)前的局部圖從新計(jì)算耗散值

u? 算法實(shí)現(xiàn)：

n??終結(jié)點(diǎn)為某一方勝利的狀態(tài)：可用true或者false分別標(biāo)記勝負(fù)

n??利用與或圖搜索更新到根節(jié)點(diǎn)

n??若根節(jié)點(diǎn)為false表示當(dāng)前棋局狀態(tài)為必?cái)∏闆r。

n??若根節(jié)點(diǎn)為true表示當(dāng)前棋局為必勝狀態(tài)。

n??根節(jié)點(diǎn)總是盡量選擇狀態(tài)為true的子節(jié)點(diǎn)進(jìn)行狀態(tài)轉(zhuǎn)移。

u? 算法局限性：

n??搜索的沒一層都要窮舉所有可能的情況，很容易引起組合爆炸的問題。

?

– 極大極小搜索算法：利用優(yōu)先深度的搜索，通過對局勢進(jìn)行評估來選擇狀態(tài)轉(zhuǎn)移的方向。

u? 極大極小搜索簡介：

n??下棋的雙方是對立的;

n??一方為“正方”,這類節(jié)點(diǎn)稱為“MAX”節(jié)點(diǎn); ?

n??另一方為“反方”,這類節(jié)點(diǎn)稱為“MIN”節(jié)點(diǎn); ?

n??正方從所有子節(jié)點(diǎn)中,選取具有最大評估值的節(jié)點(diǎn)進(jìn)行狀態(tài)轉(zhuǎn)移; ?

n??反方從其所有子節(jié)點(diǎn)中,選取具有最小評估值的節(jié)點(diǎn)驚醒狀態(tài)轉(zhuǎn)移; ?

n??反復(fù)進(jìn)行這種選取,就可以得到雙方各個(gè)節(jié)點(diǎn)的評估值。這種確定棋步的方法,稱為極大極小搜索法。 ?

u? 對各個(gè)局面進(jìn)行評估：

n??評估的目的:對后面的狀態(tài)提前進(jìn)行考慮,并且以各種狀態(tài)的評估值為基礎(chǔ)作出最好的走棋選擇。?????? ?

n??評估的方法:用評價(jià)函數(shù)對棋局進(jìn)行評估。贏的評估值設(shè)為+∞,輸?shù)脑u估值設(shè)為-∞,平局的評估值設(shè)為0。 ?

n??評估的標(biāo)準(zhǔn):由于下棋的雙方是對立的,只能選擇其中一 方為評估的標(biāo)準(zhǔn)方。 ??? 所有評估站在正方的立場!

u? 極大極小搜索算法：

n??1.T:=(s,max), Open:=(s),Close:=();?

n??2.Lopp1: ?????????????? ;擴(kuò)展深度至d

n??3.If Open=() Then Goto Loop2?

n??4.N:=First(Open),Remove(n,Open), Add(n,Close)?

n??5.If F(n)=-∞, +∞, 0, Then GotoLoop1 ;?????????????????????????????? 可以被判定

Else {ni}:=Expand(n), Add({ni},T)?

If d(ni)<kThen Add(ni,Open), Goto Loop1

Else 計(jì)算f(ni), Goto Loop1

n??6.Loop2: ???????????????????????????????? ;賦值

n??7.If Close=() Then Goto Loop3

Else np:=First(Close)

n??8.If (np Is Max) And (F(npi)有值) ???????????????????? ; npi是np的子結(jié)點(diǎn),且都有值

Then f(np):=maxf(npi), Remove(np,Close)

If (np Is MIN)And (f(npi)有值) ????????????????????????? ; npi是np的子結(jié)點(diǎn),且都有值

THEN f(np):=minf(npi), Remove(np,Close)?

n??9.Goto Loop2

n??10.Loop3:?

n??10.If f(s)有值 Then Exit(End or M(Move, T))?????????????????? ;s被賦值,結(jié)束該步

u? alpha-beta剪枝：在極小極大法中,必須求出所有終端節(jié)點(diǎn)的評估值,當(dāng)預(yù)先考慮的棋步比較多時(shí),計(jì)算量會大大增加。為了提高搜索的效率,引入了通過對評估值的上下限進(jìn)行估計(jì)、從而減少需進(jìn)行評估的節(jié)點(diǎn)范圍。

n??MAX節(jié)點(diǎn)的評估下限值:

作為正方出現(xiàn)的MAX節(jié)點(diǎn),假設(shè)它的MIN子節(jié)點(diǎn)有N個(gè),那么當(dāng)它的第一

個(gè)MIN子節(jié)點(diǎn)的評估值為alpha時(shí),則對于其它的子節(jié)點(diǎn),如果有高過alpha的, 就取那最高的值作為該MAX節(jié)點(diǎn)的評估值;如果沒有,則該MAX節(jié)點(diǎn)的評估值為alpha。總之,該MAX節(jié)點(diǎn)的評估值不會低于alpha,這個(gè)alpha就稱為該MAX節(jié) 點(diǎn)的評估下限值。

n??MIN節(jié)點(diǎn)的評估上限值:

作為反方出現(xiàn)的MIN節(jié)點(diǎn),假設(shè)它的MAX子節(jié)點(diǎn)有N個(gè),那么當(dāng)它的第一 個(gè)MAX子節(jié)點(diǎn)的評估值為beta時(shí),則對于其它子節(jié)點(diǎn),如果有低于beta的,就取那個(gè)低于beta的值作為該MIN節(jié)點(diǎn)的評估值;如果沒有,則該MIN節(jié)點(diǎn)的評估值取beta總之,該MIN節(jié)點(diǎn)的評估值不會高過beta這個(gè)beta就稱為該MIN節(jié)點(diǎn)的評估上限值。

n??剪枝條件：

???后輩節(jié)點(diǎn)的beta值≤祖先節(jié)點(diǎn)的alpha值時(shí)，alpha剪枝。

???– 后輩節(jié)點(diǎn)的alpha值≥祖先節(jié)點(diǎn)的beta值時(shí)，beta剪枝。

?

l?? 五子棋算法分析：

u? 因?yàn)槊恳徊娇勺咂宓奈恢煤芏?#xff0c;所以不適合直接使用與或圖搜索，在這里使用了極大極小搜索，并用alpha-beta剪枝進(jìn)行了優(yōu)化。

u? 為方便實(shí)現(xiàn)剪枝，而不是全部拓展所有節(jié)點(diǎn)，使用了dfs的搜索方式。

u? 維護(hù)一個(gè)當(dāng)前棋局的數(shù)組和一個(gè)當(dāng)前節(jié)點(diǎn)下一層可能走的點(diǎn)的集合。因?yàn)樯婕暗交厮?#xff0c;需要一種高效的插入和刪除的數(shù)據(jù)結(jié)構(gòu)，我這里采用了HashSet來作為集合的數(shù)據(jù)結(jié)構(gòu)。

u? 將當(dāng)前所有下過棋子的點(diǎn)的相鄰點(diǎn)放入到下一層待搜索的集合中，而不是搜索整個(gè)棋盤，這樣縮小了搜索的范圍，減少了擴(kuò)展的節(jié)點(diǎn)數(shù)。

u? 評估函數(shù)使用當(dāng)前局面連在一線上棋子的個(gè)數(shù)進(jìn)行打分，連在一起的個(gè)數(shù)越多得分越高。

u? 利用java的drawingPanel庫實(shí)現(xiàn)了圖形界面。附drawingPanel下載地址：http://www.buildingjavaprograms.com/DrawingPanel.java

?

import java.util.*; import java.awt.*; import java.awt.event.*; import javax.swing.*;public class Ai3{private static DrawingPanel panel=new DrawingPanel(700,700);private static Graphics g=panel.getGraphics();public static boolean isBlack=false;//標(biāo)志棋子的顏色public static int[][] chessBoard=new int[17][17]; //棋盤棋子的擺放情況：0無子，1黑子，－1白子private static HashSet<Point> toJudge=new HashSet<Point>(); // ai可能會下棋的點(diǎn)private static int dr[]=new int[]{-1,1,-1,1,0,0,-1,1}; // 方向向量private static int dc[]=new int[]{1,-1,-1,1,-1,1,0,0}; //方向向量public static final int MAXN=1<<28;public static final int MINN=-MAXN; private static int searchDeep=4; //搜索深度private static final int size=15; //棋盤大小public static boolean isFinished=false;public static void main(String[] args){MyMouseEvent myMouseEvent=new MyMouseEvent();panel.addMouseListener(myMouseEvent);initChessBoard();}// 初始化函數(shù)，匯圖public static void initChessBoard(){isBlack=false;toJudge.clear();panel.clear();panel.setBackground(Color.GRAY);g.setColor(Color.BLACK);for(int i=45;i<=675;i+=45){g.drawLine(45,i,675,i);g.drawLine(i,45,i,675);}// 棋盤上的五個(gè)定位基本點(diǎn)，圖中的小圓圈g.setColor(Color.BLACK);g.fillOval(353,353,14,14);g.fillOval(218,218,14,14);g.fillOval(488,218,14,14);g.fillOval(488,488,14,14);g.fillOval(218,488,14,14);// 初始化棋盤for(int i=1;i<=15;++i)for(int j=1;j<=15;++j)chessBoard[i][j]=0;// ai先手g.fillOval(337,337,45,45);chessBoard[8][8]=1;for(int i=0;i<8;++i)if(1<=8+dc[i] && 8+dc[i]<=size && 1<=8+dr[i] && 8+dr[i]<=size){Point now=new Point(8+dc[i],8+dr[i]);if(!toJudge.contains(now))toJudge.add(now);}isBlack=false;}// 通過點(diǎn)擊事件，得到棋子位置進(jìn)行下棋public static void putChess(int x,int y){if(isBlack)g.setColor(Color.BLACK);else g.setColor(Color.WHITE);g.fillOval(x-22,y-22,45,45);chessBoard[y/45][x/45]=isBlack?1:-1;if(isEnd(x/45,y/45)){String s=Ai3.isBlack?"黑子勝":"白子勝";JOptionPane.showMessageDialog(null,s);isBlack=true;initChessBoard();}else{Point p=new Point(x/45,y/45);if(toJudge.contains(p))toJudge.remove(p);for(int i=0;i<8;++i){Point now=new Point(p.x+dc[i],p.y+dr[i]);if(1<=now.x && now.x<=size && 1<=now.y && now.y<=size && chessBoard[now.y][now.x]==0)toJudge.add(now);}// Iterator it=toJudge.iterator();// while(it.hasNext()){// Point now=(Point)it.next();// System.out.printf("%d\t%d\n",now.x,now.y);// }// System.out.printf("*******************************************************\n");}}// ai博弈入口函數(shù)public static void myAI(){Node node=new Node();dfs(0,node,MINN,MAXN,null);Point now=node.bestChild.p;// toJudge.remove(now);putChess(now.x*45,now.y*45);isBlack=false;}// alpha beta dfsprivate static void dfs(int deep,Node root,int alpha,int beta,Point p){if(deep==searchDeep){root.mark=getMark();// System.out.printf("%d\t%d\t%d\n",p.x,p.y,root.mark);return;}ArrayList<Point> judgeSet=new ArrayList<Point>();Iterator it=toJudge.iterator();while(it.hasNext()){Point now=new Point((Point)it.next());judgeSet.add(now);}it=judgeSet.iterator();while(it.hasNext()){Point now=new Point((Point)it.next());Node node=new Node();node.setPoint(now);root.addChild(node);boolean flag=toJudge.contains(now);chessBoard[now.y][now.x]=((deep&1)==1)?-1:1;if(isEnd(now.x,now.y)){root.bestChild=node;root.mark=MAXN*chessBoard[now.y][now.x];chessBoard[now.y][now.x]=0;return;}boolean flags[]=new boolean[8]; //標(biāo)記回溯時(shí)要不要?jiǎng)h掉Arrays.fill(flags,true);for(int i=0;i<8;++i){Point next=new Point(now.x+dc[i],now.y+dr[i]);if(1<=now.x+dc[i] && now.x+dc[i]<=size && 1<=now.y+dr[i] && now.y+dr[i]<=size && chessBoard[next.y][next.x]==0){if(!toJudge.contains(next)){toJudge.add(next);}else flags[i]=false;}}if(flag) toJudge.remove(now);dfs(deep+1,root.getLastChild(),alpha,beta,now);chessBoard[now.y][now.x]=0;if(flag)toJudge.add(now);for(int i=0;i<8;++i)if(flags[i])toJudge.remove(new Point(now.x+dc[i],now.y+dr[i]));// alpha beta剪枝// min層if((deep&1)==1){if(root.bestChild==null || root.getLastChild().mark<root.bestChild.mark){root.bestChild=root.getLastChild();root.mark=root.bestChild.mark;if(root.mark<=MINN)root.mark+=deep;beta=Math.min(root.mark,beta);}if(root.mark<=alpha)return;}// max層else{if(root.bestChild==null || root.getLastChild().mark>root.bestChild.mark){root.bestChild=root.getLastChild();root.mark=root.bestChild.mark;if(root.mark==MAXN)root.mark-=deep;alpha=Math.max(root.mark,alpha);}if(root.mark>=beta)return;}}// if(deep==0) System.out.printf("******************************************\n");}public static int getMark(){int res=0;for(int i=1;i<=size;++i){for(int j=1;j<=size;++j){if(chessBoard[i][j]!=0){// 行boolean flag1=false,flag2=false;int x=j,y=i;int cnt=1;int col=x,row=y;while(--col>0 && chessBoard[row][col]==chessBoard[y][x]) ++cnt;if(col>0 && chessBoard[row][col]==0) flag1=true;col=x;row=y;while(++col<=size && chessBoard[row][col]==chessBoard[y][x]) ++cnt;if(col<=size && chessBoard[row][col]==0) flag2=true;if(flag1 && flag2)res+=chessBoard[i][j]*cnt*cnt;else if(flag1 || flag2) res+=chessBoard[i][j]*cnt*cnt/4; if(cnt>=5) res=MAXN*chessBoard[i][j];// 列col=x;row=y;cnt=1;flag1=false;flag2=false;while(--row>0 && chessBoard[row][col]==chessBoard[y][x]) ++cnt;if(row>0 && chessBoard[row][col]==0) flag1=true;col=x;row=y;while(++row<=size && chessBoard[row][col]==chessBoard[y][x]) ++cnt;if(row<=size && chessBoard[row][col]==0) flag2=true;if(flag1 && flag2)res+=chessBoard[i][j]*cnt*cnt;else if(flag1 || flag2)res+=chessBoard[i][j]*cnt*cnt/4;if(cnt>=5) res=MAXN*chessBoard[i][j];// 左對角線col=x;row=y;cnt=1;flag1=false;flag2=false;while(--col>0 && --row>0 && chessBoard[row][col]==chessBoard[y][x]) ++cnt;if(col>0 && row>0 && chessBoard[row][col]==0) flag1=true;col=x;row=y;while(++col<=size && ++row<=size && chessBoard[row][col]==chessBoard[y][x]) ++cnt;if(col<=size && row<=size && chessBoard[row][col]==0) flag2=true;if(flag1 && flag2) res+=chessBoard[i][j]*cnt*cnt;else if(flag1 || flag2) res+=chessBoard[i][j]*cnt*cnt/4;if(cnt>=5) res=MAXN*chessBoard[i][j];// 右對角線col=x;row=y;cnt=1;flag1=false;flag2=false;while(++row<=size && --col>0 && chessBoard[row][col]==chessBoard[y][x]) ++cnt;if(row<=size && col>0 && chessBoard[row][col]==0) flag1=true;col=x;row=y;while(--row>0 && ++col<=size && chessBoard[row][col]==chessBoard[y][x]) ++cnt;if(row>0 && col<=size && chessBoard[i][j]==0) flag2=true;if(flag1 && flag2)res+=chessBoard[i][j]*cnt*cnt;else if(flag1 || flag2) res+=chessBoard[i][j]*cnt*cnt/4;if(cnt>=5) res=MAXN*chessBoard[i][j];}}}return res;}// for debugpublic static void debug(){for(int i=1;i<=size;++i){for(int j=1;j<=size;++j){System.out.printf("%d\t",chessBoard[i][j]);}System.out.println("");}}// 判斷是否一方取勝public static boolean isEnd(int x,int y){// 判斷一行是否五子連珠int cnt=1;int col=x,row=y;while(--col>0 && chessBoard[row][col]==chessBoard[y][x]) ++cnt;col=x;row=y;while(++col<=size && chessBoard[row][col]==chessBoard[y][x]) ++cnt;if(cnt>=5){isFinished=true;return true;}// 判斷一列是否五子連珠col=x;row=y;cnt=1;while(--row>0 && chessBoard[row][col]==chessBoard[y][x]) ++cnt;col=x;row=y;while(++row<=size && chessBoard[row][col]==chessBoard[y][x]) ++cnt;if(cnt>=5){isFinished=true;return true;}// 判斷左對角線是否五子連珠col=x;row=y;cnt=1;while(--col>0 && --row>0 && chessBoard[row][col]==chessBoard[y][x]) ++cnt;col=x;row=y;while(++col<=size && ++row<=size && chessBoard[row][col]==chessBoard[y][x]) ++cnt;if(cnt>=5){isFinished=true;return true;}// 判斷右對角線是否五子連珠col=x;row=y;cnt=1;while(++row<=size && --col>0 && chessBoard[row][col]==chessBoard[y][x]) ++cnt;col=x;row=y;while(--row>0 && ++col<=size && chessBoard[row][col]==chessBoard[y][x]) ++cnt;if(cnt>=5){isFinished=true;return true;}return false;} }// 樹節(jié)點(diǎn) class Node{public Node bestChild=null;public ArrayList<Node> child=new ArrayList<Node>();public Point p=new Point();public int mark;Node(){this.child.clear();bestChild=null;mark=0;}public void setPoint(Point r){p.x=r.x;p.y=r.y;}public void addChild(Node r){this.child.add(r);}public Node getLastChild(){return child.get(child.size()-1);} }// 實(shí)現(xiàn)鼠標(biāo)事件接口 class MyMouseEvent implements MouseListener{public void mouseClicked(MouseEvent e){int x=round(e.getX()),y=round(e.getY());if(x>=45 && x<=675 && y>=45 && y<=675 && Ai3.chessBoard[y/45][x/45]==0 && Ai3.isBlack==false){Ai3.putChess(x,y);if(!Ai3.isFinished){Ai3.isBlack=true;Ai3.myAI();}Ai3.isFinished=false;}}// 得到鼠標(biāo)點(diǎn)擊點(diǎn)附近的棋盤精準(zhǔn)點(diǎn)public static int round(int x){return (x%45<22)?x/45*45:x/45*45+45;}public void mouseExited(MouseEvent e){}public void mouseEntered(MouseEvent e){}public void mouseReleased(MouseEvent e){}public void mousePressed(MouseEvent e){} }

總結(jié)

以上是生活随笔為你收集整理的博弈算法实现简单五子棋的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。