基于极大极小算法和alpha-beta剪枝实现AI井字棋

本文主要是介绍基于极大极小算法和alpha-beta剪枝实现AI井字棋，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

关于极大极小算法和alpha-beta剪枝可以参考文章的参考资料，这里仅对其进行代码实现。

其实这个算法单纯的理解并不容易，下面用代码进行实现。

说一下实现这个AI井字棋的思路：

简单的来说就是计算机希望估值函数值最大，而下棋人希望这个估值最小，因此在计算机决策是就用递归的向前看，这里的递归其实蛮不好理解的，但是可以宏观的去理解。

下面是代码的构成：

1. 一个ChessBoard的类用来处理一些关于棋盘的事件。
2. 一个TicTacToe的类用来实现游戏开始和计算机，玩家决策的事件

ChessBoard.h

//Author : yqtao
//Date   :2016.10.30
#ifndef CHESS_BOARD_H
#define CHESS_BOARD_H
#include<vector>
#include<iostream>
#include<string>
using namespace std;const int ChessBoard_Row = 13;
const int ChessBoard_Col = 26;
const int GridNuber = 9;
const char Comp_Char = 'X';
const char Human_Char = 'O';
const char Blank_Char = ' ';class ChessBoard {
public:ChessBoard();bool isEmpty(int pos);bool isFull();bool canWin(char c);bool immediateComWin(int& bestMove);bool immediateHumanWin(int& bestMove);void placeComp(int pos);void placeHuman(int pos);void unPlace(int pos);void print();
private:vector<char> boardInOneDimens;vector<string> board;};
#endif // !CHESS_BOARD_H

ChessBoard.cpp

#include"ChessBoard.h"
ChessBoard::ChessBoard() {             //默认构造函数boardInOneDimens.resize(GridNuber);for (int i = 0; i < GridNuber; i++)boardInOneDimens[i] = ' ';vector<string>tmp = {"- - - - - - - - - - - - -","|       |       |       |","|       |       |       |","|       |       |       |","- - - - - - - - - - - - -","|       |       |       |","|       |       |       |","|       |       |       |","- - - - - - - - - - - - -","|       |       |       |","|       |       |       |","|       |       |       |","- - - - - - - - - - - - -"};board = tmp;
}
//check the posion is empty or not 
bool ChessBoard::isEmpty(int pos) {return boardInOneDimens[pos] == ' ';
}
//
bool ChessBoard::isFull() {for (int i = 0; i < GridNuber; i++) {if (boardInOneDimens[i] == ' ')return false;}return true;
}
//
bool ChessBoard::canWin(char c) {//check every rowfor (int i = 0; i <= 6; i+=3) {if (boardInOneDimens[i] == c&&boardInOneDimens[i] == boardInOneDimens[i + 1] &&boardInOneDimens[i] == boardInOneDimens[i + 2])return true;}//check every colfor (int i = 0; i < 3; i++) {if (boardInOneDimens[i] == c&&boardInOneDimens[i] == boardInOneDimens[i + 3] &&boardInOneDimens[i] == boardInOneDimens[i + 6])return true;}//check every diagonalsif (boardInOneDimens[0] == c&&boardInOneDimens[4] == c&&boardInOneDimens[8] == c)return true;if (boardInOneDimens[2] == c&&boardInOneDimens[4] == c&&boardInOneDimens[6] == c)return true;return false;
}
//
bool ChessBoard::immediateComWin(int& bestMove) {for (int i = 0; i < GridNuber; i++) {if (isEmpty(i)) {boardInOneDimens[i] =Comp_Char;bool Win = canWin(Comp_Char); boardInOneDimens[i] = Blank_Char;   //backtraceingif (Win) {bestMove = i;return true;}}}return false;
}
//
bool ChessBoard::immediateHumanWin(int& bestMove) {for (int i = 0; i < GridNuber; i++) {if (isEmpty(i)) {boardInOneDimens[i] = Human_Char;bool Win = canWin(Human_Char);boardInOneDimens[i] = Blank_Char;   //backtraceingif (Win) {bestMove = i;return true;}}}return false;
}
//
void ChessBoard::placeComp(int pos) {boardInOneDimens[pos] = 'X';
}
//
void ChessBoard::placeHuman(int pos) {boardInOneDimens[pos] = 'O';
}
//
void ChessBoard::unPlace(int pos) {boardInOneDimens[pos] = ' ';
}
//
void ChessBoard::print() {int cnt = 0;for (int i = 2; i <= 10; i += 4) {for (int j = 4; j <= 20; j += 8) {board[i][j] = boardInOneDimens[cnt++];}}for (int i = 0; i < ChessBoard_Row; ++i) {cout << board[i] << endl;}
}

TicTacToe.h

#ifndef TICTACTOE_H
#define TICTACTOE_H
#include "ChessBoard.h"
enum Role { Human, Comp };
static const int CompWin = 2;
static const int Draw = 1;
static const int HumanWin = 0;
class TicTacToe {
public:void start();bool handleGameOver();bool gameIsOver(bool &draw, Role &win);Role chooseFirstPlace();void compPlace();int getBestMove();void humanPlace();int getPlacePosition();void findCompMove(int& bestMove,int& value, int alpha, int beta);void findHumanMove(int& bestMove,int& value, int alpha, int beta);
private:ChessBoard board;
};
#endif // !TicTacToe

TicTacToe.cpp

#include "TicTacToe.h"
void TicTacToe::start() {Role firstPlace = chooseFirstPlace();if (firstPlace == Comp) {  // Choose computer to be the firstcompPlace();}while (1) {board.print();if (handleGameOver()) break;humanPlace();board.print();if (handleGameOver()) break;compPlace();}
}
Role TicTacToe::chooseFirstPlace() {int choose;while (1) {cout << "who will place first" << endl;cout << "0 : human first " << endl;cout << "1 : computer first" << endl;cin >> choose;if (choose == 0 || choose == 1) {cout << endl;break;}elsecout << "error,please enter again" << endl;}return (Role)choose;
}
//
void TicTacToe::humanPlace() {int pos = getPlacePosition();board.placeHuman(pos);cout << "Your choice:" << endl;
}
//
int TicTacToe::getPlacePosition() {int m, n,pos;while (1) {cout << "It is your turn, please input where you want :" << endl;cout << "for example: 2 2 mean you want to add position 2 row,2 col:" << endl;cin >> m >> n;if (m < 0 || m>3 || n < 0 || n>3)cout << "error,please input again:" << endl;else {pos = (m - 1) * 3 + n - 1;if (board.isEmpty(pos))break;elsecout << "error,please input again:" << endl;}}return pos;
}
//
void TicTacToe::compPlace() {int bestMove = getBestMove();board.placeComp(bestMove);cout << "the computer choice is: " << endl;
}
int TicTacToe::getBestMove() {int bestMove = 0, value = 0;findCompMove(bestMove,value,HumanWin, CompWin);return bestMove;
}
void TicTacToe::findCompMove(int& bestMove,int &value, int alpha, int beta) {if (board.isFull())value = Draw;else if (board.immediateComWin(bestMove))value = CompWin;else {value = alpha;for (int i = 0; i < GridNuber&&value < beta; i++) {if (board.isEmpty(i)) {board.placeComp(i);int tmp = -1, response = -1;  // Tmp is uselessfindHumanMove(tmp, response, value, beta);board.unPlace(i);if (response > value) {value = response;bestMove = i;}}}}
}void TicTacToe::findHumanMove(int& bestMove,int & value, int alpha, int beta) {if (board.isFull())value=Draw;else if (board.immediateHumanWin(bestMove)){value=HumanWin;}else {value = beta; for (int i = 0; i < GridNuber&&value>alpha; i++) {if (board.isEmpty(i)) {board.placeHuman(i);int tmp = -1, response = -1;  // Tmp is uselessfindCompMove(tmp, response, alpha, value);board.unPlace(i);if (response <value) {value = response;bestMove = i;}}}}
}
//
bool TicTacToe::gameIsOver(bool &draw, Role &win) {if (board.canWin(Comp_Char)) {win =Comp ;draw = false;return true;}else if (board.canWin(Human_Char)) {win = Human;draw = false;return true;}else if (board.isFull()) {draw = true;return true;}else {return false;}
}bool TicTacToe::handleGameOver()  {bool draw = false;Role whoWin = Human;if (gameIsOver(draw, whoWin)) {if (draw) {cout << "Draw!" << endl;}else {if (whoWin == Comp) {cout << "You lose!" << endl;}else if (whoWin == Human) {cout << "Congratulations! You defeat the computer." << endl;}}return true;}else {return false;}
}

实现的结果如下图所示：

完成的代码和运行：

在Linux的环境下：

git clone https://github.com/yqtaowhu/DataStructureAndAlgorithm
cd DataStructureAndAlgorithm/Algorithm/TicTacToe/
make run

在window的环境下可用VS进行编译。
完整的代码在我的Github:
https://github.com/yqtaowhu/DataStructureAndAlgorithm/tree/master/Algorithm/TicTacToe

参考资料：
1. 数据结构与算法分析——C++语言描述
2. http://blog.csdn.net/tianranhe/article/details/8301756
3. http://blog.csdn.net/qq_22885773/article/details/50967021

这篇关于基于极大极小算法和alpha-beta剪枝实现AI井字棋的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---