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）：

  • L_x本层宽度（像素）.

  • L_y本层高度（像素）.

  • slingshot发射坐标(x, y) .

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

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

  • other 列表：所有其他的物品的种类、角度和坐标(x, y) .

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

  • 变量装置 Variable gadget

v25be55f05bfad5c401c9630bef0d5929c_bjpg

  • 字段装置 Clause gadget

v2b5bb685c08b022bbce2c96f6e5fb784d_bjpg

  • 交叉装置 Crossover gadget

v28fa22c86e6efb3a3099d8edb3147d512_bjpg

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

imagepng

从一个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的策略都可以在多项式时间内被证明。

  • 一个例子
    imagepng

2018-05-21更新

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

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

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

1091 0
留下你的脚步