RTS Balancing - Proven to be NP hard (or even solvable)?

[W3bbo]

With Generals 2's recent announcement, I was engaged in a discussion about how houses / factions in games have steadily grown more heterogeneous.

Consider Warcraft 1 - both sides were essentially identical, the differences mainly being cosmetic. When Command and Conquer came out the factions were still largely symmetrical but with balance achieved with the simple "cheap and light vs. expensive and heavy" formula (i.e. GDI's Mammoth Tanks vs. Nod Light spam) - but then the original CNC wasn't much of a multiplayer or skirmish game so the point is moot for that game in particular.

The last two games in the Earth franchise (Earth 2150 and 2160) all feature radically different sides with respect to resource harvesting and construction though their armies still follow the predictable rock, paper, scissors formula for balancing though E2150 is rather unbalanced in real-life multiplayer thanks to ED's nuclear weapons.

I digress - I now point to Starcraft - I remember the game was very unbalanced when it first came out in the 1990s ("zerg rush, kekekeke") but it was only through trial-and-error and constant patches do we have the balanced game we have today - with three factions with different play styles.

Back to my conversation - we were wondering if any system for balancing an RTS game's factions is NP-hard, or if it is truly solvable at all (as factors such as map layout must also be considered).

Starting with the basic case where all factions in a game share identical user-interfaces, construction methods and resource harvesting methods:

Let's propose a faction can be modelled as a set of vectors, each vector representing a class of unit, and each member of the vector represents a given parameter of that unit (i.e. unit speed, cost, HP, armor, weapon damage, weapon reload time).

Given a set of constraints on these members (e.g. Faction X's units must all have greater HP and cost than Faction Y), does there exist an algorithm which ensures no faction has any inherent advantage over another? And if so, can it be solved in polynomial time? Is it possible to solve it without resorting to a brute-force of every battle scenario?

[Orca]

Given a set of constraints on these members (e.g. Faction X's units must all have greater HP and cost than Faction Y), does there exist an algorithm which ensures no faction has any inherent advantage over another? And if so, can it be solved in polynomial time? Is it possible to solve it without resorting to a brute-force of every battle scenario?

IMO from the technical work I've done on game testing and coding (Which isn't great but I'm not pulling stuff from my ass either) it is possible to balance such games. The problem isn't that you need an algorithm to do so, the faction design and game mechanics are the heart of the problem. Having a straight 1:1 correlation for faction weaknesses/strengths only provides a simple game with simple balances. To get a complex and balanced game is tough, but not impossible. Galactic Civ II wasn't an RTS, it was turn based, but it achieved a great balance between 9 different unique factions with its game mechanics. The key to this was the fact that while every civ had its weaknesses, none were horribly crippled or overpowered, so it was a race of the mainly average with slight specializations. I think a lot of games today over emphasize strengths and weaknesses so it becomes very easy to imbalance the game. I'm tired, but thats my thoughts

[Derek]

To algorithmically balance a game, I think you would first have to be able to solve the game. From that you can determine which faction has an advantage, and then find some way to adjust accordingly. But most RTSs are do not have perfect information, so it can only be solved in a probabilistic sense. It is theoretically possible though, and would be NP-Complete (for most games). The tweaking phase would make all this take exponentially longer, but can still be solved (there are only a countable number of possible balance variations). Obviously you would pick a single map for this purpose (and for any different maps you would have to re-run the algorithm).

Of course, there are several problems with this in practice (besides being ridiculously expensive). We don't actually need perfect balance, only "good enough", and we don't actually want to balance around perfect play, but around realistic human play (typically high levels of play, but more ambitious designers may want balance at all levels of play).

[Surg]

It is theoretically possible though, and would be NP-Complete (for most games).

What would be the polynomial sized certificate for a balanced game?

[Game_boy]

Starcraft (and SC2) is so asymmetric between the races that you can't balance it with a computer. It's also the only game the developers have seriously committed to balancing over the long term (~10 years for SC1 and SC2 each likely) for competitive play ($100,000 on a match kind of risk).

The main problem is of metagame. One strategy might be strong today because players are approaching the game in a certain way, so it might need to be fixed via patch OR wait for players of the weaker race to figure out what to do against it. This happened all the time in the Korean SC1 scene.

It's also impossible to balance for every skill level. A low-level player might only be able to do a certain number of actions in a time, or have certain awarenesses and timings. It's no use if the only counter to a unit is one that has to be microed (babysat) through every shot consuming all of a players' time to do so, yet this would be fine to a naive algorithm that only balances for perfect play. Blizzard balances for the Korean competitive scene and basically hopes that low-level players see the same balance, and that one particular player doesn't have insane skill to take advantage of a high-maintenence trick. Essentially competitive balance relies on human imperfection.

For example if any Korean zerg could micro mutalisks like this:

http://www.youtube.com/watch?v=AeTNFk6XdHk

The game would immediately be hugely unbalanced towards zerg.

[Derek]

It is theoretically possible though, and would be NP-Complete (for most games).

What would be the polynomial sized certificate for a balanced game?

Presumably the optimal strategy for the game? I don't actually know for sure, but I'm pretty sure solving finding the optimal strategy for imperfect information games is NP-Complete. Feel free to prove me wrong. It's definitely solvable though.

[EvanED]

I disagree it's even a well-defined question; for many reasons such as the ones game_boy alluded to.

For instance, suppose that your game covers the epic battles of Snorks vs the Blubs. For simplicity's sake, say each side only has one kind of unit, with equal cost and production abilities. As it happens, Snorks will reliably beat Bulbs one-on-one, but with a catch: they require absolutely intense, perfect micro. Without that micro, Snorks will win every time. (Perhaps Snorks have some kind of homing attack, but with some fancy maneuvers, the Blubs can dodge it.) The crossover point at which win rates are about 50-50 is, say, 300 APM.

Is the game balanced? If not, which side is better?

[W3bbo]

I disagree it's even a well-defined question; for many reasons such as the ones game_boy alluded to.

For instance, suppose that your game covers the epic battles of Snorks vs the Blubs. For simplicity's sake, say each side only has one kind of unit, with equal cost and production abilities. As it happens, Snorks will reliably beat Bulbs one-on-one, but with a catch: they require absolutely intense, perfect micro. Without that micro, Snorks will win every time. (Perhaps Snorks have some kind of homing attack, but with some fancy maneuvers, the Blubs can dodge it.) The crossover point at which win rates are about 50-50 is, say, 300 APM.

You've got a contradiction there: "Snorks will reliably beat Bulbs one-on-one, but with a catch: they require absolutely intense, perfect micro. Without that micro, Snorks will win every time. "

I assume you mean that Snorks can win, and will reliably win, with ubermicro - therefore Blubs win if the Snorks have an unskilled player.

Is the game balanced?

Evidently not - as a player's fate depends on both their micromanagement skill and the faction they select (presumably the Blubs do not benefit from having a micromanaging player).

Surely a balanced RTS game would reduce a player's victory to a function of both the player's level of micromanagement as well as their ability to strategize on a macro scale - the player's arsenal selection should be irrelevant. (This does not preclude different factions having different playstyles - I'm not expecting someone who exclusively plays one faction to have an immediate knack with another).

If not, which side is better?

The Snarks faction is clearly better-defined, the Blubs faction is too simplistic. The designers just need to flesh-out the Blubs so that greater micromanagement results in a greater pay-off.

I note that my entire argument is based on the premise that micromanagement is integral to RTS play. Surely a "perfect player" would also do perfect micromanagement?

(As an aside, has anyone developed a variation on chess where both players make a move in the same turn/time quanta as the other player? I suppose that could be considered an RTS game, just with a very low temporal resolution).

Ninja-edit OT: I see someone has designed a kind-of similar Chess game, Kung-Fu Chess, but it's not quite as similar and is currently offline.

Ninja-edit 2: This paper, released a few days ago, is almost relevant to this thread: http://arxiv.org/pdf/1201.4995v1.pdf although it is more concerned with the complexity of play rather than balancing - there is a paragraph on Starcraft near the end.

[DrZiro]

The problem does seem altogether a little fuzzy to be thought of in this way. Any realistic simulation would have to include probabilities, both because the game is likely not deterministic, and because the mistakes of the players are random. Then the situation would most surely soon become chaotic, so we have to use some sort of statistical methods.

It would be a different matter if we were looking at turn based games, like Civilization or Battle for Wesnoth. There we have at least some chance to get a grip on the problem.

As for P or NP, I'm not even sure what your n is. Polynomial in what variable?

[Game_boy]

Ninja-edit 2: This paper, released a few days ago, is almost relevant to this thread: http://arxiv.org/pdf/1201.4995v1.pdf although it is more concerned with the complexity of play rather than balancing - there is a paragraph on Starcraft near the end.

That is the most contrived argument I have ever seen. That or anything close never happens in an actual game of Starcraft.

[DrZiro]

Haha, yeah, that is a really strange example.

[freakish777]

Some things in your question need to be better defined before answers can even be reasoned about.

Non Trivial questions:

What is our definition of Balanced?

First we define Optimal Player: "A player who, given a Set of choices A, always chooses choice A[n] from A that yields the highest probability chance to win, given the information presented to them." (their strategy is flawless, and they don't make math mistakes, you can expand this definition as you see fit to include "Executes flawlessly" for games the involve motor skill, so a Billiards/Pool player who sees the best possible shot, and always makes it, leaving the Cue ball exactly where they want, or an RTS player sees the optimal lines of play, makes their decisions in 0 seconds, and executes their decisions flawlessly).

Next we define Fair Match: "An even number of games (2, 4, 6, 8 ) in which players alternate starting positions/circumstances." (Player A starts game 1 as White in Chess and game 2 Player B does. Player A starts on the "easier to win side of the map" in Game 1 and Player B does in game 2. Etc)

My assumption is that we define a Balanced Game as one in which "an Optimal Player wins a Fair Match ((X/2) + 50)% of the time (or greater) against the average player, and 50% of the time (or greater) against another Optimal Player, where the Game is X% skill, and 100-X% luck."

So the Optimal player wins 100% of the time in chess against an average opponent, and 50% of the time in coin flips (or greater). Note that the definition of "Worst Player" doesn't help us, because the worst player would lose to opponents that did nothing (all games give the option to concede to the opponent, the "Worst Player" concedes on the spot in every game).

Note that the or greater is due to the fact that while "Bluffing", "Reading An Opponent", "Metagaming" and the like are definitely skills that help you win, they are not including in the definition of Optimal Player (so Optimal Player A may win X% and Optimal Player B who metagames and knows how to bluff and read opponents wins greater than X%). Also note that Optimal Player only pertains to in game actions/etc, and assume that games are time (so they will never go "Forget this, it's 4am, I need sleep, I give up.").

(Theoretically an Optimal Player who joined a "Coin Flip Betting Competition" that paid out after individual match wins, could leave the competition after a winning streak, quitting while they're ahead, the same way an optimal player of the "The Credit Card Game" stops after a couple of free meals).









Tangent on definitions aside, creating a Balanced Game without brute forcing would depend entirely on how good your heuristic is.

Say Factions A, B and C have 4 vector spaces: Resource Harvesting Time vs Amount, Building Build Time vs. Building Cost, Unit Build Time vs. Unit Cost, Unit Cost vs. Unit "Utility"

In Chess, a simple Heuristic such as: Pawns are worth 1, Knights and Bishops 3, Rooks 5, Queens 9, and Kings 10,000, will play a pretty good game if it can look 6 full moves ahead (in a reasonable amount of time). This heuristic doesn't account for positional play at all, but looking 6 moves ahead, it would beat most novices.

RTS's being more complex (in most RTS's pieces don't actually get "Added to the Board" they get "Harvested and Transformed From their Initial Resource State"), your heuristic would want to be based mostly around Resource Conversion and the ability to do so (the goal of war isn't to destroy your opponent, it is to destroy your opponent's ability to make war).

Is trading your Unit that cost you W resources and X minutes to build with their Unit that cost them Y resources and Z minutes give you an advantage or disadvantage? How big of one. Is the time and resources more important, or the capabilities of the units in question?

You could optimize your heuristics with genetic algorithms (presumably you have multiple AIs for each faction, each trying to find optimal strategies, as AIs dip below a certain win percentage after a certain number of epochs, the Heuristic that that AI was using is removed from the "gene" pool).

Note that this method makes no guarantees to deliver a Balanced Game. Only a best guess. Keep in mind that in the real world, perfection does not make you money. Shipping a "good enough" product on time does. On the theoretical side though, you have 2 areas to optimize (for your heuristic), Macro and Micro.

On the Macro side your inputs are going to be the Vector Spaces that differentiate your Factions and the Conversion Costs associated with Units and Buildings. How quickly can Faction F get to State S (Buildings B1, B2 are built, with 10 of Unit1 and 3 of Unit2 built)? What are the branches of play, and how quickly can a player ramp to these different states (it would seem obvious that a heuristic that placed value on not scouting with workers, and value on placing buildings closer to where the worker is currently located would produce the fastest results). What's the right mix of resources? 70% Resource A and 30% resource B?

On the Micro side, you're taking these potential states, and running units into each other (making your AI learn to avoid certain units and attack specific buildings or units, or to only engage when it has some type of temporal or spatial advantage, think "enemy is reloading for 10 seconds, move in now" or "ambush from behind these trees that they don't have line of site on"). It's important to note here that giving one of your AIs an unfair advantage is actually very helpful in learning how important that advantage actually is. Did one AI have a complete view, while the other played shrouded and had to scout to see anything? Did the advantaged AI win 70% of the time? Looks like you now know how to change the value your heuristic places on scouting and how to cost your sensor sweep after this iteration. Your heuristics will also need to be flexible and change values based on what Faction the opponent is playing (suddenly this unit isn't so good, so I won't make any), and when in the game it is (we're 20 minutes in, this small unit isn't worth making anymore).


So, each Epoch/Iteration of your Heuristics could be broken into 2 parts, the part where one AI gets an unfair advantage, both playing with the same heuristic (an extra building, an extra unit, perfect info, faster units, etc) and the part where neither gets and unfair advantage (where you pit two different heuristics against each other).

Results are stored, and updates get made to heuristics at the end of each iteration. Essentially instead of trying to brute force each possible scenario in game play, you're trying to reduce the problem set to only certain variable/vector combinations.


EDIT: removed unintentional smilies. added Macro vs. Micro side heuristic discussion

[Game_boy]

@freakish

Yes, but you've solved the wrong problem. Balancing the game for Optimal Players is nothing like balancing for those operating at the limits of human performance - let's say 400 useful apm and a certain eye-speed/gamestate information input rate, even assuming perfect decision making. In my earlier posts I tried to explain how a game that was balanced for Optimal Players is indeed balanced but also worthless.

The other nebulous constraint on balancing is keeping the game fun and hence marketable. The game can be trivially balanced by making only one race playable.

[W3bbo]

The other nebulous constraint on balancing is keeping the game fun and hence marketable. The game can be trivially balanced by making only one race playable.

That's what Warcraft 1 and Starcraft 2 did... just saying

[Game_boy]

The other nebulous constraint on balancing is keeping the game fun and hence marketable. The game can be trivially balanced by making only one race playable.

That's what Warcraft 1 and Starcraft 2 did... just saying

Starcraft 2 is pretty balanced at a competitive level now? Matchups about 50% on Korean and International databases?

[freakish777]

@freakish

Yes, but you've solved the wrong problem. Balancing the game for Optimal Players is nothing like balancing for those operating at the limits of human performance - let's say 400 useful apm and a certain eye-speed/gamestate information input rate, even assuming perfect decision making. In my earlier posts I tried to explain how a game that was balanced for Optimal Players is indeed balanced but also worthless.

The other nebulous constraint on balancing is keeping the game fun and hence marketable. The game can be trivially balanced by making only one race playable.

You do realize it would be beyond trivial to place a limit on the number of actions per second your bot is allowed to make, correct (by placing some sleeps in the code)?

Optimal Player in this case would need to not have the Execution part of the definition (limit it to "the fastest a human can actually move").

Also, OP asked for whether or not there was an algorithm for Balancing Games, and whether such an algorithm could be Polynomial in nature. I think it's possible, but the number of inputs is larger than you'd think (it's not just Unit u1 from Faction f1 has the following Property p1, and Unit u2 from Faction f2 has Property p2. You also need to account for conversion costs to actually make those Units/Buildings/Resources, you can't collect Gas in SC without first Collecting Minerals and spending time to make a building).


Say you had 2 Factions, F1 and F2. All units are capable of dealing damage, even workers. F1 can makes Units F1U1 (worker) and F1U2 (Marine), and Buildings F1B1 (makes workers) and F1B2 (makes marines).

F2 can only make units F2U1 (workers), and cannot make any additional buildings.


Balancing this game is fairly trivial. F2's worker units simply must be able to fight with F1U2 (not necessarily evenly). Also, note that there are many possible values in your vector space that would achieve Balance (in this example, you could make F2's worker be built faster, make it collect resources faster, move faster, and deal less damage than F1U1 and F1U2 and have less hit points, so every game would play as "Make as many guys as possible, then swarm and keep pounding my guys in" it wouldn't necessarily be any fun, but it would be Balanced).



The reason I brought up the Optimal Player is because it's actually necessary in the discussion for what it means for a game to be "Fair" (and who is it fair too). People tend to not have a good grasp on what it means to be fair. They think the Even and Fair are the same thing. They're not. Fair means that the better player wins more often with respect to how much better they are than their opponent. Even means both players have an equal chance of winning (50/50, not necessarily that the game is devoid of skill, but that perhaps there are some things built into the game play to try and even things up, like the power items in Mario Kart that you can't get unless you're in last place).


Even if people aren't capable of flawless strategy, if you have your game balanced by bots (who are limited in their APM to the fastest a human can actually move), you would still want to balance for flawless strategy. Eventually the best players will discover near optimal strategies, and if it's balanced for optimal strategies, it should balanced for near optimal ones as well.



EDIT: the word not needed an e on the end to make it note. Changed the meaning of the sentence to be the opposite of what I wanted to say.

[W3bbo]

The other nebulous constraint on balancing is keeping the game fun and hence marketable. The game can be trivially balanced by making only one race playable.

That's what Warcraft 1 and Starcraft 2 did... just saying

Starcraft 2 is pretty balanced at a competitive level now? Matchups about 50% on Korean and International databases?

The first one, Warcraft 1, was a serious suggestion - as both factions are essentially mirrors of each other.

The StarCraft 2 reference was a joke, however - the single-player campaign is limited to playing the Terrans (not counting the Protoss mini-campaign). I know multiplayer has all three factions, though it is interesting how the MP tech-tree is substantially different to SP.

[Game_boy]

@freakish

A player with limited (low) apm has far less micro options and also sacrifices keeping up macro while microing. Currently pure phoenix (range 4) completely counters pure mutalisk (range 3) but no one is capable of microing hard enough to not lose phoenixes while engaging.

[freakish777]

@freakish

A player with limited (low) apm has far less micro options and also sacrifices keeping up macro while microing. Currently pure phoenix (range 4) completely counters pure mutalisk (range 3) but no one is capable of microing hard enough to not lose phoenixes while engaging.

Who said anything about limiting the apm to be low?

I simply said it could be limited. As in, to ensure the bot isn't capable of apms higher than the best people in real life.

So let's say you have a method called MakeDecisionAndExecute() (which does what you think it does) and executes in 5 milliseconds on average (so our bot currently micros at 200 actions per second).

Code: Select all

void PlayGame()
{
   while (!GameOver)
   {
        MakeDecisionAndExecute();
        Sleep(495); //sleep for 495 millisecond
   }
}


Brings us to 2 actions per second (120 apm). Need 240 apm instead to more realistically simulate the best players? Change the number you're plugging into sleep (from a software engineering perspective, the Sleep line is incorrect, you'd want to read the value from a config file so that code doesn't need to be re-compiled each time you need to tweak).


Seriously. It is beyond trivial to limit the APM your bot can play at (limit != low).

[Game_boy]

I meant low = 300-400. You still can't micro or keep up production near perfectly with that.

And I don't mean mechanically implementing such a bot. The thread is about a CS problem in perfect balance, and I don't think this is possible in a limited-apm system.

[freakish777]

I meant low = 300-400. You still can't micro or keep up production near perfectly with that.

Actual numbers are relevant how?

400 apm = 6.667 actions per second -> Sleep + DecideAndExecute = 142 milliseconds.
600 apm = 10 actions per second -> Sleep + DecideAndExecute = 100 milliseconds.
1200 apm = 20 actions per second -> Sleep + DecideAndExecute = 50 milliseconds.

It's a simple math problem. Find actions per second for the best human players, set Sleep + DecideAndExecute to happen at the same rate as the best human players for your bot.

And I don't mean mechanically implementing such a bot. The thread is about a CS problem in perfect balance

The thread is about balancing a system, from a Computer Science perspective.

How do you propose we go about finding an algorithm to balance this system (or any system for that matter)?

After your algorithm claims to have found a set of solutions, each of which balance the system in question, how do you propose we check to make sure your algorithm did what it was supposed to do? How about by... mechanically implementing some bots...

and I don't think this is possible in a limited-apm system.

Why not?

Balance can be achieved in many ways. We happen to be most interested in Balanced for "the best human players" and also Balanced in such a way as that it is still a fun game. The first part can still be solved with bots, by limiting bots to only be able to carry out a maximum number of actions per second that approximates the fastest human players. The second part isn't a Computer Science question, so it probably doesn't belong in this discussion. This is why you have Dev and Test engineers do all the work for the game until it's fun to play (for non-competitive people) before you do any balancing (storing variables for unit speed, strength, etc, everything in a config file). Balancing at that point involves just altering the values in your config. Then you crash your bots into each other as a sanity check. For Faction F1, Strategy F1S1, each other Faction must possess at least 1 strategy that can beat F1S1, otherwise F1S1 is dominate and you don't have Balance. Adjust Config settings for units instrumental to F1S1 until an acceptable number of opposing strategies foil it.

[Game_boy]

I DO understand computer code and basic maths you know.

[freakish777]

I DO understand computer code and basic maths you know.

Then why do you keep bringing up apm? How is it relevant to the conversation at this point? (you mentioned that we need to ensure that we don't try to balance for computer players who have higher apm than humans, because that wouldn't be balanced for humans, I mentioned that that's really not a big deal, here's how you keep that from happening, you continue to mention apm).

[phlip]

Then why do you keep bringing up apm? How is it relevant to the conversation at this point? (you mentioned that we need to ensure that we don't try to balance for computer players who have higher apm than humans, because that wouldn't be balanced for humans, I mentioned that that's really not a big deal, here's how you keep that from happening, you continue to mention apm).

No, he mentioned Optimal Players as opposed to humans with all their human limits. APM was merely an example.

Take, say, a hypothetical: Player A is able to get 100 resources per minute, without having to do any action. Player B, has a button they have to click regularly - after each click it is disabled for a minute (so clicking it early does nothing, but clicking it late wastes time), and clicking this button gives 101 resources. An Optimal Players analysis would give the advantage to player B, even analysing it with a restricted APM (since it only takes one action each minute). However, with a human in the driving seat, they have to hit this button within 0.6 seconds of it becoming enabled, every single time, on the dot, otherwise they end up worse off. And I think most players would declare this as unbalanced in favour of A. The question of how many resources player B's button should provide every click in order for it to be "fair" is a question that's hard to well-define, let alone be solvable. In practise, the ideal amount of resources to give would vary depending on the skill level of the players - many values would have it be simultaneously such that player A has an advantage among new players, while player B has an advantage among experts. So you'd have to pick a target skill level that you want to be "balanced", whether that's the average player, or the top tier, before the question of how to balance it even has a hope of being defined well enough to be worthy of throwing some maths at. And the choice there depends on the target audience of the game... whether they're going for mass appeal, or a tournament scene, or what have you.

[Game_boy]

Thanks philip. There will be some situations with equal possible outcomes but not equal skill needed to achieve them, and you have to start modelling complex, flawed human input to account for that, to get any meaningful condition of 'balanced'.

[freakish777]

Then why do you keep bringing up apm? How is it relevant to the conversation at this point? (you mentioned that we need to ensure that we don't try to balance for computer players who have higher apm than humans, because that wouldn't be balanced for humans, I mentioned that that's really not a big deal, here's how you keep that from happening, you continue to mention apm).

No, he mentioned Optimal Players as opposed to humans with all their human limits. APM was merely an example.

Take, say, a hypothetical: Player A is able to get 100 resources per minute, without having to do any action. Player B, has a button they have to click regularly - after each click it is disabled for a minute (so clicking it early does nothing, but clicking it late wastes time), and clicking this button gives 101 resources. An Optimal Players analysis would give the advantage to player B, even analysing it with a restricted APM (since it only takes one action each minute). However, with a human in the driving seat, they have to hit this button within 0.6 seconds of it becoming enabled, every single time, on the dot, otherwise they end up worse off. And I think most players would declare this as unbalanced in favour of A. The question of how many resources player B's button should provide every click in order for it to be "fair" is a question that's hard to well-define, let alone be solvable. In practise, the ideal amount of resources to give would vary depending on the skill level of the players - many values would have it be simultaneously such that player A has an advantage among new players, while player B has an advantage among experts. So you'd have to pick a target skill level that you want to be "balanced", whether that's the average player, or the top tier, before the question of how to balance it even has a hope of being defined well enough to be worthy of throwing some maths at. And the choice there depends on the target audience of the game... whether they're going for mass appeal, or a tournament scene, or what have you.

I agree with what you're both saying, Balance can be trivial, it's the "Fun" that we're worried about. Fundamentally I guess I think that most of the "Fun" should come from game play elements that have little to do with Balance (ie, the game can be balanced one way or another and still be fun), and that making adjustments for Balance could be achieved in an algorithmic fashion with Bots (as opposed to "feeling it out"). Also, the original question asked for an algorithmic approach to Balancing a game. I'm fully aware of the possibility that trying to do so could result in an unfun game for Human players (and have actively given ways to try to avoid that). Is there something wrong with the approach I've given from a Computer Science perspective? How am I answering the wrong question (OP is asking the "wrong question" but it's an interesting question to think about, so why decide to not try to answer it)?





Let's expand my definition of Balanced Game from:

"an Optimal Player wins a Fair Match ((X/2) + 50)% of the time (or greater) against the average player, and 50% of the time (or greater) against another Optimal Player, where the Game is X% skill, and 100-X% luck."

To:

"an Optimal Player wins a Fair Match ((X/2) + 50)% of the time (or greater) against the average player, where the Game is X% skill, and 100-X% luck. Players of equal skill level win and lose Fair Matches Y% of the time against each other (Y <= 50, win rate = loss rate), and draw the remainder of the time."

You can always attempt to Balance for a subset of players most appropriate to maximize your profits (or perhaps you want to leave some unbalance in the game because your target audience involves people who like finding unbalanced strategies and abusing them, I would not at all be surprised if Blizzard knows this to be the case). With the original question asked, yes, you would need to Balance for Optimal Players as well. There is no reason the game can't be Balanced for Optimal Players as well as for Best Human Players, Very Good Human Players, Good Human Players, Average Human Players, Bad Human Players, Very Bad Human Players, and Worst Human Players, or however you want to name your skill levels for your game (off topic, note that "Worst Human Player" tries to concede every game as quickly as possible, if concessions aren't allowed, they attempt to destroy their own buildings as quickly as possible).


In the example given (obviously there are things like Chrono Boosts and Mules that are similar to this but not quite the same), regardless of where you place the amount, you'll divide your players into 2 sets. Those capable of leveraging this "ability to click for a benefit" into an advantage over those that cannot. Are all factions capable of doing this? If so, you don't have to worry about balance (it already is). If not, then you could provide Factions that don't do this a competing strategy that divides players into those same two sets and requires the same amount of skill to perform the competing strategy's action (you can also get into giving each faction different strategies that divide players into different sets of 2, say one splits players 50-50, another 40-60, and the last 60-40 and these strategies Rock-Paper-Scissors in some fashion).


Some things to think about.

1 - As far as your heuristic goes, it should place additional costs on actions that don't translate to in game resources in an attempt to deal with things like this. In an apples to oranges example (so not the best), most modern Chess heuristics assign the King a value of 3.5 with regards to position value, where as traditional heuristics placed an arbitrarily large value (and ignored position).

Let's say Unit U[n] in your game costs 100 of resource X, and 20 seconds to build, and some amount of "attention/focus/micro" from the player. We want to translate these into some type of point value that our bot understands as "the more points I have compared to my opponent, the more likely I am to win the game." So 100 resources of X converts to 50 points, and 20 seconds converts to 20 points, and Y "focus" turns into 10 points. Does U[n] then correspond to 80 points? Probably, but it could also correspond to 5 points if we're late in the game and know our opponent is building units that U[n] is highly unfavorable against (ie, your heuristic needs to change what values it's able to assign to different things as the game changes).

The goal is to make, as accurately as possible, your heuristic a reflection of the game. For all players (not just bots). If humans require an out of game resource called "focus," and another called "memory" to play the game, then those need to be resources that your heuristic accounts for (heuristics don't "Find the Optimal Strategy" they attempt to answer what the various costs are and how they associate to each other, its your bots, aided by a genetic algorithm that attempt to find an optimal strategy based off the heuristic it happens to be working with). I see no reason why a game couldn't be Balanced for both Optimal Players and Sub-Optimal Players simultaneously (ie, all skill levels).


2 - Bots can be written to interact with the game the same way people do:

Make them only able to select items they have on screen or hot-keyed.
Make them only able to control items they have selected.
Make them only able to obtain information from units that are selected.
Limit the number of units or groups of units the Bot keeps in memory to "check on" at some low number.
Only allow them to select units to give orders to so quickly, (APM, already covered).
Etc.

In short there's a lot of ways to limit bots to get them to mimic human behavior (the more you implement, the more your bot should behave like a human player). Lots of bots, for the sake of spending less time writing code, interact with games at the Object level in the code and have no understanding of a Screen. They know immediately when and where a unit is taking damage and how much damage, where as human players don't. Essentially, there will always be limitations you can place on your Bot to make it behave more like Best Human Player.

As far as differing skill levels are concerned, you can take some of your bots that learned the wrong strategies, or some of your heuristics that valued things incorrectly (they over-valued unit X, or resource Y, or they built a certain way that wasn't optimal, etc, these bots & heuristics would have been removed from your gene pool before reaching anything that resembled Optimal Player) to achieve Balance for different skill levels (you could also take your heuristic and bot that is close to Best Human Player and place further limitations on it, lower it's APM even more, shrink it's screen to be smaller than a human players so it has tunnel vision, add some randomness when it places a building, or moves a unit, so that it places units and buildings sub-optimally, "close but no cigar" this last one mimics players who know what the right strategy is, but their execution is lacking "Ok I'm going to place my bunker on my ramp... and I misclicked...").

3 - Off topic, this is really a design issue to hash out as well. Does this particular thing/strategy have to ship with the game? Does it make it more fun? Does that added marketability (due to it being more fun) outweigh the benefit of being able to balance it faster (potentially by bots, even without bots, the example given would be difficult to balance for "more skilled players" to leverage to their advantage).

Another thing to consider here is that even if a game is actually perfectly balanced for all skill levels and players (so the best bots beat average bots some percentage of the time proportional to the skill involved in the game, and likewise for best humans beating average humans, and average humans tie with average humans over a large sample size etc), there will always be someone who is discontent with the game, because they think they're better than they actually are (either because they've learned a sub-optimal strategy and are deluded into thinking it approximates optimal, or because their execution isn't all that good and they feel it's unfair that this is more of a reflex based game than a thinking game when really that reality has nothing to do with the definition of fair).

[Game_boy]

Hvaing just added all those caveats to your method, you're no longer saying anything new.

[freakish777]

Hvaing just added all those caveats to your method, you're no longer saying anything new.

Why should I add anything new if there's nothing I see wrong with my method?

Is there something wrong with the approach I've given from a Computer Science perspective?

What exactly is your aversion to real discussion?

[phlip]

In the example given (obviously there are things like Chrono Boosts and Mules that are similar to this but not quite the same)

Yeah, it's SC2 that I was thinking of - specifically, comparing the three races' basic macro spells - Mule, Spawn Larva, and Chrono Boost. With the Mule and Chrono Boost, if you're a bit late with one, or miss one entirely, you can catch up later (within reason, as long as your OC/Nexus doesn't max out on energy)... you can do a mule drop every 80 seconds, or a Chrono Boost every 40... but say you miss a mule drop, and end up doing one 2 minutes after the previous one, instead of 80 seconds... then you only need to wait 40 seconds before you can do it again - you end up with the same amount of resources, you just are a little bit lower for a brief period, and then catch up. The same applies to Chrono Boost.
With Spawn Larva, however, if you miss one, or are late with one, there's no catching up... you can't bank up larva inject time like you can with energy on the OC/Nexus... regardless of how late you are with a Spawn Larva, you still need to wait 40s before you can use Spawn Larva again on the same hatch.

The end result is that, in regards to this small segment of the game, Zerg is a less forgiving race than the other two. Depending on how you choose to balance these abilities, you either get that low-level Zerg players will have a disadvantage compared to low-level players of other races, or high-level Zerg players have an advantage over high-level players of other races.

For a non-factional example, compare Gateways with Warp Gates - Gateways let you queue units, so you have no downtime... you can queue the next unit shortly before the previous one finishes, and there'll be no down-time. Warp Gates on the other hand have no queue, so any time between cooldown finishing and you warping in the next round is wasted downtime. However, Warp Gates' cooldown is 5 seconds less than the time it takes to build a unit at a Gateway, so you can build units more quickly with Warp Gates... as long as you're always returning to the warp gates within 5 seconds of the cooldown ending. Warp Gates also have other advantages, like getting the units earlier (you get the unit at the start of the cooldown, instead of the end of the build process), and the whole warp-in-across-the-map thing, which are also harder to factor in. But the upshot is that you never see a high-level player intentionally keep gateways when warp gates are available, but at the very low levels, it's sometimes tempting to keep them as gateways, as the queues can compensate somewhat for terrible macro (as inefficient as they are for competent players).

What exactly is your aversion to real discussion?

Well, from my skim reading, you basically just seem to be using a lot of words to say "you do the best thing to do, by finding the best thing, and then doing it, where 'best thing' is defined as the thing which is the best"... it's sorta hard to respond to that in any sort of in-depth way.

The answer to "can a program do x?" is not "yes, by making a heuristic, and then having that heuristic do x", no matter how many words it takes to say it.

[freakish777]

In the example given (obviously there are things like Chrono Boosts and Mules that are similar to this but not quite the same)

Yeah, it's SC2 that I was thinking of - specifically, comparing the three races' basic macro spells - Mule, Spawn Larva, and Chrono Boost. With the Mule and Chrono Boost, if you're a bit late with one, or miss one entirely, you can catch up later (within reason, as long as your OC/Nexus doesn't max out on energy)... you can do a mule drop every 80 seconds, or a Chrono Boost every 40... but say you miss a mule drop, and end up doing one 2 minutes after the previous one, instead of 80 seconds... then you only need to wait 40 seconds before you can do it again - you end up with the same amount of resources, you just are a little bit lower for a brief period, and then catch up. The same applies to Chrono Boost.
With Spawn Larva, however, if you miss one, or are late with one, there's no catching up... you can't bank up larva inject time like you can with energy on the OC/Nexus... regardless of how late you are with a Spawn Larva, you still need to wait 40s before you can use Spawn Larva again on the same hatch.

The end result is that, in regards to this small segment of the game, Zerg is a less forgiving race than the other two. Depending on how you choose to balance these abilities, you either get that low-level Zerg players will have a disadvantage compared to low-level players of other races, or high-level Zerg players have an advantage over high-level players of other races.

For a non-factional example, compare Gateways with Warp Gates - Gateways let you queue units, so you have no downtime... you can queue the next unit shortly before the previous one finishes, and there'll be no down-time. Warp Gates on the other hand have no queue, so any time between cooldown finishing and you warping in the next round is wasted downtime. However, Warp Gates' cooldown is 5 seconds less than the time it takes to build a unit at a Gateway, so you can build units more quickly with Warp Gates... as long as you're always returning to the warp gates within 5 seconds of the cooldown ending. Warp Gates also have other advantages, like getting the units earlier (you get the unit at the start of the cooldown, instead of the end of the build process), and the whole warp-in-across-the-map thing, which are also harder to factor in. But the upshot is that you never see a high-level player intentionally keep gateways when warp gates are available, but at the very low levels, it's sometimes tempting to keep them as gateways, as the queues can compensate somewhat for terrible macro (as inefficient as they are for competent players).

Yep, I get all that, and what I was basically saying was that when you put stuff like that in your game, you aren't unbalancing the game. You're splitting your players into "skilled enough to, on average, leverage it into an advantage over those not skilled enough." Now, obviously the real issue is "how big of a difference in skill does it take" and is it still fun. If the difference in skill level required to leverage into an advantage is too small, then bad players complain because the guy beating them is just barely better than he is (which makes it seem like it randomly benefits people), and if it's too high, then good players complain because it's not worth the effort (and again, you get into issues where you need strategies like this for different factions rock paper scissoring).

To balance and try to maintain it being fun, you'd want to set up your bots at different skill levels.

What exactly is your aversion to real discussion?

Well, from my skim reading, you basically just seem to be using a lot of words to say "you do the best thing to do, by finding the best thing, and then doing it, where 'best thing' is defined as the thing which is the best"... it's sorta hard to respond to that in any sort of in-depth way.

You should maybe not skim? This isn't what I'm saying at all. The definitions (Optimal Player, Fair Match, Balanced Game, etc) were there for bookkeeping purposes, because trying to have a discussion without some sort of agreed upon definitions makes things much harder. If people misunderstood why I put them in, my bad they should have been explained better.

The answer to "can a program do x?" is not "yes, by making a heuristic, and then having that heuristic do x", no matter how many words it takes to say it.

What? Heuristics don't "do" X. Bots that use heuristics do X. Heuristics attempt to provide valuations and costs for Positions/Units/Resources/Conversions, etc, for different circumstances.

So, at time t0 in the game (early), a worker is worth 100, and at time t10 (late) a worker is worth 50.

When your bot enters DecideAndExecute(), the Decide part of it will have the list of each and every action it can possibly make, it then uses the heuristic to place valuations on the result of each action (action A results in State S1 for me, State S1 is worth 50,000, action B results in State S2 for me, State S2, is worth 75,000, I choose action B). Then it carries those out (sorry if you guys already know this, but I'm not sure how you guys are coming up with what you're saying).

Your initial heuristic is 99.99999999+% likely to be wrong. This is why you run your bots against each other several thousand (or million) times, and after each iteration (say 5 fair matches and 5 unfair matches), you update your heuristic with a genetic algorithm to changes the values of the heuristic.

Eventually your heuristic will most accurately reflect the real valuations of your game as it stands. If, with this "pretty close" heuristic, your bots always do the same thing (and win), you know there's a dominant strategy in your game, and it's now time to change the game (to weaken that strategy to try and balance the game). This is where the code variables (build rate, unit strength, unit speed, etc) come in. These get updated when you have a dominant strategy based on your heuristic (you know how much Unit X is currently valued at time t5, the earliest it comes out, and it's too good, change a variable(s) associated with Unit X to make it worse).

Config File holds variables.
Heuristics hold valuations (heuristics go in a gene pool).
Bots use heuristic to decide what is the highest Expected Value play.

1. Crash bots against each other X times. After X times, when a bot wins with Strategy S1 frequently, update heuristic that was used with a genetic algorithm to value Strategy S1 (or units/buildings/resources/etc involved in Strategy S1) more highly (the genetic part of it is to give it some randomness so it properly explores our problem space, updating the specific valuations for S1 is to try and guide it in the right direction, you need both).
2. If Epochs < Y (epochs = number of times 4 has been done), Go back to 1.
3. If Strategy S1 was played too often (all the time? 75% of the time?), and winning over anything that isn't Strategy S1 some large percentage of the time (>66%? > 55%?, by bots of equal skill), then change Config File variables to weaken S1, go back to 1 and reset Epochs to zero.
4. If Epoch > Some large constant Z * Y and no dominant Strategy found, assume balance.
5. Repeat for each skill level you wish to balance.

This (really rough) algorithm (eventually) finds variables that will balance your game (dependent on your genetic algorithm and different numbers for X and Y and the percentages, as they will yield different results, you need numbers large enough to provide a level of certainty, but also need them to be small enough so as not to take forever, numbers should change depending on Epoch as well, the closer you get to your heuristic accurately reflecting the game, the more certain you want to be, for instance, as Z * number of Epochs already run gets large, the percentage of the time a strategy wins over another to trigger 3, we want it to go to 50%, and we want to pay attention to how often it gets played less). Whether that game is fun or not is a different story (but that should almost entirely be left to your Game Designers).

What is wrong with this from a CompSci perspective?

[phlip]

You're splitting your players into "skilled enough to, on average, leverage it into an advantage over those not skilled enough." [...] To balance and try to maintain it being fun, you'd want to set up your bots at different skill levels.

... And then what? When your different-skill-level bots come back and give different answers to the question of "what do I have to do to make this balanced?", what do you do then? From a CS perspective.

This (really rough) algorithm

Which is exactly the problem. It's like you're talking with someone about how to build a house. And your answer goes into great detail about buying a plot of land, and gives exact instructions on how to arrange a loan, and get the land titles sorted out, and the like. And then you just say "and then you build a house on it". The bits that you're handwaving away as "a heuristic", "find the most optimal action" or "DecideAndExecute()" are the interesting parts of the problem, while the bits you're going into detail on are just a framework. It's hard for people to get excited about a framework.

[freakish777]

You're splitting your players into "skilled enough to, on average, leverage it into an advantage over those not skilled enough." [...] To balance and try to maintain it being fun, you'd want to set up your bots at different skill levels.

... And then what? When your different-skill-level bots come back and give different answers to the question of "what do I have to do to make this balanced?", what do you do then? From a CS perspective.

Actually, what should happen is your bots should find multiple points that balance the game at each skill level (think of the game variables, unit speed, strength, etc as an N dimensional graph, there should be multiple different sets of N coordinates that create balance). From there, across all your skill levels, you pick the points that are the closest together (Skill Level L1 gives points A, B, C, Skill Level L2 gives, D, E, and A' which is similar to A, etc, you choose A and A' and pick somewhere that averages the different variables, your Skill Level divisions can be redrawn also if it ultimately provides balance while maintaining fun).

This (really rough) algorithm

Which is exactly the problem. It's like you're talking with someone about how to build a house. And your answer goes into great detail about buying a plot of land, and gives exact instructions on how to arrange a loan, and get the land titles sorted out, and the like. And then you just say "and then you build a house on it". The bits that you're handwaving away as "a heuristic", "find the most optimal action" or "DecideAndExecute()" are the interesting parts of the problem, while the bits you're going into detail on are just a framework. It's hard for people to get excited about a framework.

That's because Heuristic is a well defined term:

http://en.wikipedia.org/wiki/Heuristic#Computer_science

In this particular example, we want to modify our heuristic with each iteration to improve it so it more accurately reflects the game, which is (in my opinion) exciting (not to mention more relevant to the initial question asked, which was about balancing the game, not making a bot that could play the game, which is actually sort of boring at this point, it's been done multiple times). Furthermore, getting into particulars for a heuristic requires particulars for a game/problem...

Since the number of units and buildings, conversion costs, positions, etc is really really large (however complex your game is, your heuristic needs to capture that complexity), I'm not really going to get into trying to list everything or give a concrete example (there simply isn't time since I'm not getting paid for this, even if an example was provided). That said, you could model your units and buildings like such (t is time):

Resource Value = F(t) = ((Slope * t) + BaseValue)
Unit[x] value Creation = F(t, enemyComposition) = ((Slope * t) + BaseValue) - UnfavorableEnemyComposition(enemyComposition, x)
Unit value Placement = F(positionA, positionB, t) = SomeConstant(TimeConstantA*t*distance(positionA, positionB) + SomeOtherConstant)
Map Visibility = F(percentageUncovered, t) = (KnowledgeConstant * percentageUncovered) - (TimeConstantB * t)


So when your Heuristic is asked "How much is making Unit[x] Worth At Time t0" it returns a value. Same for "How much is placing this unit on the map at positionA, with respect to some interesting positionB, when it takes t seconds to move it there" and "How valuable is map visibility at this point in the game?" Note that UnfavorableEnemyComposition will just be a switch statement, that will return some value to increase or decrease values for that unit based on your enemy's composition.

I'm reasonably confidantthat Resource Value and Unit Value Creation are about correct, and most slopes should be negative, as resources/units get outclassed by larger units (and you need to bring in even more resources to keep up), and I'm comfortable with Unit Value Placement if I were asked by a company to write this in exchange for a salary. Map Visibility, I'm hazarding a guess for the sake of time (and assuming that as time passes scouting should become less less valuable, because you should have already done it). The list of formulas that make up your heuristic will be gigantic for an RTS.

Note that you want different Placement formulas for each type of "interesting thing" on the map (because proximity to different things are valued differently), such as Ramp To Your Base, Beacon That Increases Amount of Map You See, Trees You Can Ambush From Behind, Inside My Base, Inside Enemy Base, In A Ball With Other Units, Near Enemy Units (maximum value when you're in range to hit them and they're out of range to retaliate), also the last two here need some more math involved for "how powerful is that army" based off of the Unit Value Creation formulas.

When you modify your heuristic, you're modifying BaseValue, Slope, SomeConstant, TimeConstantA, SomeOtherConstant, etc (even the type of function could be updated, but that adds a huge layer of complexity that shouldn't be necessary).

If your game does anything like Stack Rewards (do 2 Voidrays attacking the same thing actually have a higher damage output than 2 Voidrays attacking different things?) then the Heuristic needs to reflect that; F(t, n, enemyComposition) = ((Slope * t) + BaseValue) * n * StackingReward - EnemyComposition(enemyComposition), and now you have to update StackingReward also (provided there isn't some way for you to grab it directly from the game variables).





Decide of DecideAndExecute() is just Minimax executing at as shallow a depth as possible (since we're an RTS, we don't have time to figure out what the best plan is if it takes more than X time to figure out, we're better off pretending our heuristic gives us a perfect valuation each time and executing immediately, since we're going to change our heuristic for the better with each iteration anyways). In theory it's just minimax, but given today's computer speeds we need to prune uninteresting things. So instead of asking our heuristic for Unit Value Placement for each unit and for each actual position on the map, we instead limit to "Ball Value Placement" and positions of the Interesting Things we can see on the map (do I see a Ramp To My Base on the map? How about a beacon that increases visibility? what about their base or their units?, etc). A very interesting part about this (with having to limit it) would be how do we still get the Bot to Explore Fog of War areas (really, any "strategy" that requires multiple actions, because we need to search at least that number of actions deep to support that strategy. Ultimately, if exploring with only 1 unit early in the game, while leaving a ball at your ramp is optimal, your Heuristic should get to a point where it values "Place Ball At Ramp Early in Game" highly, and "Increase Map Visibility Early in Game" high enough (which can be accomplished with only 1 unit) such that it takes 1 unit out of the Ball and begins moving it.




Execute is mostly just "Ok, call the function that does the action that Decide told me was best" with modifications for different skill levels (I covered this earlier, you could introduce some randomness or some sleeps into the code to decrease how well Execute actually does what it's supposed to, this seems preferable, to me, over intentionally using a sub-optimal heuristic to simulate a lower skilled player).

[phlip]

It's like you're talking with someone about how to build a house. And your answer goes into great detail about buying a plot of land, and gives exact instructions on how to arrange a loan, and get the land titles sorted out, and the like. And then you just say "and then you build a house on it".

That's because Heuristic is a well defined term:

http://en.wikipedia.org/wiki/Heuristic#Computer_science

It's certainly at least as well-defined as "house".

In this particular example, we want to modify our heuristic with each iteration to improve it so it more accurately reflects the game, which is (in my opinion) exciting

It certainly is. That's kinda why it'd be better if you looked more into that, rather than just handwavily saying "and then you modify the heuristic". I get that it's a challenging thing to do. That's kinda the point. You really do seem to be saying both "it's easy, you just do x", while simultaneously saying "I don't want to go into details about x, it's too hard".

Besides, you've said "a heuristic"... you can give more details than that, without needing to get into the particulars of a given case. How approximate are we talking here? Something like a greedy algorithm, which is pretty simple, but often quite far off the mark? Or something like a neural net, much more complicated, and hard to analyse, but giving better results? Or someting akin to the Christofides algorithm, hand-tailored to the problem, and giving a result that's at least close to the right answer in all cases? And then, how do you modify it every iteration, as you suggest? For a neural net this is built-in, but for the hand-tailored option this is very non-trivial. What level of approximation are we working at?

Resource Value = F(t) = ((Slope * t) + BaseValue)
Unit[x] value Creation = F(t, enemyComposition) = ((Slope * t) + BaseValue) - UnfavorableEnemyComposition(enemyComposition, x)
Unit value Placement = F(positionA, positionB, t) = SomeConstant(TimeConstantA*t*distance(positionA, positionB) + SomeOtherConstant)
Map Visibility = F(percentageUncovered, t) = (KnowledgeConstant * percentageUncovered) - (TimeConstantB * t)
[...]
When you modify your heuristic, you're modifying BaseValue, Slope, SomeConstant, TimeConstantA, SomeOtherConstant, etc (even the type of function could be updated, but that adds a huge layer of complexity that shouldn't be necessary).

Ah, I see, the "spherical cow" level of approximation.

Decide of DecideAndExecute() is just Minimax executing at as shallow a depth as possible (since we're an RTS, we don't have time to figure out what the best plan is if it takes more than X time to figure out, we're better off pretending our heuristic gives us a perfect valuation each time and executing immediately, since we're going to change our heuristic for the better with each iteration anyways). [...]

See, this is what I'm talking about. You spend a lot of words describing something simple like minimax, spending most of your time offloading the complexity into the heuristic. But the heuristic you mentioned is also very simple, and you spend most of your time offloading the complexity into the iterative processing. But the iterative processing you mentioned is also very simple, and you spend most of the time offloading the complexity into the various parameters. Which you then handwave away. And what you're left with is a bunch of words describing the simple edges of the problem, and all the complex middle of the problem is just a big handwavery vague gap.

[freakish777]

It's like you're talking with someone about how to build a house. And your answer goes into great detail about buying a plot of land, and gives exact instructions on how to arrange a loan, and get the land titles sorted out, and the like. And then you just say "and then you build a house on it".

That's because Heuristic is a well defined term:

http://en.wikipedia.org/wiki/Heuristic#Computer_science

It's certainly at least as well-defined as "house".

Fair enough if that's how you see it. That's not exactly how I see it.

In this particular example, we want to modify our heuristic with each iteration to improve it so it more accurately reflects the game, which is (in my opinion) exciting

It certainly is. That's kinda why it'd be better if you looked more into that, rather than just handwavily saying "and then you modify the heuristic". I get that it's a challenging thing to do. That's kinda the point. You really do seem to be saying both "it's easy, you just do x", while simultaneously saying "I don't want to go into details about x, it's too hard".

Besides, you've said "a heuristic"... you can give more details than that, without needing to get into the particulars of a given case. How approximate are we talking here? Something like a greedy algorithm, which is pretty simple, but often quite far off the mark? Or something like a neural net, much more complicated, and hard to analyse, but giving better results? Or someting akin to the Christofides algorithm, hand-tailored to the problem, and giving a result that's at least close to the right answer in all cases? And then, how do you modify it every iteration, as you suggest? For a neural net this is built-in, but for the hand-tailored option this is very non-trivial. What level of approximation are we working at?

I already said a Genetic Algorithm (which are also used to update the weights in Neural Nets usually) could be used to update values of the Heuristic. Hence why I suggest you not skim.

Also, I'm not saying "it's easy, just do X" and then being handwavy. What I said was "making your bots play at varying levels of skill" and compensating for things like APM are (mind-numbingly) easy.

Resource Value = F(t) = ((Slope * t) + BaseValue)
Unit[x] value Creation = F(t, enemyComposition) = ((Slope * t) + BaseValue) - UnfavorableEnemyComposition(enemyComposition, x)
Unit value Placement = F(positionA, positionB, t) = SomeConstant(TimeConstantA*t*distance(positionA, positionB) + SomeOtherConstant)
Map Visibility = F(percentageUncovered, t) = (KnowledgeConstant * percentageUncovered) - (TimeConstantB * t)
[...]
When you modify your heuristic, you're modifying BaseValue, Slope, SomeConstant, TimeConstantA, SomeOtherConstant, etc (even the type of function could be updated, but that adds a huge layer of complexity that shouldn't be necessary).

Ah, I see, the "spherical cow" level of approximation.

Seeing as I'm not getting paid more than $75,000 a year to work on this problem, yes, that's the level of approximation on the Heuristic you're getting from me as a starting reference. Furthermore, to try and give a Heuristic (not a heuristic algorithm, but the heuristic itself) without an example RTS to work off of would be just stupid.

If you want to pay me $75k a year, I'd be more than willing to play college professor for you (and for a half million dollar a year budget that allows me to hire 2~3 other Software Engineers, a Project Manager for requirements gathering, requisition necessary hardware including beefy servers for our bots to play a lot of Epochs on, etc, I'd be happy to IMPLEMENT IT for you, or Blizzard, or whoever).

Decide of DecideAndExecute() is just Minimax executing at as shallow a depth as possible (since we're an RTS, we don't have time to figure out what the best plan is if it takes more than X time to figure out, we're better off pretending our heuristic gives us a perfect valuation each time and executing immediately, since we're going to change our heuristic for the better with each iteration anyways). [...]

See, this is what I'm talking about. You spend a lot of words describing something simple like minimax, spending most of your time offloading the complexity into the heuristic. But the heuristic you mentioned is also very simple, and you spend most of your time offloading the complexity into the iterative processing. But the iterative processing you mentioned is also very simple, and you spend most of the time offloading the complexity into the various parameters. Which you then handwave away. And what you're left with is a bunch of words describing the simple edges of the problem, and all the complex middle of the problem is just a big handwavery vague gap.

So what you're saying is there's a future for me in teaching at the college level?

Jokes aside, no, that's not what I've said. Let me be clear, the vast majority of the meat of this algorithm lies in the Heuristic (the thing that tells us what the values are, as everything else relies on it).

Also the heuristic is not (necessarily) going to be hard to come up with. Rather, it's going to be tedious, and very likely require a lot of in depth knowledge of the game/problem to begin with.

And no, I'm not going to get into how to model the initial heuristic on any in depth level, due to how complex RTS's are, and how differentiated they are from each other. Yes, you're either going to need to hand tailor the functions you pick to your game, or you're going to need to make your genetic algorithm to update not just values, but to update the functions used as well (which makes it more complicated, and shouldn't be necessary).

For each Unit Type in your game, you need an "Estimated Value Of An Additional Unit U1, At Time T1, Given the Composition of your Opponent's Units" function to be defined in the heuristic.

Same for each building.
Same for moving units to any "interesting" or distinguishable feature on the map.
And in relation to any other building or group of units on the maps.
Same for placing buildings.
Same for Map Visibility.
Same for <INSERT ALL FEATURES OF YOUR GAME>.


Updating the values the heuristic uses in it's functions that aren't input parameters with each iteration based off a genetic algorithm should be non-challenging.

[Game_boy]

What you're saying is obvious. Anyone who's played an RTS could write down the names of all those parameters and pseudocode. You don't even need to write it.

If you were doing a shortest path algorithm it would be like:

Define each node on the network as a Point. A Network is a collection of Points arranged in a network. Define a path as a set of Points in the Network of Points such that there is a Path betweeen each Point on the Network, such that there is a Path. "Short Path" is a Path that is short.

Our heuristic is a Heuristic which finds a Short Path in the Network by some parameters <short> <path> and <network>. At Time T, the shortest Path "P" on the Network is a path that is the shortest. SomeOtherConstant is a Constant that isn't the same as TheFirstConstantIWasReferringTo.

Routine <CalculateShortestPath> calculates a Network Path that is Short for an acceptable value of Shortness that is an attribute of a Path. Simply run <CalculateShortestPath> with the given parameters and you will get a suitably short Path as output.

[freakish777]

What you're saying is obvious.

Because to someone, it's not obvious.

If you were doing a shortest path algorithm it would be like:

Define each node on the network as a Point. A Network is a collection of Points arranged in a network. Define a path as a set of Points in the Network of Points such that there is a Path betweeen each Point on the Network, such that there is a Path. "Short Path" is a Path that is short.

Our heuristic is a Heuristic which finds a Short Path in the Network by some parameters <short> <path> and <network>. At Time T, the shortest Path "P" on the Network is a path that is the shortest. SomeOtherConstant is a Constant that isn't the same as TheFirstConstantIWasReferringTo.

Routine <CalculateShortestPath> calculates a Network Path that is Short for an acceptable value of Shortness that is an attribute of a Path. Simply run <CalculateShortestPath> with the given parameters and you will get a suitably short Path as output.

No. If I were doing Shortest Path algorithm it would be like this:

http://en.wikipedia.org/wiki/Shortest_path_algorithm

To be cliche, "I'm not going to reinvent the wheel."


This isn't a classroom environment, and I'm not being paid to provide subject matter knowledge to anyone.


Heuristics don't "do" things. Heuristic Algorithms do (the algorithm that uses the heuristic). Our heuristic is a collection of formulas that get called by the algorithms that our Bots use (mostly Decide of DecideAndExecute() does). An "optimal play" isn't optimal because it's "best," it's optimal because it yields the highest percentage chance of winning among all available actions given the current state of the game (hey, something else that's obvious). This collection of formulas provides evaluations of different game states in point values. The Bot then chooses the action that leads to the game state with the highest point value.

Just like Adversarial Search algorithms have been doing for 50+ years (you know, obviously, so I shouldn't have to even be saying this)...

The interesting part is in updating our heuristic (our list of formulas that evaluate game state) so that when our Bot asks "Here's a game state, give me a point value" it will eventually give point values that accurately reflect the percentage chance of winning from that game state.

If you're not familiar with Minimax (or expecitmax, or negascout), or how it makes use of a Heuristic (AIMA's definition is much better than wiki's, but you'd need a copy of the book), or how to implement a Genetic Algorithm, then feel free to take some AI classes. In fact, I hear Stanford even has a free version of their Intro AI course online, so you don't even have to pay anything (not that the intro course is likely to cover GAs).

[Game_boy]

"I'm not being paid to provide subject matter knowledge to anyone."

I give up on this thread. You don't get it.

[Koa]

Human limitations are difficult to replicate computationally. Something as simple as a sleep command to replicate human APM limitations is folly for several reasons. First because skill isn't determined by APM, but by how advanced the heuristic is for determining what the most effective course of action would be. Second because computers learn in a different way than a human, they don't make assumptions, they don't feel emotions that would affect judgement. I'd argue these things actually are a factor in balancing. People lose games through sheer frustration of certain strategies regardless of their actual effectiveness. Third, they would be unhinged to excel at some of the most difficult tasks for a human, and would fail at some of the most simple. A human can't pay attention to 10 different engagements on the map at once, whereas a bot, even with a speed limitation, would.

If you don't replicate human limitations properly, and you balance the game using bots, then you are balancing the game for bots. To make an analogy, imagine a physical sport wherein two teams of unequal value are pitted against each other, and you need to incorporate handicaps in order to balance the two for an equal possibility of winning. To do this, you replace some members on the team with an impossible entity (and mathematically assess their statistical relevance to the game by how many of them exist against real players) to create an effective frame of reference to judge the humans' capabilities. These entities can, say, teleport in a field game. This hypothetical game is no longer relevant for determining handicaps for the human players, as they've completely skewed the results due to their unique ability.

Also, you can't really have a computer teach itself to play an RTS such as SC2 using genetic algorithms. The number of differing scenarios is simply too complex. You can, for instance, make a genetic algorithm for it to learn how to do mutalisk micro (as shown above). There have been serious attempts to make bots for BW, and every time they would have problems dealing with scenarios that would be trivial for a human. Things like a single worker would ruin the bot's economy because the bot would constantly make a wrong decision to never attack it. You would have to feed it the information to, yes, attack that worker, or make a specific genetic algorithm so that it could learn when it should. This is a simple scenario of a worker attacking a worker, and is just a drop in the sea of the complexity of SC2. That's why phlip made the comment of "and then you build a house on it." The amount of information that you would have to teach a bot in order for it to teach itself would be enormous.

But even assuming that you could overcome all of these issues, how could you derive any sensible data from such a bot for the end of balancing? Let's say that a bot can obtain a 95% winrate using marines or something (which it likely would unless you accurately replicate human limitations). What parameters of the game do you change to fix this issue? Is it marines themselves, or is it that the other races don't have an answer for marines? What if the answer is that the other races don't have an early game advantage that would stifle the specific marine strategy that is causing the winrate? What if the other races DO have an early game advantage, but it just hasn't been discovered yet? Such a bot could only be a vague consultant for balancing concerns.

Then there's also the problem of skill gradients, or what is an acceptable human limitation. How much is a human capable of, and where do you draw the line of when they should be rewarded and when they should be punished for when they are and aren't capable of doing a specific task. That's a big one.

Is balance between sufficiently differing races in an RTS NP Hard or not solvable? That's a hard question. However ridiculously complex the above is, it may still be possible to solve every issue. I think it would be important to define what is balance, but I think such a definition could only be subjective in nature for games like Starcraft.

[freakish777]

People lose games through sheer frustration of certain strategies regardless of their actual effectiveness.

Not relevant for creating a balanced game. 100% necessary for creating a fun game, but that isn't what was asked for.

A human can't pay attention to 10 different engagements on the map at once, whereas a bot, even with a speed limitation, would.

I never said "Just limit APM, that's all you need to do." I said "There's things you can do, like limit APM, to make a bot approximate a human player." Set 4 (X,Y) coordinates and have them represent a screen, only give bots information on units that are within the boundary lines. Not particularly complicated.

If you don't replicate human limitations properly

Clearly the goal would be to do it properly.

Also, you can't really have a computer teach itself to play an RTS such as SC2 using genetic algorithms.

I didn't suggest using a Genetic Algorithm to have a computer "teach" itself how to play. I suggested using a GA for it to learn the variable/function values for it's heuristics that it uses to determine how important a unit/building/game variable is.

There have been serious attempts to make bots for BW

Serious attempts by who? Source?

Things like a single worker would ruin the bot's economy because the bot would constantly make a wrong decision to never attack it.

This doesn't sound at all like a learning system, but rather someone who hard coded a bunch of static strategies and said "Pick from one of these pre-existing strategies."

The amount of information that you would have to teach a bot in order for it to teach itself would be enormous.

This isn't correct. More like the hardware and development cost involved is prohibitive (the hardware in particular, we're talking about playing several thousand games per epoch and recording data for each game, and wanting probably a couple hundred epochs, the servers are going to be expensive).

The reason Blizzard doesn't have bots that balance games for them isn't a technical one, but an economic one. There's little to no point in poring money into such a project when they have millions of fanboys eager to get into a beta release (what they do spend some money on, is statistics recording, they're pretty open about the fact that they record data for every single game played on BattleNet, which you'd need anyways for any such Bot Balancing System).

But even assuming that you could overcome all of these issues, how could you derive any sensible data from such a bot for the end of balancing? Let's say that a bot can obtain a 95% winrate using marines or something (which it likely would unless you accurately replicate human limitations). What parameters of the game do you change to fix this issue? Is it marines themselves, or is it that the other races don't have an answer for marines?

Just to be clear you should be carrying out Epochs until your GA has come to a resting spot on the values for the variables/functions of your Heuristic and balancing shouldn't happen before that (so, no knee-jerk reacting to a threshold of 95% win rate).

Let's make an assumption that the units and building in the game are static (game design has finished, graphic artists have started animating all the motions for units, story people are placing final touches on any story involved in a single player campaign, Software Engineers are nearing completion) and so are the mechanics (you're not allowed to change the actions available to a unit, add or subtract units, etc, just change variables such as Speed, Speed of Attack, Damage per attack, Cooldown Rate, Build Rate, etc).

Now here's the thing, you don't make a single change that would balance the game and go "Ok, I'm done." You record your current values, noting what values the Heuristics variables/functions had at the time, then you make any change that decreases that strategy. On the next Epoch when you've decreased it to, say, 85% against non-same strategies, you should accelerate towards convergence.

I should point out here, that in what I initially proposed, I wasn't as clear about something as I should have been, 2 GAs are necessary, 1 for optimizing the heuristic, and one for balancing purposes (it was clear in my head, but I wasn't clear with what I typed, sorry about that).

Carrying on, in this case, you have to decide what convergence (for balance) looks like. Is it simply 50%? Is it "bot selects strategy X, 1/Y times where Y is the number of strategies we wish to support, and wins, at best, 50% of the time with it?"

Now, in the above, you also need to limit the balancing GA to make changes to only relevant units. There's no sense in making Carriers do more damage to try and make Marines less effective, so you're going to filter on units that engaged Marines from your recorded data. There is one exception to this, and that's making build times smaller for opposing strategies. So, your options are "Make Marines Worse" or "Make Units That Engaged Marines Better" or "Make Bigger Units That We Think Crush Marines Build Quicker" and it's not particularly relevant which one you pick, you'll (eventually) achieve balance whichever way you go. That said, making both changes and branching into two different groups is preferable (assuming you have the hardware).

A quick side note, if you must choose only one and want to be deterministic about everything for some reason, it's preferable to tone down the unit that's too good. Followed by making the non-Worker unit that took the most damage from the unit that's too good, better.

What if the other races DO have an early game advantage, but it just hasn't been discovered yet? Such a bot could only be a vague consultant for balancing concerns.

This shouldn't happen, but if it does it's (hopefully) irrelevant.

Why shouldn't it happen? Since your epochs run until your GA has stopped updating values, the Heuristic should be near a perfect representation of the game in that particular state, so there shouldn't be any "undiscovered strategies" (this is because you're basically running an adversarial/minimax search, and getting values from your Heuristic).

Realistically though, it could happen, since you may not have time for long enough epochs for your GA to settle the Heuristic values or your hardware might not able to execute an adversarial search at a depth large enough to "see" a particular strategy. So why would it be irrelevant even if it happened? Say you've already toned down Strategy X which was discovered 2 epochs ago, and Strategy Y (that would have beaten the non-toned down strategy X) is discovered (possible when you don't have time for long epochs, shouldn't magically get discovered by adversarial search unless you tweaked that algorithm in between epochs). What then? Tone down Strategy Y. Potentially Strategy X creeps back into being used more heavily, but maybe it doesn't. The point is our balancing GA is tweaking until we've matched some criteria for balance, making larger changes the further away from balance we are, and smaller changes the closer we are.

I think it would be important to define what is balance

Agreed, which is why my initial post focused on definitions for game play first. I think any definition of balance needs to first address what a Fair Game means and go from there. A game being fair has nothing to do with how fun it is, or how frustrating it can be. It could be frustrating because it's unfair, but it's not necessarily unfair just because it's frustrating.

[Koa]

Not relevant for creating a balanced game. 100% necessary for creating a fun game, but that isn't what was asked for.

This is a problem of the disagreement on the definition of balance, which is why it would be important to define.

I never said "Just limit APM, that's all you need to do." I said "There's things you can do, like limit APM, to make a bot approximate a human player." Set 4 (X,Y) coordinates and have them represent a screen, only give bots information on units that are within the boundary lines. Not particularly complicated.

You'd also have to replicate physical input limitations and the capacity to understand information. You'll have to draw lines of what is acceptably possible for a human, and at what point should imbalance be acceptable when a human is capable of exceeding those limitations. I'd say it's a lot more complicated than you're letting on. You might find these things irrelevant (going to repeat myself some here, forgive me), but if you don't accurately represent human limitations, you're balancing the game for bots. This also comes down to the definition of balance, and I'm afraid it may be subjective in nature.

I didn't suggest using a Genetic Algorithm to have a computer "teach" itself how to play. I suggested using a GA for it to learn the variable/function values for it's heuristics that it uses to determine how important a unit/building/game variable is.

I guess I wasn't very clear. I know what you're suggesting, but I don't think you understand how incredibly complicated that heuristic would have to be to gather all the information required to solve the game. You could attempt it by mimicking human play (and even that would be amazingly difficult to accomplish to any degree of accuracy), but a heuristic capable of truly solving SC2 is so over my head that... I can't even explain it... I'd have to assume you're an alien. How do you plan on building the heuristic? A GA? How do you build that GA? A heuristic? How do you build that heuristic? Why not just build a fullblown sentient AI while you're at it? I can't even tell if I'm joking.

I don't think there is a human on this planet that can say with any certainty that they can build such a bot before they've attempted to do so without exercising ignorance (no offence intended).

Serious attempts by who? Source?
This doesn't sound at all like a learning system, but rather someone who hard coded a bunch of static strategies and said "Pick from one of these pre-existing strategies."

Expressive Intelligence Studio at UCSC I believe. There is a lot of scripting involved, but that's because it's necessary to develop something tangible within a meaningful time frame.

The reason Blizzard doesn't have bots that balance games for them isn't a technical one, but an economic one.

I'd say it's both, but yes the economic one is more prominent.

Let's make an assumption that the units and building in the game are static (game design has finished, graphic artists have started animating all the motions for units, story people are placing final touches on any story involved in a single player campaign, Software Engineers are nearing completion) and so are the mechanics (you're not allowed to change the actions available to a unit, add or subtract units, etc, just change variables such as Speed, Speed of Attack, Damage per attack, Cooldown Rate, Build Rate, etc).

But the game isn't even static! The ladder map pool changes every 3 months in SC2. Do you build another bot that determines what is a balanced map, or do you push out a balance patch every season that is based on an average qerklaernasdlfknalkghh44tjelrthalweknral;wkerhalewrua point of convergence alkfnjal;wekryauweoprihawerhnalkrenalsdn heuristic lawerlawekrnha;lwekrnalwkuerasopdifanfk

Is such a bot possible? Yes. Is it way over everyone in this thread's collective mind? Yes. Is it feasible in 2012? No. Could someone begin work on it in 2012? Sure, why not. Could an RTS be balanced with such a bot? Define balance. Could you define balance? No, you would have to redefine it.

Could a bot assist in modifying parameters to provide a state of such a redefinition of balance? Of course. Would such a game, whose parameters are dictated by mathematics to achieve the state of such a redefinition of balance, be balanced? No, while the two definitions of balance (subjective, and defined objectivity) would be similar in some sense, they would never be equal. The best course will always be to give the players the same tools for success. While the pieces and board of chess are completely equal, they have unequal tools (white moves first) and is therefore, at least slightly, imbalanced.

(I've put a lot of thought into the points that I made, much more than a reader could gather in these two posts. I finally found that the immeasurable complexity involved in both a bot and the creation of a bot is really just a strawman to the original question, and I feel my eventual conclusion is irrefutable.)