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

2024-03-18 10:38

本文主要是介绍基于极大极小算法和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井字棋的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/822077

相关文章

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文

golang版本升级如何实现

《golang版本升级如何实现》:本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型(范围、哈希、列表、键值),主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区(Range Partitioning1、新建分区表:2、分

MySQL 定时新增分区的实现示例

《MySQL定时新增分区的实现示例》本文主要介绍了通过存储过程和定时任务实现MySQL分区的自动创建,解决大数据量下手动维护的繁琐问题,具有一定的参考价值,感兴趣的可以了解一下... mysql创建好分区之后,有时候会需要自动创建分区。比如,一些表数据量非常大,有些数据是热点数据,按照日期分区MululbU