/22/ StarCraft Offtopic - Juegos edition

#32 El de tastosis llego a 40k y el coreano a mas de 60k, tambien puede ser que el primer grupo del torneo fuera en el que estaba flash y la gente queria verle volver a jugar en algo donde no fuera trash.

PD: Avilo online

I think everytime that I do well at a tournament—I won twice now—both times I felt pretty bad at the start, but only in one match-up. Like, for the GPL that I won, my PvT was really, really bad—my worst match-up by far. And I just didn’t hit any Terrans.

At HomeStory my PvP was really, really bad, and I should have lost on the first day to GungFuBanda. But, once I got past him, I didn’t get any more PvPs and I won. So I guess the secret to winning tournaments is just having two good match-ups and praying that your bracket is lucky.

http://www.teamliquid.net/forum/starcraft-2/511773-harstem-interviewed-at-community-summit-i-make-more-money-but-im-worse

Lo veo y lo subo a El secreto es ser bueno en el matchup vs Zerg y dejar que los winrates hagan el resto

#33 Está forzándose a no ragear y soltar un cumplido cada game y antes le han hecho un 16pool y casi explota.

que asco de verano, esto de haber perdido la pasión por los videojuegos+estar de vacaciones es deprimente y encima en reset de tolerancia de maria

por un momento pensé en jugar de nuevo al sc2 pero luego vi que protoss daba penasco y se me pasó

alguna serie decente?

#45 Yo me estoy viendo outcast y es el sida.

#46 Es worth la de Mr robot vi la sipnosis y me dio un pelin de ebola.

#52 creíamos que avilo era el tier más bajo existente de retrasadez terran pero eso eran sus viewers todo este tiempo

#39

Abstract

The computational complexity of several gameplay mechanics crucial to the Protoss race is studied. Playing Protoss is determined to be NP-hard. Consequently, assuming P ≠ NP, playing Protoss optimally may require exponential amounts of thinking.

Complexity of pylon placement

Ever since Legacy of the Void, placing pylons optimally is more important than ever. While it was already hard in previous expansions due to needing to power buildings, the new expansion makes pylons an important form of defense. In fact, certain units, such as the liberator, are impossible to be destroyed using ground units, and necessitate the use of pylons to provide defense.

Claim 1: Given a finite set of buildings (assumed to be 2D points), a finite set of 2D points where enemies may attack (such as locations for liberators to siege up behind your mineral line), the problem of placing the minimum number of pylons to cover these vital spots is NP-hard.

Proof: The problem is equivalent to the minimum unit disk cover problem, a special case of the geometric set cover problem. This is well-known to be NP-hard [1] [2].

Notes: If you are willing to make over 4 times as many pylons as is optimal, you can solve it in O(n log n) [2]. Bear in mind though, this is spending over 300 extra minerals per pylon. Think how late your expansions will be due to this wanton expenditure of minerals.

Complexity of casting psionic storm and disruptor balls

Casting area-of-effect spells such as psionic storm and shooting disruptor balls is essential to defeating masses of enemy units, as the units of other races are more cost efficient than Protoss ones. However, as our energy/charges is limited, we can only cast a finite number of spells, whilst endless hordes of marines and zerglings approach. We must destroy the maximum number of enemy units using our fixed number of psionic storms/disruptor balls.

Claim 2: Given a set of enemy units, which we shall assume to be 2D points, hitting the maximum amount of units with a fixed number k of unit disks is NP-hard.

Proof: This problem is closely related to the minimum unit disk cover problem. We show it is as hard as minimum unit disk cover by reduction: If there exists a solution to solve the psionic storm problem, then we can simply binary search on k to solve the minimum unit disk cover problem. Therefore the psionic storm problem is also NP-hard.

Complexity of walling off

Constructing a wall out of buildings is essential to defending against attacks from zerglings, hellions, and even ultralisks.

Claim 3: Given a ramp of integer width y, and given a multiset of buildings of width x1, x2, ..., xm, determining whether it is possible to wall off the ramp leaving a gap of exactly one is NP-hard.

Proof: This is simply the subset sum problem where we wish to find a subset of the m buildings whose width sum up to y-1. This is well-known to be NP-hard [3].

Notes: As we see, even determining the existence of a possible wall is difficult. That said, this particular instance is efficiently solvable in pseudopolynomial time using dynamic programming as the number of distinct building widths is small.

Complexity of destroying overlords using a Void Ray

Unlike other races whose supply buildings are firmly placed on the ground, the Zerg overlord has the overpowered ability of being able to fly, thereby providing free scouting. Moreover, they have the ability to morph into overseers or ventral sacs, making them extremely dangerous. We must deal with this using a void ray. Unfortunately, as Flux Vanes have been removed from the game, void rays are very slow, so we must optimize the void ray's route.

Claim 4: Given a set of enemy overlords, which we shall assume to be 2D points, determining the best order to destroy them using a void ray is NP-hard.

Proof: This is simply the travelling salesman problem, which is well-known to be NP-hard since the Hamiltonian cycle problem is NP-hard [3].

Notes: The problem becomes even harder if you take into account the optimal time to activate the prismatic alignment ability. This is left as an exercise to the reader.

Complexity of A-moving

A-moving may seem like a trivial problem to many Starcraft players, but it is in fact the difficult problem of multi-agent planning. Starcraft I players will understand that Protoss units, such as the Dragoon, are inherently more difficult for path planning compared to the units of other races. In Starcraft II, this problem is exacerbated by the fact that Protoss units tend to be clumped up as a deathball, introducing additional computational complexity.

Claim 5: Given a deathball of n units, each with a start position and a desired end position, finding optimal routes from each start position to an end position such that they are conflict-free in space and time is NP-hard.

Proof: By reduction to multi-agent planning on a graph, well-known to be NP-hard [4].

Notes: All races suffer from this problem. But Terrans are less affected, as a Terran player has sufficient APM to split his marines such that collisions are unlikely, allowing the use of efficient heuristic algorithms in practice. Moreover, as Zerg gameplay revolves around amassing Mutalisks, which do not collide, path planning is trivial.

Complexity of playing Protoss

Theorem 1: Playing Protoss is NP-hard.

Proof: From above Claims.

Notes: If you manage to play Protoss efficiently, you may have solved the P = NP problem. In this case, you can collect your one million dollars from the Millennium Prize as well as get rich by defeating encryption algorithms used by financial institutions.

References

• [1] Das, G. K., Fraser, R., López-Ortiz, A., & Nickerson, B. G. (2011, February). On the discrete unit disk cover problem. In International Workshop on Algorithms and Computation (pp. 146-157). Springer Berlin Heidelberg.
• [2] Liu, P., & Lu, D. (2014). A fast 25/6-approximation for the minimum unit disk cover problem. arXiv preprint arXiv:1406.3838.
• [3] Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations (pp. 85-103). springer US.
• [4] Papadimitriou, C. H., Raghavan, P., Sudan, M., & Tamaki, H. (1994, November). Motion planning on a graph. In Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on (pp. 511-520). IEEE.

https://www.reddit.com/r/starcraft/comments/4tdw9g/why_protoss_is_hard/