找到一个带变量������的问题 给定一个解（下落位置和旋转的序列）
NP Reduction？
From 3-partition
2018/8/25
南京邮电大学计算机学院
17
Reduction
End
Begin
2018/8/25
南京邮电大学计算机学院
18
Tetris Game
NP-complete
Stephen Arthur Cook (1939--) 1982年图 灵 奖
2018/8/25
南京邮电大学计算机学院
10
算法的复杂度
Class NP-Complete
A decision problem c is NP-complete if
c is in NP Every problem in NP is reducible to c in polynomial time.
3
Байду номын сангаас戏分类
电脑游戏按内容分：
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. RPG角色扮演游戏（Role-playing Game） ACT动作游戏（Action Game） AVG冒险游戏（Adventure Game） FPS第一人称视角射击游戏（First Personal Shooting Game） FGT格斗游戏（Fighting Game） SPT体育类游戏（Sports Game） PZL益智类游戏（Puzzle Game） RCG竞速游戏（Racing Game） RTS即时战略游戏（Real-Time Strategy Game） STG射击类游戏（Shoting Game） SLG策略游戏（Strategic Simulation Game） MUG音乐游戏（Music Game） SIM生活模拟游戏（Simulation Game） TAB桌面游戏（Table Game） CAG卡片游戏（Card Game）
Class NP-Hard
A decision problem c is NP-hard if
Every problem in NP is reducible to c in polynomial time.
南京邮电大学计算机学院
2018/8/25
11
P=NP？
2018/8/25
南京邮电大学计算机学院
南京邮电大学计算机学院
4
2018/8/25
游戏分类
Information
Perfect information：Chess, Go Imperfect information: Card game
Number of players
Single player: Tetris, 2048 Game Multi players: Chess, Go, Card Game
2018/8/25
南京邮电大学计算机学院
27
游戏怎么玩？
看得远 看得准
2018/8/25
南京邮电大学计算机学院
28
Search
Mini-Max search ������ − ������ pruning Monte-Carlo method Monte-Carlo tree search
南京邮电大学计算机学院
21
玩游戏的人工智能
形式化：游戏的常见模型 游戏怎么玩？
看得远 看得准
2018/8/25
南京邮电大学计算机学院
22
游戏的常见模型
单个agent
Markov Decision Process
多个Agent
Markov Game
2018/8/25
南京邮电大学计算机学院
6
8
4
2018/8/25
南京邮电大学计算机学院
9
P=NP?
The hardest problem in NP Cook’s theorem (1971)
The SAT problem (Boolean satisfiability) The first NP-Complete problem the problem of determining if there exists an interpretation that satisfies a given Boolean formula.
2018/8/25
南京邮电大学计算机学院
2
游戏（Game）
游戏定义
游戏是一种具有某种功能的活动，具有两个最基本的特性： ①以直接获得快感（包括生理和心理的愉悦）为主要目的。 ②主体参与互动。
总的来说游戏有四个特征：
有趣 不确定 规则 虚构
2018/8/25
南京邮电大学计算机学院
{20, 25, 45} {23, 27, 40}
2018/8/25
NPC
14
南京邮电大学计算机学院
TSP
TSP：The travelling salesman problem
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city? Given the costs and a number x, decide whether there is a roundtrip route cheaper than x？
2018/8/25
南京邮电大学计算机学院
5
目录
游戏的复杂度 玩游戏的人工智能 展望
2017/8/25
南京邮电大学计算机学院
6
进度
游戏的复杂度 玩游戏的人工智能 展望
2017/8/25
南京邮电大学计算机学院
7
游戏的复杂度
算法的复杂度
P NP NP-Complete NP-hard
游戏的复杂度
Tetris的NP-Complete问题
2018/8/25
南京邮电大学计算机学院
8
算法的复杂度
Class P
Decision problems that can be solved by a deterministic Turing machine that runs in polynomial time.
Class NP
Decision problems that can be solved by a nondeterministic Turing machine that runs in polynomial time. NP can be defined using deterministic Turing machines as verifiers.
奖励 ������������,������
Agent 1 Agent 2
动作 A1 动作 A2
状 态
������������
奖励 ������������,������
Agent n
动作 An
环境 ������������+������
2018/8/25
南京邮电大学计算机学院
26
Markov Game
Maximizing the number of rows cleared while playing the given piece sequence
NP-hard
Given an initial gameboard and a sequence of ������ pieces, for any constant ������ > 0, it is NP-hard to approximate to within a factor of ������1−������ the maximum number of pieces that can be placed without a loss, or the maximum number of rows that can be cleared.
2018/8/25
南京邮电大学计算机学院
19
回顾
游戏的复杂度
算法复杂度p, np, np-complete, np-hard 游戏复杂度
启示？
玩游戏 v.s.“不正经”？
2018/8/25
南京邮电大学计算机学院
20
进度
游戏的复杂度 玩游戏的人工智能 展望
2017/8/25
2018/8/25
南京邮电大学计算机学院
29
极大极小搜索
Min: Max: 6 6
11
Min:
6
-1
11
-7
Max:
2018/8/25
6
8
4
-1
3
11
9
-7
30
南京邮电大学计算机学院
Minimax search
A worst-case approach
In zero-sum games, Nash equilibrium
Maxi-min value
������ = max min ������(������, ������)
������ ������
2018/8/25
南京邮电大学计算机学院
31
������ − ������剪枝搜索
Min: Max:
≥6 ？ ≤6 6 ？
6
≥11
Min:
6
？ ≤4