1-前言

为了应对大学院考试，我们来学习相关人工智能相关知识，并且是基于相关课程。使用课程为MIT的公开课。

通过学习，也算是做笔记，让自己更理解些。

2-课程链接

是在B站看的视频，链接如下：
https://www.bilibili.com/video/BV1dM411U7qK?spm_id_from=333.788.videopod.episodes&vd_source=631b10b31b63df323bac39281ed4aff3&p=6

3-具体内容解释说明

一、这一节在 AI 里是干什么的？

前面的「路径搜索（BFS、A*）」是假设世界是客观的：
👉 路不动、不会反抗你。

而这一节开始假设：

你的对手会“故意做对你最不利的选择”

典型场景：

• 棋类游戏（五子棋、象棋、围棋）
• 博弈问题
• 自动对战 AI

---

二、博弈（Game）是什么（考试定义）

在这里指的是 两人零和博弈：

• Player MAX：想让结果 尽量大
• Player MIN：想让结果 尽量小
• 一方得分 = 另一方损失

👉 入试默认：
双方都绝对理性

---

三、极小化极大（Minimax）算法

1️⃣ 核心思想（一句话版）

我选一个行动，使得“对手最坏应对下，我的结果仍然最好”

听起来绕？拆开：

• 我假设对手 一定选最坏的
• 在这个前提下
• 我选择对我 最有利的行动

---

2️⃣ 用树来理解（考试最爱）

• 根节点：当前局面
• MAX 层：我行动
• MIN 层：对手行动
• 叶子节点：局面的评价值（分数）

规则：

• MAX 节点：取 子节点的最大值
• MIN 节点：取 子节点的最小值

一路往上“回传”分数。

---

3️⃣ 为什么叫“极小化极大”

• 对手：极小化 我的收益
• 我：在此基础上 极大化 自己的收益

---

四、α-β 剪枝（α-β pruning）

1️⃣ 为什么需要它？

Minimax 的致命问题：

• 分支太多
• 搜索树爆炸
• 很慢

👉 α-β 剪枝 = 不用看“已经确定不可能更优”的分支

---

2️⃣ α 和 β 分别是什么？

• α（alpha）：
  👉 MAX 目前 至少能保证的最好分数
• β（beta）：
  👉 MIN 目前 最多允许的分数上限

---

3️⃣ 剪枝规则（必考）

当搜索过程中发现：

α ≥ β

说明：

• 当前分支再往下
• 不可能影响最终决策

👉 直接停止搜索这个分支（剪枝）

---

4️⃣ 剪枝的效果

• 结果不变
• 速度大幅提升

👉 入试标准说法：

α-β 剪枝在不影响最优解正确性的前提下减少搜索节点数

---

五、这类题在考试里怎么考？

常见问法

• Minimax 假设了玩家具有什么特性？
• α-β 剪枝会不会改变最终决策？
• α ≥ β 时意味着什么？
• Minimax 与路径搜索的本质区别是什么？

👉 不考代码，不考公式

---

六、和你之前学的「搜索」怎么区分（重点）

搜索类型	假设	代表
路径搜索	环境不反抗	BFS、A*
博弈搜索	对手最坏应对	Minimax
加速技巧	剪掉无用分支	α-β

---

七、考试用一句话模板（直接背）

极小化极大法是一种用于两人零和博弈的对抗搜索方法，假设双方均理性行动，通过在 MAX 层选择最大值、MIN 层选择最小值来确定最优策略。α-β 剪枝通过维护 α 和 β 边界，在不影响最优解正确性的前提下减少搜索空间。

---

4-课后练习（日语版本）

---

🔹 問題1（経路探索・A*）

A*探索に関する説明として最も適切なものはどれか。

a. ヒューリスティック関数が常に実際のコストを過大評価するとき、最短経路が保証される
b. 評価関数 f(n)=g(n)+h(n) を用い、g(n) は開始点からの累積コストを表す
c. ヒューリスティック関数を用いないため、幅優先探索と同一である
d. 負のコストを含むグラフに対しても常に正しく動作する

---

🔹 問題2（経路探索・比較）

幅優先探索（BFS）とダイクストラ法に関する説明として正しいものはどれか。

a. BFS は常に最短経路を求めることができる
b. ダイクストラ法は負の重みを含むグラフにも適用できる
c. 辺のコストがすべて等しい場合、BFS は最短経路を求められる
d. BFS はヒューリスティック関数を利用する探索手法である

---

🔹 問題3（博弈・Minimax）

極小化極大法（Minimax 法）に関する説明として最も適切なものはどれか。

a. 確率的に相手の行動を予測し、期待値を最大化する
b. 各プレイヤーが合理的に行動し、相手が最悪の選択をすると仮定する
c. 単一エージェントの経路探索問題に用いられる
d. 評価関数は探索過程で使用されない

---

🔹 問題4（α–β 剪枝）

α–β 剪枝に関する説明として正しいものはどれか。

a. 剪枝を行うことで最終的な最適解が変化する可能性がある
b. α は MIN プレイヤーの最小許容値を表す
c. α ≥ β となった場合、その分岐以下の探索を打ち切ることができる
d. α–β 剪枝は探索の深さを浅くするアルゴリズムである

---

✅ 参考：答题提示（超重要）

• 「常に」「必ず」 → 多半是错
• 负の重み / ヒューリスティック / 合理的玩家 → 高频考点
• α–β 剪枝：结果不变，速度变快 → 一定要记住

---

5-课后答案解析（日语版本）

✅ 判定结果

题号	你的答案	正确答案	判定
1	C	B	❌
2	C	C	✅
3	B	B	✅
4	A	C	❌

👉 总计：2 / 4
👉 错的都是“易混淆但高频”的点，非常典型

---

🔍 逐题解析（入试版简洁说明）

---

❌ 問題1（A* 探索）

你选：C

ヒューリスティック（Heuristic） 的意思是：简单说就是：不用最严谨、最全面的计算，而是用“经验 + 直觉 + 简化规则”来更快地做出判断或找到一个“够好”的答案。

ヒューリスティック関数を用いないため、幅優先探索と同一である

❌ 错因：
A* 一定使用ヒューリスティック関数 h(n)，否则就不是 A*。

✅ 正确答案：B

f(n)=g(n)+h(n) を用い，g(n) は開始点からの累積コスト

📌 命题意图：确认你是否真正理解 A* 的评价函数。

---

✅ 問題2（BFS vs ダイクストラ）

ダイクストラ：Dijkstra算法（最短路径算法）

你选：C（正确）

辺のコストがすべて等しい場合，BFS は最短経路を求められる

✔ 标准正确
📌 这是大学院超爱考的一句话结论

---

✅ 問題3（Minimax）

你选：B（正确）

相手が最悪の選択をすると仮定する

✔ 完全命中核心定义
📌 看到「合理的」「最悪」基本就锁定 Minimax

---

❌ 問題4（α–β 剪枝）

你选：A

剪枝を行うことで最終的な最適解が変化する可能性がある

❌ 错因：
这是α–β 剪枝最核心的反命题

✅ 正确答案：C

α ≥ β の場合，探索を打ち切る

📌 考试必背：

α–β 剪枝は「結果を変えずに探索量を減らす」

---

🎯 你的真实水平评估（很重要）

• 概念理解：OK
• 核心思想：OK
• 容易被“否定型/极端表述”带跑

👉 这正是 大学院会刷人的地方

---

🔑 考前提分技巧（马上能提升）

1. 看到

   • ❌「用いない」
   • ❌「常に」「必ず」
   • ❌「結果が変わる」
     → 高度警惕

2. A* / α–β
   → 定义句直接背

---

6-总结

知识一点点记录吧，最后应对考试，打下基础