- 【人工智能】Astar算法求解8数码问题（QDU）
- 【人工智能】利用α-β搜索的博弈树算法编写一字棋游戏（QDU）
- 【人工智能】Fisher 线性分类器的设计与实现（QDU）
- 【人工智能】感知器算法的设计实现（QDU）
- 【人工智能】SVM 分类器的设计与应用（QDU）
- 卷积神经网络 CNN 框架的实现与应用（写的比较水，就没放上）
实验目的
理解和掌握博弈树的启发式搜索过程，能够用选定的编程语言实现简单的博弈游戏。
- 学习极大极小搜索及 α − β \alpha-\beta α−β 剪枝。
- 利用学到的算法实现一字棋
实验原理
游戏规则
“一字棋"游戏（又叫"三子棋"或"井字棋”），是一款十分经典的益智小游戏。“井字棋"的棋盘很简单，是一个 3×3 的格子，很像中国文字中的"井"字，所以得名"井字棋”。"井字棋"游戏的规则与"五子棋"十分类似，"五子棋"的规则是一方首先五子连成一线就胜利；"井字棋"是一方首先三子连成一线就胜利。 井字棋（英文名 Tic-Tac-Toe） 井字棋的出现年代估计已不可考，西方人认为这是由古罗马人发明的；但我们中国人认为，既然咱们都发明了围棋、五子棋，那发明个把井字棋自然是不在话下。这些纯粹是口舌之争了，暂且不提。
极小极大分析法
设有九个空格，由 MAX，MIN 二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子， 谁先使自己的棋子构成"三子成一线"（同一行或列或对角线全是某人的棋子），谁就取得了胜利。
用圆圈表示 MAX，用叉号代表 MIN。比如下图中就是 MAX 取胜的棋局：
估价函数定义如下：
设棋局为
P
P
P，估价函数为
e
(
P
)
e(P)
e(P)。
- 若 P P P 对任何一方来说都不是获胜的位置，则 $e§=e(那些仍为 MAX 空着的完全的行、列或对角线的总数)-e(那些仍为 MIN 空着的完全的行、列或对角线的总数) $
- 若 P P P 是 MAX 必胜的棋局，则 e ( P ) ＝ + ∞ e(P)＝+∞ e(P)＝+∞ （实际上赋了 60）
- 若 P P P 是 B 必胜的棋局，则 e ( P ) ＝ − ∞ e(P)＝-∞ e(P)＝−∞ （实际上赋了-20）
比如
P
P
P 如下图示,则
e
(
P
)
=
5
−
4
=
1
e(P)=5-4=1
e(P)=5−4=1
需要说明的是，
+
∞
+∞
+∞ 赋
60
60
60，
−
∞
-∞
−∞ 赋
−
20
-20
−20 的原因是机器若赢了，则不论玩家下一步是否会赢，都会走这步必赢棋。
α-β 剪枝算法
上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了
α
−
β
\alpha-\beta
α−β剪枝技术。
**
α
−
β
\alpha-\beta
α−β剪枝技术的基本思想或算法**是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。
具体的剪枝方法如下：
- 对于一个与节点 MIN，若能估计出其倒推值的上确界 β \beta β，并且这个 β \beta β 值不大于 MIN 的父节点（一定是或节点）的估计倒推值的下确界 α \alpha α，即 α ≥ β α≥β α≥β，则就不必再扩展该 MIN 节点的其余子节点了（因为这些节点的估值对 MIN 父节点的倒推值已无任何影响了）。这一过程称为 α α α 剪枝。
- 对于一个或节点 MAX，若能估计出其倒推值的下确界 α α α，并且这个 α α α 值不小于 MAX 的父节点（一定是与节点）的估计倒推值的上确界 β β β，即 α ≥ β α≥β α≥β，则就不必再扩展该 MAX 节点的其余子节点了（因为这些节点的估值对 MAX 父节点的倒推值已无任何影响了）。这 一过程称为 β β β 剪枝。
从算法中看到：
- MAX 节点（包括起始节点）的 α α α 值永不减少
- MIN 节点（包括起始节点）的 β β β 值永不增加
在搜索期间，
α
α
α 和
β
β
β 值的计算如下：
- 一个 MAX 节点的 α α α 值等于其后继节点当前最大的最终倒推值
- 一个 MIN 节点的 β β β 值等于其后继节点当前最小的最终倒推值
举个例子理解一下该过程：
详细步骤：
- 树要从倒数第二层开始处理，且所有的处理都要"从左往右"处理
- MIN层节点的取值是其子节点中的最小值，如果有子节点被剪了，那么就取剩下的子节点中的最小值
- MAX层节点的取值是其子节点中的最大值，如果有子节点被剪了，那么就取剩下的子节点中的最大值
- 满足以下依据才可以剪枝 - 假设有节点x，根据节点x的某个子节点确定了节点x的取值范围- 节点x也有父节点(包括直接父节点与间接父节点)，这些父节点在你确定节点x的值时，可能已经有了取值范围，也可能还没有取值范围- 如果这些父节点已经有取值范围了，那么，如果节点x的聚值范围与节点x的父节点(直接或间接)的取值范围没有交集或交集中只有一个元素，则剪掉节点x的其他子节点，其他子节点指的就是节点x的所有子节点中除推出节点x范围的那个节点外的节点
- 当所有未被剪掉的节点的值都确定后，剪枝结束
输赢判断算法设计
因为每次导致输赢的只会是当前放置的棋子，输赢算法中只需从当前点开始扫描判断是否已经形成三子。对于这个子的八个方向判断是否已经形成三子。如果有，则说明有一方胜利，如果没有则继续搜索，直到有一方胜利或者搜索完整个棋盘。
实验设计
实现了两个版本的，一个是C++版，另一个是Java版。
其中C++版可视化较差，实现的功能较少，但是
α
−
β
\alpha-\beta
α−β剪枝的极大极小值算法比较清晰，方便学习和复习算法；
而Java版在实现算法的基础上包装了可视化外壳，让整个程序更加产品化。
下面的核心算法是两个版本共有的，而有关程序设计的讲解不包含对C++版的介绍。
核心算法
PvP：
玩家与玩家对战时不需要任何算法，只需要对每一次棋盘的点击事件进行监听，当存在一方胜利或者棋盘下满（平局）时结束游戏。
PvE：
玩家与电脑对战，玩家方的落子依然无需算法支持，只需要由玩家控制即可。
对于电脑而言，通过递归的方式实现极大极小分析法，选择最佳落子位置。此算法不仅仅需要定义模拟电脑寻找最佳落子处的函数，还需要定义模拟玩家寻找最佳落子处的函数，通过轮流（递归）调用两个函数模拟轮流落子的过程。对于电脑遇到的某一种状态，即要选择落子位置时，进行递归，找到最佳落子位置后进行递归返回。
何时进行递归返回就是剪枝条件，在本算法中规定剪枝层数为两层，当到达第三层时如果没法锁定棋局（锁定棋局：可以确定胜方或者确定平局），则对递归到的节点进行调用估值函数进行估值，递归返回的其中一个信息就是此状态下的估值，估值函数定义为：棋盘空位填充为电脑方的棋子后三子连线的条数与填充为玩家方的棋子后三子连线的条数之差。
在电脑落子的函数中调用的电脑寻找最佳落子处的函数，即进行递归模拟轮流落子得到最佳落子位置。
在电脑寻找最佳落子处的函数中先判断是否可以找到一个位置落子，使电脑方直接获胜，如果存在这样的位置，就选择此位置落子，该状态的估值也就为正无穷，表示必胜；如果不存在，则再判断剪枝层数，如果到达剪枝层数则直接调用估值函数计算该状态的价值；如果也未到达剪枝层数，则尝试在某个空位进行落子，也就是将棋盘上某个位置标记为电脑的棋子，再调用玩家寻找最佳落子处的函数，即电脑落子完成，轮到模拟玩家落子。玩家寻找最佳落子处的函数也会再调用电脑寻找最佳落子处的函数从而实现递归，并通过引用向上层递归层传回子结点（子状态）的估值，通过子结点的估值更新当前结点的估值。无论是否更新当前结点的估值，都需要进行回溯，即由于是模拟落子所以需要在递归返回后将状态恢复为之前的状态，将落子位置置为空。
如果在每次模拟寻找落子位置时去尝试每一种方法，即尝试落在每一个空位上。将递归的过程理解为建树的过程，可以想象，如此建树会导致时间复杂度非常高（其实虽然时间复杂度很高，但由于井字棋最多存在九个格子，所以耗时还是可以接受的），通过
α
−
β
\alpha-\beta
α−β剪枝以减少不必要的开销。
每次递归的时候，我们需要将
α
\alpha
α值或
β
\beta
β值传入，让下一层（即对手）选择落子位置的时候可以剪枝，减少需要判断的落子位置。
MAX结点的剪枝策略为根据传入的
β
\beta
β值，此
β
\beta
β值为当前MAX结点的上一个状态即MIN结点的最大值，因为要保证子结点（MAX）与祖先结点（MIN）的范围存在交集，也就是要保证MAX结点的状态估值必须都要小于
β
\beta
β，这样
(
−
∞
,
β
]
(-∞,\beta]
(−∞,β]与
[
α
,
+
∞
)
[\alpha,+∞)
[α,+∞)才存在交集，如果已经存在不相交的情况了，则后面的也没必要判断，即进行剪枝即可。
MIN结点的剪枝策略与MAX结点的剪枝策略类似，不再赘述。如此一来，不仅获得了电脑的最佳落子位置，而且将时间复杂度降到最低。
剪枝流程
前三层完整状态：
经
α
−
β
\alpha-\beta
α−β剪枝的前三层状态：
程序中的剪枝过程：
剪枝至少涉及三层结点，下面以三层为例讲述剪枝函数的实现。
主要是理解每层参数传递的关系，顶层MAX结点要子结点（MIN结点）传递其
α
\alpha
α值用于剪枝，即如果当前MIN结点的
β
\beta
β值小于等于
α
\alpha
α则发生剪枝，**无需再计算MIN结点的子结点中后续的结点**；MIN结点的子结点MAX结点向MIN结点提供的每个MAX节点的估值不仅要用于更新MIN结点的
β
\beta
β值，也要用于剪枝；当彻底更新完MIN节点的
β
\beta
β值时（即MIN结点的估值确定）需要向上层传递，更新MIN的父结点MAX结点的
α
\alpha
α值。
程序设计
预期流程图：
最终实现的流程图：
最终实现采用第二个流程图所展现的流程对整个程序进行控制。
初始界面
初始界面包含四部分：logo”Tic-Tac-Toe“、”PvP“玩家对战玩家的选项、”PvE“玩家对战电脑的选项、”exit“退出。
游戏界面
游戏界面主要包含两部分，上方是计分板，下方是棋盘。计分板分别记录着P1（或P）与P2（E）的分数。
为了方便区分当前落子方是P1（或P）还是P2（或E），特意将计分板落子方的标识高亮显示。
游戏规则：
- 当一方胜过另一方时，胜方才会加分，平局不加分。
- PvP模式下，P1落子为 X X X，P2落子为 O O O；PvE模式下，电脑的落子为 X X X，玩家的落子为 O O O。
- 双方轮流先后手，PvP模式下P1优先落子，PvE模式下，电脑优先落子。
PvP界面：
PvE界面：
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t7tbJqlS-1641477827466)(C:\Users\23343\AppData\Roaming\Typora\typora-user-images\image-20211119162928763.png)]](https://img-blog.csdnimg.cn/c999c969216a4f1e8e70854eeabe9304.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiN54mM5LiN5pS5,size_13,color_FFFFFF,t_70,g_se,x_16)
程序待优化方面
- 弹出的对话框透明化。为了实现更佳的用户体验，当对局结束后，弹出不透明的结果提示框会遮挡棋盘信息，当用户需要观察棋局时需要拖拽提示框，所以将提示框透明化具有很显著的意义，但是最终没能实现。
- 本算法默认的剪枝层数为2层，当设置剪枝层数为3层时会出现错误。
- 还可以在PvP模式下加入”提示“功能。
运行截图
PvP：
如下状态说明轮到P1落子。
下图说明P2落完子后又轮到P1。
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bdTTr6I6-1641477827466)(C:\Users\23343\AppData\Roaming\Typora\typora-user-images\image-20211119161145533.png)]](https://img-blog.csdnimg.cn/fa5aa7bfa55d40f591033138920b6956.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiN54mM5LiN5pS5,size_13,color_FFFFFF,t_70,g_se,x_16)
下图说明P1获胜，弹出提示框说明P1获胜。
当点击确定后，计分板会将胜方的分数加一。同时可以看到，上一回合为P1先手落子，所以本回合轮到P2优先落子。
PvE：
在PvE模式下，规定电脑优先落子，之后轮流先后手。
为了更好的用户体验，电脑落子的动作会在计算出最佳落子位置后延迟1s，模仿计算机思考的过程。
平局则双方都不会加分。同时下回合将轮到玩家优先落子。
附录1（C++代码）
C++代码只是简单地将
α
−
β
\alpha-\beta
α−β剪枝的极大极小分析法实现了，并采用输出窗口的方式进行可视化。在写Java代码前通过该C++程序熟悉了核心算法。
#include<bits/stdc++.h>
using namespace std;
int chessBoard[3][3];
int isWin();
int evaluate();
bool gameOver();
void playGame();
void printChessBoard();
void computerPlace();
void humanPlace();
bool computerImmidiateWin(int&);
bool humanImmidiateWin(int&);
void findComputerBestMove(int&, int&, int, int, int);
void findHumanBestMove(int&, int&, int, int, int);
void printChessBoard() {
cout << "ChessBoard:" << endl << endl;
for(int i = 0;i < 9;i ++) {
if(chessBoard[i/3][i%3] == 1) cout << "○";
if(chessBoard[i/3][i%3] == 0) cout << "□";
if(chessBoard[i/3][i%3] == -1) cout << "×";
if(i%3 == 2) cout << endl;
}
}
int isWin() {
for(int i = 0;i < 3;i ++) {
if(chessBoard[i][0] != 0 && chessBoard[i][0] == chessBoard[i][1] && chessBoard[i][1] == chessBoard[i][2]) return chessBoard[i][0];
if(chessBoard[0][i] != 0 && chessBoard[0][i] == chessBoard[1][i] && chessBoard[1][i] == chessBoard[2][i]) return chessBoard[0][i];
}
if(chessBoard[0][0] != 0 && chessBoard[0][0] == chessBoard[1][1] && chessBoard[1][1] == chessBoard[2][2]) return chessBoard[0][0];
if(chessBoard[2][0] != 0 && chessBoard[2][0] == chessBoard[1][1] && chessBoard[1][1] == chessBoard[0][2]) return chessBoard[2][0];
return 0; // 0 不代表平局
}
bool computerImmidiateWin(int& bestMove) {
for(int i = 0;i < 9;i ++) {
if(chessBoard[i/3][i%3]) continue;
chessBoard[i/3][i%3] = 1;
bool win = (isWin() == 1);
chessBoard[i/3][i%3] = 0;
if(win) {
bestMove = i;
return true;
}
}
return false;
}
bool humanImmidiateWin(int& bestMove) {
for(int i = 0;i < 9;i ++) {
if(chessBoard[i/3][i%3]) continue;
chessBoard[i/3][i%3] = -1;
bool win = (isWin() == -1);
chessBoard[i/3][i%3] = 0;
if(win) {
bestMove = i;
return true;
}
}
return false;
}
int evaluate() {
int tmp[3][3], computerValue = 0, playerValue = 0;
for(int i = 0;i < 9;i ++)
tmp[i/3][i%3] = (!chessBoard[i/3][i%3]?1:chessBoard[i/3][i%3]);
for(int i = 0;i < 3;i ++)
computerValue += (tmp[i][0]+tmp[i][1]+tmp[i][2])/3 + (tmp[0][i]+tmp[1][i]+tmp[2][i])/3;
computerValue += (tmp[0][0] + tmp[1][1] + tmp[2][2])/3 + (tmp[2][0]+tmp[1][1]+tmp[0][2])/3;
for(int i = 0;i < 9;i ++)
tmp[i/3][i%3] = (!chessBoard[i/3][i%3]?-1:chessBoard[i/3][i%3]);
for(int i = 0;i < 3;i ++)
playerValue += (tmp[i][0]+tmp[i][1]+tmp[i][2])/3 + (tmp[0][i]+tmp[1][i]+tmp[2][i])/3;
playerValue += (tmp[0][0] + tmp[1][1] + tmp[2][2])/3 + (tmp[2][0]+tmp[1][1]+tmp[0][2])/3;
return computerValue + playerValue;
}
void findComputerBestMove(int& bestMove, int& value, int alpha, int beta, int deep) {
if(computerImmidiateWin(bestMove)) {
value = 60;
return ;
}
if(deep == 3) {
value = evaluate();
return ;
}
value = alpha;
for(int i = 0;i < 9 && value < beta;i ++) {
if(chessBoard[i/3][i%3]) continue;
chessBoard[i/3][i%3] = 1;
int tmp = -1, response = -1;
findHumanBestMove(tmp, response, value, beta, deep+1);
chessBoard[i/3][i%3] = 0;
if(response > value) value = response, bestMove = i;
}
}
void findHumanBestMove(int& bestMove, int& value, int alpha, int beta, int deep) {
if(humanImmidiateWin(bestMove)) {
value = -20;
return ;
}
if(deep == 3) {
value = evaluate();
return ;
}
value = beta;
for(int i = 0;i < 9 && value > alpha;i ++) {
if(chessBoard[i/3][i%3]) continue;
chessBoard[i/3][i%3] = -1;
int tmp = -1, response = -1;
findComputerBestMove(tmp, response, alpha, value, deep+1);
chessBoard[i/3][i%3] = 0;
if(response < value) value = response, bestMove = i;
}
}
void computerPlace() {
int bestMove = 0, value = 0;
const int deep = 1, alpha = -20, beta = 60;
findComputerBestMove(bestMove, value, alpha, beta, deep);
chessBoard[bestMove/3][bestMove%3] = 1;
}
void humanPlace() {
int x, y;
while(true) {
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 >> x >> y;
if (x < 0 || x > 3 || y < 0 || y > 3 || chessBoard[x-1][y-1] != 0) cout << "error, please input again:" << endl;
else break;
}
chessBoard[x-1][y-1] = -1;
}
bool gameOver() {
if(isWin()) return true;
int i;
for(i = 0;i < 9;i ++)
if(chessBoard[i/3][i%3] == 0) break;
return i == 9;
}
void playGame() {
int computerFirst;
memset(chessBoard, 0, sizeof chessBoard);
printChessBoard();
while(true) {
cout << "\nWho take the first step:\n1)Player. 2)Computer.[ ]\b\b";
cin >> computerFirst;
if(computerFirst != 1 && computerFirst != 2) getchar();
else break;
}
if(computerFirst == 2) computerPlace();
while(true) {
printChessBoard();
if(gameOver()) break;
humanPlace();
printChessBoard();
if(gameOver()) break;
computerPlace();
}
}
int main()
{
int option;
while(1) {
playGame();
if(isWin() == 0) cout << "\nDraw" << endl;
else if(isWin() == 1) cout << "\nComputer Win!\n" << endl;
else cout << "\nPlayer Win!\n" << endl;
cout << "\nTry Again?\n1)Yeah.\t2)Exit.[ ]\b\b";
cin >> option;
if(option != 1 && option != 2) getchar();
if(option == 2) break;
}
}
附录2（Java代码）
三个public类，分别是程序入口的Main类、界面设计的Window类和实现井字棋的TicTacToe类。
Main.java
创建TicTacToe对象，TicTacToe类的构造函数中调用了实现全部功能的函数。
packageexp2;/**
* @author LJR
* @create 2021-11-14 21:28
*/publicclassMain{publicstaticvoidmain(String[] args){newTicTacToe();}}
Window.java
界面设计的类，同时也绑定了对初始界面中按钮的点击事件。
packageexp2;importjavax.swing.*;importjava.awt.*;/**
* @author LJR
* @create 2021-11-14 21:27
*/publicclassWindowextendsJFrame{privatestaticfinallong serialVersionUID =-6740703588976621222L;publicJButton[] nineBoard =newJButton[9];// 棋盘都是按钮publicJButton[] buttons;// 方便井字棋类中绑定监听publicstaticboolean gameStart_PvE =false;// 游戏是否开始publicstaticboolean gameStart_PvP =false;// 游戏是否开始publicstaticint option =0;// 1：PvP or 2：PvEpublicJTextField[] sorceBoard_pve;// 计分板publicJTextField[] sorceBoard_pvp;publicWindow(){super("利用α-β搜索的博弈树算法编写一字棋游戏");Container c =this.getContentPane();
c.add(getJButton());
c.setBackground(Color.white);this.setSize(300,330);this.setUndecorated(false);this.setLocationRelativeTo(null);this.setVisible(true);this.setResizable(false);this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);}publicJTextField[]generateSorceBoard(intPorE){// 生成计分板String text[][]=newString[][]{{"P1","0",":","0","P2"},{"P","0",":","0","E"}};// string 0 : PvP string 1 : pveint bound_x[]={65,95,125,155,185};int align[]={JTextField.LEFT,JTextField.RIGHT,JTextField.CENTER,JTextField.LEFT,JTextField.RIGHT};int size_w =30, size_h =30, font_size =20, font_flag =Font.PLAIN;String font_style ="Forte";JTextField[] jfs =newJTextField[5];for(int i =0; i <5; i++){
jfs[i]=newJTextField(text[PorE][i]);
jfs[i].setBounds(bound_x[i],0, size_w, size_h);
jfs[i].setFont(newFont(font_style, font_flag, font_size));
jfs[i].setHorizontalAlignment(align[i]);
jfs[i].setForeground(newColor(255,255,255));
jfs[i].setOpaque(false);
jfs[i].setFocusable(false);
jfs[i].setCursor(Cursor.getPredefinedCursor(Cursor.DEFAULT_CURSOR));
jfs[i].setBorder(BorderFactory.createEmptyBorder(0,0,0,0));// 设置无边框}return jfs;}publicJButton[]generateButtons(){// 生成{"PvP", "PvE", "exit"}按钮String[] text =newString[]{"PvP","PvE","exit"};int[][] pos =newint[][]{{40,140},{160,140},{110,210}}, size =newint[][]{{76,35},{76,35},{60,35}};JButton[] jbs =newJButton[3];int font_size =30, font_flag =Font.PLAIN, color_R =255, color_G =131, color_B =62;String font_style ="Forte";for(int i =0; i <3; i++){
jbs[i]=newJButton(text[i]);
jbs[i].setBounds(pos[i][0], pos[i][1], size[i][0], size[i][1]);
jbs[i].setFont(newFont(font_style, font_flag, font_size));
jbs[i].setForeground(newColor(color_R, color_G, color_B));
jbs[i].setCursor(Cursor.getPredefinedCursor(Cursor.HAND_CURSOR));// 鼠标移入按钮变小手
jbs[i].setOpaque(false);// 透明
jbs[i].setBorder(BorderFactory.createEmptyBorder(0,0,0,0));
jbs[i].setContentAreaFilled(false);
jbs[i].setFocusPainted(false);
jbs[i].setRolloverEnabled(true);}return jbs;}publicJPanelgetJButton(){JPanel jP =newJPanel();
jP.setOpaque(false);
jP.setLayout(null);// 设置空布局，即绝对布局// 游戏界面JPanel chessboard_panel =newJPanel();
chessboard_panel.setLayout(null);
chessboard_panel.setBounds(0,0,300,330);
chessboard_panel.setBackground(newColor(45,45,45));JLabel jl =newJLabel();Icon icon1 =newImageIcon("src/board_2.jpg");// 注意路径
jl.setIcon(icon1);
jl.setBorder(BorderFactory.createEmptyBorder(0,0,0,0));
jl.setBounds(0,30, icon1.getIconWidth(), icon1.getIconHeight());
chessboard_panel.add(jl);
chessboard_panel.setVisible(false);
jP.add(chessboard_panel);// 计分板
sorceBoard_pvp =generateSorceBoard(0);
sorceBoard_pve =generateSorceBoard(1);// 开始界面JPanel start_panel =newJPanel();
start_panel.setLayout(null);// 必须设置面板为空布局
start_panel.setBackground(newColor(50,50,50));
start_panel.setBounds(0,0,300,330);
jP.add(start_panel);// logoJLabel logo =newJLabel();Icon icon =newImageIcon("src/TicTacToe_1.png");// 注意路径
logo.setIcon(icon);
logo.setBounds(10,50, icon.getIconWidth(), icon.getIconHeight());
start_panel.add(logo);
buttons =generateButtons();for(int i =0; i <3; i++) start_panel.add(buttons[i]);
buttons[0].addActionListener((actionEvent ->{// pvp // 绑定点击监听
option =1;// pvpfor(int i =0; i <5; i++) chessboard_panel.add(sorceBoard_pvp[i]);
chessboard_panel.setVisible(true);
start_panel.setVisible(false);startGame_PvP();// PvP开始}));
buttons[1].addActionListener((actionEvent ->{// pve
option =2;// pvefor(int i =0; i <5; i++) chessboard_panel.add(sorceBoard_pve[i]);
chessboard_panel.setVisible(true);
start_panel.setVisible(false);startGame_PvE();// 游戏开始}));
buttons[2].addActionListener((actionEvent ->{// exitSystem.exit(0);}));// 每个格子都是一个按钮for(int i =0; i <9; i++){
nineBoard[i]=newJButton();
nineBoard[i].setBounds(i %3*72+37, i /3*72+27,65,65);
nineBoard[i].setCursor(Cursor.getPredefinedCursor(Cursor.HAND_CURSOR));// 鼠标移入按钮变小手
nineBoard[i].setOpaque(false);// 透明，有无皆可？
nineBoard[i].setBorder(BorderFactory.createEmptyBorder(0,0,0,0));// 暂时注释
nineBoard[i].setContentAreaFilled(false);
nineBoard[i].setFocusPainted(false);
nineBoard[i].setRolloverEnabled(true);
jl.add(nineBoard[i]);}return jP;}publicvoidstartGame_PvE(){// System.out.println("PvE");Window.gameStart_PvE =true;// 只有当用户点击了PvE后才可以开始执行进程中的内容}publicvoidstartGame_PvP(){// System.out.println("PvP");Window.gameStart_PvP =true;}}
TicTacToe.java
核心类，该类其中包含了各种内部类和各种线程。该类中实现了
α
−
β
\alpha-\beta
α−β剪枝的极大极小分析算法，同时监听了一些对游戏界面落子点击等事件。
packageexp2;importjavax.swing.*;importjava.awt.*;/**
* @author LJR
* @create 2021-11-15 15:50
*/publicclassTicTacToe{Window window;// 使用其中的成员// 锁publicObject lock =newObject();// 棋盘int chessBoard[][]=newint[3][3];// 变量，PvEboolean thread_computer_over =false;// 电脑线程是否结束boolean thread_human_over =false;// 玩家线程是否结束boolean newgame =true;// 是否开始新游戏int cnt =0;// 奇偶控制youCanClick的真假，不知道为什么通过取反对youCanClick赋值无效int nowStatus =0;// 现在是PvE还是PvPint beclickedButton =-1;// 被点击的按钮的编号boolean humanPlaceOver =false;// 是否正在等待玩家点击，落子boolean youCanClick =false;// 控制玩家点击格子是否有效，即若false则玩家不能落子boolean buttonsAlive[]=newboolean[9];// 该按键是否能被点击是否有效，即若flase则该处已被落子// 可见允许在某处落子首先要保证youCanClick=true，且buttonsAlive[i]=true// 变量，PvPboolean thread_p1_over =false;// player1的线程是否结束boolean thread_p2_over =false;boolean inP1Turn =true;// 处在P1的回合booleanP1PlaceOver=false;booleanP2PlaceOver=false;// 线程ControlScoreBoardColor thread_color =newControlScoreBoardColor();// PvEComputer thread_computer;Human thread_human;JudgeOver thread_judge =newJudgeOver();JudgeOption thread_option =newJudgeOption();ChangeRound thread_changeRound =newChangeRound();// PvPPlayer1 thread_p1 =newPlayer1();Player2 thread_p2 =newPlayer2();JudgeOver_PvP thread_gameover_pvp =newJudgeOver_PvP();ChangeRound_PvP thread_changeRound_pvp =newChangeRound_PvP();// 构造函数，一切的入口publicTicTacToe(){for(int i =0; i <9; i++) chessBoard[i /3][i %3]=0;// 初始化棋盘for(int i =0; i <9; i++) buttonsAlive[i]=true;// 最初任何位置均允许落子
window =newWindow();// 界面设计
thread_option.start();// 判断用户点击的PvP还是PvEaddButtonClickListener();}// 内部类，自定义整数类，因为Java自带的Integer类的value为final，要想实现类似于C++引用的功能，必须使用对象classMyInteger{privateint value;publicMyInteger(){}publicMyInteger(int value){this.value = value;}publicvoidsetValue(int value){this.value = value;}publicintgetValue(){return value;}}// 内部类，更改当前下棋方的计分板的颜色的线程，让下棋者更清楚地知道该谁落子classControlScoreBoardColorextendsThread{publicvoidrun(){while(true){try{Thread.sleep(30);}catch(InterruptedException exception){
exception.printStackTrace();}if(Window.gameStart_PvP){if(inP1Turn){
window.sorceBoard_pvp[0].setForeground(newColor(255,131,62));
window.sorceBoard_pvp[4].setForeground(newColor(255,255,255));}else{
window.sorceBoard_pvp[0].setForeground(newColor(255,255,255));
window.sorceBoard_pvp[4].setForeground(newColor(255,131,62));}}if(Window.gameStart_PvE){if(youCanClick){
window.sorceBoard_pve[0].setForeground(newColor(255,131,62));
window.sorceBoard_pve[4].setForeground(newColor(255,255,255));}else{
window.sorceBoard_pve[0].setForeground(newColor(255,255,255));
window.sorceBoard_pve[4].setForeground(newColor(255,131,62));}}}}}// 内部类，顶层线程，该线程中根据用户点击的是PvP还是PvE启动不同的线程classJudgeOptionextendsThread{publicvoidrun(){while(true){try{Thread.sleep(100);}catch(InterruptedException exception){
exception.printStackTrace();}if(Window.option ==1){
nowStatus =1;Window.option =0;gameStart_PvP();}if(Window.option ==2){
nowStatus =2;Window.option =0;gameStart_PvE();}}}}// 内部类，PvE：判断游戏结束的线程classJudgeOverextendsThread{publicvoidrun(){while(true){try{Thread.sleep(500);}catch(InterruptedException exception){
exception.printStackTrace();}if(thread_computer_over && thread_human_over){if(isWin()==0){// 若干空格保证文字居中JOptionPane.showMessageDialog(null," 平局","本局结果",1);// System.out.println("draw");}elseif(isWin()==1){JOptionPane.showMessageDialog(null," 你失败了","本局结果",1);
window.sorceBoard_pve[3].setText(Integer.parseInt(window.sorceBoard_pve[3].getText())+1+"");// 电脑积分加一// System.out.println("computer win");}else{JOptionPane.showMessageDialog(null," 你获胜了","本局结果",1);
window.sorceBoard_pve[1].setText(Integer.parseInt(window.sorceBoard_pve[1].getText())+1+"");// 玩家积分加一// System.out.println("player win");}try{Thread.sleep(300);}catch(InterruptedException exception){
exception.printStackTrace();}clearChessBoard();// 清空棋盘并初始化一些变量，方便下局的开始}}}}// 内部类，PvE：实现电脑与玩家轮流先后手classChangeRoundextendsThread{publicvoidrun(){while(true){try{Thread.sleep(300);}catch(InterruptedException exception){
exception.printStackTrace();}if(newgame){
newgame =false;
youCanClick =(cnt %2!=0);
cnt++;
thread_computer =newComputer();
thread_human =newHuman();
thread_computer.setName("computer");
thread_human.setName("human");
thread_computer.start();
thread_human.start();}}}}// 内部类，PvE：电脑线程classComputerextendsThread{publicvoidrun(){while(true){if(gameOver()){Window.gameStart_PvE =false;// 游戏结束
thread_computer_over =true;// System.out.println("computer gameOver");return;}try{// 不睡一会不行Thread.sleep(50);// 这个睡眠事件可以理解为刷新时间}catch(InterruptedException e){
e.printStackTrace();}if(Window.gameStart_PvE){synchronized(lock){if(!youCanClick){// 电脑回合try{// 让计算机多睡会，模仿井字棋小游戏（如果计算机在玩家落子后直接显示，效果不佳）Thread.sleep(1000);}catch(InterruptedException e){
e.printStackTrace();}computerPlace();// 核心算法
youCanClick =true;}else{try{
lock.wait();}catch(InterruptedException e){
e.printStackTrace();}}}}}}}// 内部类，PvE：玩家线程classHumanextendsThread{publicvoidrun(){while(true){if(gameOver()){Window.gameStart_PvE =false;// 游戏结束
thread_human_over =true;// System.out.println("player gameOver");return;}try{// 不睡一会不行Thread.sleep(50);}catch(InterruptedException e){
e.printStackTrace();}if(Window.gameStart_PvE){synchronized(lock){if(youCanClick){// 玩家回合并humanPlace();// 等待点击事件的发生
youCanClick =false;}else{
lock.notify();}}}}}}// 内部类，PvP：判断游戏是否结束classJudgeOver_PvPextendsThread{publicvoidrun(){while(true){try{Thread.sleep(500);}catch(InterruptedException exception){
exception.printStackTrace();}if(thread_p1_over && thread_p2_over){if(isWin()==0){// 若干空格保证文字居中JOptionPane.showMessageDialog(null," 平局","本局结果",1);System.out.println("draw");}elseif(isWin()==1){JOptionPane.showMessageDialog(null," P1获胜了","本局结果",1);
window.sorceBoard_pvp[1].setText(Integer.parseInt(window.sorceBoard_pvp[1].getText())+1+"");// P1积分加一System.out.println("P1 win");}else{JOptionPane.showMessageDialog(null," P2获胜了","本局结果",1);
window.sorceBoard_pvp[3].setText(Integer.parseInt(window.sorceBoard_pvp[3].getText())+1+"");// P2积分加一System.out.println("P2 win");}try{Thread.sleep(300);}catch(InterruptedException exception){
exception.printStackTrace();}clearChessBoard();// 清空棋盘并初始化一些变量，方便下局的开始}}}}// 内部类，PvP：实现玩家1与玩家2轮流先后手classChangeRound_PvPextendsThread{publicvoidrun(){while(true){try{Thread.sleep(300);}catch(InterruptedException exception){
exception.printStackTrace();}if(newgame){
newgame =false;
inP1Turn =(cnt %2==0);
cnt++;System.out.println(inP1Turn);
thread_p1 =newPlayer1();
thread_p2 =newPlayer2();
thread_p1.setName("P1");
thread_p2.setName("P2");
thread_p1.start();
thread_p2.start();}}}}// 内部类，PvP：玩家1线程classPlayer1extendsThread{publicvoidrun(){while(true){if(gameOver()){Window.gameStart_PvP =false;// 游戏结束
thread_p1_over =true;// System.out.println("p1 gameOver");return;}try{Thread.sleep(50);}catch(InterruptedException exception){
exception.printStackTrace();}if(Window.gameStart_PvP){synchronized(lock){if(inP1Turn){// P1的回合P1Place();// P1落子
inP1Turn =false;}else{try{
lock.wait();}catch(InterruptedException exception){
exception.printStackTrace();}}}}}}}// 内部类，PvP：玩家2线程classPlayer2extendsThread{publicvoidrun(){while(true){if(gameOver()){Window.gameStart_PvP =false;// 游戏结束
thread_p2_over =true;// System.out.println("p2 gameOver");return;}try{Thread.sleep(50);}catch(InterruptedException exception){
exception.printStackTrace();}if(Window.gameStart_PvP){synchronized(lock){if(!inP1Turn){// P2的回合P2Place();// P2落子
inP1Turn =true;}else{
lock.notify();}}}}}}// PvE：顶层函数，启动三个线程：1.判断本局是否结束的线程 2.更改当前下棋方的计分板的颜色的线程 3.切换先后手的线程publicvoidgameStart_PvE(){
thread_judge.start();// 一直存活
thread_color.start();// 谁落子，谁的计分板显示为橙色
thread_changeRound.setName("round");
thread_changeRound.start();// 电脑下棋的线程和玩家下棋的线程均在此线程中开启}// PvP：顶层函数，启动三个线程：1.判断本局是否结束的线程 2.更改当前下棋方的计分板的颜色的线程 3.切换先后手的线程publicvoidgameStart_PvP(){
thread_gameover_pvp.start();// 一直存活
thread_color.start();
thread_changeRound_pvp.setName("round");
thread_changeRound_pvp.start();// 电脑下棋的线程和玩家下棋的线程均在此线程中开启}// 玩家1落子函数publicvoidP1Place(){if(!Window.gameStart_PvP)return;// 这样player线程才能终止// System.out.println("waiting for P1");while(!P1PlaceOver){try{// 不睡一会不行Thread.sleep(50);}catch(Exception e){}}
chessBoard[beclickedButton /3][beclickedButton %3]=1;// System.out.println("P1 place!");P1PlaceOver=false;}// 玩家2落子函数publicvoidP2Place(){if(!Window.gameStart_PvP)return;// 这样player线程才能终止// System.out.println("waiting for P2");while(!P2PlaceOver){try{// 不睡一会不行Thread.sleep(50);}catch(Exception e){}}
chessBoard[beclickedButton /3][beclickedButton %3]=-1;// System.out.println("P2 place!");P2PlaceOver=false;}// 为井字棋按钮绑定点击事件，由于监听中只能使用lambda表达式或者常量，所以需要对每个单独绑定监听publicvoidaddButtonClickListener(){
window.nineBoard[0].addActionListener((actionEvent ->{// 0if(youCanClick && nowStatus ==2&& buttonsAlive[0]){// 允许玩家点击// System.out.println("effective click 0");
buttonsAlive[0]=false;// 此位置已存在棋子（双方均不可以再下）
youCanClick =false;// 玩家不可以落子，因此点击事件已经发生了，说明玩家刚下完
beclickedButton =0;// 0 号被点击
humanPlaceOver =true;// 用于控制等待玩家落子
window.nineBoard[0].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明落子}if(nowStatus ==1&& buttonsAlive[0]){// PvP// System.out.println("effective click 0");
buttonsAlive[0]=false;// 此位置已存在棋子（双方均不可以再下）
beclickedButton =0;// 0 号被点击if(inP1Turn){P1PlaceOver=true;// 如果当前落子的是P1则说明P1落完
window.nineBoard[0].setIcon(newImageIcon("src/X_1.gif"));// 点击后修改按钮背景，表明P1落子}else{P2PlaceOver=true;// 如果当前落子的是P2则说明P2落完
window.nineBoard[0].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明P2落子}}}));
window.nineBoard[1].addActionListener((actionEvent ->{// 1if(youCanClick && nowStatus ==2&& buttonsAlive[1]){// 允许玩家点击// System.out.println("effective click 1");
buttonsAlive[1]=false;
youCanClick =false;
beclickedButton =1;
humanPlaceOver =true;
window.nineBoard[1].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明落子}if(nowStatus ==1&& buttonsAlive[1]){// PvP// System.out.println("effective click 1");
buttonsAlive[1]=false;// 此位置已存在棋子（双方均不可以再下）
beclickedButton =1;if(inP1Turn){P1PlaceOver=true;// 如果当前落子的是P1则说明P1落完
window.nineBoard[1].setIcon(newImageIcon("src/X_1.gif"));// 点击后修改按钮背景，表明P1落子}else{P2PlaceOver=true;// 如果当前落子的是P2则说明P2落完
window.nineBoard[1].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明P2落子}}}));
window.nineBoard[2].addActionListener((actionEvent ->{// 2if(youCanClick && nowStatus ==2&& buttonsAlive[2]){// 允许玩家点击// System.out.println("effective click 2");
buttonsAlive[2]=false;
youCanClick =false;
beclickedButton =2;
humanPlaceOver =true;
window.nineBoard[2].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明落子}if(nowStatus ==1&& buttonsAlive[2]){// PvP// System.out.println("effective click 2");
buttonsAlive[2]=false;// 此位置已存在棋子（双方均不可以再下）
beclickedButton =2;if(inP1Turn){P1PlaceOver=true;// 如果当前落子的是P1则说明P1落完
window.nineBoard[2].setIcon(newImageIcon("src/X_1.gif"));// 点击后修改按钮背景，表明P1落子}else{P2PlaceOver=true;// 如果当前落子的是P2则说明P2落完
window.nineBoard[2].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明P2落子}}}));
window.nineBoard[3].addActionListener((actionEvent ->{// 3if(youCanClick && nowStatus ==2&& buttonsAlive[3]){// 允许玩家点击// System.out.println("effective click 3");
buttonsAlive[3]=false;
youCanClick =false;
beclickedButton =3;
humanPlaceOver =true;
window.nineBoard[3].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明落子}if(nowStatus ==1&& buttonsAlive[3]){// PvP// System.out.println("effective click 3");
buttonsAlive[3]=false;// 此位置已存在棋子（双方均不可以再下）
beclickedButton =3;if(inP1Turn){P1PlaceOver=true;// 如果当前落子的是P1则说明P1落完
window.nineBoard[3].setIcon(newImageIcon("src/X_1.gif"));// 点击后修改按钮背景，表明P1落子}else{P2PlaceOver=true;// 如果当前落子的是P2则说明P2落完
window.nineBoard[3].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明P2落子}}}));
window.nineBoard[4].addActionListener((actionEvent ->{// 4if(youCanClick && nowStatus ==2&& buttonsAlive[4]){// 允许玩家点击// System.out.println("effective click 4");
buttonsAlive[4]=false;
youCanClick =false;
beclickedButton =4;
humanPlaceOver =true;
window.nineBoard[4].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明落子}if(nowStatus ==1&& buttonsAlive[4]){// PvP// System.out.println("effective click 4");
buttonsAlive[4]=false;// 此位置已存在棋子（双方均不可以再下）
beclickedButton =4;if(inP1Turn){P1PlaceOver=true;// 如果当前落子的是P1则说明P1落完
window.nineBoard[4].setIcon(newImageIcon("src/X_1.gif"));// 点击后修改按钮背景，表明P1落子}else{P2PlaceOver=true;// 如果当前落子的是P2则说明P2落完
window.nineBoard[4].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明P2落子}}}));
window.nineBoard[5].addActionListener((actionEvent ->{// 5if(youCanClick && nowStatus ==2&& buttonsAlive[5]){// 允许玩家点击// System.out.println("effective click 5");
buttonsAlive[5]=false;
youCanClick =false;
beclickedButton =5;
humanPlaceOver =true;
window.nineBoard[5].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明落子}if(nowStatus ==1&& buttonsAlive[5]){// PvP// System.out.println("effective click 5");
buttonsAlive[5]=false;// 此位置已存在棋子（双方均不可以再下）
beclickedButton =5;if(inP1Turn){P1PlaceOver=true;// 如果当前落子的是P1则说明P1落完
window.nineBoard[5].setIcon(newImageIcon("src/X_1.gif"));// 点击后修改按钮背景，表明P1落子}else{P2PlaceOver=true;// 如果当前落子的是P2则说明P2落完
window.nineBoard[5].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明P2落子}}}));
window.nineBoard[6].addActionListener((actionEvent ->{// 6if(youCanClick && nowStatus ==2&& buttonsAlive[6]){// 允许玩家点击// System.out.println("effective click 6");
buttonsAlive[6]=false;
youCanClick =false;
beclickedButton =6;
humanPlaceOver =true;
window.nineBoard[6].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明落子}if(nowStatus ==1&& buttonsAlive[6]){// PvP// System.out.println("effective click 6");
buttonsAlive[6]=false;// 此位置已存在棋子（双方均不可以再下）
beclickedButton =6;if(inP1Turn){P1PlaceOver=true;// 如果当前落子的是P1则说明P1落完
window.nineBoard[6].setIcon(newImageIcon("src/X_1.gif"));// 点击后修改按钮背景，表明P1落子}else{P2PlaceOver=true;// 如果当前落子的是P2则说明P2落完
window.nineBoard[6].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明P2落子}}}));
window.nineBoard[7].addActionListener((actionEvent ->{// 7if(youCanClick && nowStatus ==2&& buttonsAlive[7]){// 允许玩家点击// System.out.println("effective click 7");
buttonsAlive[7]=false;
youCanClick =false;
beclickedButton =7;
humanPlaceOver =true;
window.nineBoard[7].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明落子}if(nowStatus ==1&& buttonsAlive[7]){// PvP// System.out.println("effective click 7");
buttonsAlive[7]=false;// 此位置已存在棋子（双方均不可以再下）
beclickedButton =7;if(inP1Turn){P1PlaceOver=true;// 如果当前落子的是P1则说明P1落完
window.nineBoard[7].setIcon(newImageIcon("src/X_1.gif"));// 点击后修改按钮背景，表明P1落子}else{P2PlaceOver=true;// 如果当前落子的是P2则说明P2落完
window.nineBoard[7].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明P2落子}}}));
window.nineBoard[8].addActionListener((actionEvent ->{// 8if(youCanClick && nowStatus ==2&& buttonsAlive[8]){// 允许玩家点击// System.out.println("effective click 8");
buttonsAlive[8]=false;
youCanClick =false;
beclickedButton =8;
humanPlaceOver =true;
window.nineBoard[8].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明落子}if(nowStatus ==1&& buttonsAlive[8]){// PvP// System.out.println("effective click 8");
buttonsAlive[8]=false;// 此位置已存在棋子（双方均不可以再下）
beclickedButton =8;if(inP1Turn){P1PlaceOver=true;// 如果当前落子的是P1则说明P1落完
window.nineBoard[8].setIcon(newImageIcon("src/X_1.gif"));// 点击后修改按钮背景，表明P1落子}else{P2PlaceOver=true;// 如果当前落子的是P2则说明P2落完
window.nineBoard[8].setIcon(newImageIcon("src/O_1.gif"));// 点击后修改按钮背景，表明P2落子}}}));}// 清空棋盘并初始化变量publicvoidclearChessBoard(){for(int i =0; i <9; i++){
chessBoard[i /3][i %3]=0;// 初始化棋盘
buttonsAlive[i]=true;// 按键都是可点击的
window.nineBoard[i].setIcon(newImageIcon("src/tm.png"));}// PvE
thread_human_over =false;
thread_human_over =false;Window.gameStart_PvE =true;// 游戏开始
newgame =true;
beclickedButton =-1;// 被点击的按钮的编号
humanPlaceOver =false;// 是否正在等待玩家点击，落子// PvP
thread_p1_over =false;
thread_p2_over =false;Window.gameStart_PvP =true;// 游戏开始
beclickedButton =-1;// 被点击的按钮的编号P1PlaceOver=false;P2PlaceOver=false;}// --------------- 极大极小算法核心（start） ---------------// 判断是否存在一方胜利intisWin(){// 判断是否存在一方胜利for(int i =0; i <3; i++){if(chessBoard[i][0]!=0&& chessBoard[i][0]== chessBoard[i][1]&& chessBoard[i][1]== chessBoard[i][2])return chessBoard[i][0];if(chessBoard[0][i]!=0&& chessBoard[0][i]== chessBoard[1][i]&& chessBoard[1][i]== chessBoard[2][i])return chessBoard[0][i];}if(chessBoard[0][0]!=0&& chessBoard[0][0]== chessBoard[1][1]&& chessBoard[1][1]== chessBoard[2][2])return chessBoard[0][0];if(chessBoard[2][0]!=0&& chessBoard[2][0]== chessBoard[1][1]&& chessBoard[1][1]== chessBoard[0][2])return chessBoard[2][0];return0;// 0 不代表平局}// 判断游戏是否结束publicbooleangameOver(){if(isWin()!=0)returntrue;int i;for(i =0; i <9; i++)if(chessBoard[i /3][i %3]==0)break;return i ==9;}// 计算估值intevaluate(){int tmp[][]=newint[3][3], computerValue =0, playerValue =0;// 计算MAX的估值（computer）for(int i =0; i <9; i++)
tmp[i /3][i %3]=(chessBoard[i /3][i %3]==0?1: chessBoard[i /3][i %3]);for(int i =0; i <3; i++)
computerValue +=(tmp[i][0]+ tmp[i][1]+ tmp[i][2])/3+(tmp[0][i]+ tmp[1][i]+ tmp[2][i])/3;
computerValue +=(tmp[0][0]+ tmp[1][1]+ tmp[2][2])/3+(tmp[2][0]+ tmp[1][1]+ tmp[0][2])/3;// 计算MIN的估值（player）for(int i =0; i <9; i++)
tmp[i /3][i %3]=(chessBoard[i /3][i %3]==0?-1: chessBoard[i /3][i %3]);for(int i =0; i <3; i++)
playerValue +=(tmp[i][0]+ tmp[i][1]+ tmp[i][2])/3+(tmp[0][i]+ tmp[1][i]+ tmp[2][i])/3;
playerValue +=(tmp[0][0]+ tmp[1][1]+ tmp[2][2])/3+(tmp[2][0]+ tmp[1][1]+ tmp[0][2])/3;return computerValue + playerValue;}// 电脑：尝试找最佳的一步，如果这步能获胜，则下这步，否则通过alpha-beta剪枝的极大极小算法找最佳位置publicbooleancomputerImmidiateWin(MyInteger bestMove){for(int i =0; i <9; i++){if(chessBoard[i /3][i %3]!=0)continue;
chessBoard[i /3][i %3]=1;boolean win =(isWin()==1);
chessBoard[i /3][i %3]=0;if(win){
bestMove.setValue(i);// 如果找到某一步可以使电脑胜利，则bestMove设置为此步，通过“引用”返回returntrue;}}returnfalse;}// 玩家：尝试找最佳的一步，如果这步能获胜，则下这步，否则通过alpha-beta剪枝的极大极小算法找最佳位置publicbooleanhumanImmidiateWin(MyInteger bestMove){for(int i =0; i <9; i++){if(chessBoard[i /3][i %3]!=0)continue;
chessBoard[i /3][i %3]=-1;boolean win =(isWin()==-1);
chessBoard[i /3][i %3]=0;if(win){
bestMove.setValue(i);returntrue;}}returnfalse;}// 电脑：alpha-beta剪枝的极大极小算法publicvoidfindComputerBestMove(MyInteger bestMove,MyInteger value,int alpha,int beta,int deep){if(computerImmidiateWin(bestMove)){// 如果存在必胜的一步，则走这步
value.setValue(60);// 必胜对应的估值为60return;}if(deep ==3){// 最多到第三层，其实是两层剪枝
value.setValue(evaluate());// 当前节点的估值return;}
value.setValue(alpha);for(int i =0; i <9&& value.getValue()< beta; i++){// 如果当前节点的value（这个value表示的就是MAX节点的范围[value,+∞)） >= 其祖先节点的beta（即靠近树根的MIN节点的范围(-∞,beta]）if(chessBoard[i /3][i %3]!=0)continue;// 非零才行
chessBoard[i /3][i %3]=1;MyInteger tmp =newMyInteger(-1), response =newMyInteger(-1);findHumanBestMove(tmp, response, value.getValue(), beta, deep +1);// -1为临时值，会在递归中更新；response为子节点的估值，回传值；当前节点的value值作为alpha值，即MAX节点的范围[value,+∞)，用于该函数内部的剪枝
chessBoard[i /3][i %3]=0;// 回溯if(response.getValue()> value.getValue()){// 当前节点为MAX节点，所以需要用子节点的最大值更新
value.setValue(response.getValue());
bestMove.setValue(i);// 更新最佳落子点}}}// 玩家：alpha-beta剪枝的极大极小算法publicvoidfindHumanBestMove(MyInteger bestMove,MyInteger value,int alpha,int beta,int deep){if(humanImmidiateWin(bestMove)){
value.setValue(-20);return;}if(deep ==3){
value.setValue(evaluate());return;}
value.setValue(beta);for(int i =0; i <9&& value.getValue()> alpha; i++){if(chessBoard[i /3][i %3]!=0)continue;
chessBoard[i /3][i %3]=-1;MyInteger tmp =newMyInteger(-1), response =newMyInteger(-1);findComputerBestMove(tmp, response, alpha, value.getValue(), deep +1);
chessBoard[i /3][i %3]=0;if(response.getValue()< value.getValue()){
value.setValue(response.getValue());
bestMove.setValue(i);}}}// 电脑落子publicvoidcomputerPlace(){MyInteger bestMove =newMyInteger(0), value =newMyInteger(0);// 通过对象传，可以实现类似C++的引用的效果finalint deep =1, alpha =-20, beta =60;findComputerBestMove(bestMove, value, alpha, beta, deep);
chessBoard[bestMove.getValue()/3][bestMove.getValue()%3]=1;
buttonsAlive[bestMove.getValue()]=false;// System.out.println(bestMove.getValue());
window.nineBoard[bestMove.getValue()].setIcon(newImageIcon("src/X_1.gif"));}// 玩家落子publicvoidhumanPlace(){if(!Window.gameStart_PvE)return;// 这样player线程才能终止// System.out.println("waiting for human");while(!humanPlaceOver){try{// 不睡一会不行Thread.sleep(50);}catch(Exception e){}}
chessBoard[beclickedButton /3][beclickedButton %3]=-1;// System.out.println("human place!");
humanPlaceOver =false;}// --------------- 极大极小算法核心（end） ---------------}
本文转载自: https://blog.csdn.net/weixin_46221946/article/details/122354032
版权归原作者 不牌不改 所有， 如有侵权，请联系我们删除。
版权归原作者 不牌不改 所有， 如有侵权，请联系我们删除。