AI 交互实验
和可莉比赛炸鱼、下山找宝箱、清营地,在小游戏里探索算法。读文章答题攒下的原石,可以去“可莉祈愿”给可莉抽装扮。
可莉炸鱼:K-means 聚类
星落湖里藏着好几群鱼。先自己放蹦蹦炸弹,再看可莉用 K-means 一轮轮把炸弹挪到鱼群中间,比比谁炸得多。
正在准备星落湖……
湖面
琴团长:可莉!你又去星落湖炸鱼了?跟我去禁闭室,好好反省。
旅行者—平均距离 —
可莉的算法—平均距离 —
原理透视
分配:每条鱼认领最近的炸弹 · 更新:炸弹移到这队鱼的平均位置
距离平方和 SSE(越小越好)—
湖面编号 —。点湖面放炸弹,再点一次可以拿起来。
- 已玩局数
- 0
- 赢过可莉
- 0
- 被关禁闭
- 0
K-means 不知道正确答案,它只重复两件事:每条鱼认领离自己最近的炸弹;每颗炸弹挪到认领它的鱼的平均位置。重复到没有鱼换队为止,距离平方和(SSE)每一步都不会变大。它追求“离得近”而不是“炸得多”,所以玩家有机会赢。
可莉下山找宝箱:梯度下降
山上起了大雾,宝箱藏在最低的山谷里。先带可莉在雾里摸索,再看她用梯度下降——只看脚下哪边最陡——一步步往下走。
正在准备蒙德的山……
山
旅行者带路—终点海拔 —
可莉的梯度下降—终点海拔 —
原理透视
新位置 = 旧位置 − η × 坡度(梯度)· 风之翼:再加上 0.8 × 上一步
海拔随步数的变化—
山的编号 —。点地图带路,每步最远约 53 像素;雾里只能看到走过的地方。
- 已玩局数
- 0
- 赢过可莉
- 0
- 飞出地图
- 0
梯度下降不知道宝箱在哪,它只会算脚下的坡度(梯度),然后朝最陡的下坡方向迈一步:新位置 = 旧位置 − η × 梯度。步子 η 太小会困在史莱姆坑(局部最小值);太大会在山谷两侧来回弹,甚至飞出地图(发散)。风之翼(动量)保留上一步的惯性,有时能冲出小坑,但也更容易冲过头。
可莉清营地:贪心算法
路上排着一串丘丘人营地,一颗蹦蹦炸弹能炸到左右 2 格以内。先自己扔,看最少要几颗;再看可莉的直觉和妙计谁更省——最后把你的炸弹挪一挪,亲眼看贪心为什么最优。
正在侦察丘丘人营地……
营地
旅行者—清掉 —
可莉的直觉—清掉 —
原理透视
妙计:炸弹位置 = 最左还没炸的营地 + r(r = 2,不超出道路)
从左数连续清掉的营地(妙计始终领先)—
道路编号 —。点路面放炸弹,再点一次可以收回;为什么妙计最少,见《贪心算法入门》的覆盖证明。
- 已玩局数
- 0
- 赢过可莉
- 0
- 拿到最少
- 0
