基于极大极小分析法的井字棋对弈

人工智能αβ剪枝实现的一字棋实验报告The document was prepared on January 2, 2021实验5： -剪枝实现一字棋一、实验目的学习极大极小搜索及 - 剪枝算法实现一字棋。

二、实验原理1.游戏规则"一字棋"游戏（又叫"三子棋"或"井字棋"），是一款十分经典的益智小游戏。

"井字棋" 的棋盘很简单，是一个 3×3 的格子，很像中国文字中的"井"字，所以得名"井字棋"。

"井字棋"游戏的规则与"五子棋"十分类似，"五子棋"的规则是一方首先五子连成一线就胜利；"井字棋"是一方首先三子连成一线就胜利。

2.极小极大分析法设有九个空格，由 MAX，MIN 二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成"三子成一线"(同一行或列或对角线全是某人的棋子)，谁就用圆圈表示 MAX，用叉号代表 MIN比如左图中就是 MAX 取胜的棋局。

估价函数定义如下设棋局为 P，估价函数为e(P)。

(1) 若 P 对任何一方来说都不是获胜的位置，则 e(P)=e(那些仍为 MAX 空着的完全的行、列或对角线的总数)-e(那些仍为 MIN 空着的完全的行、列或对角线的总数)(2) 若 P 是 MAX 必胜的棋局，则 e(P)＝+ （实际上赋了 60）。

(3) 若 P 是 B 必胜的棋局，则 e(P)＝- （实际上赋了-20）。

e(P)=5-4=1需要说明的是，+赋60，-赋-20的原因是机器若赢了，则不论玩家下一步是否会赢，都会走这步必赢棋。

3. -剪枝算法上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。

于是在极小极大分析法的基础上提出了- 剪枝技术。

井字棋剪枝算法
井字棋剪枝算法是一种基于博弈树搜索的算法，被用于解决井字棋游戏中的最佳下棋策略问题。

该算法通过递归地搜索可能的游戏状态，找到当前最佳的下棋决策，并剪去一些无需继续搜索的不必要的节点，以减少搜索的时间和空间复杂度。

井字棋剪枝算法的基本思想是采用极大极小值搜索，即假设玩家A和玩家B轮流下棋，A追求最大化自己的得分，B追求最小化A的得分。

算法通过递归地搜索游戏树的每个可能节点，为每个节点计算一个得分，然后根据当前轮到的玩家是A 还是B来选择得分最大或最小的子节点。

在搜索过程中，剪枝算法会根据一些启发式规则来判断当前搜索的节点是否值得继续搜索。

如果某个节点的某个分支已经可以确定最终结果，即玩家A或B已经取得胜利或者平局，那么该节点的搜索可以提前结束，不再继续搜索该节点的其它分支。

这样可以避免重复计算和不必要的搜索，提高程序的搜索效率。

井字棋剪枝算法的核心是搜索和剪枝策略的设计，包括如何评估每个游戏状态的得分、如何判断游戏是否结束、如何选择得分最大或最小的子节点以及如何进行剪枝等方面的问题。

这些设计需要根据具体的游戏规则和需求来进行调整和优化。

博弈树极大极小算法举例
嘿，朋友们！今天咱就来唠唠博弈树极大极小算法。

这可不是什么深奥得让人摸不着头脑的东西哦！就好比下象棋，咱得考虑每一步走了之后，对手会怎么回应，自己又该怎样应对才能达到最好的结果。

比如说玩井字棋吧！这就是一个简单的例子。

你下了一步棋，哎呀，那接下来对方可能会怎么走呢？你得在脑子里像树枝一样展开各种可能。

对方要是走这里，那你就得这样应对；要是走那里，你又得换种办法。

这就是在构建博弈树呀！
想象一下，你和对手就像在一个充满策略的迷宫里，每一个选择都是一道门。

你在努力找到通往胜利的那扇门，而对手也在拼命阻挡你。

就好像在一场激烈的比赛中，双方都全力以赴，试图战胜对方。

再比如说猜拳！剪刀石头布，很简单吧，但这里面也藏着博弈树极大极小算法的影子呢。

你出剪刀，对方可能出石头也可能出布，那你要怎么根据对方之前的出拳习惯来决定自己这次出什么呢？是不是很有意思？
在很多游戏中都能看到这种算法的运用，它就像是一个聪明的军师，帮你分析局势，找出最佳策略。

其实，生活中也到处都是这样的“博弈”，和朋友讨论去哪里玩，和家人商量做什么菜，这些不都是在做选择，在构建小小的博弈树吗？我们都在不自觉地运用着这种智慧呢！
所以啊，博弈树极大极小算法并不是什么遥不可及的高大上概念，而是实实在在存在于我们的生活和游戏中的智慧结晶呀！它让我们的决策更明智，让游戏变得更有挑战性和乐趣。

大家都快来感受一下这神奇的算法吧！。

简单的井字棋AIDEMOMinimax算法在“类与对象”实训课上，有⼀道附加题让我们⽤ OOP 做⼀个的井字棋模拟程序，要求中电脑是随机落⼦的，这样显然不是很优雅。

回忆起以前学的对抗搜索（这⾥叫 MaxMin 算法），我继续给游戏中的电脑⼀⽅写了个 AI。

由于井字棋游戏运算规模很⼩，⼤部分的剪枝⼿段变得⽐较鸡肋，但以此为引搜索了⼀些资料，了解⼀些有趣的计算机博弈论知识，有机会再继续探究⼀下。

极⼤极⼩（Minimax）算法Minimax算法⼜名极⼩化极⼤算法，是⼀种找出失败的最⼤可能性中的最⼩值的算法（即最⼩化对⼿的最⼤得益）。

通常以递归形式来实现。

Minimax算法常⽤于棋类等由两⽅较量的游戏和程序。

该算法是⼀个零总和算法，即⼀⽅要在可选的选项中选择将其优势最⼤化的选择，另⼀⽅则选择令对⼿优势最⼩化的⼀个，其输赢的总和为0（有点像能量守恒，就像本⾝两个玩家都有1点，最后输家要将他的1点给赢家，但整体上还是总共有2点）。

很多棋类游戏可以采取此算法，例如tic-tac-toe。

Alpha-beta 剪枝Alpha-beta剪枝是⼀种搜索算法，⽤以减少极⼩化极⼤算法（Minimax算法）搜索树的节点数。

这是⼀种对抗性搜索算法，主要应⽤于机器游玩的⼆⼈游戏（如井字棋、象棋、围棋）。

当算法评估出某策略的后续⾛法⽐之前策略的还差时，就会停⽌计算该策略的后续发展。

该算法和极⼩化极⼤算法所得结论相同，但剪去了不影响最终决定的分枝。

待改进的点：判定胜利的⽅法⽐较蠢，可以⽤循环代替没有对搜索树的预计深度进⾏评估，使 AI 做出最 “快” 的策略代码可读性不强，不符合⼯程代码规范#include <bits/stdc++.h>using namespace std;class MyChess {private:char A[3][3];int step;public:MyChess();void DispChessboard();void PlayerMove();void ComputerMove();bool isFull();int MaxSearch();int MinSearch();int checkWin();};MyChess::MyChess() {memset(A,0,sizeof(A));step=0;}void MyChess::DispChessboard() {cout<<"-------------------\n";for (int i=0;i<3;i++) {cout<<"| "<<A[i][0]<<" | "<<A[i][1]<<" | "<<A[i][2]<<" |\n";cout<<"-------------------\n";}}void MyChess::PlayerMove() {int x,y;cout<<"Step "<<++step<<" piece(x,y): ";cin>>x>>y;while (A[x][y] || x>2 || x<0 || y>2 || y<0) {cout<<"ERROR!! piece(x,y): ";cin>>x>>y;}A[x][y]='O';}void MyChess::ComputerMove() { // 模拟 AI 的选择过程int x,y,score=1;for (int i=0;i<3;i++) {for (int j=0;j<3;j++) {if (!A[i][j]) {A[i][j]='X';int temp=MaxSearch();if (score>temp) x=i,y=j,score=temp;A[i][j]=0;}}}A[x][y]='X';}int MyChess::MaxSearch() { // ⼈类执⼦时，希望找到权值最⼤的⼦节点int ret=-1,sta=checkWin();if (sta) return sta;if (isFull()) return 0;for (int i=0;i<3;i++) for (int j=0;j<3;j++)if (!A[i][j]) A[i][j]='O',ret=max(ret,MinSearch()),A[i][j]=0;return ret;}int MyChess::MinSearch() { // 电脑执⼦时，希望找找到权值最⼩的⼦节点int MyChess::MinSearch() { // 电脑执⼦时，希望找找到权值最⼩的⼦节点int ret=1,sta=checkWin();if (sta) return sta;if (isFull()) return 0;for (int i=0;i<3;i++) for (int j=0;j<3;j++)if (!A[i][j]) A[i][j]='X',ret=min(ret,MaxSearch()),A[i][j]=0;return ret;}bool MyChess::isFull() { // 平局判定for (int i=0;i<3;i++)for (int j=0;j<3;j++)if (!A[i][j]) return false;return true;}int MyChess::checkWin() {for (int i=0;i<3;i++) if (A[i][0]=='O' && A[i][1]=='O' && A[i][2]=='O') return 1; for (int i=0;i<3;i++) if (A[0][i]=='O' && A[1][i]=='O' && A[2][i]=='O') return 1; for (int i=0;i<3;i++) if (A[i][0]=='X' && A[i][1]=='X' && A[i][2]=='X') return -1; for (int i=0;i<3;i++) if (A[0][i]=='X' && A[1][i]=='X' && A[2][i]=='X') return -1; if (A[0][0]=='O' && A[1][1]=='O' && A[2][2]=='O') return 1;if (A[2][0]=='O' && A[1][1]=='O' && A[0][2]=='O') return 1;if (A[0][0]=='X' && A[1][1]=='X' && A[2][2]=='X') return -1;if (A[2][0]=='X' && A[1][1]=='X' && A[0][2]=='X') return -1;return 0;}int main() {MyChess Ch; int now=1;Ch.DispChessboard();while (!Ch.isFull()) {if (now&1) {Ch.PlayerMove();if (Ch.checkWin()==1) { Ch.DispChessboard(),cout<<"You win!\n"; break; } else if (Ch.isFull()) { Ch.DispChessboard(),cout<<"Gme tie!\n"; break; } }else {puterMove();Ch.DispChessboard();if (Ch.checkWin()==-1) { cout<<"Computer win!\n"; break; }}now^=1;}return 0;}。

基于极大极小分析法的井字棋对弈任务分析：首先，我们要知道，“井字棋”游戏（又叫“三子棋”），是一款十分经典的益智小游戏，想必很多玩家都有玩过。

“井字棋”的棋盘很简单，是一个3×3的格子，很像中国文字中的“井”字，所以得名“井字棋”。

“井字棋”游戏的规则与“五子棋”十分类似，“五子棋”的规则是一方首先五子连成一线就胜利；“井字棋”是一方首先三子连成一线就胜利。

游戏时一方是电脑，另一方是玩家。

所以，这类游戏在开始时有两种方式：一种是玩家先走；另一种是电脑先走。

这是我们要考虑的第一个问题。

其次，由于与玩家对战的是计算机，所以我们要编写一个过程，它可以使程序模拟人的思维与人下棋（其实就是“人工智能”的体现），这个过程也是本游戏的关键。

此外，我们还要编写两个过程，其一用来时刻判断棋盘中是否有三个棋子连成一线；其二用来判断如果有三个棋子连成一线，是哪一方连成一线的，即判断哪一方获胜。

如图所示为井字棋的一个格局,而格局之间的关系是由比赛规则决定的.通常,这个关系不是线性的,因为从一个棋盘格局可以派生出几个格局.例如图左侧所示的格局可以派生出5歌格局.例如图右侧所示,而从每一个新的格局又可派生出4个可能出现的格局.因此,若将从对弈开始到结束的过程中所有可能出现的格局都画在一张图上，则可以得到一颗倒长的”树”.图1 对弈问题中格局之间的关系设计思路设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。

用叉号表示MAX，用圆圈代表MIN。

为了不致于生成太大的博弈树，假设每次仅扩展两层。

估价函数定义如下：设棋局为P，估价函数为e(P)。

(1) 若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数。

井字棋算法设计与分析井字棋（Tic-Tac-Toe）是一种简单而受欢迎的棋盘游戏，针对井字棋的算法设计与分析如下：算法设计：1.完全搜索算法（BruteForce）：这是一种简单但耗时较长的算法。

它通过递归的方式搜索所有可能的棋局状态，然后评估每个状态的胜负情况，决定最佳的下棋位置。

该算法需要考虑回溯和剪枝技巧，以减少搜索空间的大小。

2.极小化极大算法（Minimax）：这是一种常用的井字棋算法。

它通过假设对手能够选择最佳的落子位置，并最大化对手的得分，然后选择自己能够最大化自己得分的落子位置。

这个过程通过递归搜索来实现，直到达到游戏结束的状态。

3.Alpha-Beta剪枝算法：这是Minimax算法的改进版本。

Alpha-Beta剪枝算法在搜索树的过程中基于确定的上下界（alpha和beta）进行剪枝操作，以提高搜索效率。

它可以减少不必要的搜索路径，以更快地找到最佳的落子位置。

算法分析：1.时间复杂度：完全搜索算法的时间复杂度较高，约为O(9！)，因为棋盘上最多有9个格子需要考虑。

而Minimax算法和Alpha-Beta 剪枝算法采用了剪枝操作，可以减少搜索的深度，从而大大降低了时间复杂度。

2.空间复杂度：井字棋的状态空间相对较小，只有9个格子可以放置X或O，因此算法的空间复杂度相对较低。

使用递归的Minimax 算法和Alpha-Beta剪枝算法只需要额外的栈空间来保存递归调用的状态。

3.最佳行动策略：Minimax算法和Alpha-Beta剪枝算法都能够找到最佳行动策略，即在给定棋局状态下选择最优的落子位置。

这些算法会考虑所有可能的行动，并根据评估函数来进行选择。

总的来说，井字棋的算法设计与分析主要涉及到完全搜索算法、Minimax算法和Alpha-Beta剪枝算法。

这些算法在时间复杂度、空间复杂度和最佳行动策略方面有不同的特点，选择适合的算法取决于具体需求和对性能的要求。

井字棋算法,从网上找的C/C++ 2009-11-30 18:03:17 阅读284 评论0 字号：大中小订阅摘要：本文就作者编写的井字棋程序进行了简要的介绍，并重点介绍了该程序采用的算法、程序设计方案、对算法的改进等内容。

关键字：井字棋，评估函数，极大极小值算法，α-β剪枝算法1. 程序说明本程序旨在完成一个具有人机博弈功能的井字棋程序，具有良好的用户界面、支持人机对弈和双人对弈两种模式，并具有悔棋、选择难易级别等功能。

该程序是中科院研究生院2005年秋季学期《人工智能原理》课程的项目一。

2. 设计方案2.1 设计步骤本程序最主要的任务是完成图形界面的井字棋的人机对弈模块的设计。

在人机对弈过程中，计算机方所采用的算法，也就是博弈树的搜索技术是最重要的。

所以，设计时，作者按照以下步骤进行：(1) 选定博弈算法；(2) 建立一个简单的应用程序（如字符界面程序）来测试算法；(3) 选定图形界面中要实现的其他功能（如双人对弈、悔棋、难易级别选定、联机对战等）；(4) 实现图形界面的井字棋程序。

所采用的核心算法将在第3节介绍。

本程序要实现两个程序，一个是字符界面的算法测试程序，另一个是要正式提交的图形界面程序。

下面是对这两个程序的设计方案的介绍。

2.2 字符界面的算法测试程序该测试程序由标准C++编写，作者采用了极大极小值算法。

除了主程序外，它还包括具有以下功能的函数：(1) 棋盘初始化函数：void Init()；(2) 打印棋盘函数：void PrintQP()；(3) 用户输入落子位置函数void UserInput()；(4) 判断当前棋局是否有一方获胜，并判断哪一方获胜的函数：int IsWin(State s)；(5) 评估函数值计算函数：int e_fun(State s)；(6) 极大极小值算法主函数：int AutoDone()；其中前三个函数是对程序中当前的棋局进行读写操作的函数，第4、5个函数是对当前的棋局进行判断的函数，最后一个函数中包含了计算机决定在哪个位置落子所采用的核心算法，并且可以判断计算机落子前后棋局的状态，如果在搜索树的深度范围内能判断哪一方必胜，则可提前打印输赢信息，并结束本棋局。

JavaScript通过极⼤极⼩值算法实现AI井字棋游戏话不多说直接上运⾏截图：⿊棋是玩家的位置，红⾊⽅是电脑。

电脑会根据当前棋盘的情况选择⼀个对⾃⼰有利却对玩家不利的情况。

算法可以实现电脑胜利，或者电脑和玩家平局。

代码如下：<!DOCTYPE html><html><head><meta charset="UTF-8"><title>井字棋AI</title><style>.title {text-align: center;}.chess {display: block;/*变成块级元素，使⽤margin居中*/margin: 50px auto;box-shadow: 5px 5px 5px #B9B9B9, -2px -2px 2px #EFEFEF;cursor: pointer;}div {text-align: center;}.restart {padding: 10px 20px;background-color: #EE82EE;border-radius: 5px;color: white;cursor: pointer;}</style></head><body><h3 class="title">--井字棋--</h3><canvas class="chess" width="450px" height="450px"></canvas><div><a class="restart" onclick="rst()">重新开始</a></div></body><script>var chess = document.getElementsByClassName("chess")[0];var title = document.getElementsByClassName("title")[0];var context = chess.getContext("2d");context.strokeStyle = "#B9B9B9"window.onload = function() {drawChessBoard();Init()}function drawChessBoard() {for(var i = 0; i < 4; i++) {//设置横线起始点坐标context.moveTo(15, 15 + i * 140)//设置横线结束点坐标context.lineTo(435, 15 + i * 140)//连接2点context.stroke();//设置竖线context.moveTo(15 + i * 140, 15)//设置横线结束点坐标context.lineTo(15 + i * 140, 435)//连接2点context.stroke();}}//定义⼆维数组标记棋⼦var chessboard = []for(var i = 0; i < 4; i++) {chessboard[i] = [];for(var j = 0; j < 4; j++) {chessboard[i][j] = 0;}}const NUMBER = 3const STEP = 9const MAN = 1const COMPUTER = -1const SEARCHDEPTH = 9const INT_MAX = 999999const INT_MIN = -1000000var player = 0var isGameOver = falsevar currentDepth = 0var bestPosition = {x: 0,y: 0}function Init() {for(let i = 0; i < NUMBER; i++) {for(let j = 0; j < NUMBER; j++) {chessboard[i][j] = 0}}player = MANisGameOver = falsecurrentDepth = 0}function isEnd() {let i = 0let j = 0var count = 0for(i = 0; i < NUMBER; i++) { //⾏count = 0;for(j = 0; j < NUMBER; j++)count += chessboard[i][j];if(count == 3 || count == -3)return count / 3;}for(j = 0; j < NUMBER; j++) { //列count = 0;for(i = 0; i < NUMBER; i++)count += chessboard[i][j];if(count == 3 || count == -3)return count / 3;}count = 0;count = chessboard[0][0] + chessboard[1][1] + chessboard[2][2]; if(count == 3 || count == -3)return count / 3;count = chessboard[0][2] + chessboard[1][1] + chessboard[2][0]; if(count == 3 || count == -3)return count / 3;return 0;}function MaxMinSearch(depth) {var value = 0;if(player == MAN) value = INT_MIN;if(player == COMPUTER) value = INT_MAX;if(isEnd() != 0) {return Evaluate();}if(depth == SEARCHDEPTH) {value = Evaluate();return value;}for(let i = 0; i < NUMBER; i++) {for(let j = 0; j < NUMBER; j++) {if(chessboard[i][j] == 0) {if(player == MAN) {chessboard[i][j] = MAN;player = COMPUTER;var nextvalue = MaxMinSearch(depth + 1); player = MAN;if(value < nextvalue) {value = nextvalue;if(depth == currentDepth) {bestPosition.x = i;bestPosition.y = j;}}} else if(player == COMPUTER) {chessboard[i][j] = COMPUTER;player = MAN;var nextvalue = MaxMinSearch(depth + 1); player = COMPUTER;if(value > nextvalue) {value = nextvalue;if(depth == currentDepth) {bestPosition.x = i;bestPosition.y = j;}}}chessboard[i][j] = 0;}}}return value;}function Logic(){if (isGameOver) {if (isEnd() == MAN) {alert("游戏结束玩家胜利")} else if (isEnd() == COMPUTER) {alert("游戏结束电脑胜利")} else {alert("游戏结束平局")}}}function Evaluate() {var value = isEnd();if(value == MAN) return INT_MAX;if(value == COMPUTER) return INT_MIN; }chess.onclick = function(event) {if(player != MAN) {return;}//获取坐标var x = event.offsetX;var y = event.offsetY;x = Math.trunc((x - 15) / 140)y = Math.trunc((y - 15) / 140)ManPlay(x, y)if(isEnd() == 0 && currentDepth < 8) {ComputerPlay()if(isEnd() != 0) {isGameOver = true}} else {isGameOver = true}Logic()}function ManPlay(x, y) {chessboard[x][y] = MANDrawBroad(x,y,MAN)currentDepth++player = COMPUTER}function ComputerPlay() {MaxMinSearch(currentDepth)chessboard[bestPosition.x][bestPosition.y] = COMPUTERDrawBroad(bestPosition.x,bestPosition.y,COMPUTER)currentDepth++player = MAN}//落⼦时绘画棋盘function DrawBroad(i, j, player) {context.beginPath();context.arc(85 + i * 140, 85 + j * 140, 40, 0, 2 * Math.PI); //画圆context.closePath();var color;if(player == MAN) {color = "#000";} else {color = "red"}context.fillStyle = color;context.fill();}function rst() {window.location.reload();}</script></html>其中，代码的242⾏和244⾏中的context.beginPath();context.arc(85 + i * 140, 85 + j * 140, 40, 0, 2 * Math.PI); //画圆context.closePath();分别是落笔和抬笔的操作。