Angry Birds 的计算复杂度问题

时间做了一个关于 NP 问题的题目，老师一开始就给了个 ppt，看起来贼吃力，后来一个 assignment 才很鸡贼的又给了一篇文章，是他的一个学生的论文讨论这个问题。当时快考试了，匆匆写了些乱七八糟的，现在把它翻出来，趁着假期时间整理一下所学知识。开个坑督促自己把这篇文章研究完，同时也记录下自己的理解。

据说去年的 assignment 也是这篇文章，当时文章还未发表，还让学长们写 review。这里的图片都是我自己重新画的，也与原文不大一样，别坑了人家。😂
另：让我们拟题目怕不是自己找不到题目哦! 🌚 🌚
又另：把学生未发表的 paper 给我们看真的好么 😓

先列一下可能需要阅读的相关论文：

1. Aloupis, G.; Demaine, E. D.; Guo, A.; and Viglietta, G. 2014. Classic Nintendo games are (computationally) hard. In_Proceedings of the 7th International Conference on Fun with Algorithms_, 40–51.
2. Foris ˇ ek, M. 2010. Computational complexity of two- dimensional platform games. In_Proceedings of the 5th In- ternational Conference on Fun with Algorithms_, 214–227.
3. Kendall, G.; Parkes, A.; and Spoerer, K. 2008. A survey of NP-complete puzzles._ICGA Journal_31:13–34.
4. Viglietta, G. 2014. Gaming is a hard job, but someone has to do it!_Theory of Computing Systems_54:595621.
5. Sun, Y., Wang, Q., Li, N., Bertino, E., & Atallah, M. (2011). On the complexity of authorization in RBAC under qualification and security constraints.IEEE Transactions on Dependable and Secure Computing,8(6), 883-897.
6. Renz, J.; Ge, X.; Verma, R.; and Zhang, P. 2016. Angry Birds as a challenge for artificial intelligence. In_Proceed- ings of the 30th AAAI Conference_, 4338–4339. * 嗯，看了，全是吹水，没啥卵用

工具

1. http://www.battlefieldsingleplayer.com/apachethunder/angrybirds/
2. https://www.processon.com

相关概念

P 类问题：所有可以在多项式时间内求解的判定问题构成 P 类问题。_判定问题：_判断是否有一种能够解决某一类问题的能行算法的研究课题。

NP 类问题：所有的非确定性多项式时间可解的判定问题构成 NP 类问题。非确定性算法：非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的，算法的验证阶段是确定性的，它验证猜测阶段给出解的正确性。设算法 A 是解一个判定问题 Q 的非确定性算法，如果 A 的验证阶段能在多项式时间内完成，则称 A 是一个多项式时间非确定性算法。有些计算问题是确定性的，例如加减乘除，只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式能推出下一个质数是多少呢？这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式（polynomial）时间内算出来，就叫做多项式非确定性问题。

**NPC 问题：**NP 中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有 NP 问题都是多项式时间可解的.这些问题被称为 NP-完全问题(NPC 问题)。

NP-hard：通俗来说是其解的正确性能够被“很容易检查”的问题，这里“很容易检查”指的是存在一个多项式检查算法。相应的，若 NP 中所有问题到某一个问题是图灵可归约的，则该问题为 NP 困难问题。

3-SAT【NPC】2、SAT 规约到 3SAT - CSDN 博客

分析

文章从 3SAT 问题的一个 instance 归约出 AB 的一个 instance，由于 3SAT 是 NPC 问题，则证明了 AB 是 NP-hard。同时，通过证明 AB 问题在 NP 内，我们可以证明 AB 问题是 NPC 问题。

3SAT 中，一个 clause 由三个 literal 并得到，一个 instance 由多个 clause 交得到，每个 literal 的真值由 variable 输入。

e.g. (x⋁(-z)⋁y)⋀(x⋁(-x)⋁(-y))⋀((-y)⋁(-x)⋁z)

为了将 3SAT 问题归约至 AB 问题，需要对 AB 的规则进行定义。

对 Angry Birds 的定义：

每一层（Level）：

• 本层宽度（像素）.

• 本层高度（像素）.

• 发射坐标.

• 可用的鸟的类型和顺序的列表.

• 列表：所有猪的类型、角度和坐标. *这里的角度感觉应该是笔误吧，不存在的

• 列表：所有其他的物品的种类、角度和坐标.

文章定义了几种 gadget，来表示 AB 内的机制。

• 变量装置 Variable gadget

• 字段装置 Clause gadget

• 交叉装置 Crossover gadget

定理 1:对 AB level 问题的解是 NP 困难的

从一个 NP 完全问题 3SAT 归约到上面的框架。

所有的鸟被发射到变量装置，然后激活对应的字段装置。如果所有字段装置都被激活，那么这层就被解决了。

由此，我们通过从 3SAT 归约到 Angry Birds 问题，证明了 AB 是 NP 困难的。

定理 2:AB 问题是 NP 完全的

我们上面已经证明了 AB 问题是 NP 困难的，那么，如果想要证明 AB 问题是 NP 完全的，我们还需要证明 AB 问题在 NP 里。

根据上面 NP 问题的定义，我们可以转化到 AB 问题上：对任何一个给定 level 的策略，都可以在一个确定性的图灵机上，以相对于 level 描述的大小的多项式时间来验证，并且对于任何给定的 level，都有有限数量的状态和策略。

这样，我们就需要进一步做两个证明：

引理 2.1：对任何 AB level，其状态和策略的数目都是有限的。

引理 2.2：任何对于给定的 AB level 的策略都可以在多项式时间内被证明。

• 一个例子
  

2018-05-21 更新

上午闲的没事倒腾电脑，发现了这个被遗忘在角落里的文章。当时做作业的时候就各种难受，最后也没太弄明白，还看了去年未发表的文章，对其中的公式证明和最后的 generalisation 啥的也没大看懂。

当时这篇文章还没有发表，也不好列出太多细节。现在发表了，这里给下文章引用吧，是我的老师们和一个学长写的。

Stephenson, M., Renz, J., & Ge, X. (2017). The Computational Complexity of Angry Birds and Similar Physics-Simulation Games.