作业题目：
- 你对人工智能定义的理解？
人工智能是智能科学中涉及研究、设计与应用智能机器和智能系统的一个分支，而智能科学是一门与计算机科学并行的学科。
人工智能是智能机器所执行的通常与人类智能有关的智能行为，这些智能行为涉及学习、感知、思考、理解、识别、判断、推理、证明、通信、设计、规划、行动和问题求解等活动。
- 解释什么是图灵测试？
图灵测试（The Turing test）由艾伦·麦席森·图灵发明，指测试者与被测试者（一个人和一台机器）隔开的情况下，通过一些装置（如键盘）向被测试者随意提问。进行多次测试后，如果机器让平均每个参与者做出超过30%的误判，那么这台机器就通过了测试，并被认为具有人类智能。图灵测试一词来源于计算机科学和密码学的先驱艾伦·麦席森·图灵写于1950年的一篇论文《计算机器与智能》，其中30%是图灵对2000年时的机器思考能力的一个预测，目前我们已远远落后于这个预测。
- 你希望人工智能帮你做些什么？
回答问题：回答关于各种领域的问题，对人所不知道的提供信息和解释概念。
写作和编辑：撰写文章、报告、邮件和其他文本。
编程和技术支持：解决编程问题、编写代码或提供技术支持。
语言翻译
根据用户的需求提供帮助和支持，使我们的生活更加便捷和高效。
4、8数码问题，如上图所示的过程，要求：空格按照左、上、右、下的顺序依次扩展。
分别用BFS、DFS（深度为5）、UCS、Greedy （启发函数h自拟） 、A*（启发函数h自拟）算法进行求解。
BFS：通过广度优先搜索从初始状态逐步向目标状态前进，记录每一步的移动操作，直到找到解决方案。
创建一个双端队列（deque），用于进行广度优先搜索。
队列中的元素是一个三元组 (当前状态, 移动序列, 步数)，其中：
当前状态 表示当前的数码状态。
移动序列 用于记录达到当前状态的移动序列。
步数 表示从初始状态到当前状态的步数。
from collections import deque
# 定义初始状态和目标状态
initial_state = [[2, 8, 3], [1, 0, 4], [7, 6, 5]]
goal_state = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
# 定义移动方向：左、上、右、下
directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
direction_names = ['Left', 'Up', 'Right', 'Down']
# 创建一个队列，用于BFS
queue = deque([(initial_state, "", 0)]) # (当前状态，移动序列，步数)
# BFS算法
while queue:
current_state, move_sequence, steps = queue.popleft()
# 检查是否达到目标状态
if current_state == goal_state:
print("找到解决方案！")
print("移动序列：", move_sequence)
print("步数：", steps)
break
# 扩展当前状态
empty_row, empty_col = None, None
for row in range(3):
for col in range(3):
if current_state[row][col] == 0:
empty_row, empty_col = row, col
for i in range(4):
new_row, new_col = empty_row + directions[i][0], empty_col + directions[i][1]
if 0 <= new_row < 3 and 0 <= new_col < 3:
# 创建新状态
new_state = [list(row) for row in current_state]
new_state[empty_row][empty_col], new_state[new_row][new_col] = new_state[new_row][new_col], \
new_state[empty_row][empty_col]
new_move_sequence = move_sequence + direction_names[i]
# 将新状态加入队列
queue.append((new_state, new_move_sequence, steps + 1)) 
DFS：通过深度优先搜索从初始状态开始，沿着一个分支一直深入到底，直到找到解决方案或达到深度限制。然后，它会回溯到前一个状态，继续搜索其他分支，直到找到解决方案为止。
创建一个堆栈（deque），用于进行深度优先搜索。
堆栈中的元素是一个三元组 (当前状态, 移动序列, 步数)，其中：
当前状态 表示当前的数码状态。
移动序列 用于记录达到当前状态的移动序列。
步数 表示从初始状态到当前状态的步数。
from collections import deque
# 定义初始状态和目标状态
initial_state = [[2, 8, 3], [1, 0, 4], [7, 6, 5]]
goal_state = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
# 定义移动方向：左、上、右、下
directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
direction_names = ['Left', 'Up', 'Right', 'Down']
# 创建一个堆栈，用于DFS
stack = deque([(initial_state, "", 0)]) # (当前状态，移动序列，步数)
# DFS算法
while stack:
current_state, move_sequence, steps = stack.pop()
# 检查是否达到目标状态
if current_state == goal_state:
print("找到解决方案！")
print("移动序列：", move_sequence)
print("步数：", steps)
break
# 扩展当前状态
empty_row, empty_col = None, None
for row in range(3):
for col in range(3):
if current_state[row][col] == 0:
empty_row, empty_col = row, col
if steps < 5: # 深度限制为5
for i in range(4):
new_row, new_col = empty_row + directions[i][0], empty_col + directions[i][1]
if 0 <= new_row < 3 and 0 <= new_col < 3:
# 创建新状态
new_state = [list(row) for row in current_state]
new_state[empty_row][empty_col], new_state[new_row][new_col] = new_state[new_row][new_col], \
new_state[empty_row][empty_col]
new_move_sequence = move_sequence + direction_names[i]
# 将新状态加入堆栈
stack.append((new_state, new_move_sequence, steps + 1)) 
UCS：通过 UCS 算法以最小代价的方式从初始状态开始，逐步扩展状态直到找到目标状态为止。
创建一个优先队列（priority_queue），用于进行UCS搜索。
优先队列中的元素是元组 (total_cost, current_state, move_sequence, steps)，按照 total_cost 的大小进行优先级排序。
使用 UCS 算法进行搜索：
不断从优先队列中弹出具有最小 total_cost 的节点。
import heapq
# 定义初始状态和目标状态
initial_state = [[2, 8, 3], [1, 0, 4], [7, 6, 5]]
goal_state = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
# 定义移动方向：左、上、右、下
directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
direction_names = ['Left', 'Up', 'Right', 'Down']
# 定义初始节点
initial_node = (0, initial_state, "", 0) # (总代价，当前状态，移动序列，步数)
# 创建一个优先队列，用于UCS
priority_queue = [initial_node]
# UCS算法
while priority_queue:
total_cost, current_state, move_sequence, steps = heapq.heappop(priority_queue)
# 检查是否达到目标状态
if current_state == goal_state:
print("找到解决方案！")
print("移动序列：", move_sequence)
print("步数：", steps)
break
# 扩展当前状态
empty_row, empty_col = None, None
for row in range(3):
for col in range(3):
if current_state[row][col] == 0:
empty_row, empty_col = row, col
for i in range(4):
new_row, new_col = empty_row + directions[i][0], empty_col + directions[i][1]
if 0 <= new_row < 3 and 0 <= new_col < 3:
# 创建新状态
new_state = [list(row) for row in current_state]
new_state[empty_row][empty_col], new_state[new_row][new_col] = new_state[new_row][new_col], \
new_state[empty_row][empty_col]
new_move_sequence = move_sequence + direction_names[i]
new_cost = steps + 1
# 计算总代价
new_total_cost = new_cost
# 将新状态加入优先队列
heapq.heappush(priority_queue, (new_total_cost, new_state, new_move_sequence, new_cost)) 
Greedy：Greedy算法是一种启发式搜索算法，它在每一步都选择具有最小启发函数值的状态，因此它可能会陷入局部最优解，但通常运行速度很快。我使用不匹配数量作为启发函数，以贪婪的方式尝试接近目标状态。
定义启发函数（heuristic function）：
heuristic(state) 计算每个状态与目标状态的不匹配的数量，用于评估状态的优劣。这里的启发函数采用了"不匹配数量"，即当前状态中与目标状态不相同的方格的数量，作为估计的代价。
创建一个优先队列（priority_queue），用于进行Greedy算法搜索。使用Greedy算法进行搜索：
不断从优先队列中弹出具有最小 heuristic_value 的节点。
from collections import deque
# 定义初始状态和目标状态
initial_state = [[2, 8, 3], [1, 0, 4], [7, 6, 5]]
goal_state = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
# 定义移动方向：左、上、右、下
directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
direction_names = ['Left', 'Up', 'Right', 'Down']
# 定义启发函数：计算每个状态与目标状态的不匹配的数量
def heuristic(state):
mismatch_count = 0
for row in range(3):
for col in range(3):
if state[row][col] != goal_state[row][col]:
mismatch_count += 1
return mismatch_count
# 创建一个优先队列，用于Greedy 算法
priority_queue = deque([(initial_state, "", 0, 0)]) # (当前状态，移动序列，启发函数值，步数)
# Greedy 算法
while priority_queue:
current_state, move_sequence, heuristic_value, steps = priority_queue.popleft()
# 检查是否达到目标状态
if current_state == goal_state:
print("找到解决方案！")
print("移动序列：", move_sequence)
print("步数：", steps)
break
# 扩展当前状态
empty_row, empty_col = None, None
for row in range(3):
for col in range(3):
if current_state[row][col] == 0:
empty_row, empty_col = row, col
for i in range(4):
new_row, new_col = empty_row + directions[i][0], empty_col + directions[i][1]
if 0 <= new_row < 3 and 0 <= new_col < 3:
# 创建新状态
new_state = [list(row) for row in current_state]
new_state[empty_row][empty_col], new_state[new_row][new_col] = new_state[new_row][new_col], \
new_state[empty_row][empty_col]
new_move_sequence = move_sequence + direction_names[i]
new_heuristic_value = heuristic(new_state)
new_steps = steps + 1
# 将新状态加入优先队列，按照启发函数值排序
priority_queue.append((new_state, new_move_sequence, new_heuristic_value, new_steps))
priority_queue = deque(sorted(priority_queue, key=lambda x: x[2])) 
A*算法：A*算法是一种启发式搜索算法，它综合考虑了每个状态的启发函数值和已经花费的代价（步数），以找到最优的路径。我利用不匹配数量作为启发函数，并按照总代价（启发函数值 + 步数）的大小进行搜索，以确保在估计代价和实际代价之间取得平衡，找到最优的解决方案。
使用A*算法进行搜索：
不断从优先队列中弹出具有最小 total_cost 的节点。
检查当前状态是否达到目标状态，如果是，输出解决方案并结束搜索。
如果当前状态不是目标状态，则扩展当前状态，生成新的可能状态，并将它们加入优先队列中继续搜索。
扩展状态的过程：
找到当前状态中的空格的位置 (empty_row, empty_col)。
针对空格的四个移动方向，尝试生成新的状态，即将空格与相邻方格进行交换，生成一个新的数码状态。
计算新的 heuristic_value，这里使用启发函数计算。
计算新的 steps，即步数。
计算新的 total_cost，即启发函数值与步数之和。
将新状态加入优先队列，并按照 total_cost 的大小重新排序队列，以确保按照总代价的A*策略进行搜索。
from collections import deque
# 定义初始状态和目标状态
initial_state = [[2, 8, 3], [1, 0, 4], [7, 6, 5]]
goal_state = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
# 定义移动方向：左、上、右、下
directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
direction_names = ['Left', 'Up', 'Right', 'Down']
# 创建一个优先队列，用于A*算法
priority_queue = deque([(initial_state, "", 0, 0)]) # (当前状态，移动序列，启发函数值，步数)
# 定义启发函数：计算每个状态与目标状态的不匹配的数量
def heuristic(state):
mismatch_count = 0
for row in range(3):
for col in range(3):
if state[row][col] != goal_state[row][col]:
mismatch_count += 1
return mismatch_count
# A*算法
while priority_queue:
current_state, move_sequence, heuristic_value, steps = priority_queue.popleft()
# 检查是否达到目标状态
if current_state == goal_state:
print("找到解决方案！")
print("移动序列：", move_sequence)
print("步数：", steps)
break
# 扩展当前状态
empty_row, empty_col = None, None
for row in range(3):
for col in range(3):
if current_state[row][col] == 0:
empty_row, empty_col = row, col
for i in range(4):
new_row, new_col = empty_row + directions[i][0], empty_col + directions[i][1]
if 0 <= new_row < 3 and 0 <= new_col < 3:
# 创建新状态
new_state = [list(row) for row in current_state]
new_state[empty_row][empty_col], new_state[new_row][new_col] = new_state[new_row][new_col], \
new_state[empty_row][empty_col]
new_move_sequence = move_sequence + direction_names[i]
new_heuristic_value = heuristic(new_state)
new_steps = steps + 1
# 计算总代价（启发函数值 + 步数）
new_total_cost = new_heuristic_value + new_steps
# 将新状态加入优先队列，按照总代价排序
priority_queue.append((new_state, new_move_sequence, new_heuristic_value, new_steps))
priority_queue = deque(sorted(priority_queue, key=lambda x: x[2] + x[3])) 
- 请分别用极小化极大算法和α-β剪枝算法计算博弈树
极小化极大算法： minimax 函数是算法的核心，它采用了递归的方式来搜索博弈树，同时应用了极小化极大策略。这个函数的参数包括当前轮到哪个玩家（player）和当前博弈树节点（node）。
如果轮到玩家1（player == 1），则选择子节点中的最大值作为当前节点的值；如果轮到玩家0，则选择子节点中的最小值作为当前节点的值。这是博弈树中玩家1追求最大化结果，而玩家0追求最小化结果的基本原则。
递归结束后，将当前节点的值设置为计算出的最大值或最小值，并返回该值。
# 极小化极大算法
def minimax(player, node):
if not node["value"]:
values = []
for child in node["children"]:
values.append(minimax(player ^ 1, child))
if player == 1:
node["value"] = max(values)
else:
node["value"] = min(values)
return node["value"]
# 构建完全二叉树
tree1 = {
"value": None,
"children": [
{
"value": None,
"children": [
{
"value": None,
"children": [
{
"value": 10,
"children": [],
},
{
"value": 6,
"children": [],
},
],
},
{
"value": None,
"children": [
{
"value": 100,
"children": [],
},
{
"value": 8,
"children": [],
},
],
},
],
},
{
"value": None,
"children": [
{
"value": None,
"children": [
{
"value": 1,
"children": [],
},
{
"value": 2,
"children": [],
},
],
},
{
"value": None,
"children": [
{
"value": 20,
"children": [],
},
{
"value": 4,
"children": [],
},
],
},
],
},
],
}
def main(tree):
res = minimax(1, tree)
print("最佳值:", res)
print(tree)
main(tree1) 
α-β剪枝算法：在极小化极大算法中应用α-β剪枝，以加速博弈树的搜索过程。这种技术可以显著减少搜索的分支数，提高算法的效率，特别是在博弈树很大的情况下。
根据α-β剪枝的原则来更新 alpha 和 beta。如果在搜索过程中发现某个子节点的值已经超出了当前玩家的上界 beta（对于玩家0）或下界 alpha（对于玩家1），则可以剪枝，停止继续搜索该分支，因为已经找到更好的选择。
# 极小化极大算法 + α-β剪枝 def alpha_beta(player, node, alpha, beta): if not node["value"]: values = [] for child in node["children"]: val = alpha_beta(player ^ 1, child, alpha, beta) values.append(val) if player == 1: # max层 子元素的值大于当前下界的值 更新下界 alpha = max(alpha, val) # max层 下界大于等于上界直接返回下界（返回较大者） if alpha >= beta: return alpha else: # min层 子元素的值小于当前上界的值 更新上界 beta = min(beta, val) # min层 下界大于等于上界直接返回上界（返回较小者） if alpha >= beta: return beta # 返回当前层节点的极值，便于父元素进行剪枝（并不是返回alpha或者beta） if player == 1: node["value"] = max(values) else: node["value"] = min(values) return node["value"]
（二叉树构建部分与上面相同）
- 课程设计作业：井字棋
在3*3格子上进行的连珠游戏，和五子棋比较类似，由于棋盘一般不画边框，格线排成井字故得名。游戏由分别代表O和X的两个游戏者轮流在格子里留下标记（一般来说先手者为X）。由最先在任意一条直线上成功连接三个标记的一方获胜。
使用深度优先搜索、结合极小化极大搜索、结合α-β剪枝算法分别设计出井字棋游戏。
编程语言不限。
输入用鼠标或键盘操作：（三选一）
①可以用鼠标选择人类的着棋位置
②也可以用上下左右键选择位置按Enter键着子
③也可以通过输入坐标(0,1)来输入着棋位置
输出：
①可以通过图形界面实时输出
②也可以通过在控制台打印3*3数组的形式输出没步任何电脑着棋后的状态例如：print(“XOO\nOXX\nOOX\n”)
设计思路：
输入操作：通过输入坐标(0,1)来输入着棋位置
输出：在控制台打印3*3数组的形式输出每步电脑着棋后的状态
check_win(board, player) 函数：检查是否有获胜者。它会检查每一行、每一列以及两个对角线上是否有连续的三个相同符号（"X"或"O"），如果有，就返回True。
check_tie(board) 函数：检查游戏是否平局。如果棋盘上没有空格（" "），则返回True。
get_player_move(board) 函数：获取玩家的落子位置。通过输入行数和列数，然后检查该位置是否为空，如果为空，则返回选择的位置。
minimax(board, depth, alpha, beta, maximizing) 函数：在深度优先搜索的基础上实现极小化极大算法（Minimax）结合α-β剪枝。这是一个递归函数，用于模拟玩家和电脑的决策过程，以确定最佳落子位置。如果当前局面有玩家获胜（"X"胜利）返回-10，如果电脑获胜（"O"胜利）返回10，如果平局返回0。
如果当前是最大化玩家（电脑）的回合（maximizing为True），则尝试所有可能的落子位置，对每个位置递归调用minimax来计算分数。同时，使用α-β剪枝来减少搜索空间，如果发现某个分支已经比β大，就可以剪枝不再搜索，因为这个分支对最终结果不会有影响。最终返回最高分数。
如果当前是最小化玩家（玩家）的回合（maximizing为False），同样尝试所有可能的落子位置，对每个位置递归调用minimax来计算分数。同时，使用α-β剪枝来减少搜索空间，如果发现某个分支已经比α小，就可以剪枝不再搜索，因为这个分支对最终结果不会有影响。最终返回最低分数。
play_game() 函数：这是游戏的主函数，包括玩家选择先后手、游戏主循环。在游戏主循环中，根据玩家选择的先后手，交替进行玩家和电脑的回合。玩家的回合通过输入来获取落子位置，电脑的回合通过minimax函数来计算最佳落子位置。
游戏开始后，玩家可以选择先手（"X"）或者电脑先手（"O"），然后游戏会交替进行，直到有一方获胜或者游戏平局。
设计的关键在于minimax函数，它通过递归搜索棋盘状态树来找到最佳落子位置，同时通过α-β剪枝来减少搜索时间，从而提高了计算效率。我把minimax算法的搜索深度（depth）设置为9，表示电脑将考虑9步后的棋盘状态来做出决策。增加搜索深度会使电脑更聪明，但也会增加计算时间。根据我的测试，9步时的电脑我已经无法战胜，且运行时间较快，可以很好的满足要求。
源码：
import math
def print_board(board):
# 打印游戏棋盘
for row in board:
print(" | ".join(row))
print()
def check_win(board, player):
# 检查是否有获胜者
for i in range(3):
if all(board[i][j] == player for j in range(3)):
return True
if all(board[j][i] == player for j in range(3)):
return True
if all(board[i][i] == player for i in range(3)):
return True
if all(board[i][2 - i] == player for i in range(3)):
return True
return False
def check_tie(board):
# 检查是否平局
for row in board:
for cell in row:
if cell == " ":
return False
return True
def get_player_move(board):
# 获取玩家落子位置
while True:
try:
row = int(input("输入行数 (1-3): ")) - 1
col = int(input("输入列数 (1-3): ")) - 1
if board[row][col] == " ":
return row, col
else:
print("这个位置已经被占,请重新输入.")
except ValueError:
print("请输入1-3之间的数.")
def minimax(board, depth, alpha, beta, maximizing):
# 极大极小/α-β剪枝算法
if check_win(board, "X"):
return -10, None
if check_win(board, "O"):
return 10, None
if check_tie(board):
return 0, None
if maximizing:
best_score = -math.inf
best_move = None
for row in range(3):
for col in range(3):
if board[row][col] == " ":
board[row][col] = "O"
score, _ = minimax(board, depth - 1, alpha, beta, False)
board[row][col] = " "
if score > best_score:
best_score = score
best_move = (row, col)
alpha = max(alpha, best_score)
if beta <= alpha:
break
return best_score, best_move
else:
best_score = math.inf
best_move = None
for row in range(3):
for col in range(3):
if board[row][col] == " ":
board[row][col] = "X"
score, _ = minimax(board, depth - 1, alpha, beta, True)
board[row][col] = " "
if score < best_score:
best_score = score
best_move = (row, col)
beta = min(beta, best_score)
if beta <= alpha:
break
return best_score, best_move
def play_game():
board = [[" " for j in range(3)] for i in range(3)]
print_board(board)
# 玩家选择先后手
while True:
user_choice = input("选择X或者O（X先手）: ")
if user_choice.lower() == "x":
player = "X"
break
elif user_choice.lower() == "o":
player = "O"
break
else:
print("请输入X或O.")
# 游戏主循环
while True:
if player == "X":
# 玩家先手
while not check_win(board, "X") and not check_tie(board):
row, col = get_player_move(board)
board[row][col] = "X"
print_board(board)
if check_win(board, "X"):
print("玩家获胜!")
return
if check_tie(board):
print("平局!")
return
_, (row, col) = minimax(board, 9, -math.inf, math.inf, True)
print("电脑思考后落子", (row + 1, col + 1))
board[row][col] = "O"
print_board(board)
if check_win(board, "O"):
print("玩家失败!")
return
if check_tie(board):
print("平局!")
return
else:
# 电脑先手
while not check_win(board, "O") and not check_tie(board):
_, (row, col) = minimax(board, 9, -math.inf, math.inf, True)
print("电脑思考后落子", (row + 1, col + 1))
board[row][col] = "X"
print_board(board)
if check_win(board, "X"):
print("玩家失败!")
return
if check_tie(board):
print("平局!")
return
row, col = get_player_move(board)
board[row][col] = "O"
print_board(board)
if check_win(board, "O"):
print("玩家获胜!")
return
if check_tie(board):
print("平局!")
return
if __name__ == '__main__':
play_game() 
|
|
|
|
