Starcraft 2 : The Dune II Clone

[yurell]

Played 4v4 today. Placed into diamond and am now rank one and beating master league payers. Last one raged so hard it was satisfying (I'm barely gold 1v1 SEA, but who'd have thought co-ordination and teamwork matters more in a team game than individual skill?).

[SirBryghtside]

New game announced!

[Diadem]

Awesome.

[BlackSails]

New game announced!

Multiple endings, each influenced by your choices and color-coded for your convenience! (Further epic endings planned for post release as downloadable content.)

Trolol

[phlip]

WTB: Command line utility that takes a replay, and generates a video of the file. Ideally non-interactive.

That would be pretty awesome. Unfortunately, given the replay file is (as I understand it) pretty slim with the details, such a program would have to either (a) break open and hijack the SC2 engine, or (b) reproduce it entirely. Not a small project.

However, I wonder if it would be possible to make a map file that was identical to a stock map, except it has scripts running to export all the unit movements to file. And then convince SC2 to use that map instead of the real one when you load the replay. That would at least get you something you could work with to make a video, though it most certainly wouldn't be non-interactive.

[Diadem]

You could just run SC2 in the background and record it.

The problem is, what are you going to record? The entire map? That will make the video ridiculously huge, or of a prohibitively low resolution. Just the main base of player 1? That's not very interesting to look at. Or are you going to write an AI that can focus on the interesting parts of the replay?

[Jesse]

Or are you going to write an AI that can focus on the interesting parts of the replay?

They already did that, we're called 'casters'.

[Xeio]

Or are you going to write an AI that can focus on the interesting parts of the replay?

The PeepMode maps already have something like that actually. The camera can move to combat/construction automatically. It's ok at it, though I haven't used it enough to really make a judgement.

The problem is, all of that is built in the existing map editor, trying to do it in a replay would be a lot more difficult.

[mike-l]

It wouldn't be completely terrible just to follow player 1's camera.

[Yakk]

Really, the vast majority of the map is going to be nearly completely static. Away from the conflict, only animals are seriously moving -- and if you restrict yourself to the view of the players, you just have some looping animations in the fog of war.

If you made a video of the entire map at screen resolution, it shouldn't cost much more than recording player1's view. A smart encoder might spend more bits at higher quality at player1s and 2s view.

[Xeio]

If you made a video of the entire map at screen resolution, it shouldn't cost much more than recording player1's view. A smart encoder might spend more bits at higher quality at player1s and 2s view.

I think you underestimate show shitty it would be to watch the entire map at 1080p (or probably even double or triple that), even if the encoding size is reasonable.

Hey look, that blue blob is moving! Oh, it hit the red blob and now they're both smaller...

[Yakk]

1080p? Bah, no. Full resolution of the map!

Sure, we'd need a playback engine that can handle zooming into various parts of the video stream...

Yes, this is getting less and less practical.

[Xeio]

Sure, we'd need a playback engine that can handle zooming into various parts of the video stream...

You mean... hrmmm ... like a game engine?

[Koa]

Game Theory: SC2 is impossible to balance. Article I wrote on TL.

[Yakk]

Ya. Well that was a lot of words to describe how you are wrong. And using the name of a branch of mathematics to make it seem less like an opinion piece and somehow definitive....

There is nothing fundamental about asymmetric games that prevents balance.

Np hard does not mean insolvable. It actually means expensive to solve and easy to verify a solution. Well the expensive part is assumed and unproven[1].

It is not that you are wrong in your conclusions, but rather nothing you say is a valid and sound argument for said conclusions. If you framed it as an opinion piece, go for it. Framing it as a game theoretical statement, and misusing theoretical CS statements makes it without foundation.

Possibly you redeem yourself near the end. I stopped reading around the picture of three player chessmen. Anyone who finished care to let me know if it got better?

Probably I am being to harsh.

(edit: Spelling fixes.)
[1] Strongly assumed, with lots of justification, but nobody has shown that NP-hard problems aren't easy to solve. But it would be highly surprising if you did find a way to solve an NP-hard easily. Slightly less surprising than discovering a way to travel faster than light using elastic bands and coffee filters, but pretty surprising.

[Will]

Probably I am being to harsh.

No, you're pretty much spot on.
There's a good message in there, Koa, one I happen to agree with. Most of the time when people bitch about "balance" what they really mean is "I lost to this strategy." But your argument is complete nonsense, couched in terms you clearly don't understand.

I don't want to discourage you, here. Analyzing games on a mathematical level is a fine and noble goal. I suggest you spend more time reading up on game theory (as well as complexity classes and what it means for a problem to be undecidable); learning more about these mathematical tools will undoubtably give you deeper insights about SC2 as well.

[Koa]

I said in the thread that when I was speaking on "game theory" that I wasn't intending it to mean the specific science of the same name. I thought it fitting to describe where I was coming from, but probably a mistake for those who are more aware of the science. Otherwise none of it was opinion and is largely mathematical thought. You'd have to explain to me specifically how I am wrong. I never suggested that np-hard meant unsolvable. If anything I completely sidestepped talking about it at all, as it was irrelevant to the point I was making.

[mike-l]

There was no math in there at all... You assert without proof that the only way a game can be balanced is if it's symmetric or we trade spots. And of course, it's without proof because it's wrong. If you change roulette to be a push on 0/00 then it's a perfectly balanced asymmetric game. SC2 could be balanced if, for example, Z can always kill T if the game goes to 20 minutes, T can kill Z in 2 ways before 20 minutes, but not if Z prepares perfectly for either attack. As long as the branching point is at a point where scouting cannot occur, then TvZ is perfectly balanced, as either side can guess 50/50 and guarantee a 50/50 outcome.

And you said 'Is SC2 NP-complete or is it solvable', which is what Yakk was pointing out as a false dichotomy.

[Koa]

Mathematical thought expressed in words and not numbers. I did use experience in the beginning but my conclusion was not based upon opinion in any sense.

[mike-l]

I didn't mean there were no numbers. I meant there was no mathematics. It's just unsupported gibberish.

[Koa]

Hm, then I did not articulate it well enough. It is a complicated idea. Very difficult to express. Some people have gotten my point though, and are arguing on my behalf in the thread. Others already know it to be true, and thus don't need my article to explain it.

[mike-l]

True balance is a state of a game where two players have an equal chance to win, and where their skill/ability is the only factor for determining who is victorious. This can only be accomplished in two ways. One, that both players have equal or acceptably equal tools to accomplish victory (examples are everything from chess to MMA). Two, that the tools switch hands between the players in a sort of best of three format. Since neither occurs in SC2 outside of mirror matches (which falls under 'mostly equal', or 'acceptably equal'), SC2 can never be truly balanced

This is wrong. Both Yakk and I have said why. Also chess is widely considered to not be balanced, so even your examples are wrong. (as chess is a game of perfect information and no randomness, it's necessarily either imbalanced or a draw)

[Yakk]

Hm, then I did not articulate it well enough. It is a complicated idea. Very difficult to express.

You seem to be discounting the possibility that you are simply wrong. Maybe not in conclusion, but definitely your argument (as written) is simply incorrect.

Why do you believe you aren't wrong? What evidence do you have that you are actually correct? Do you have the mental tools to write out your argument in such a way that you can then check to see if it has errors?

You aren't saying "it could be impossible", you are saying "it is impossible". And if you are pretending to actually be showing something is impossible, then you actually need to have your argument to be much stronger than what you have articulated.

I agree that it could be impossible, and regardless it is ridiculously hard. I don't see a solid argument (coming from you) that you have shown it actually is impossible. And the more technical claims you have made (ie, "balance is only possible in two cases") are just blatantly incorrect.

--

And if your standard of quality of mathematical reasoning is that "there are people on a Starcraft forum who agree with me", then ... well ... um ...

Please read this article:
https://en.wikipedia.org/wiki/Dunning%E ... ger_effect

[Koa]

You seem to be discounting the possibility that you are simply wrong. Maybe not in conclusion, but definitely your argument (as written) is simply incorrect.

It's pretty clear that I didn't write it well enough, or that you didn't give it a chance. Not sure which, but I haven't seen an argument against it other than attacking my personal credibility.

You aren't saying "it could be impossible", you are saying "it is impossible". And if you are pretending to actually be showing something is impossible, then you actually need to have your argument to be much stronger than what you have articulated.

I agree that it could be impossible, and regardless it is ridiculously hard. I don't see a solid argument (coming from you) that you have shown it actually is impossible. And the more technical claims you have made (ie, "balance is only possible in two cases") are just blatantly incorrect.

Fair enough. I could have extended the article to several times its length, but then I don't think anyone would read it, and I'm pretty sure it's already been proven.

And if your standard of quality of mathematical reasoning is that "there are people on a Starcraft forum who agree with me", then ... well ... um ...

Please read this article:
https://en.wikipedia.org/wiki/Dunning%E ... ger_effect

I felt you were using that against my argument, so I leveraged using it to save myself the trouble of having to explain it.

This is wrong. Both Yakk and I have said why. Also chess is widely considered to not be balanced, so even your examples are wrong. (as chess is a game of perfect information and no randomness, it's necessarily either imbalanced or a draw)

I actually explain that... otherwise I don't see why it is wrong. Help me? Otherwise there's nothing to discuss.

[mike-l]

If you change roulette to be a push on 0/00 then it's a perfectly balanced asymmetric game. SC2 could be balanced if, for example, Z can always kill T if the game goes to 20 minutes, T can kill Z in 2 ways before 20 minutes, but not if Z prepares perfectly for either attack. As long as the branching point is at a point where scouting cannot occur, then TvZ is perfectly balanced, as either side can guess 50/50 and guarantee a 50/50 outcome.

Both those situations are asymmetric without side swapping, and both are balanced.

[Koa]

I'm not familiar with roulette unfortunately, but maybe I'll look into that example later. I'll think on the latter example in the meantime. I'm not sure yet.

[mike-l]

I'm not familiar with roulette unfortunately, but maybe I'll look into that example later. I'll think on the latter example in the meantime. I'm not sure yet.

Fine, I flip a coin, you choose. We have different tools, but it's clearly balanced.

[Yakk]

More importantly, when doing mathematical reasoning (and not doing an opinion piece) your goal is to show how and why you are right. Not to be sufficiently vague that others have to work to show how you are wrong. You made a claim about asymmetry. You should have either a proof in mind or the like at the very least...

[Diadem]

Also chess is widely considered to not be balanced

By whom? Chess is almost perfectly balanced (white scores somewhere around 52%).

I mean what do you mean when you say a game is balanced?? If only perfect balance is good enough then no, chess is not balanced. But that's to be an unnecessary strict criterion. There are three ways I can win a game. Luck, skill, or imbalance. I'd say a game is balanced if in the overwhelming majority of games the winner is not determined by the latter factor. This is certainly true for chess, and probably also for starcraft II.

The tricky part about balance is that it can depend on skill level. Blizzard's job is to make a game that is balanced for both amateurs and pros. But not just that, it has to be fun to play as well, and fun to watch. And, people often forget this, the races need internal balance, in that several strategies are viable and no single strategy or unit dominates gameplay for that race. Not an easy job. But I'd say Blizzard is doing a pretty good job so far.

Of course the balance that starcraft II has is a dynamic one. People figure and new strategies, and blizzard changes the game in response to keep things balanced. I'm fine with that.

[yurell]

By whom? Chess is almost perfectly balanced (white scores somewhere around 52%).

White scores 52%? I presume of wins (not 52% white wins, n% draw, (48-n)% black wins), but even still a 4% difference is huge, especially for high ELO. It's not nice to know you've an inbuilt 4% disadvantage going into the finals.

[mike-l]

Well, most modern estimates are more like 54-56, which is rather imbalanced considering that 1/3rd of games are drawn. In non drawn games it's more like 60/40 which is definitely imbalanced.

[BlackSails]

Balancing a game is very clearly not in NP. If I hand you a game and claim that it is balanced, this is not an easy statement to verify.

[Koa]

I understand now. I didn't provide the mathematical reasoning that I used to determine it was true as it is exceptionally complicated for the case of SC2, and therefore my conclusion can only be seen as opinion. I only provided a few outlying examples of unsolvable problems, but that is no where near a proof to a claim of impossibility. I do believe that my conclusion is mathematically correct, and that I could find papers that prove it on a more fundamental level, but the arguments that I used are unsubstantiated. I suppose my goal was not to prove that it was impossible, but to get people to think about the problems that I presented and to start them along the path that I took to understanding it. But I threw the answer in their face without much reasoning towards the process of making it, making it kind of worthless in some regards.

Also, your example can be reduced into two coinflips (or maybe more?), which is either imbalanced or symmetric depending on how you interpret it. It can be interpreted different ways which confused me initially.

[Diadem]

By whom? Chess is almost perfectly balanced (white scores somewhere around 52%).

White scores 52%? I presume of wins (not 52% white wins, n% draw, (48-n)% black wins), but even still a 4% difference is huge, especially for high ELO.

No, not wins, scores. If I had meant wins I would have said wins.

Well, most modern estimates are more like 54-56, which is rather imbalanced considering that 1/3rd of games are drawn. In non drawn games it's more like 60/40 which is definitely imbalanced.

The exact percentage depends on time controls, playing level and era the game is from. But fair enough, 52% seems to be the low end of the range, so let's take 55%. That's still pretty even. You can ignore draws, but that's not really a fair way of looking at it. Draws exist, they are part of the game, and can be one of the strategic aims of one of the players.

Anyway, a 55% score really is not much. It translates to an elo rating advantage of about 30 points. Most people's rating fluctuate much more than that over the course of a year. It's really not a big advantage. In fact there are quite a few players who prefer the black pieces.

It's not nice to know you've an inbuilt 4% disadvantage going into the finals.

Ah but chess never works like that.

There are three main ways to play competitive chess. Tournaments, team games and matches. In tournaments you switch colours each round. It's impossible to keep perfect color balance for every player, but in an 8 round tournament you will always have black at least 3 times and white at least 3 times. Most longer tournaments have an odd number of rounds, so the colour balance is always plus or minus one. For team games the colours alternate for each board, so each team will have white and black an equal number of times.

And at the highest level, chess is played in matches. This is how the world championship is (or used to be, they've been fucking around with the system in recent years alas) determined. A multi-game match between players. Each player gets white and black an equal number of times.

So in any individual chess game the advantage is already pretty small, but overall it generally balances out completely.

[mike-l]

The fact that things are done to balance out who plays white is proof that it's considered imbalanced.

Anyway, this is all very off topic. I was just pointing out that the same tools don't guarantee an even game, as other things like asymmetric knowledge and priority can bring imbalance.


Koa, by that logic, SC2 in general can be reduced to a large number of coin flips, so everyone has the same tools.

[Will]

So in any individual chess game the advantage is already pretty small, but overall it generally balances out completely.

If you think a 10% advantage is "pretty small" I hope nobody ever gives you a job balancing competitive games.

[Yakk]

Balancing a game is very clearly not in NP. If I hand you a game and claim that it is balanced, this is not an easy statement to verify.

Balancing some games is quite clearly in NP. All games? I would say that there is at least one game where determining if it is balanced is outside of NP, but I don't have one in mind. SC2-like games? I do not know. But NP is a pretty big class.

The verification step of an NP problem is cheap and easy verification with the proof that the answer is right.

If something isn't in NP, it in effect says that even if you had a proof of the answer, the proof would be too long to practically verify. More accurately, as the free parameters in the problem description grow, the length of the proof required to show that your answer is right grows ridiculously fast in the size of the problem description.

(These proofs are called "certificates", but I find thinking of them as "proofs that the answer is right" generates a more correct impression asto how huge the set of NP problems really has to be.)

As mentioned previously, it has been shown that an arbitrary SC2 map state can be NP-hard to determine who wins (or if it is a draw). The proof of this involved a quite convoluted map set up (a bunch of harvesters blocked behind mineral patches, cannons guarding the paths between resource collecting nodes, a land-locked enemy, and just enough surplus resources to just barely defeat the land-locked enemy -- in which the win or draw question of SC2 was reduced to finding a planar Hamiltonian path.)

(As an example: EXPSPACE complete problems are known to be outside of NP. Regular expression with squaring (squaring operator is "two copies of whatever is matched") equivalence is EXPSPACE complete -- proving that two generic RE-with-squaring expressions are equivalent requires a "proof" whose length grows exponentially in the length of the two expressions, and that proof is (as far as we know) not easy to verify (if it was trivial to verify, we'd know that EXPSPACE = EXPEXPTIME, which I don't believe we know).)

[mike-l]

Another note. If we put a finite limit on game length, something outrageous like 100 years, then there are only finitely many possible actions each player can do, and only finitely many things a player can see over the course of the game, so there are only finitely many strategies (of course this number is absolutely huge). So I could make the gigantic payoff matrix of every strategy for one race vs every strategy of another race, and find the nash equilibrium of this game. There's no reason the value of the game at that equilibrium can't be 0.5 (though it's pretty unlikely it would be exactly this). I could restrict strategies to limit APM, or limit subsequent actions in a more advanced way (eg you can click faster in a small area than alternating between minimap and battlefield clicks), and then find the nash equilibrium of that.

Computationally this is completely infeasible, but the fact remains that there is a theoretically accurate measure of how balanced a game is, and it's certainly possible for a game to be balanced no matter how varied the strategies of each player is.

Making a game asymmetric certainly makes things harder to balance, in that perfectly symmetric games are automatically balanced, but it certainly doesn't make it impossible.

[EvanED]

So in any individual chess game the advantage is already pretty small, but overall it generally balances out completely.

If you think a 10% advantage is "pretty small" I hope nobody ever gives you a job balancing competitive games.

After all, you wouldn't want to publish a game that's as much of a bomb as chess has been.

(OK, that's not particularly fair. But there's at least a small truth in my sarcasm I feel.)

[Koa]

Koa, by that logic, SC2 in general can be reduced to a large number of coin flips, so everyone has the same tools.

Technically yes, but a great deal of them that interact asymmetrically thus different tools and imbalance. The only asymmetry provided in your example is flavour text, or it's not a 50/50 expected outcome depending on interpretation.