前天写了个五子棋ai助手，但是效果并不理想
说是ai，其实是纯算法，主要用了Minimax和Threat-First Heuristic算法
Minimax（极大极小值搜索）：论坛人机对战的算法，是一种博弈树搜索算法，假设双方都采用最优策略，通过递归搜索所有可能的走法（计算量过大，会导致浏览器卡顿），找到对自己最有利的落子位置。
Threat-First Heuristic（威胁优先启发式）：是一种启发式算法，不进行深度搜索，而是直接评估每个候选点的威胁程度，选择威胁最大的位置。
所以效果不太理想
，一把没赢，真一把没赢！！！
所以效果不太理想
，一把没赢，真一把没赢！！！
今天优化了一下算法，主要从以下地方入手：
一、Minimax算法
工作原理
1. 构建博弈树
- 根节点：当前局面
- 每一层：一方所有可能的落子
- 叶子节点：评估函数计算局面得分
2. 递归搜索
- Maximizing层（我方）：选择得分最高的分支
- Minimizing层（对方）：选择得分最低的分支
- 从叶子节点向上回溯，逐层选择最优值
3. Alpha-Beta剪枝
- Alpha：我方当前找到的最好值（下界）
- Beta：对方当前找到的最好值（上界）
- 当 Alpha >= Beta 时，可以剪枝（不再搜索该分支）
优化方向
1. 置换表（Transposition Table）
- 使用Zobrist哈希快速计算局面哈希值
- 缓存已计算过的局面，避免重复计算
- 存储边界类型（exact/lower/upper），支持更精确的剪枝
2. 迭代加深搜索（Iterative Deepening）
- 从深度1开始，逐步加深搜索
- 在时间限制内尽量搜深
- 保留上一层最优解，确保稳定性
3. 启发式候选点排序
- 使用威胁评分（threatScoreForMove）对候选点排序
- 优先搜索威胁大的位置（活四、冲四等）
- 提高Alpha-Beta剪枝效率
4. TopK裁剪
- 根据搜索深度动态调整候选点数量
- 深度3+：只考虑10个最佳候选点
- 深度2：考虑14个候选点
- 深度1：考虑22个候选点
二、Threat-First算法（威胁优先算法）
工作原理
1. 候选点生成
- 只考虑已有棋子周围的空位（邻居检查）
- 限制搜索范围，减少计算量
2. 威胁评分（threatScoreForMove）
- 评估我方在该位置落子后的威胁
- 评估对方在该位置落子后的威胁
- 综合计算威胁分数
3. 可选的两层搜索
- 深度1：纯启发式，只考虑当前威胁
- 深度2+：考虑对手下一手的最好威胁（简化两层搜索）
优化方向
1. 先杀/先防检查（借鉴Minimax）
- 在生成候选点前，先快速检查是否能直接赢或必须防
- 使用快速候选点生成（只考虑邻居1格），减少计算量
- 遇到必杀或必防局面时立即返回，无需后续计算
2. 威胁评分缓存
- 使用Map缓存已计算的威胁评分
- 避免重复计算相同位置的威胁
- 显著减少重复计算，提升性能
3. 动态候选点数量调整
- 根据深度动态调整候选点数量：
- 深度3+：28个候选点
- 深度2：32个候选点
- 深度1：36个候选点
- 对手应手候选点也动态调整（16-20个）
- 深度越深，候选点越少，提高效率
4. 早期终止优化
- 找到必杀位置（威胁分数 >= 1e12）立即返回
- 找到必防位置（威胁分数 >= 9e11）优先处理
- 减少不必要的计算，提升响应速度
5. 对手应手搜索优化
- 对手候选点数量根据深度动态调整
- 优化搜索逻辑，减少CPU占用
- 两层搜索更高效
特点
- 速度快：不进行深度搜索，计算量小
- CPU友好：适合低性能设备
- 实战强：优先处理威胁，符合人类下棋思路
- 深度不足：无法预见多步后的局面（但通过两层搜索部分弥补）
写在最后：
如果看到我开的局，可以放心进
1. 只开 50 硬币的局，测试为主，硬币有限可以多测几次。
2. 如果你赢了，那就是赚了。如果你输了，可以私信我返还硬币，赚的都给你（就当帮我测试了）
域名市场
域名载入中...
