博弈树负值极大alpha-beta剪枝算法代码实现
## 初始化输入、确定输出
首先明确算法的输入、输出，这其实是一个试错的过程，可能要到整体项目做的差不多才能确定，我是已经做完了，所以就直接贴出来了。
def ai(player, ratio, length, board, depth): """ AI入口 :param player: 当前玩家. 初始化ai与human的棋子列表. :param ratio: 进攻系数. :param length: 棋盘边长. :param board: 棋盘值. 1表示白子,-1表示黑子,0表示空. :param depth: 搜索深度. :return: 落子位置x, 落子位置y, 搜索次数. """ # 设置全局变量 global list_ai, list_human, list_ai_add_human, list_all, x, y, search_count, DEP, LEN, RAT # 初始化 DEP, LEN, RAT = depth, length, ratio list_ai, list_human, list_ai_add_human, list_all = init_list(player, board) # 设置alpha和beta的初始值 alpha = -99999999 beta = 99999999 # 回溯搜索 backtrack(True, depth, alpha, beta) list_ai.append((x, y)) return x, y, search_count, is_win(list_ai)
该函数被命名为ai，也就是电脑的意思，接受以下参数：
player: 当前玩家，用于初始化 AI 和人类玩家的棋子列表。
因为传入的只有棋盘值，棋盘值有1和-1，那电脑到底应该把1作为自己的棋子，还是-1呢？这就需要用到参数player，如果player == 'black'，表示电脑是黑子，那么电脑会把-1作为自己的棋子，1作为敌方棋子。
ratio: 进攻系数，可能是用于调整 AI 对进攻和防守的权衡。
进攻系数就是上面说的权重。
length: 棋盘的边长。
board: 表示棋盘状态的二维数组，其中1表示白子，-1表示黑子，0表示空。
depth: 搜索的深度，决定了 AI 进行决策时回溯的层数。
搜索的深度就是所谓的“能看几步”，我电脑目前看3步就要算个40来秒，着实不太行了。
该函数返回落子的位置(x, y)、搜索次数和是否获胜。
在函数内部，使用global关键字声明一些全局变量，包括list_ai、list_human、list_ai_add_human、list_all、x、y、search_count、DEP、LEN和RAT。分别表示ai的棋子、敌方的棋子、ai的棋子+敌方的棋子，所有的位置坐标、计算出来的x坐标、计算出来的y坐标、算法搜索次数（主要是debug用）、搜索深度、棋盘长度、进攻系数。
这里做成全局变量是因为就不要传参了，不然每个函数的形参都要写一大堆，挺麻烦的。
接下来，将传入的参数初始化到对应的全局变量中。将 depth 赋值给 DEP，length 赋值给 LEN，ratio 赋值给 RAT。然后调用 init_list 函数，使用 player 和 board 参数来初始化 list_ai、list_human、list_ai_add_human 和 list_all 这些列表。
设置初始的alpha和beta值，用于进行Alpha-Beta剪枝。
调用 backtrack 函数进行回溯搜索，传入参数 True 表示当前是 AI 的回合，搜索的深度为 depth，并使用 alpha 和 beta 进行 Alpha-Beta 剪枝。搜索完成后，将得到的落子位置 (x, y) 添加到 list_ai 列表中，然后返回 (x, y)、search_count（搜索次数）和调用 is_win 函数判断 list_ai 是否包含获胜的棋型。
## 开始回溯
def backtrack(is_me, depth, alpha, beta): """ 博弈树极大极小值alpha-beta剪枝搜索 :param is_me: 当前是不是轮到自己下棋. :param depth: 回溯深度. :param alpha: :param beta: :return: """ # 约束条件：已经有一方获胜 或者 搜索深度为0 if is_win(list_ai) or is_win(list_human) or depth == 0: return evaluation(is_me) # 生成当前局面下所有的候选步 blank_list = list(set(list_all).difference(set(list_ai_add_human))) # 启发式搜索， 优先剪枝 order(blank_list) # 搜索顺序排序 提高剪枝效率 # 遍历每一个候选步 for next_step in blank_list: global search_count search_count += 1 # 如果要评估的位置没有相邻的子， 则不去评估 减少计算 if not has_neightnor(next_step): continue if is_me: list_ai.append(next_step) else: list_human.append(next_step) list_ai_add_human.append(next_step) value = -backtrack(not is_me, depth - 1, -beta, -alpha) if is_me: list_ai.remove(next_step) else: list_human.remove(next_step) list_ai_add_human.remove(next_step) if value > alpha: if depth == DEP: global x, y x = next_step[0] y = next_step[1] # alpha + beta剪枝点 if value >= beta: return beta alpha = value return alpha
上面的代码是用博弈树极大极小值算法和alpha-beta剪枝搜索实现五子棋最优点搜索的函数。
函数名为backtrack，接受四个参数：
is_me：表示当前轮到的是自己还是对手下棋，是一个布尔值。
depth：回溯的深度，即搜索树的层数。
alpha：alpha剪枝的初始值，表示极大值。
beta：beta剪枝的初始值，表示极小值。
函数的作用是在博弈树中进行搜索，并返回评估值。
函数的执行流程如下：
1. 约束条件检查：如果已经有一方获胜或者搜索深度为0，则返回当前局面的评估值，表示当前局面的好坏程度。
2. 生成当前局面下所有的候选步：通过计算当前局面中空白位置和已下棋位置的差集，得到所有可下棋的位置。
3. 启发式搜索：对候选步进行排序，以提高剪枝效率。还对周围没有棋子的点位进行搜索优化，没有的话就不去遍历它。
4. 遍历每一个候选步：
对于每个候选步，将其添加到当前下棋方的位置列表中。
调用递归函数backtrack，以更新搜索树，并返回一个评估值。
通过alpha-beta剪枝进行优化：
如果当前轮到自己下棋（is_me为True），更新alpha值为评估值value和alpha的较大值。
如果轮到对手下棋（is_me为False），更新beta值为评估值value和beta的较小值。
如果评估值value大于alpha，则更新alpha为value。
如果depth等于最大搜索深度（DEP），记录当前位置x和y。
如果评估值value大于等于beta，则进行剪枝，直接返回beta。
5. 返回alpha作为当前局面的评估值。
## 判赢
判赢函数有2个用法：一个是在回溯里面作为约束条件，还有一个是在得到计算出的落子之后，判断这样下棋有没有赢。
def is_win(L): """ 判断输赢 :param L: 电脑或玩家的落子列表 :return: True or False. """ def check_five_in_a_row(start_row, start_col, row_delta, col_delta): for i in range(5): if (start_row + i * row_delta, start_col + i * col_delta) not in L: return False return True for m in range(LEN): for n in range(LEN): # 判断横向是否有五子连珠 if n < LEN - 4 and check_five_in_a_row(m, n, 0, 1): return True # 判断纵向是否有五子连珠 if m < LEN - 4 and check_five_in_a_row(m, n, 1, 0): return True # 判断右上斜向是否有五子连珠 if m < LEN - 4 and n < LEN - 4 and check_five_in_a_row(m, n, 1, 1): return True # 判断右下斜向是否有五子连珠 if m < LEN - 4 and n > 3 and check_five_in_a_row(m, n, 1, -1): return True return False
判断输赢函数is_win，接受一个落子列表L作为参数，并返回一个布尔值表示是否有一方获胜。
函数的执行流程如下：
1. 定义了一个内部函数check_five_in_a_row，用于检查指定起始位置和方向上是否存在五子连珠。
· 函数接受四个参数：起始行start_row、起始列start_col、行的增量row_delta和列的增量col_delta。
· 使用循环遍历五个位置，检查每个位置是否存在于落子列表L中，如果有任何一个位置不在列表中，则返回False。
· 如果所有位置都在列表中，则返回True，表示存在五子连珠。
2. 使用两层嵌套的循环遍历棋盘上的每个位置，对于每个位置，分别进行以下判断：
- 判断横向是否有五子连珠：如果当前位置的列小于LEN-4（棋盘边界判断）且调用check_five_in_a_row函数返回True，则表示存在横向五子连珠，返回True。
- 判断纵向是否有五子连珠：如果当前位置的行小于LEN-4且调用check_five_in_a_row函数返回True，则表示存在纵向五子连珠，返回True。
- 判断右上斜向是否有五子连珠：如果当前位置的行小于LEN-4且列小于LEN-4且调用check_five_in_a_row函数返回True，则表示存在右上斜向五子连珠，返回True。
- 判断右下斜向是否有五子连珠：如果当前位置的行小于LEN-4且列大于3且调用check_five_in_a_row函数返回True，则表示存在右下斜向五子连珠，返回True。
3. 如果在遍历完所有位置后仍未返回True，则表示不存在五子连珠，返回False。
## 评估-计算分数
计算分数分2个函数，一个是计算整体的分数evaluation，另外一个是针对某个点计算某个方向上的分数cal_score。
# 评估函数 def evaluation(is_me): if is_me: my_list = list_ai enemy_list = list_human else: my_list = list_human enemy_list = list_ai # 算自己的得分 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 * RAT * 0.1 return total_score
上述代码是一个评估函数evaluation，用于评估当前局面的得分。函数根据当前轮到的是自己还是对手，计算出相应的得分。
函数的执行流程如下：
1. 根据参数is_me判断当前轮到的是自己还是对手，将对应的落子列表赋值给my_list和enemy_list。
2. 初始化变量：
score_all_arr：用于存储得分形状的位置，用于计算如果有相交则得分翻倍。
my_score：自己的得分，初始值为0。
3. 遍历自己的落子列表my_list，对于每个位置(m, n)，分别进行以下操作：
调用cal_score函数计算在水平、垂直、右斜和左斜四个方向上的得分，并累加到my_score中。
在计算得分的过程中，使用enemy_list和my_list作为参数，以判断对手的棋子是否存在，同时将得分形状的位置存储到score_all_arr中。
4. 初始化变量：
score_all_arr_enemy：用于存储对手的得分形状的位置。
enemy_score：对手的得分，初始值为0。
5. 遍历对手的落子列表enemy_list，对于每个位置(m, n)，分别进行以下操作：
调用cal_score函数计算对手在水平、垂直、右斜和左斜四个方向上的得分，并累加到enemy_score中。
在计算得分的过程中，使用my_list和enemy_list作为参数，以判断自己的棋子是否存在，同时将得分形状的位置存储到score_all_arr_enemy中。
6. 计算总得分：
将自己的得分my_score减去对手的得分enemy_score乘以一个权重因子RAT和0.1的结果，得到总得分total_score。
7. 返回总得分total_score作为当前局面的评估值。
# 每个方向上的分值计算 def cal_score(m, n, x_decrict, y_derice, 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_decrict == item[2][0] and y_derice == item[2][1]: return 0 # 在落子点方向上循环查找得分形状 for offset in range(-5, 1): pos = [] for i in range(0, 6): if (m + (i + offset) * x_decrict, n + (i + offset) * y_derice) in enemy_list: pos.append(2) elif (m + (i + offset) * x_decrict, n + (i + offset) * y_derice) in my_list: pos.append(1) else: pos.append(0) tmp_shap5 = (pos[0], pos[1], pos[2], pos[3], pos[4]) tmp_shap6 = (pos[0], pos[1], pos[2], pos[3], pos[4], pos[5]) for (score, shape) in shape_score: # 命中一个得分形状 if tmp_shap5 == shape or tmp_shap6 == shape: if score > max_score_shape[0]: max_score_shape = (score, ((m + (0+offset) * x_decrict, n + (0+offset) * y_derice), (m + (1+offset) * x_decrict, n + (1+offset) * y_derice), (m + (2+offset) * x_decrict, n + (2+offset) * y_derice), (m + (3+offset) * x_decrict, n + (3+offset) * y_derice), (m + (4+offset) * x_decrict, n + (4+offset) * y_derice)), (x_decrict, y_derice)) # 计算两个形状相交， 如两个3活 相交， 得分增加 一个子的除外 if max_score_shape[1] is not None: for item in score_all_arr: for pt1 in item[1]: for pt2 in max_score_shape[1]: if pt1 == pt2 and max_score_shape[0] > 10 and item[0] > 10: add_score += item[0] + max_score_shape[0] score_all_arr.append(max_score_shape) return add_score + max_score_shape[0]
上述代码是计算在指定方向上的得分函数cal_score，用于评估棋局中某个位置在特定方向上的得分情况。
函数的执行流程如下：
1. 初始化变量：
- add_score：加分项，用于记录在当前方向上的额外得分。
- max_score_shape：最大得分形状，初始值为(0, None)，用于记录在当前方向上的最高得分形状及其分值。
2. 检查当前方向上是否已经有得分形状，如果有，则不进行重复计算，直接返回0。
3. 在落子点的方向上循环遍历，查找可能的得分形状。遍历范围为从偏移-5到1，共6个位置。
4. 对于每个位置，判断该位置在落子列表中的状态：
- 如果在对手的落子列表中，将状态设置为2。
- 如果在自己的落子列表中，将状态设置为1。
- 如果为空位，将状态设置为0。
5. 根据当前位置及其相邻位置的状态，形成长度为5或6的形状。
6. 遍历预定义的得分形状和对应的分值：
- 如果当前形状与预定义的形状匹配，命中得分形状。
- 如果当前得分高于max_score_shape中记录的最高得分，则更新max_score_shape为当前得分形状。
7. 判断两个形状是否相交：
- 如果max_score_shape不为None，表示存在最高得分形状。
- 遍历已记录的得分形状，检查是否与最高得分形状相交：
- 如果相交且两个形状的分值都大于10，则将相交的得分形状的分值加到add_score中。
8. 将最高得分形状记录到score_all_arr中。
9. 返回加分项add_score与最高得分形状的分值之和作为当前方向上的总得分。
通过遍历落子点的特定方向上的位置，并判断形成的形状是否与预定义的得分形状匹配，从而计算出该方向上的得分情况。同时，如果存在相交的得分形状，则额外增加得分。最终返回当前方向上的总得分。
总结
ai 调用 backtrace进行回溯。
backtrace里面有约束条件：判赢is_win、depth是否为0。
如果满足约束条件，那么计算总棋局分数evaluation，evaluation会调用cal_score，cal_score计算某个点在某个方向的分数。
如果不满足约束条件，做一下启发（剪枝），然后接着递归。
最后返回四个参数：x、y坐标，搜索次数、是否赢了。
