Angry Birds 的计算复杂度问题

本贴最后更新于 2389 天前,其中的信息可能已经渤澥桑田

时间做了一个关于 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):Level = (L_x , L_y , slingshot, birds, pigs, other)

  • 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.

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...