极小极大算法和alpha-beta算法
2022/5/5 17:14:04
本文主要是介绍极小极大算法和alpha-beta算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
package com.jn.rz.实验三; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * @author 江南大学1033190417 * @date 2022/5/5 10:42 */ public class Status { public char[][] status; public Status(char[][] status) { this.status = status; } //估价函数 public int f() { //计算MAX所有赢线 int M = 0; for (int i = 0; i < 3; i++) { if (status[i][0] != 'O' && status[i][1] != 'O' && status[i][2] != 'O') { ++M; } if (status[0][i] != 'O' && status[1][i] != 'O' && status[2][i] != 'O') { ++M; } } if (status[0][0] != 'O' && status[1][1] != 'O' && status[2][2] != 'O') { ++M; } if (status[0][2] != 'O' && status[1][1] != 'O' && status[2][0] != 'O') { ++M; } //计算MIN所有赢线 int O = 0; for (int i = 0; i < 3; i++) { if (status[i][0] != 'X' && status[i][1] != 'X' && status[i][2] != 'X') { ++O; } if (status[0][i] != 'X' && status[1][i] != 'X' && status[2][i] != 'X') { ++O; } } if (status[0][0] != 'X' && status[1][1] != 'X' && status[2][2] != 'X') { ++O; } if (status[0][2] != 'X' && status[1][1] != 'X' && status[2][0] != 'X') { ++O; } return M - O; } //判断胜负 public boolean isWin(char temp) { return ((status[0][0] == temp && status[0][1] == temp && status[0][2] == temp) || (status[1][0] == temp && status[1][1] == temp && status[1][2] == temp) || (status[2][0] == temp && status[2][1] == temp && status[2][2] == temp) || (status[0][0] == temp && status[1][0] == temp && status[2][0] == temp) || (status[0][1] == temp && status[1][1] == temp && status[2][1] == temp) || (status[0][2] == temp && status[1][2] == temp && status[2][2] == temp) || (status[0][0] == temp && status[1][1] == temp && status[2][2] == temp) || (status[0][2] == temp && status[1][1] == temp && status[2][0] == temp)); } //判断赢家 public int winner() { /* 当玩家先手时,max为玩家,所以返回1表示玩家赢,返回-1表示电脑赢,返回0表示平局或者还没结束; 当电脑先手时,max为电脑,所以返回1表示电脑赢,返回-1表示玩家赢,返回0表示平局或者还没结束。 */ if ((isWin('O') && first == 1) || (isWin('X') && first == -1)) { return 1; } else if ((isWin('X') && first == 1) || (isWin('O') && first == -1)) { return -1; } else { return 0; } } //判断棋牌是否下满 public boolean isFull() { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (status[i][j] == '.') return false; } } return true; } /** * 极小极大算法 * 通过递归,从叶子节点,推出父子节点(即往上推出)的值,该树的取值只有三种要么1,要么-1,要么0。 * * @param player 当前玩家 * @param nextPlayer 下一个玩家 * @return */ public int maxMinSearch(char player, char nextPlayer) { int maxVal = 2, minVal = 2; int win = winner(); if (win != 0) {//如果是叶子结点 return win; } if (isFull()) {//如果下满没有赢家是平局 return 0; } for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (status[i][j] == '.') { status[i][j] = player; int val = maxMinSearch(nextPlayer, player); status[i][j] = '.'; if ((player == 'O' && first == 1) || (player == 'X' && first == -1)) { if (maxVal < val) maxVal = val; } else if ((player == 'X' && first == 1) || (player == 'O' && first == -1)) { if (minVal > val) minVal = val; } } } } int reval = 0; if ((player == 'O' && first == 1) || (player == 'X' && first == -1)) { reval = maxVal; } else if ((player == 'X' && first == 1) || (player == 'O' && first == -1)) { reval = minVal; } return reval; } /** * alpha-beta算法 * @param player * @param nextPlayer * @param alpha -2 * @param beta 2 * @return */ public int alphaBetaSearch(char player,char nextPlayer,int alpha,int beta){ int win = winner(); if (win != 0) {//如果是叶子结点 return win; } if (isFull()) {//如果下满没有赢家是平局 return 0; } for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (status[i][j] == '.') { status[i][j] = player; int val = alphaBetaSearch(nextPlayer, player,alpha,beta); status[i][j] = '.'; if ((player == 'O' && first == 1) || (player == 'X' && first == -1)) { if (alpha<val) alpha=val; else return beta; } else if ((player == 'X' && first == 1) || (player == 'O' && first == -1)) { if (beta>val) beta=val; else return alpha; } } } } int reval = 0; if ((player == 'O' && first == 1) || (player == 'X' && first == -1)) { reval = alpha; } else if ((player == 'X' && first == 1) || (player == 'O' && first == -1)) { reval = beta; } return reval; } //玩家下棋 public void player() { Scanner scanner = new Scanner(System.in); while (true) { System.out.print("输入要下的位置(0-8):"); int pos = scanner.nextInt(); int x = pos / 3; int y = pos % 3; if (status[x][y] == '.') { status[x][y] = piece; break; } else { System.out.println("该位置有棋子了,请重新输入!"); } } } //电脑下棋,根据极小极大算法 public int computer() { int bestVal = 2;//用来记录先手为玩家时,电脑取min时,能取的最小值 int bestVal2 = -2;//用来记录先手为电脑时,电脑取max时,能取的最大值 List<Integer> myMoves = new ArrayList<>();//记录电脑能做的位置 for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (status[i][j] == '.') { status[i][j] = comPiece; int val = maxMinSearch(piece, comPiece); status[i][j] = '.'; if (first == 1) { if (val < bestVal) { bestVal = val; myMoves = new ArrayList<>(); myMoves.add(3 * i + j); } else if (val == bestVal) { myMoves.add(3 * i + j); } } else if (first == -1) { if (val > bestVal2) { bestVal2 = val; myMoves = new ArrayList<>(); myMoves.add(3 * i + j); } else if (val == bestVal2) { myMoves.add(3 * i + j); } } } } } return myMoves.get((int) (Math.random() * (myMoves.size()) - 1)); } //电脑下棋,根据alpha-beta算法 public int computer2() { int bestVal = 2;//用来记录先手为玩家时,电脑取min时,能取的最小值 int bestVal2 = -2;//用来记录先手为电脑时,电脑取max时,能取的最大值 List<Integer> myMoves = new ArrayList<>();//记录电脑能做的位置 for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (status[i][j] == '.') { status[i][j] = comPiece; int val = alphaBetaSearch(piece, comPiece,-2,2); status[i][j] = '.'; if (first == 1) { if (val < bestVal) { bestVal = val; myMoves = new ArrayList<>(); myMoves.add(3 * i + j); } else if (val == bestVal) { myMoves.add(3 * i + j); } } else if (first == -1) { if (val > bestVal2) { bestVal2 = val; myMoves = new ArrayList<>(); myMoves.add(3 * i + j); } else if (val == bestVal2) { myMoves.add(3 * i + j); } } } } } return myMoves.get((int) (Math.random() * (myMoves.size()) - 1)); } public void main(){ int nextMove = first; while (!isFull() && winner() == 0) { if (nextMove == 1 && !isFull()) {//玩家下 player(); print(status); nextMove = -1; } if (nextMove == -1 && !isFull()) {//电脑下 int computer = computer2(); status[computer / 3][computer % 3] = comPiece; System.out.println("电脑下的棋子"); print(status); nextMove = 1; } } printResult(); } //答应输赢结果 public void printResult(){ if (first==1){ if (piece=='O'){ System.out.println(new String[]{"电脑赢了", "平局", "你赢了"}[winner() + 1]); }else { System.out.println(new String[]{"你赢了", "平局", "电脑赢了"}[winner() + 1]); } }else if (first==-1){ if (piece=='X'){ System.out.println(new String[]{"电脑赢了", "平局", "你赢了"}[winner() + 1]); }else { System.out.println(new String[]{"你赢了", "平局", "电脑赢了"}[winner() + 1]); } } } //玩家优先是1 public static int first; //玩家选择的棋子 public static char piece; //电脑的棋子 public static char comPiece; public static void print(char[][] status) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { System.out.print(status[i][j] + "\t"); } System.out.println(); } } public static void main(String[] args) { char[][] begin = new char[][]{ {'.', '.', '.'}, {'.', '.', '.'}, {'.', '.', '.'}, }; Status status = new Status(begin); Scanner scanner = new Scanner(System.in); System.out.print("Human first[y/n]:"); String flag = scanner.nextLine(); first = flag.equals("y") ? 1 : -1; System.out.print("Human select X/O[X/O]:"); piece = scanner.nextLine().charAt(0); comPiece = piece == 'O' ? 'X' : 'O'; print(begin);//打印初始棋盘 status.main(); } }
这篇关于极小极大算法和alpha-beta算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-0601-电商商品中心解密:仅凭SKU真的足够吗?
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能