01恢复双方身体历史
02枚举己方最多 4 个落点
03BFS 计算空间与资源
04枚举对手全部合法一步
05按最坏局面选择最高分
输入：地图 + 双方状态
→输出：一个合法落点
安全创客实践
AI 对抗 · 网格搜索 · 状态压缩
蒜头攻防
蒜头攻防
大战
让“贪吃蛇”从寻找一条路，升级为在同时移动、动态缩圈和对手博弈中做实时决策。
状态重建BFS 多指标最坏情形评分四进制 Hash
挑战定义
难点不在“走一步”，而在同时预判
每回合只有 100 ms。双方同时移动，地图持续缩圈，苹果和护盾又会改变长度与碰撞胜负。
- 信息不完整：地图只给占用区域，不给精确身体顺序
- 动作不确定：看不到对手本回合选择
- 空间动态：尾格释放、身体增长、边界收缩同时发生
########
#·11●··#
#··1·#◆#
#··!··2#
#·#··22#
########
总体方案
五步闭环，把复杂规则压成一次实时决策
核心创新一
用历史恢复身体，让尾格释放进入搜索
占用字符只告诉我们“哪里有身体”，连续回合的头坐标才能恢复“身体顺序”。
head[t] → head[t−1] → … → tail
新头压入历史；再用地图可见长度校准，覆盖初始生长和吃道具后的变化。
直接收益：若本步不增长，旧尾格可以临时开放；AI 因此能判断“绕回自己的尾巴”是否可行。
动态身体
模型
历史头坐标可见长度校准本回合尾格释放未来尾部连通
模型
核心创新二
BFS 不只求最短路，而是测量生存质量
一次 BFS，复用五类结果
指标强弱示意连通面积area
下一步出口mobility
尾部连通tail
苹果距离apple
护盾距离shield
“最近”不是目标，可持续地到达才是目标。
- 面积足够，或仍能回到未来尾部，才允许积极增长
- 出口过少、即将缩圈、同格败碰直接高额惩罚
- 领先时保空间，落后且临近终局时提高资源收益
对抗决策
把对手的四种回应都算一遍，选择最坏也能接受的动作
Score(move) = minopp ∈ legal Eval(move, opp)
- 同格碰撞：按护盾状态，再按移动后长度判断
- 最坏领地：比较双方 BFS 到达时间，取所有回应中的最小领地
- 封路机会：对手无合法步或仅有必败回应时，提升终局优先级
一个候选动作的四种未来
↑安全
→领地 −4
↓败碰
←封路
这里的结论取决于最差的“败碰”，因此该动作被淘汰。
算法题创新
四进制 Hash：用一个整数表示整条蛇的形状
0上
1右
2下
3左
hash = hash × 4 + direction
1223→107₁₀
给定蛇头坐标，再记录相邻身体节的相对方向序列，就能唯一恢复整条蛇。
int get_shape_hash(Snake *s, int k) {
int hash = 0;
for (int i = 1; i < k; ++i)
hash = hash * 4 + direction(i);
return hash;
}
刚好匹配约束：k ≤ 9，最多 8 位四进制数，因此 0…4⁸−1 = 65535，可直接作为 vis[16][16][65536] 的下标。
能力迁移
算法题压缩状态，大项目用状态做决策
贪吃蛇算法题
- 完整蛇形是搜索状态
- 四进制编码实现紧凑判重
- BFS 保证最少步数
→
蒜头攻防大战
- 身体历史是动态状态
- 尾格释放提升模型一致性
- BFS 服务于多指标对抗评分
共同方法：先找到最小充分状态，再只搜索影响未来的信息。
结论
在 100 ms 内，把生存、资源与博弈放进同一个决策器
我们交付的不是一条固定路线，而是一套能随局面更新的实时决策方法。
最大 50×50O(nm) 单回合固定数组G++11
01动态状态：身体历史 + 尾格释放
02稳健对抗：对手全枚举 + 最坏领地
03状态压缩：四进制 Hash 支撑算法题 BFS