每日例行赊赞
一、实验目的
（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)));
}
}
}
// 如果无法到达终点，返回null
return 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)));
}
}
}
// 如果无法到达终点，返回null
return 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算法里面。最后却被验证有无解的逆序对给难住了，算法没问题，找了半天错误，后来关了重新打开就没事了。
体会：用时更少，可以避免多余的搜索
第二题的体会就很搞笑了，下棋要么是平局，要么是电脑赢。算法的问题导致了电脑有时候不太“聪明”，明明还有一步就赢了，偏要多走一步