人工智能实验8 搜索技术：A*八数码，一字棋游戏

每日例行赊赞

一、实验目的

（1）掌握搜索技术的相关理论，能根据实际情况选取合适的搜索方法；

（2）进一步熟悉盲目搜索技术，掌握其在搜索过程中的优缺点；

（3）掌握启发式搜索的思想，能针对实际问题选取合适的评价函数；

（4）掌握问题归约的解决问题的思想，掌握与或图的搜索技术并能应用；

（5）深入理解博弈树搜索方法，并能应用于对弈类问题；

（6）根据自身情况，能选择合适的编程语言，实现启发式搜索、博弈树搜索方法、α-β剪枝算法，并能应用于实际AI问题。

二、实验内容

选择一种编程语言（最好为python或java），编程实现下面题目要求。

八数码难题

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格可用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局，找到一种启发式移动方法，实现从初始布局到目标布局的转变，并与实验7 的盲目移动方法对比。

1.需求分析

使用启发式移动方法解决八数码问题

2.数据结构、功能模块设计与说明

数据结构：类，小根堆，哈希表，数组

（1）A* 算法与估计函数设计

在二维坐标中，以实际距离 + 当前距离和终点的曼哈顿距离为启发值

给每个节点类【每个状态视为一个节点】加入一个字符串属性作为变成现在的样子的操作，然后之前做法的节点的操作数在堆排序换为【启发值】

而是否要入堆的依据则是利用哈希表，如果当前变化出来的字符串，已经在哈希表中存在，显然，它不应该入堆。因为它已经入堆一次

（2）判断初始状态和目标状态有没有可行解

当数字序列的逆序对个数为偶数：有解，为奇数：无解

3.核心代码（不要将全部代码贴在报告上）与测试结果说明

 /*** 计算字符串中所有字符'x'与其位置对应的坐标点之间的曼哈顿距离之和。** @param s 输入的字符串* @return 字符串中所有字符'x'与其位置对应的坐标点之间的曼哈顿距离之和*/static int function(String s){int result = 0;for(int i = 0; i < s.length(); i++) {if(s.charAt(i) != 'x'){continue;}int x1 = i/3, y1 = i%3;int x2 = (s.charAt(i)-'1')/3, y2=(s.charAt(i)-'1')%3;result += Math.abs(x1-x2) + Math.abs(y1-y2);}return result;}

static String bfs(){// 小根堆PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2)->o1.count-o2.count);heap.add(new Node(start, "", function(start)));visited.put(start, 0);// 定义方向数组和操作数组int [] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};String[] operations = {"up", "right", "down", "left"};// BFS 主循环while(!heap.isEmpty()) {Node node = heap.poll();// 如果找到目标状态，返回操作顺序if (node.state.equals(end)) { // 结束，返回操作顺序return node.path;}// 获取 'x' 的位置int index = node.state.indexOf('x'); // x的位置int Xstart = index / 3, Ystart = index % 3; // 计算出x的坐标// 遍历四个方向for (int i = 0; i < 4; i++) {char[] oldState = node.state.toCharArray();int Xend = Xstart + dx[i], Yend = Ystart + dy[i];String operate = operations[i];// 检查移动是否越界if (Xend < 0 || Xend >= 3 || Yend < 0 || Yend >= 3)continue;// 交换 'x' 和目标位置swap(oldState, index, Xend * 3 + Yend);// 转换字符数组为字符串String newState = String.valueOf(oldState);// 如果新状态未被访问过if (!visited.containsKey(newState)) {visited.put(newState, visited.get(node.state) + 1);// 将新状态加入堆中，并更新路径和计数heap.add(new Node(newState, node.path + operate + ' ', visited.get(node.state) + 1 + function(newState)));}}}// 如果无法到达终点，返回nullreturn null;
}

 //判断有无解，当数字序列的逆序对个数为偶数：有解，为奇数：无解String sequence = "";for(int i= 0; i < start.length(); i++) {if(start.charAt(i) != 'x') //等价于start[i]sequence += start.charAt(i);}int count = 0;for(int i=0; i < sequence.length(); i++) {for (int j = 0; j < sequence.length(); j++) {if((int) sequence.charAt(i) > (int) sequence.charAt(j))count++;}}if(count % 2 == 0){System.out.println("解存在");System.out.println(bfs());}else{System.out.println("解不存在");}

测试结果

完整代码：

import java.util.*;public class Astar8shuma {static String start = "2831647x5"; //初始状态static String end = "1238x4765"; //目标状态static HashMap<String, Integer> visited = new HashMap<>();static class Node{String state; //状态String path; //上下左右Integer count;//构造函数public Node(String state, String path, Integer count) {this.state = state;this.path = path;this.count = count;}}/*** 交换字符数组中指定位置的两个字符。*/static void swap(char[] a, int x, int y) {char temp = a[x];a[x] = a[y];a[y] = temp;}/*** 计算字符串中所有字符'x'与其位置对应的坐标点之间的曼哈顿距离之和。** @param s 输入的字符串* @return 字符串中所有字符'x'与其位置对应的坐标点之间的曼哈顿距离之和*/static int function(String s){int result = 0;for(int i = 0; i < s.length(); i++) {if(s.charAt(i) != 'x'){continue;}int x1 = i/3, y1 = i%3;int x2 = (s.charAt(i)-'1')/3, y2=(s.charAt(i)-'1')%3;result += Math.abs(x1-x2) + Math.abs(y1-y2);}return result;}static String bfs(){// 小根堆PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2)->o1.count-o2.count);heap.add(new Node(start, "", function(start)));visited.put(start, 0);// 定义方向数组和操作数组int [] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};String[] operations = {"up", "right", "down", "left"};// BFS 主循环while(!heap.isEmpty()) {Node node = heap.poll();// 如果找到目标状态，返回操作顺序if (node.state.equals(end)) { // 结束，返回操作顺序return node.path;}// 获取 'x' 的位置int index = node.state.indexOf('x'); // x的位置int Xstart = index / 3, Ystart = index % 3; // 计算出x的坐标// 遍历四个方向for (int i = 0; i < 4; i++) {char[] oldState = node.state.toCharArray();int Xend = Xstart + dx[i], Yend = Ystart + dy[i];String operate = operations[i];// 检查移动是否越界if (Xend < 0 || Xend >= 3 || Yend < 0 || Yend >= 3)continue;// 交换 'x' 和目标位置swap(oldState, index, Xend * 3 + Yend);// 转换字符数组为字符串String newState = String.valueOf(oldState);// 如果新状态未被访问过if (!visited.containsKey(newState)) {visited.put(newState, visited.get(node.state) + 1);// 将新状态加入堆中，并更新路径和计数heap.add(new Node(newState, node.path + operate + ' ', visited.get(node.state) + 1 + function(newState)));}}}// 如果无法到达终点，返回nullreturn null;}public static void main(String[] args) {//判断有无解，当数字序列的逆序对个数为偶数：有解，为奇数：无解String sequence = "";for(int i= 0; i < start.length(); i++) {if(start.charAt(i) != 'x') //等价于start[i]sequence += start.charAt(i);}int count = 0;for(int i=0; i < sequence.length(); i++) {for (int j = 0; j < sequence.length(); j++) {if((int) sequence.charAt(i) > (int) sequence.charAt(j))count++;}}if(count % 2 == 0){System.out.println("解存在");System.out.println(bfs());}else{System.out.println("解不存在");}//System.out.println(bfs());}
}

编程实现一字棋游戏人机对弈，在九宫格棋盘上人机轮流在棋盘上摆各自的棋子，每次一枚，谁先取得三子一线结果的一方获胜。（请用极小极大值搜索算法或α-β剪枝算法实现）

1. 需求分析

用极小极大值搜索算法实现一字棋游戏人机对弈

2. 数据结构、功能模块设计与说明

数据结构：Vector动态数组，数组

3. 评估函数 evaluate() 的算法设计思路

判断胜负：
- 首先调用 isWin() 函数来判断当前玩家是否获胜。
- 如果当前玩家获胜 (isWin() 返回 1)，则返回一个较高的分数（例如 -10 + countEmptyCells()），其中 countEmptyCells() 返回棋盘上剩余空格的数量。这里使用 -10 加上剩余空格数是为了在获胜时给予一定的奖励，同时考虑棋盘剩余空格对局势的影响（剩余空格越多，局势越开放，对获胜者来说可能意味着更多的优势，尽管获胜本身已经确定了主要得分）。
- 如果对手获胜 (isWin() 返回 -1)，则返回一个较低的分数（例如 10 - countEmptyCells()），同理，这里使用 10 减去剩余空格数是为了在对手获胜时给予一定的惩罚。
平局情况：如果当前既不是当前玩家获胜也不是对手获胜（isWin() 返回 0），则返回 0，表示当前棋盘状态是平局。

4. 极大极小值搜索算法 minimaxSearch(int depth, boolean isMaximizingPlayer) 的算法设计思路：

判断胜负和终止条件：
- 首先调用 isWin() 函数来判断当前玩家是否获胜。如果已经有玩家获胜，则直接调用 evaluate() 返回评估值，因为此时不需要继续搜索。
- 如果当前没有位置可以下棋（positions 列表为空），则返回 0，表示平局。
初始化极值：根据当前玩家是最大化玩家 (isMaximizingPlayer 为 true) 还是最小化玩家 (false)，分别初始化 value 为 Integer.MIN_VALUE 或 Integer.MAX_VALUE。这是为了在后续搜索中，最大化玩家寻找最大值，最小化玩家寻找最小值。
生成所有可能的下棋位置：遍历棋盘，找到所有空格位置，记录在一个 positions 列表中。
递归搜索：
- 对每一个可能的下棋位置，假设当前玩家在当前位置下棋（更新棋盘状态）。
- 递归调用 minimaxSearch() 函数，传入深度加 1 和当前玩家的对手作为参数（!isMaximizingPlayer）。
- 递归返回后，撤销当前位置的棋子（恢复棋盘状态）。
更新极值：根据当前玩家是最大化玩家还是最小化玩家，分别更新 value 为当前搜索到的最大值或最小值。
返回极值：返回最终找到的极值，即当前玩家在当前深度下的最佳得分。

5. 核心代码（不要将全部代码贴在报告上）与测试结果说明

7、// 评估函数
static int evaluate() {int flag = isWin();if (flag != 0) {return flag == 1 ? -10 + countEmptyCells() : 10 - countEmptyCells();}return 0; // 平局？
}
8、// 极大极小值搜索算法
static int minimaxSearch(int depth, boolean isMaximizingPlayer) {int value;if (isWin() != 0) {return evaluate(); // 如果已经赢了，直接返回结果}if (isMaximizingPlayer) {value = Integer.MIN_VALUE;} else {value = Integer.MAX_VALUE;}Vector<Integer> positions = new Vector<>(); // 记录还有哪些位置可以下棋for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {if (board[i][j] == '_') {positions.add(i * 3 + j); // 记录位置}}}if (positions.isEmpty()) {return 0; // 如果已经没有位置可以下棋，直接返回平局}for (int pos : positions) {int x = pos / 3;int y = pos % 3;board[x][y] = isMaximizingPlayer ? 'O' : 'X'; // 下棋int score = minimaxSearch(depth + 1, !isMaximizingPlayer); // 递归搜索board[x][y] = '_'; // 取消下棋if (isMaximizingPlayer) {value = Math.max(value, score); // 取最大值} else {value = Math.min(value, score); // 取最小值}}return value; // 返回极值
}

测试结果

完整代码：

import java.util.*;public class TicTacToeGame {static char[][] board = new char[3][3];static int player;// 判断胜负，返回1是玩家赢，-1是电脑赢，0是平局static int isWin() {// 判断行for (int i = 0; i < 3; i++) {if (board[i][0] != '_' && board[i][0] == board[i][1] && board[i][1] == board[i][2]) {return board[i][0] == 'X' ? 1 : -1;}}// 判断列for (int i = 0; i < 3; i++) {if (board[0][i] != '_' && board[0][i] == board[1][i] && board[1][i] == board[2][i]) {return board[0][i] == 'X' ? 1 : -1;}}// 判断对角线if ((board[0][0] != '_' && board[0][0] == board[1][1] && board[1][1] == board[2][2]) ||(board[0][2] != '_' && board[0][2] == board[1][1] && board[1][1] == board[2][0])) {return board[1][1] == 'X' ? 1 : -1;}// 判断是否平局for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {if (board[i][j] == '_') {return 0; // 还有空位，游戏继续}}}return 0; // 平局}// 评估函数static int evaluate() {int flag = isWin();if (flag != 0) {return flag == 1 ? -10 + countEmptyCells() : 10 - countEmptyCells();}return 0; // 平局？}// 计算空格数static int countEmptyCells() {int result = 0;for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {if (board[i][j] == '_') {result++;}}}return result;}// 极大极小值搜索算法static int minimaxSearch(int depth, boolean isMaximizingPlayer) {int value;if (isWin() != 0) {return evaluate(); // 如果已经赢了，直接返回结果}if (isMaximizingPlayer) {value = Integer.MIN_VALUE;} else {value = Integer.MAX_VALUE;}Vector<Integer> positions = new Vector<>(); // 记录还有哪些位置可以下棋for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {if (board[i][j] == '_') {positions.add(i * 3 + j); // 记录位置}}}if (positions.isEmpty()) {return 0; // 如果已经没有位置可以下棋，直接返回平局}for (int pos : positions) {int x = pos / 3;int y = pos % 3;board[x][y] = isMaximizingPlayer ? 'O' : 'X'; // 下棋int score = minimaxSearch(depth + 1, !isMaximizingPlayer); // 递归搜索board[x][y] = '_'; // 取消下棋if (isMaximizingPlayer) {value = Math.max(value, score); // 取最大值} else {value = Math.min(value, score); // 取最小值}}return value; // 返回极值}// 打印棋盘static void printBoard() {for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {System.out.print(board[i][j] + " ");}System.out.print("\n");}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (true) {for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {board[i][j] = '_'; // 初始化棋盘}}do {System.out.println("请选择先手，玩家（0），电脑（1）");System.out.println("请输入：");player = scanner.nextInt();} while (player != 0 && player != 1);int i;for (i = 1; i <= 9; i++) {if (player == 1) { // 电脑先手，电脑下int bestScore = Integer.MIN_VALUE;int bestMove = -1;for (int pos = 0; pos < 9; pos++) {int x = pos / 3;int y = pos % 3;if (board[x][y] == '_') {board[x][y] = 'O'; // 下棋int score = minimaxSearch(0, false); // 极大极小值搜索board[x][y] = '_'; // 取消下棋if (score > bestScore) {bestScore = score; // 更新最佳分数bestMove = pos; // 更新最佳位置}}}board[bestMove / 3][bestMove % 3] = 'O'; // 下棋到最佳位置player = 0; // 玩家下棋} else { // 玩家下棋printBoard(); // 打印棋盘System.out.println("请输入下棋位置，从左上角编号0-8：");int x;do {x = scanner.nextInt(); // 获取用户输入的位置if (x < 0 || x > 8 || board[x / 3][x % 3] != '_') {System.out.println("这个位置不能下，请重新输入:"); // 输入验证失败提示} else {break; // 输入有效，退出循环}} while (true); // 确保输入有效位置board[x / 3][x % 3] = 'X'; // 下棋到指定位置player = 1; // 电脑下棋}int winner = isWin(); // 判断是否有人获胜if (winner != 0) { // 有人获胜，结束游戏printBoard(); // 打印最终棋盘状态if (winner == 1) {System.out.println("恭喜您获胜！\n"); // 玩家获胜提示} else if (winner == -1) {System.out.println("电脑获胜！\n"); // 电脑获胜提示}break; // 退出当前游戏循环，准备下一次游戏或退出程序}}if (i >= 9) { // 如果棋盘已满，平局结束游戏printBoard(); // 打印最终棋盘状态System.out.println("平局！\n"); // 平局提示}System.out.println("再玩一次？(y/n)"); // 询问是否再玩一次char option = scanner.next().charAt(0); // 获取用户输入的选择字符if (option != 'y') { // 如果用户选择不再玩，退出程序循环，结束程序break; // 退出程序循环，结束程序}}}
}

实验存在的问题与体会：

两个实验题都遇到了不少的问题：

第一题的困难点在于怎么将A*算法融合在bfs算法里面。最后却被验证有无解的逆序对给难住了，算法没问题，找了半天错误，后来关了重新打开就没事了。

体会：用时更少，可以避免多余的搜索

第二题的体会就很搞笑了，下棋要么是平局，要么是电脑赢。算法的问题导致了电脑有时候不太“聪明”，明明还有一步就赢了，偏要多走一步

参考资料：【人工智能】搜索技术（八数码 + 一字棋游戏）_人工智能一字棋-CSDN博客