c++实现井子棋（α-β剪枝）

在基础模块上增加了minimax算法，并用α-β剪枝优化。

chess.h

public:     bool canWin(int& bestMove,char c);//minimax

chess.cpp

bool chess::canWin(int& bestMove,char c){//minimax for(int i=0;i<number;i++){ if(isEmpty(i)){ boardOneLine[i]=c; bool win=isWinner(c); boardOneLine[i]=blank; if(win){ bestMove=i; return true; } } } return false; }

tic_tac_toe.h

static const int blackwin=2; static const int whitewin=0; static const int draw=1; public:     int getBestMove();//minimax     void findBlackMove(int& bestMove,int& value,int a,int b);//minimax     void findWhiteMove(int& bestMove,int& value,int a,int b);//minimax

tic_tac_toe.cpp

void tic_tac_toe::BlackPlace(){     /*srand(time(NULL));     while(1){         int pos=rand()%9;         if(board.isEmpty(pos)){             board.placeBlack(pos);             break;         }     }*/     //minimax     int bestMove=getBestMove();     board.placeBlack(bestMove); } int tic_tac_toe::getBestMove(){ int bestMove=0; int value=0; findBlackMove(bestMove,value,whitewin,blackwin); return bestMove; } void tic_tac_toe::findBlackMove(int& bestMove,int& value,int a,int b){ if(board.isFull()) value=draw; else if(board.canWin(bestMove,'X')){ value=blackwin; } else{ value=a; for(int i=0;i<number&&value<b;i++){ if(board.isEmpty(i)){ board.placeBlack(i); int tmp=-1; int res=-1; findWhiteMove(tmp,res,value,b); board.placeBlank(i); if(res>value){ value=res; bestMove=i; } } } } } void tic_tac_toe::findWhiteMove(int& bestMove,int& value,int a,int b){ if(board.isFull()) value=draw; else if(board.canWin(bestMove,'O')) value=whitewin; else{ value=b; for(int i=0;i<number&&value>a;i++){ if(board.isEmpty(i)){ board.placeWhite(i); int tmp=-1; int res=-1; findBlackMove(tmp,res,a,value); board.placeBlank(i); if(res<value){ value=res; bestMove=i; } } } } }

小优化：

void tic_tac_toe::start(){ Role first=chooseRole(); if(first==BlackRole){ //BlackPlace();         //黑棋第一步随机         srand(time(NULL)); int pos=rand()%9; if(board.isEmpty(pos)) board.placeBlack(pos); } while(1){ board.printChess(); if(gameOver())break; WhitePlace(); board.printChess(); if(gameOver())break; BlackPlace(); } }

附维基伪代码：

function minimax(node, depth) if node is a terminal node or depth = 0 return the heuristic value of node if the adversary is to play at node let α := +∞ foreach child of node α := min(α, minimax(child, depth-1)) else {we are to play at node} let α := -∞ foreach child of node α := max(α, minimax(child, depth-1)) return α

模块化：

tic_tac_toe.h

public: int a_b(int& bsm,int player,int a,int b);//a_b

tic_tac_toe.cpp

int tic_tac_toe::getBestMove(){ int bsm=0; a_b(bsm,BlackRole,whitewin,blackwin); return bsm; } int tic_tac_toe::a_b(int& bsm,int player,int a,int b){ if(board.isFull()) return draw; else if(player){ if(board.canWin(bsm,'O')) return whitewin; else{ for(int i=0;i<number;i++){ if(board.isEmpty(i)){ board.placeWhite(i); int ans=a_b(bsm,player^1,a,b); board.placeBlank(i); if(ans<b){ b=ans; //bsm=i; } if(a>=b) return b; } } } return b; } else { if(board.canWin(bsm,'X')) return blackwin; else{ for(int i=0;i<number;i++){ if(board.isEmpty(i)){ board.placeBlack(i); int ans=a_b(bsm,player^1,a,b); board.placeBlank(i); if(ans>a){ a=ans; bsm=i; } if(a>=b) return a; } } } return a; } }