2024电赛E题三子棋：Python与Minimax算法实现全解析

简介2024年全国大学生电子设计竞赛E题“三子棋游戏”完整Python源码来自省赛一等奖参赛作品适合电赛选手、机器人爱好者及计算机/电子类专业学生参考。压缩包共27个文件以20个.py源码文件为主体分模块实现了三子棋不败算法backgammon.py、棋子识别算法detectChess.py、电磁铁驱动控制electromagnets.py和灯光反馈控制ledContorl.py并包含5个.pyc缓存、1个README说明文档与1个license许可证包体仅45KB目录结构清晰便于逐个文件阅读。已有699人学习下载代码经过运行验证能够帮助读者从图像识别、策略决策到执行机构控制梳理完整电赛方案也适合作为课设、毕设或嵌入式视觉项目的初版框架。1. 2024年电赛E题三子棋游戏用Python快速拿下博弈核心三子棋的规则简单到一句话能讲完但2024年电赛E题把三子棋游戏放到竞赛平台上之后真正的难点都压在“机器对手”身上棋盘显示和落子交互只是体力活AI能不能在有限硬件资源里做出像样的决策才是拉开差距的地方。Python在这套源代码里的角色是先把博弈逻辑彻底跑通胜负判断十几行能写完AI用一个递归函数实现调试时终端直接打印棋盘状态比一上来就在单片机上调C省出大把时间。下面按一线备赛最常用的做法把Python三子棋源代码拆成棋盘建模、AI决策、电赛适配三个层面末尾补上板前的自动化验证方法。备赛团队可以照这套路线改出自己的方案做博弈算法入门的开发者也能直接把Minimax实现挪到自己的项目里。2. 三子棋核心逻辑与胜负判定棋盘建模和Python实现三子棋的棋盘是固定的3x3网格整套源代码里与界面无关的部分只有三块棋盘状态、落子写入、终局判定。这一章先把这三块用最稳的方式写出来再解释为什么这样设计能在后面接AI时不返工。2.1 二维列表棋盘与落子写入棋盘的建模方式选择直接决定后续代码的可读性。3x3固定网格用嵌套列表是Python里最自然的表达外层列表是行内层列表是列每个格子存储当前棋子的标记X或O空位统一用None。不要用一维数组加公式换算坐标——虽然省两个字符但后面Minimax搜索里反复要写board[row][col]二维写法能少掉一半以上的坐标错误。BOARD_SIZE 3 EMPTY None def create_board(): 初始化3x3棋盘每个位置为None表示空位 return [[EMPTY for _ in range(BOARD_SIZE)] for _ in range(BOARD_SIZE)] def make_move(board, position, player): 在0~8的编号位置落子。 位置换算position // 3 是行索引position % 3 是列索引。 row, col position // 3, position % 3 if board[row][col] is not EMPTY: raise ValueError(f位置 {position} 已被占用) board[row][col] player这里的create_board用列表推导生成三个互相独立的子列表。如果图省事写成[[None] * 3] * 3三个内层列表会指向同一个对象改一格棋子会连动整列——这个问题几乎每个写过Python棋盘的人都会踩一次。make_move把0到8的一维编号换算成行列上层不管是拿键盘输入还是接收AI候选都只需要传一个数字不用每次同时维护两个坐标。格子被占用时抛异常把非法落子的责任推给调用方而不是默默覆盖已有棋子。2.2 胜负判断的8种赢法三行、三列、两条对角线三子棋总共只有8种赢法。最可靠的原生实现是把这8种组合直接用常量表列出来逐个检查是否属于同一个玩家。网络上确实有人用循环加偏移量生成赢法但在竞赛代码里少一层抽象总是好事评审翻代码时能立刻看明白也绝对不会因为偏移量生成逻辑错误漏掉某条对角线。赢法位置编号组合第0行0, 1, 2第1行3, 4, 5第2行6, 7, 8第0列0, 3, 6第1列1, 4, 7第2列2, 5, 8主对角线0, 4, 8副对角线2, 4, 6WIN_LINES [ [0, 1, 2], [3, 4, 5], [6, 7, 8], # 行 [0, 3, 6], [1, 4, 7], [2, 5, 8], # 列 [0, 4, 8], [2, 4, 6] # 对角线 ] def check_winner(board, player): 判断指定玩家是否已经形成一条赢法。 不修改棋盘只做状态查询可在AI搜索中被大量调用。 for line in WIN_LINES: cells [board[pos // 3][pos % 3] for pos in line] if all(cell player for cell in cells): return True return Falsecheck_winner要接收player参数而不是在函数内部判断谁赢是因为AI搜索时既需要检查AI是否取胜也需要检查人类是否已经形成胜势两种情况都要在同一次终局判定里出现。所有涉及棋盘读写的操作都会改原始列表所以这个函数不能缓存结果每次都现算好在8种赢法一共只取24个格子调用几千次也在毫秒级。2.3 平局判定与空位枚举平局条件是棋盘满且无人赢所以需要在check_winner返回False之后继续判断是否还有空格。把空位枚举和“棋盘满了”两个能力分开是因为AI的候选落子列表直接依赖前者而终局流程依赖后者二者语义不同放在同一个函数里会让调用方同时做两件事。def is_full(board): 所有格子都不是None即认为棋盘已满 for row in board: for cell in row: if cell is EMPTY: return False return True def get_available_positions(board): 返回所有空位的一维编号供AI搜索枚举候选落子 result [] for idx in range(9): row, col idx // 3, idx % 3 if board[row][col] is EMPTY: result.append(idx) return resultget_available_positions每次从0到9扫一遍三子棋规模下完全够用。如果在AI搜索里发现耗时不正常优先看这里是否被无意中放进了递归内层并重复计算。实际项目中我一般还会加一个board_to_string函数把当前棋盘按横线格式打印出来调试时放在每次落子之后肉眼确认逻辑是否符合预期。平局判断is_full与check_winner的执行顺序也值得注意先判胜负再判平局否则最后一个棋子同时形成赢法时会被误判成和棋。3. 人机对战AI极小化极大算法与Python递归实现三子棋的人机对战如果只靠随机落子演示时过不了两三局就会被看出没技术含量。要让AI具备可解释的决策能力极小化极大Minimax是电赛场景下性价比最高的算法整套搜索树最大只有9!个叶子数量级在36万Python完全扛得住而且算法本身不依赖任何第三方库。3.1 Minimax 的博弈树思想把一局三子棋看成一颗对抗搜索树每个节点是一个棋盘状态轮到AI时AI从所有子节点里选收益最大的轮到人类时AI假设人类会选对AI最不利的分支。这样从终局倒推回当前局面AI每一步都在穷举“我走这儿人类会怎样应对”的完整博弈树。终局收益定义为AI赢1、人类赢-1、平局0不做赢棋步数的加权因为三子棋中对局长度太短加权反而让AI在两条必胜路径之间犹豫。由于三子棋不会出现重复状态不需要使用置换表随着搜索进行棋局快速收敛Alpha-Beta剪枝成为主要的加速手段。剪枝的核心在于维持两个数值alpha表示当前AI已经找到的最优收益下界beta表示当前人类允许的最差收益上界。当某个分支的收益判断证明它不可能优于已找到的路径时直接停止扩展该分支三子棋场景通常能剪掉接近一半的节点。3.2 AI类的完整Python实现import math import random class TicTacToeAI: def __init__(self, ai_playerO, human_playerX, max_depth9): self.ai ai_player self.human human_player self.max_depth max_depth def evaluate(self, board): 终局收益AI赢返回1人类赢返回-1否则0 if check_winner(board, self.ai): return 1 if check_winner(board, self.human): return -1 return 0 def minimax(self, board, depth, is_ai_turn, alpha, beta): score self.evaluate(board) if score ! 0: return score moves get_available_positions(board) if not moves: return 0 if depth self.max_depth: return 0 if is_ai_turn: best -math.inf for move in moves: row, col move // 3, move % 3 board[row][col] self.ai best max(best, self.minimax( board, depth 1, False, alpha, beta)) board[row][col] None alpha max(alpha, best) if beta alpha: break return best else: best math.inf for move in moves: row, col move // 3, move % 3 board[row][col] self.human best min(best, self.minimax( board, depth 1, True, alpha, beta)) board[row][col] None beta min(beta, best) if beta alpha: break return best def best_move(self, board): 枚举所有可落子位置返回minimax评分最高的落子 best_score -math.inf candidates [] for move in get_available_positions(board): row, col move // 3, move % 3 board[row][col] self.ai score self.minimax(board, 1, False, -math.inf, math.inf) board[row][col] None if score best_score: best_score score candidates [move] elif score best_score: candidates.append(move) return random.choice(candidates)递归体里的核心是“落子-递归-撤销”三连每次递归都直接修改当前的board列表返回上一层前立刻恢复成空这样整个搜索过程只维护一份棋盘副本内存占用恒定。如果改写成每次复制新列表再传下去36万节点的搜索会多出数百万次列表拷贝Python里能把毫秒级操作拖到秒级。best_move在多个评分都等于最优值的候选里随机选一个这个设计不是装饰性的三子棋先手不败意味着完全正确的AI在开局时有四五个同样最优的位置固定取第一个会让对局结果千篇一律评审连续玩三局就能记住你的套路随机选择能显著增加棋路变化。3.3 搜索深度与棋力的关系max_depth是控制棋力的关键参数。9层对应三子棋完整博弈树AI是理论上不输棋的完美玩家4层时AI只能看到两步之后的威胁中盘会漏掉一些连续的杀招2层几乎退化成贪心策略只盯当前局面的直接得失适合做低难度入口。max_depth行为特点典型用途9完整搜索攻击与防守都无懈可击电赛正式评审4能看到两步威胁偶尔失误演示版默认难度2当前局面贪心容易被骗入门教学演示在前面的实现里max_depth设为9时实际递归深度很少到达上限因为大部分分支会在终局提前返回普通PC上单步耗时基本在几十毫秒以内。如果你在性能较弱的开发板上发现AI落子卡顿先检查剪枝条件是否因为缩进错误跑到了循环外面再考虑把max_depth降为7——三子棋里7层和9层的棋力表现对一般用户来说几乎无法区分。3.4 延迟与随机性让AI看起来更像“对手”即使AI计算只需30毫秒我也建议在UI层强制加0.3到0.5秒的落子延时。这纯粹是演示体验问题人类对局时思考时间与决策难度有关电脑瞬间落子又下得极准反而会让人觉得是从预设表里读答案。延时自然落在UI线程里不影响AI计算本身两行代码就能实现。此外可以在best_move里加入一个随机失误参数比如设置mistake_rate0.15时有15%概率从评分第二的候选里随机挑一个而不是总选最优。这个参数比调低搜索深度更可控它保留了AI“看懂威胁”的能力只是偶尔犯明显错误模拟出和人下棋的真实感而不至于让AI显得毫无章法。4. 电赛适配从PC仿真到嵌入式平台的迁移要点PC上运行良好的Python三子棋源代码不会直接变成电赛作品中间要过一道“平台适配”的关卡屏幕用哪套方案、按键怎么映射、GPIO抖动怎么处理。这一章的思路是把所有硬件相关代码隔离在UI层让棋盘逻辑和AI模块在迁移时一字不改。4.1 逻辑与界面分离的项目结构三子棋这样的项目规模不大但一旦涉及界面就必须拆文件。如果把pygame.draw调用和minimax函数写在一起后面换显示方案时整个文件都要重写。常见的做法是拆成四个角色board负责棋盘状态与终局判定ai负责决策game负责对局流程UI层只做两件事——把玩家操作翻译成落子位置把落子结果画到屏幕上。tic_tac_toe/ ├── board.py # create_board, check_winner, make_move ├── ai.py # TicTacToeAI类 ├── game.py # 对局流程控制 ├── ui_terminal.py # 终端版输入0~8落子 ├── ui_pygame.py # 图形版鼠标/触摸落子 └── main.py # 程序入口# game.py —— 与界面完全无关的对局循环 def play_one_round(board, ai, human_playerX, ai_playerO, wait_for_human_move): current human_player while True: if current ai_player: move ai.best_move(board) make_move(board, move, ai_player) else: move wait_for_human_move(board) make_move(board, move, human_player) if check_winner(board, current): return current if is_full(board): return None current ai_player if current human_player else human_playerplay_one_round里唯一需要外部注入的是wait_for_human_move函数它在终端版里读键盘在pygame里等鼠标点击在硬件方案里等按键事件。只要保持这个函数签名不变从终端版切到图形版时game.py一行都不用改。函数本身作为参数传进来而不是在game.py里直接import某个UI模块是为了避免循环依赖UI层需要调用game.py里的流程函数game.py不该反过来依赖UI层。4.2 三套界面方案的取舍界面方案依赖适用场景在电赛中的角色tkinterPython标准库快速验证逻辑跨平台PC端原型演示pygamepygame库界面流畅易做选中高亮带屏幕的Linux板GPIO字符/LCD硬件驱动库直接驱动竞赛屏幕最终硬件作品tkinter最大的优势是不需要安装任何第三方库一台装好Python的机器就能直接跑适合赛前快速验证AI算法和整体玩法。pygame的绘制模型更贴近游戏循环光标移动、选中高亮、落子动画都好实现但目标板需要额外安装pygame部分嵌入式Linux环境安装会卡在依赖上。GPIO直驱方案最贴合电赛硬件要求三子棋的3x3棋盘可以用8x8点阵或16x2字符屏表达但绘制和刷新都要自己处理这也是大多数最终提交方案的选择。4.3 5键导航的输入映射实现竞赛硬件上最常见的输入配置是5个按键上、下、左、右、确认。实现逻辑是维护一个光标坐标方向键移动光标确认键在光标位置落子。这个设计比“9个格子对应9个按键”省引脚也比“编号循环切换”直观得多。class KeypadNavigator: 方向键移动光标确认键选择返回0~8的位置编号 def __init__(self): self._row 1 self._col 1 def move(self, dr, dc): self._row max(0, min(2, self._row dr)) self._col max(0, min(2, self._col dc)) def confirm(self, board): if board[self._row][self._col] is EMPTY: return self._row * 3 self._col return None # 在pygame事件循环里 # clock pygame.time.Clock() # while running: # for event in pygame.event.get(): # if event.type pygame.KEYDOWN: # if event.key pygame.K_UP: # navigator.move(-1, 0) # elif event.key pygame.K_RETURN: # pos navigator.confirm(board) # if pos is not None: # make_move(board, pos, human_player) # clock.tick(30)move里的max(0, min(2, ...))把光标钳位在棋盘边界内到达最左一列后继续按左键不会串到上一行末尾这是按键映射最容易忽略的细节。confirm返回None表示当前位置已有棋子UI层对这个结果什么都不做而不是报错或覆盖棋子——演示时用户连续按确认键是必然操作空白格落子、非空白格忽略比任何提示弹窗都自然。4.4 迁移到开发板的四个高频坑第一是Python版本差异板子上自带的Python可能停留在3.7或3.9如果代码里用了高版本的match语句或:海象赋值一启动就报语法错误。保守做法是全程只用基础语法列表推导和函数默认参数这些3.5时代就存在的特性已经足够写完整个三子棋项目。第二是GPIO按键抖动。物理按键在按下和释放瞬间会产生短暂的电平抖动一次按压可能被识别成多次触发光标一下跳两格。软件去抖最常见的实现是记录上次事件时间戳间隔不足50毫秒的事件直接丢弃。第三是pygame帧率失控。不指定帧率的while循环会全速刷新CPU占用率直接拉满同时方向键响应快到光标乱飞。用pygame.time.Clock对象在每轮循环末尾tick(30)把刷新率锁定在30帧。第四是递归深度限制。三子棋的Minimax最大深度只有9层不会触发Python默认的1000层递归上限但如果赛前临时把代码扩展到五子棋思路递归深度会迅速增长一定要提前用sys.setrecursionlimit评估别等现场看到RecursionError再慌。5. 验证与调试三子棋AI上板前的自动化检查三子棋的逻辑正确性靠手玩是验证不完的。9种先手开局、中间的分支变换、终局的胜负平三种结果靠人一局局点至少要点几十盘还容易受情绪影响漏看。自动化测试能把这套验证压缩到几秒钟并且每次修改代码后都能无脑重跑。5.1 全局面回归让AI应对所有先手开局写一段循环让AI后手应对人类先手的全部9个开局人类每次都走第一个空位。这个人类策略足够弱AI如果输掉任何一个局面说明胜负判定或Minimax收益符号有漏洞。def test_ai_never_loses(): ai TicTacToeAI(ai_playerO, human_playerX) for first in range(9): board create_board() make_move(board, first, X) turn O while not is_full(board): if turn O: make_move(board, ai.best_move(board), O) else: make_move(board, get_available_positions(board)[0], X) if check_winner(board, O): raise AssertionError(fAI 在先手{first}时落败) if check_winner(board, X): break turn X if turn O else O print(OK)注意断言只禁止AI输不禁让人赢三子棋后手在对手完美时没有必胜路径“AI不输”已经是最强标准。测试在秒级完成每次改完ai.py先跑它再动界面代码。5.2 耗时打点与固定杀着回归如果演示时AI落子偶尔卡顿用perf_counter前后打点确认耗时是否真的落在AI计算上。三子棋完美AI单步应在百毫秒内超过这个量级优先检查剪枝条件是否失效、棋盘是否在递归里被复制。start time.perf_counter() move ai.best_move(board) print(f{time.perf_counter() - start:.3f}s)固定棋局用例比全局面回归更快、失败指向更明确。例如构造一个“AI一步可胜”的局面断言AI一定选中必胜点board create_board() for pos, player in [(0, X), (1, X), (3, O), (4, O)]: make_move(board, pos, player) move TicTacToeAI(ai_playerO, human_playerX).best_move(board) assert move 8, fAI 应下位置8实际选择了 {move}这类用例覆盖“一步取胜、双重威胁、唯一空位”等关键分支配合全局面回归能让你在上板前把算法层的低级错误全部拦下。把这些用例存成test_ai.py直接python test_ai.py执行改动AI后先跑测试再打包是我在电赛备赛周期里最后一步必做的动作。本文还有配套的精品资源点击获取