一、课设要求
基于A*算法的五子棋博弈系统
A)给出用 A*算法设计实现五子棋博弈的思想与方法。
B)设计实现五子棋博弈交互系统。
C)对不同的格局，以及不同的初始状态和目标状态，记录 A*算法的落棋求解结果。
分析A*算法设计实现五子棋博弈的有效性。
二、代码实现
注：该代码在码者编辑此文档时进行过微调，如有bug可评论或私信，感谢。
2.1 原代码
- 作者：罗WWEEII (luo_wweeii) - Gitee.com
- 项目链接：gobang_AI: 基于博弈树α-β剪枝搜索的五子棋AI (gitee.com)
因为本人不擅长python，再加上从零开始也很浪费时间，所以直接去gitee上面找的现有代码进行修改。(原作者如有介意请联系删除)
2.2 核心代码
2.2.1 A*算法实现
open表：用于存储待评估的点；closed表：用于记录已经评估过的点；价值：价值越高，越容易获胜；代价：价值取反；
- 首先，将所有落子的邻接点放入open表中，放入的时候会进行落子评估，获取落子在一个点后的棋局价值；
- 从open表中取出价值最高的点；
- 落子判断，判断当前点是否合法、当前点是否在closed表中、当前搜索是否达到搜索深度（DEPTH）；
- 将当前落子的所有邻接点放入open表，放入前也会进行价值计算；
- 循环第二步至第四步，直到到达循环出口（open表为空，达到递归深度）；
代码：
def a_star_search(): open_list = [] # 所有带搜索的点 closed_set = {} # 记录已经搜索过的点以及其价值评估分数 for point in list3: neighbors = get_neighbors(point) # 取出所有落子的邻接点 for neighbor in neighbors: if neighbor in list_all and neighbor not in list3 and neighbor not in closed_set.keys(): # 修改此处检查邻居是否在 closed_set 的键中 # 后续两个append()和remove()是为了评估落下评估点后的棋局状态(但实际还未落下)，所以需要先添加进两个list中，之后再删除 list1.append(neighbor) # 将邻居加入AI列表 list2.append(neighbor) # 将邻居加入人类落子列表 if neighbor not in [node for (_, node) in open_list]: # 检查节点是否已经存在于open列表中 heapq.heappush(open_list, (-evaluation(True), neighbor)) # 将当前点加入open列表 # 从列表中删除刚刚加入的邻居 list1.remove(neighbor) list2.remove(neighbor) if not open_list: return None while open_list: # 在a_star_search函数中修改取出具有最小代价的节点的行为 min_cost = min(open_list)[0] # 获取当前最小代价 min_cost_nodes = [node for cost, node in open_list if cost == min_cost] # 找到所有具有最小代价的节点列表 current_node = random.choice(min_cost_nodes) # 从具有相同最小代价的节点列表中随机选择一个节点 open_list.remove((min_cost, current_node)) # 从open_list中移除选择的节点 current_cost = min_cost if current_node not in closed_set: if current_node not in list3: closed_set[current_node] = current_cost # 记录当前点和评估分数 if len(closed_set) >= DEPTH: # 到达搜索深度 max_score_node = min(closed_set, key=closed_set.get) # 找到评估分数最大的点(代价最小,即价值最大) return max_score_node neighbors = get_neighbors(current_node) for neighbor in neighbors: if neighbor in list_all and neighbor not in list3 and neighbor not in closed_set.keys(): # 修改此处检查邻居是否在 closed_set 的键中 list1.append(neighbor) # 将邻居加入AI列表 list2.append(neighbor) # 将邻居加入列表 if neighbor not in [node for (_, node) in open_list]: # 检查节点是否不在open列表中 heapq.heappush(open_list, (-evaluation(True), neighbor)) # 将节点推入open列表 # 从列表中删除刚刚加入的邻居 list1.remove(neighbor) list2.remove(neighbor) # 如果搜索完所有可搜索的点时仍未到达搜索深度，则返回评估分数最大的点 max_score_node = min(closed_set, key=closed_set.get) return max_score_node2.2.2 评估函数
1> 评估模型
当某一行/列构成评估模型中的状态时，便相应的累加记分。
# 棋型的评估分数,例：落子为* * 1 1 0 0 0 * * 时的棋型得10分 1为计算分数的对象的棋子,0为可落子的空位置 shape_score = [(10, (1, 1, 0, 0, 0)), (10, (1, 0, 1, 0, 0)), (10, (1, 0, 0, 1, 0)), (50, (0, 1, 1, 0, 0)), (50, (0, 1, 0, 1, 0)), (100, (1, 1, 0, 1, 0)), (100, (0, 0, 1, 1, 1)), (100, (1, 1, 1, 0, 0)), (500, (0, 1, 0, 1, 1, 0)), (500, (0, 1, 1, 0, 1, 0)), (2000, (0, 1, 1, 1, 0)), (4000, (1, 1, 1, 0, 1)), (4000, (1, 1, 0, 1, 1)), (4000, (1, 0, 1, 1, 1)), (5000, (1, 1, 1, 1, 0)), (5000, (0, 1, 1, 1, 1)), (100000, (0, 1, 1, 1, 1, 0)), (99999999, (1, 1, 1, 1, 1))]
2> 评估函数
在评估函数中，首先会根据传参，相应的进行待计算棋子列表的初始化，然后计算双方每个落子的每个方向上的得分情况（使用score_all_arr来保证不会对一种得分情况进行重复计算），最后带权相加当前的棋局得分情况。
ratio：进攻的系数；小于1：进攻型、大于1：防守型
# 一个点的价值评估函数 def evaluation(is_ai): if is_ai: my_list = list1 enemy_list = list2 else: my_list = list2 enemy_list = list1 # 算自己的得分 score_all_arr = [] # 得分形状的位置,避免重复计算 my_score = 0 for pt in my_list:# 计算自己的所有点在四个方向上的得分情况 m = pt[0] n = pt[1] my_score += cal_score(m, n, 0, 1, enemy_list, my_list, score_all_arr) my_score += cal_score(m, n, 1, 0, enemy_list, my_list, score_all_arr) my_score += cal_score(m, n, 1, 1, enemy_list, my_list, score_all_arr) my_score += cal_score(m, n, -1, 1, enemy_list, my_list, score_all_arr) # 算敌人的得分 score_all_arr_enemy = [] enemy_score = 0 for pt in enemy_list: m = pt[0] n = pt[1] enemy_score += cal_score(m, n, 0, 1, my_list, enemy_list, score_all_arr_enemy) enemy_score += cal_score(m, n, 1, 0, my_list, enemy_list, score_all_arr_enemy) enemy_score += cal_score(m, n, 1, 1, my_list, enemy_list, score_all_arr_enemy) enemy_score += cal_score(m, n, -1, 1, my_list, enemy_list, score_all_arr_enemy) total_score = my_score + enemy_score * ratio return total_score3> 得分计算
该函数会根据参数，相应的查找传入点的传入方向上的前后共十一个位置，优先记录该方向上得分最高的相应得分棋型。同时这里还增加了部分特判规则，当待查找的点落入棋盘外时，会调整直接进入下一次循环，避免无效查询。
# 一个方向上的分值计算 def cal_score(m, n, x_direct, y_direct, enemy_list, my_list, score_all_arr): add_score = 0 # 加分项 # 在一个方向上， 只取最大的得分项 max_score_shape = (0, None) # 如果此方向上，该点已经有得分形状，不重复计算 for item in score_all_arr: for pt in item[1]: if m == pt[0] and n == pt[1] and x_direct == item[2][0] and y_direct == item[2][1]: return 0 # 在落子点 左右方向上循环查找得分形状 for offset in range(-5, 1): # offset = -2 pos = [] found_valid_pos = False # 布尔变量用于记录是否找到有效位置 for i in range(0, 6): next_pos = (m + (i + offset) * x_direct, n + (i + offset) * y_direct) if not (0
