# 井字棋_minimax算法_alpha-beta剪枝
**Repository Path**: DaleGG/Tic-Tac-Toe
## Basic Information
- **Project Name**: 井字棋_minimax算法_alpha-beta剪枝
- **Description**: 井字棋_minimax算法_alpha-beta剪枝
并且实现了4*4棋盘
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No
## Statistics
- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-06-03
- **Last Updated**: 2022-06-06
## Categories & Tags
**Categories**: Uncategorized
**Tags**: None
## README
# 棋盘对弈
**MIN-MAX(minimax)算法 Alpha-Beta剪枝**
## 介绍
Minimax算法被广泛应用在棋类（零和游戏，回合制，双方都很聪明采用最优策略，完全信息）游戏中，是一种找出失败的最大可能性中的最小值的算法。是基于决策树和搜索的智能算法。
以“井字棋”为例
我们通过穷举所有结果（或者有其他估值函数这里不展开） 并为输、赢、平局 打上标签（例如0表示平局，+1表示X赢）
对于X来说，目的是要上自己更可能地得到1（由于井字棋只有0，-1，1），X会尽量选取最大，所以MAX行就表示X要获得最大，反之O为MIN行，要选取最小。
由此，我们就可以从Terminal最终结果反推每层。
-----------
井字棋多叉树深度比较深，这里我们用更简单的例子来说明
圆圈为MAX层，力求结果最大，反之方形为MIN层，力求最小。
假设双方都选择了最优路径
1. 先手为根，力求最大会左走
2. 后手为方，依然左走
最终游戏为60分
> 剪枝版见 alpha-beta剪枝
## MinMax算法
（Java实现）
在已知叶子节点值的情况下，回溯生成每层的值，用到树形结构，递归。
```java
/**
* 最基本
* 二叉树 minmax
* @param node 当前节点
* @param who 区分先手后手
*/
static int minmax(Node node, boolean who) {
/*这是一棵完全二叉树*/
if (node.children[0] == null) {
//叶子节点 直接返回
return node.value;
}
if (who) {
int temp = Integer.MIN_VALUE;
int value = minmax(node.left, !who);//向左孩子遍历，并换人
temp = Math.max(value, temp);//取左子树的"最大值"
value = minmax(node.right, !who);
temp = Math.max(value, temp);//取右子树的"最大值"
node.value = temp;
return temp;
} else {
int temp2 = Integer.MAX_VALUE;
int value = minmax(node.left, !who);//向左孩子遍历，并换人
temp2 = Math.min(value, temp2);//取左子树的"最小值"
value = minmax(node.right, !who);//向左孩子遍历，并换人
temp2 = Math.min(value, temp2);//取右子树的"最小值"
node.value = temp2;
return temp2;
}
}
```
对代码简化
```java
/**
* 多叉树 minmax 代码简化
*/
static int minmax2(Node node, boolean who) {
/*这是一棵完全二叉树*/
if (node.children[0] == null) {
return node.value;
}
int temp = who ? Integer.MIN_VALUE : Integer.MAX_VALUE;
/*改用数组实现多叉树*/
int value;
for (int i = 0; i < 2 && node.children[i] != null; i++) {
value = minmax2(node.children[i], !who);//孩子遍历，并换人
temp = who ? Math.max(value, temp) : Math.min(value, temp);//取右子树的"最大值"
}
node.value = temp;
return temp;
}
```
> 其他参考代码见尾
这里有一个很大的缺陷，对于局面复杂的问题（例如五子棋），需要很大的空间。以及部分节点跟最后的结果无关，无需展开局面和计算估值，所以我们需要剪枝。
## alpha-beta剪枝
Alpha-beta(α − β)剪枝的名称来自计算过程中传递的两个边界，这些边界基于已经看到的搜索树部分来限制可能的解决方案集。 其中，Alpha(α)表示目前所有可能解中的最大下界，Beta(β)表示目前所有可能解中的最小上界。
因此，如果搜索树上的一个节点被考虑作为最优解的路上的节点（或者说是这个节点被认为是有必要进行搜索的节点），那么它一定满足以下条件（N 是当前节点的估价值）：
$$
α \leqslant N \leqslant β
$$
在我们进行求解的过程中，α 和β 会逐渐逼近。如果对于某一个节点，出现了α > β 的情况，那么，说明这个点一定不会产生最优解了，所以，我们就不再对其进行扩展（也就是不再生成子节点），这样就完成了对博弈树的剪枝。
还是用上面的例子：
1、
初始参数alpha设为-∞ beta为+∞ ，按照递归顺序（其中叶子节点直接向上层返回），先处理左边正方形，更新最小值上界Beta为60。
2、
递归返回到根，注意此时仍然是beta由+∞，更新最大值下界Alpha为 60（此时只受到左子树影响）
3、
根向右递归，注意此时保留由根节点递归传来的alpha=60 beta=+∞ 参数，然后由孩子更新最小值上界Beta为15。此时违背alpha <= beta的条件，我们就可以对右子树，进行剪枝如下图（对于根节点已知最大下界至少为60，右子树存在不超过下界60时，如15，他一定会选择走左子树，所以对右子树多余部分可剪枝）。
就这样，在规模更大的对弈中，我们将删除大量不需要的情况，依然能让我们进行最优的决策。
附上代码（java）
```java
/**
* 二叉树（完全），实现alpha-beta剪枝 minmax
*
* @param node 结点
* @param who 最大者为true 最小者为false
* @param alpha 下界由最大者管理，若子树返回这大于alpha 则对其更新
* @param beta 上界由最小者管理----
*/
static int ab_minmax1(Node node, boolean who, Integer alpha, Integer beta) {
if (node.left == null) {
return node.value;
}
if (who) {
int temp = Integer.MIN_VALUE;
int value = ab_minmax1(node.left, !who, alpha, beta);//向左孩子遍历，并换人
temp = Math.max(value, temp);//取左子树的"最大值"
alpha = Math.max(alpha, temp);
if (beta <= alpha) {
node.right = null;
} else {
//剪枝了右边 就不用访问右边了
value = ab_minmax1(node.right, !who, alpha, beta);
temp = Math.max(value, temp);//取右子树的"最大值"
}
node.value = temp;
return temp;
} else {
int temp2 = Integer.MAX_VALUE;
int value = ab_minmax1(node.left, !who, alpha, beta);//向左孩子遍历，并换人
temp2 = Math.min(value, temp2);//取左子树的"最小值"
beta = Math.min(beta, temp2);
if (beta <= alpha) {
node.right = null;
} else {
//剪枝了右边 就不用访问右边了
value = ab_minmax1(node.right, !who, alpha, beta);
temp2 = Math.min(value, temp2);//取右子树的"最小值"
}
node.value = temp2;
return temp2;
}
}
```
```java
/**
* 多叉树 alpha_beta剪枝 minmax
*/
static int ab_minmax3(Node node, boolean who, Integer alpha, Integer beta) {
/*这是一棵完全二叉树*/
if (node.children[0] == null) {
//若为叶子节点 直接返回值给上层
return node.value;
}
int temp = who ? Integer.MIN_VALUE : Integer.MAX_VALUE;
/*改用数组实现多叉树*/
int value;
for (int i = 0; i < node.children.length && node.children[i] != null; i++) {
value = ab_minmax3(node.children[i], !who,alpha, beta);//孩子遍历，并换人
temp = who ? Math.max(value, temp) : Math.min(value, temp);//取孩子最大值和最小值
if (who) {
//最大者改下限alpha
alpha = Math.max(alpha, temp);
//剪枝
if (beta <= alpha) {
if (i + 1 < 2) {
node.children[i + 1] = null;
continue;
}
}
} else {
//最小者改上限beta
beta = Math.min(beta, temp);
if (beta <= alpha) {
if (i + 1 < 2) {
node.children[i + 1] = null;
//剪掉后就不用继续访问下层了哈
continue;
}
}
}
}
node.value = temp;
return temp;
}
```
## 其他参考代码
树形结构定义
```java
class Node {
Integer value;
Node left;
Node right;
Node[] children;
public Node(Integer value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
//此处多叉树用二叉树代替，读者可自行更改
this.children = new Node[]{left, right};
}
@Override
public String toString() {
return value + " ";
}
}
```
遍历方法
```java
/**
* 多叉树遍历
* @param node
*/
static void bianli2(Node node) {
if (node == null) {
return;
}
//先根遍历
System.out.println(node);
for (int i = 0; i < node.children.length; i++) {
bianli2(node.children[i]);
}
}
/**
* 二叉树遍历
* @param node
*/
static void bianli(Node node) {
if (node == null) {
return;
}
//先序遍历
System.out.println(node);
bianli(node.left);
bianli(node.right);
}
```
主函数测试（实例为上文举例的简单例子）
```java
public static void main(String[] args) {
Node a = new Node(60, null, null);
Node b = new Node(63, null, null);
Node c = new Node(15, null, null);
Node d = new Node(58, null, null);
Node e = new Node(null, a, b);
Node f = new Node(null, c, d);
Node root = new Node(null, e, f);
ab_minmax3(root, true, Integer.MIN_VALUE, Integer.MAX_VALUE);
bianli2(root);
}
```
## 游戏
由此启发 设计了4字棋游戏 效果不错
```java
import java.util.Scanner;
public class tic4 {
static char[] chess = new char[16];
static Scanner input = new Scanner(System.in);
public static void main(String[] args) {
//初始化
StartGame();
//这里默认玩家先下棋
char who = 'x';
//当双方都没赢 并棋盘有空 游戏继续
while (!Win('x') && !Win('o') && !isFull()) {
switch (who) {
case 'x':
playerGo();
who = 'o';
break;
case 'o':
computerGo();
who = 'x';
break;
}
}
//最终的结果界面 显示结果
if (Win('o')) {
System.out.println("Computer win！");
} else if (Win('x')) {
System.out.println("player win!");
} else {
System.out.println("it ends in a draw！");
}
}
private static void computerGo() {
int best = 0; //记录最佳位置
int bestScore = -1000;
int score;
for (int i = 0; i < chess.length; i++) {
if (chess[i] == '-') {
chess[i] = 'o';//电脑尝试下这里
score = bestInput('x', -10000, 10000);//core
if (score >= bestScore) {
bestScore = score;
System.out.println("电脑在"+i+"的分数："+bestScore);
best = i;
}
chess[i] = '-'; //只是试探并没下 重新置为空
}
}
//真正地下棋
chess[best] = 'o';
Print();
}
/**
* 核心
*
* @param who 用于区分max 和 min
* @param alpha
* @param beta
* @return
*/
private static int bestInput(char who, int alpha, int beta) {
//递归先写结束
if (Win('o')) {
//如果电脑赢了 (电脑取max)
return 1;
} else if (Win('x')) {
return -1;
} else if (isFull()) {
//棋盘满了 平局
return 0;
} else {
int score;
for (int i = 0; i < chess.length; i++) {
if (chess[i] == '-') {
chess[i] = who; //尝试计算下这一步
//并切换选手 继续计算
score = (who == 'x') ? bestInput('o', alpha, beta) : bestInput('x', alpha, beta);
//因为是试下 所以要还原
chess[i] = '-';
if (who == 'o') {
//max层 电脑
if (score > alpha) {
alpha = score;
}
if (alpha >= beta) {
//直接剪枝 返回给的是min ，min会选小也就是beta
return beta;
}
} else {
//min层
if (score < beta) {
beta = score;
}
if (alpha >= beta) {
//直接剪枝 返回
return alpha;
}
}
}
}
//最终返回
if (who == 'o')
return alpha;
else
return beta;
}
}
private static void playerGo() {
System.out.println("棋盘位置为0-15,请输入：");
int a = input.nextInt();
if (a >= 0 && a <= 15 && chess[a] == '-') {
chess[a] = 'x';
Print();
} else {
//输入错误给予提示
System.out.println("Your character input is wrong, please re-enter!");
playerGo();
}
}
public static void StartGame() {
//初始化棋盘
for (int i = 0; i < chess.length; i++) {
chess[i] = '-';
}
System.out.println("开始游戏");
Print();//打印期盼
}
/**
* 打印棋盘
*/
private static void Print() {
System.out.println("**********");
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
System.out.print("| ");
System.out.print(chess[i * 4 + j] + " ");
if (j == 3)
System.out.println("|");
}
if (i == 3) System.out.println("**********");
}
}
//判断输赢
public static Boolean Win(char player) {
if (chess[0] == player && chess[1] == player && chess[2] == player && chess[3] == player)
return true;
if (chess[4] == player && chess[5] == player && chess[6] == player && chess[7] == player)
return true;
if (chess[8] == player && chess[9] == player && chess[10] == player && chess[11] == player)
return true;
if (chess[12] == player && chess[13] == player && chess[14] == player && chess[15] == player)
return true;
if (chess[0] == player && chess[4] == player && chess[8] == player && chess[12] == player)
return true;
if (chess[1] == player && chess[5] == player && chess[9] == player && chess[13] == player)
return true;
if (chess[2] == player && chess[6] == player && chess[10] == player && chess[14] == player)
return true;
if (chess[3] == player && chess[7] == player && chess[11] == player && chess[15] == player)
return true;
if (chess[0] == player && chess[5] == player && chess[10] == player && chess[15] == player)
return true;
if (chess[3] == player && chess[6] == player && chess[9] == player && chess[12] == player)
return true;
return false;
}
//判断棋盘是否还有地方能下棋子
public static boolean isFull() {
//判断棋盘是否为空
for (int i = 0; i < chess.length; i++) {
if (chess[i] == '-')
return false; //棋盘还有位置可以下 不为空
}
return true;
}
}
```
效果如图：
