A dynamic problem involving probabilities

[suszterpatt]

I encountered an interesting problem with one of my spare time projects, and I think I might have a lead on how to solve it, but I couldn't find any substantial help with any of the scientific search engines nor google.

Ok, so here's the problem. Imagine you have a virtual game world that's so immense that you can't afford the kind of server it would take to monitor it all. So what you do is split it up into n parts, buy n smaller servers, and connect the servers together so that they can pass players to one another as the players move from the territory of one server to the other. Not too complicated, right?

Here's where things get tricky. We want to prevent players from all moving to the territory of one server, and instead distribute them more or less evenly over the game area. To this end, we introduce objectives. Each objective is tied to a specific point in the game world, and as such, to one specific server. If a player takes on an objective, they will be transported to that point (and that server) for some time, and will gain some amount of money (it doesn't really matter how much). Adversely, moving to a point with no objectives costs the players money.

Now, we can state that the probability of players moving to a certain server is characterised by the number of objectives in that server. Our goal is to devise a system/algorithm/heuristic/whatever that maintains a roughly even distribution of players among the n servers through alterations in these probabilities.

I've been doing some research and came across a theorem that is very similar to my problem. The theorem says that if a) you have two urns with balls in them, and b) that upon dropping a new ball, the probability of it landing in the urn with the least balls already in it is 2/3, and 1/3 for it falling into the urn with the most balls; under these conditions, the distribution of the number of balls in both urns is a uniform distribution.

My problem is almost identical to the above described two urn situation, except I have n urns, and I can remove balls as well as insert them.


Can anyone help me out with this? Either with some relevant reading material (online or offline), a programming method that could provide a solution, another forum where I might get more input, anything would be greatly appreciated.

 

[CycloWizard]

Generally, I would approach this problem using a simple weighting system. Make the rate at which the players get paid on server x inversely proportional to the normalized number of players on that server (i.e. v_x = a* p_tot/p_x, where a is a proportionality constant, v_x is the velocity of payment, p_x is the number of players on the server, and p_tot is the total number of players). The proportionality constant 'a' is simply a factor dictating how much money/hour the players make for playing on this server. Of course, this won't work if the game pays for achieving an objective. If this is the case, then you're in a lot of trouble because one objective will likely always be more lucrative than another such that its server will also be more crowded.

edit: If this isn't helpful, let me know how the objective/reward scheme is set up and I might be able to suggest something else.

 

[suszterpatt]

Ok, a bit more info about the mechanics of the game.

Objectives consist of a designated goal, a maximum number of players that can accept it, an amount of money paid upon completion, and other optional bonuses. All this information is available to players before they choose to accept it. As mentioned above, travelling to any part of the game world other than where the objective is costs money.

There are 3 possible outcomes to an objective: aborted, failed, or successful. After a player reached one of these conclusions, they're free to pick a new mission whereever they want. Objectives are created and cancelled on the fly, as the need arises to increase or decrease the population of a given area.


Now payment is a really complicated matter. First of all, all players slowly lose money over time, at a rate that differs from player to player. They gain money when they successfully complete an objective, but the amount depends on not only the promised payoff, but also the player's performance regarding the optional goals. All in all, accurately calculating even an expected payoff for an objective is practically impossible, the best estimation is some intuitive "chance to succeed" ratio (especially when you consider differences in skill level between players).


While altering the payoff of objectives is certainly an option, we'd like to limit that to relatively small, maybe 5-10% differences from the original, and have the quantity of objectives be the dominant aspect.

------------------------------------------------------------------------------------------

With all that in mind, I've been thinking a bit more about this. Since moving to "irrelevant" areas costs money, it's safe to assume that few people will do so, and as such ignoring them from the balancing process should not have drastic consequences. Furthermore, these people will sooner or later accept an objective (due to them constantly losing money until they do), integrating themselves into the system. This means that we only need to balance the number of players who assigned themselves to an objective.

As stated above, what we need to achieve is to have p_i := p_tot/n players in each server. In other words, that should be the sum of players who accepted objectives on each server (remember, we're ignoring "vagabonds"). Suppose a server has more than p_i players. This can easily be fixed by cancelling objectives until the player count reduces to p_i. This can be done instantly.

Now if it's below p_i, things get trickier. Adding as many objectives that the sum of their max playercount fills the gap wouldn't work, since we don't have a guarantee that all those spots will be filled. The simple approach is to wait a bit after adding objectives, and if the population still isn't high enough, add more objectives. This may or may not take too long though as the playercount converges to p_i. However, if we could estimate the number of players that will accept a certain objective, we could use the sum of these expected values as an upper limit. This is where increasing the payoff would play a part: obviously a better paying objective would attract more people.

The only question now is, how do we determine the expected number of people who accept a certain type of objective? I imagine that since we're dealing with a significant human factor here, analytic methods wouldn't do us much good: instead, we should develop an AI that learns this information during a beta testing stage, and applies it to the world later on (possibly re-learning it as necessary). It seems to me that an artificial neural network is just what we need here, but my experience in that field is restricted to a single 90 minute AI lecture from college that was this tuesday, which is the only reason I know about neural networks in the first place.


Well this is a nice wall of text... you think I'm on the right track here?

 

[CycloWizard]

There might be a couple ways to do it. AI seems like a lot of work to me, but I'm not a hard-core programmer, so you can do that if you want. If it were me, I would try to develop some heuristics/guidelines based on a relatively small-scale beta test.

The key is to come up with some metric by which you can predict the probabilities. In this case, it's hard to know what metric is appropriate without knowing more about the objectives themselves. If one objective is worth more money, all other things being equal, that server should always be more crowded. However, if the objectives that are worth more take more time or have a higher risk (how to assess the time or risk in this case you would have to figure out, of course, during the beta), then you could develop a semi-empirical mulit-modal probability distribution.

The way I see this working is that you have your metric (e.g. reward/risk ratio) for each objective. Then in the beta, you track the number of players on each server. Some relationship should exist between your metric and the mean number of players, which one would anticipate would be some increasing function since higher reward:risk should draw in more players. The standard deviations of the number of players on at a given time gives you an idea of how much leeway you need in the server capacity to handle all of them that may be on at a given time. I'm not sure how this approach could deal with new objectives created on demand, since it would take considerable time for players to get feedback on the metric and establish a stable equilibrium. The simplest way to allow for this would be to simply allow a certain fudge factor (which engineers love to do) in the transient period while players feel out the new objectives.

This approach is obviously oversimplified, since things like time of day and other factors are probably also important variables, but the same method can be applied by using multivariate regression and statistics. The tuning parameters would also likely have to be adjusted to scale with the number of players. Maybe you will need AI after all.

 

[Gibsons]

Something real simple that might help is to put a timer on the objectives. Whenever someone accomplishes some objective, the timer resets to zero. If the timer goes over a certain number, the reward gets increased by some percent, and maybe does so several times up to some arbitrary limit. Thus, the least popular objectives automatically get an increase in reward.

You might want to look for some info from the world of MUDs, some of them have been dealing with issues like this for a very long time and had to come up with clever solutions as they didn't/don't have the horsepower for anything like AI. There's a discussion group on mudconnect.com that might be helpful.

 

[suszterpatt]

If we do end up using any of these metrics or estimated values, it will be better to write an AI for them for our project. Ideally, this is a game that could go on for years uninterrupted, which means there can be significant shifts in player behavior. It would be better to let an AI monitor these changes than to have personnel dedicated for the same task: after all, a computer could do this faster and, depending on the quality of the AI, more accurately.


Anyway, mudconnect seems to be the perfect place to ask about this, many hugs for that. :heart:

 

[Foxery]

I see your text wall, and raise you one novelette.

What you describe sounds much like a typical MMO, so I'm going to toss some ideas your way based on my perspective as a player who has sometimes wondered what causes the behaviors I observed while playing. (Disclaimer: These are my own educated guesses, using Warcraft as a prime example. Blizzard does not publicly disclose the details of their hardware setups or programming strategies.)

Question 1: Do new players start in the same area, or can they be distributed across several starting zones?
Reasoning: Level 1 characters in WoW have 6 starting zones to choose from, and will almost never travel to a different starting zone. They spread out evenly through the world towards each other, but are rarely funneled into the same place at the same time.
Counter-example: When the expansion was released, all players were funneled into a single new starting zone. Servers crashed regularly, and players were dropped frequently. After the initial rush, players who gained levels were again able to spread out into multiple zones, and performance returned to normal.

Question 2: Within the rules of your game, is it practical for any player to have access to any zone? i.e. Can you actually spread out objectives, or are there requirements / prerequisities?
Reasoning: The higher your level in an MMO, the more zones you have to choose from. Old ones also become completely useless to you, but continue to be populated by the next day's new players. However, in WoW's case with clearly defined progression and zone borders, load is always weighted towards the current average player level. The majority of the population moves from level 1 to 30 to 60 zones, then most stay at 60.
Counter-example: Capital cities (more generally, safe/resting zones) have desirable resources for players of any and all levels. These always have high load, and you just have to live with it.

Question 3: If you base rewards off of the (un)popularity of objectives, will this appear fair to players, or will it confuse them? Also, does your game encourage cooperation and teams, or Every-man-for-himself?
Reasoning: Players who believe an area is superior will tell their friends, and everyone will flock to it. Depending on how quickly and rationally the rewards change, you will either confuse players, or greatly exacerbate load imbalances as the population ebs and flows.

Question 4: How long is a player expected to stay in one zone before completing it, or otherwise moving?
Reasoning: Less movement gives you more time to control/adapt, and generally smoother shifts in load. If players start spread out and well balanced, and are not greatly motivated to move around, (or do so slowly,) they will tend to stay well balanced.

Objectives consist of a designated goal, a maximum number of players that can accept it,

The only question now is, how do we determine the expected number of people who accept a certain type of objective?

Connecting the dots: Can you make an objective unavailble for a while when it is currently being attempted? Does this make sense within the context of the game world? And more importantly, will players who are turned away still have enough other options available to keep them busy?

Ideally, this is a game that could go on for years uninterrupted, which means there can be significant shifts in player behavior.

Unless you want to run exactly 1 CPU per 1 zone, set up the world such that you can run multiple zones on each CPU, and give yourself the ability to move the software between machines. i.e. Initially, population is balanced and you are 1:1. A year from now, Zones B,C,D are relative ghost towns while Zones E and F are hot spots. Copy B+C+D to a single machine whose total load will remain reasonable, and you can retask two CPUs to newly created content or turn them off.

Saving the best for last

Depending on the structure of your world, one of Blizzard's more brilliant mechanics is Instancing. For zones which require a group, and which many groups want to use at once, the server creates a unique copy of the zone for each group. The players can be moved to any CPU that happens to be free, because they no longer occupy the same space as other groups in the zone. After completing their objectives, they exit the Instance and rejoin the normal, populated game world.


I understand you can't tell us too much about your project, but I hope something I've mentioned here is of use to you!

 

[suszterpatt]

Answers 1 & 2: from the very beginning, you can accept objectives whereever there are available ones. In that regard, there's no distinction between new and old players. However, objectives are not generated all over the world. Imagine a war between two countries: the exciting stuff happens on and around the front line, so that's what we want players to experience.


Answer 3: We're trying to cater to cowboys and teamplayers alike. There are means to form small or large teams in the game, and different objectives can only be accepted by individuals or teams of various sizes. This way we have better control over players. As for making payment changes seem fair, I'm sure we can think of a way to do it, so that should be no problem.


Answers 4 & 5: It'd be very hard to give a timeframe on how long a player is assigned to an objective, mainly because of the skill differences and general human factor involved. We're aiming for a single objective to be relatively short, about 10-30 minutes if performed against moderate resistance. However, stalemates might form that could slow down progress almost indefinitely, and it's possible that an objective will remain active for days or even weeks by its nature, while players assigned to it come and go as they please. A player might hop in, kill a target in 15 minutes and move someplace else, or he might spend all night trying to fend off enemy attacks in the same spot. This is why we have player limits on objectives, and yes, that means exactly that no more than a given amount of players can be assigned to the same objective at any one time. This will make sense in the game's context, and as per the above, players will have a wide variety of objective choices at all times.


As for instancing, we'll have to do that in some form or another, if for no other purpose than to provide reasonable connection times all over the globe. It would be a pretty poor decision to have a single centralized server farm to which people from the other side of the world are forced have 500 ping

 

[Foxery]

Originally posted by: suszterpatt
As for instancing, we'll have to do that in some form or another, if for no other purpose than to provide reasonable connection times all over the globe. It would be a pretty poor decision to have a single centralized server farm to which people from the other side of the world are forced have 500 ping

Well, yes, but Instancing goes one step farther.
Players select a "Server" which is in their time zone. After that, the real number of CPUs their data is passed between is invisible to them. If your Instanced zones end up being extremely popular, as they are in Warcraft, you can buy more servers to host more Instances. New groups are moved to whichever CPU happens to be free, and the players never know the difference.

I'm tapped out on ideas, but it sounds like you are on the right track and dong very well. At some point, you will simply have to hold a Beta test to watch how real people behave, and make further adjustments from there.