今天看到这里给出了一个“星际争霸是 NP-hard 问题”的一个证明。具体地说，给定一个初始布局（包括地图、双方已有资源、双方已有建筑、双方已有兵力），判断其中一方是否能获胜，这个问题是 NP-hard 的。当然，考虑到即时战略游戏的复杂性，这个结论并不出人意料；真正有趣的，则是如何巧妙地利用游戏中的元素，构造出极其精巧的初始局面，从而转化成某个已知的 NP-complete 问题。下面是原文中给出的证明。这个证明有没有什么漏洞？你还能想到哪些别的证明方法？欢迎在下面留言一同分享。
假设初始时有 A 、 B 两位玩家，他们分别位于两个孤岛上。玩家 B 有非常多的地面兵力，但没有空中单位，并且已有资源为 0 ，而且还没有任何经济来源。他只能坐等玩家 A 来攻打他。玩家 A 一开始则完全没有兵力，但他有不少可以生产作战单位的建筑，也有一定的经济来源，理论上有获胜的希望。地图上还有第三个孤岛，孤岛周边放满 B 的对空防御，玩家 A 即使派遣空中部队也无法进入该孤岛。
初始时，玩家 A 的资源刚好够造一个农民，玩家 A 还需要收集额外的 x 个单位的资源才足以消灭玩家 B 。但是，玩家 A 的所有可采集资源都在第三个孤岛上。这个孤岛上有 n 个采矿点，每个采矿点都配备有一个基地，以及 x/n 个单位的矿石资源。每个采矿点也都还预先配备了一个农民，只不过这个农民被矿石围在里面出不来了。采矿点与采矿点之间靠一些小路连接，每条路上都有玩家 B 的防御塔，保证一个农民走过去必死无疑，但是两个农民走过去恰好能活一个。
游戏开始后，玩家 A 唯一获胜的途径便是，在某个采矿点建造一个农民，采完这个采矿点的矿，把被困的农民救出来，然后选择某条小路走到下一个采矿点（途中死掉一个农民），继续采矿并解救农民，以此类推，直到走遍每一个采矿点，采完所有的矿。很容易看到，玩家 A 相当于要解决一个 Hamilton 路的问题（注意，即使平面图的 Hamilton 路问题也是 NP-complete 的）。因此，星际争霸是 NP-hard 的。
Laus deo
cow…..
only l here now?
这只是给定局面下的复杂度啊，显然存在复杂度低得多的局面，但是不知道是否存在更高复杂度的局面……
这个地图可以做出来吧。B是人族，A是虫族，只要造出一个守护者就可以灭掉B了。
前排
可以过去两个半血农民吗？
地核……
地幔……
不是吧…太神奇了…竟然能化归成Hamilton路问题
我觉得这根本就是不可解问题，因为给定初始条件很可能无法确定谁赢谁输。
当然，在这个图中自然是NP-Hard的。
感觉有点问题，首先就是每个矿点要围住一个农民至少要16点矿吧，这导致了x一定的时候，n不能很大，于是为了任意的n都能给出构造方案需要很大的x，但是当x很大的时候，只需要一个空中单位就能搞掉B，解决方法是A和B的孤岛之间加若干B的防空塔，这样A必须要损失一大堆才能通过，然而由于人族有大和炮，虫族飞龙变的那个专门对地的（名字不记得了）射程都比塔远，而神族的话有装甲，我觉得通过操作应该能无损地推塔，所以x也不能很大。。不过我想出来一个终极解决办法：n很大时由于人口限制，你必须把农民搞死才能造兵，不然一堆资源没人口就囧了。。这样理论上任意大的n都成立。。还望星际高手指导如何不造兵自残农民。。
地壳:
有问题….
问题保证了你可活动农民的血总量为1管….
所以你并不能分兵….
回12楼，农民可以对焊的。
不过考虑到微操，胜负就无法判定了。如果微操忽略，应该还是可以计算的：）
给出初始条件判定谁赢肯定是可解问题，因为整张地图每一格的内容，再加上每一个对象的参数等所有条件，总状态还是有限的，因此可以枚举
@14
农民对焊也得找个人过去啊。这样还是要找hamilton路不是？
我有个想法，请参考：
还是借助汉密尔顿回路问题。
假设人族虫族单挑，人族只剩一个房子和一个1血枪兵，虫族只剩若干基地和若干lurker，这些基地和lurker分布在地图上很多由桥连接的小岛上。每个桥都很窄，只能枪兵通过，lurker无法穿行。初始状态是，每个岛上都有一个虫族基地和一只lurker，而且这个lurker刚好被虫族基地卡在岛的一角。
假设当枪兵来到任何一个岛上，都可以攻击虫族基地，且不被lurker攻击。（这容易做到）。而当该基地被打掉后，lurker就可以在该岛自由移动（当然不能出岛），它会在岛正中心埋下，攻击范围辐射整个岛。换句话说，枪兵无法再安全通过这个岛。（当然，在此之前，枪兵还是有时间逃离该岛的）
从而，人族唯一的取胜可能是，寻找一个汉密尔顿回路，走遍所有岛。
似乎只能说明SC可以做出NP-hard的情况，而不能说SC是NP-hard的。
类似“白马非马”之辩
我想到一个用顶点覆盖的方法, 平面图的顶点覆盖仍是 NPC 的
问题: 给出一平面图, 是否能选取 k 个顶点覆盖所有的边
基本思想是每条边转成一玩家 A 的士兵, 每个顶点有一玩家 B 的基地
玩家 A 只能坐以待毙, 玩家 B 则刚好有生产 k 个军队的资源
从某个顶点生产的军队只能杀掉与它相邻的边上的士兵
详细的做法我写了在 http://gagguy.blogspot.com/
p.s. 文中 “从而转化成某个已知的 NP-complete 问题” 好像应该是 “从某个已知的 NP-complete 问题转化成星际”, 因为要证明 NP-HARD 相当於证明 “如果懂得解决星际的话就懂得解决 平面图 hamiliton path”
@18 只需证明其存在np-hard复杂度的情况就行了。并不要求所有的问题实例都是np-hard的。
寻找hamilton通路的问题，也存在复杂度很低的特例不是吗。
这个证明的缺点是，构造的情况太特殊了。
人们其实想知道的是，星际游戏的“平均复杂度”。或者说，建立在一个通常比赛环境作为初始环境前提下的复杂度证明。
但是我认为那个复杂度是不可证的。因为复杂度依赖于算法，而目前还没有一个可以战胜有实力的人类选手的AI算法。没有算法哪来复杂度。
至于说目前游戏采取的算法，那当然是P的。否则计算机怎么执行他。
A是人类只剩个红血基地和一个兵，B还有些建筑分布在各地，A要在基地燃烧完全之前消灭完B所有建筑，那就是个Open TSP问题。
我想到一个用顶点覆盖的方法, 平面图的顶点覆盖仍是 NPC 的
问题: 给出一平面图, 是否能选取 k 个顶点覆盖所有的边
基本思想是每条边转成一玩家 A 的士兵, 每个顶点有一玩家 B 的基地
玩家 A 只能坐以待毙, 玩家 B 则刚好有生产 k 个军队的资源
从某个顶点生产的军队只能杀掉与它相邻的边上的士兵
详细的做法我写了在 http://gagguy.blogspot.com/
p.s. 文中 “从而转化成某个已知的 NP-complete 问题” 好像应该是 “从某个已知的 NP-complete 问题转化成星际”, 因为要证明 NP-HARD 相当於证明 “如果懂得解决星际的话就懂得解决 平面图 hamiliton path”
感觉似乎有些问题，仔细看看再说。。。
这个构造略微有点牵强的感觉…………虽然说找不出什么错误……
咋没人检查检查我 17 楼的类似构造啊
@17：不一定吧，要看操作的吧，以前见过用3个枪兵干掉一个lurker。当然，考虑到操作的话，当然会是NP了吧。
考虑到神族的幻象的话，那还有概率的成分
= =
@16 农民不需要对焊，这么多对方防御随便找个都能自杀..
@17 有个小问题，枪兵到一个岛不见得一定要打岛上的基地，这样的话这个岛就可以反复通行了。所以需要设计成没有消灭基地就不能通过这个岛。这个可能就有难度了..
呵呵，这个有意思了点儿吧，虽然我不太爱玩星际争霸
首先，如果要用Hamilton Path来证明这个问题是NP-hard，需要对Hamilton Path的所有instance都能构造出来对应的基地摆放。但显然SC是在一个平面上的游戏，基地的摆放总是可平面的。
所以应当说是用“平面图的Hamilton Path”这个问题来归约（当然，这也是NPC问题）。
另外，我记得SC里面建筑和单位的数目是有限的吧，好像是最多1024个左右，当然，我们可以定义更一般的“星际争霸”，允许无限大的地图以及单位的数目。
听过过可以干掉人类的ai(zvt爆飞龙狂甩),因为电脑的微操作和效率是人类不能及的,而且人类都会失误电脑不会.
好吧，这也可以，我被你给折服了
OIer + SCer 路过 。。。
同样dota也可设计出NP的打野问题
同样dota也可设计出NP的打野问题
同样dota也可设计出NP的打野问题
@27 假设农民被矿包围的话必须派农民过去先把它搞出来才能自杀。。
同样dota也可设计出NP的打野问题
jizhanwang
楼主写得很不错，学习了啊 哈哈..
为什么要走汉密尔顿路呢，每条路都是死一个农民，保证去下一个矿点的时候是2个农民不就行了？
星际争霸。我玩了很久了~
有点意思啊呵呵
哈哈很不错
弱弱地问一句….：我看懂了怎样证明它是NPC问题的…可是证明了它是NPC问题，为什么最后又可以得到它是一个NP hard问题呢？
回47楼：
NP hard是证明NP Complete的一个小步骤。
打个比方吧，要证明第一问题A是NP Complete的话，必须证明：
1. A∈NP
2. 所有NP Complete问题都能在P时间内转换成A
第二步就是关于NP-hard的证明。
所以，一般来说，NP-hard和NP Complete区别不是很大。是NP-hard的话，很多情况下都是NP-complete（但并不是所有情况下都是这样）。反过来，是NP-complete的话，一定是NP-hard。
@43楼：如果不走汉密尔顿回路，会走到之前采过的矿区，一旦进去就再也无法出来了。
@47楼：NPC是NP-Hard的子集，所以一定是NP-Hard
@18楼：只要能够造出一种情况是NPC的，整个问题就是NPC的，哪怕其他情况都是P的
如果这也可以证明的话，那么人的一生不也是可以证明了
挺好的~
有bug啊，怎样解救农民啊？每条路上都有玩家 B 的防御塔，保证一个农民走过去必死无疑，怎样两个农民一起过啊？可以用图来证明吗？不要只是文字啊，看得很吃力啊~
有bug啊，怎样解救农民啊？每条路上都有玩家 B 的防御塔，保证一个农民走过去必死无疑，怎样两个农民一起过啊？可以用图来证明吗？不要只是文字啊，看得很吃力啊~~~~
出来打酱油的
楼上说的矿数和解救农民难度都不是问题，这些可以通过设置地图触发来解决。不错，等考完试就做一张地图出来。