Guild Wars 2

I’m sure I’m not the only person who gets irked by the requirement to complete all WvW maps for 100% world completion. Simply put, some of us don’t like getting zerged or playing for the competitive aspect. While it doesn’t do harm to require exploration of the mists for world completion, players really shouldn’t have to go out of their way to join a dominating server to complete a rather basic achievement.

The latest patch gives losing servers a way to gain grounds. However, it’s still not enough when it comes to map completion. Why? Colors.

I have been patiently waiting for our server to get green for the past few weeks (maybe a month now), and it really ticks me off to see our server land with either red or blue again each time WvW resets. I’m from a tier 1 server (Jade Quarry), and the match up each week just never changes. It’s always Sea of Sorrows vs. Stormbluff Isles vs. Jade Quarry. Week after week. For the past month now, Sea of Sorrow has had green, and Jade Quarry and Stormbluff Isle kept switching back and forth between blue and red.

Needless to say, this encourages server hopping for the world completion. Stonemist Castle would be flipped a few times…but we can never seem to get the SoS borderlands map. In the end, I decided to hop over to SoS for a week (now that ArenaNet has expanded server size as of Wintersday patch) just for the world completion.

It’s pretty ridiculous…and it’s something that can be solved by simply guaranteeing a rotation system of colors if the match ups don’t change often (and they tend not to).

The breakout mechanic is only going to make this harder because the tower nearest each servers spawn on enemy borderlands is going to be very difficult to hold for any length of time.

How would your rotation work when servers shift from one bracket to another ?

I think randomizing the colors each WvW reset would be a simpler option to produce the same result.

Green is 1, 4, 7 Blue is 2, 5, 8 Red is 3, 6, 9 so simple make sure your server gain in rank and you switch color

Shadow.3475:

Green is 1, 4, 7 Blue is 2, 5, 8 Red is 3, 6, 9 so simple make sure your server gain in rank and you switch color

That doesn’t help the top WvW server.

Snoring Sleepwalker.9073:

The breakout mechanic is only going to make this harder because the tower nearest each servers spawn on enemy borderlands is going to be very difficult to hold for any length of time.

How would your rotation work when servers shift from one bracket to another ?

I think randomizing the colors each WvW reset would be a simpler option to produce the same result.

Randomizing the colors each WvW reset would be simpler, but point of me asking for some kind of cycling system is that there should be some sort of heuristic to try to ensure that no world will have the same color as what it has gotten in the past 2 rounds – and that can vary based on implementation. Currently, there is obviously no such system, which results in even worlds in the same tier getting the same color round after round.

It doesn’t necessarily have to be a strict cycling system, per se. Since you asked, I came up with an algorithm/pseudocode (warning, not for the algorithm/programming illiterate) that will guarantee that at least 1 world in any round will get a different color from what it has gotten in the previous 2 rounds – with an example that follows (if you want to skip straight to that):

for world in worldMatchups:
    world.colorHistory = [null, null]

round = 0

do:
    if round > 1: 
        round = 0
    // a list containing the possible colors to choose from
    unobtainedColors = [red, green, blue]
    worldMatchups.shuffle()

    for world in worldMatchups:
        color = selectColor(world.colorHistory, unobtainedColors)
        unobtainedColors.remove(color)
        world.colorHistory[round] = color
        world.color = color

     round += 1
while true

selectColor(colorHistory, unobtainedColors):
    unobtainedColors.shuffle()
    for color in unobtainedColors:
        if color not in colorHistory:
            return color
    return unobtainedColors.first() // all unobtained colors are in history...so just take the first one (it's randomized already)

An example of how the above would work…let’s take JQ, SoS, and SBI as example world matchups.

Round 1

Pure randomized ordering of who to pick colors. Let’s say the order is: JQ, SoS, and finally SBI.

JQ has 1/3 chance at getting green, blue, or red. Suppose it gets blue. After this, SoS has 1/2 chance at picking either red or green – assume SoS gets green. Now SBI is left with 100% chance at getting red. This is the end of round 1. Save the current result into each world’s history (of up to 2 prior rounds). So at the end of round 1, we’ll have:

JQ: blue
SoS: green
SBI: red

Round 2

We do the exact same thing as last time in randomly selecting the order in which the worlds will pick colors. Let’s suppose that the order this time is SBI, JQ, SoS.

Now each world will randomly select a color such that if a color chosen is already in its history, that world will roll for a color again until the possible colors to pick from have been exhausted or when the world gets a color that was not in its history, whichever comes first.

This means that SBI can only get green or blue this round, since red would already be in its history. Let’s suppose SBI gets blue this time. Now JQ’s only choices, based on its history and what SBI has chosen already this round (blue), would be green or red. Suppose JQ gets green. This leaves SoS with red. So at the end of round 2, the history of colors would be as follows:

JQ: blue, green
SoS: green, red
SBI: red, blue

Up to this point, no world has been knocked into another tier yet. If this continues, the next round will ensure that JQ will get red, SoS blue, and SBI green. We would then replace the first item in the history of each server by this, and the next round, we will replace the second item in the history…then first, then second, so on and so forth.

But let’s suppose that in round 3, JQ gets knocked to a different tier and swaps places with Dragonbrand, whose history is identical to that of SBI’s. We want to ensure fairest selection such that all worlds are given different colors if possible. Let’s focus on SoS, SBI, and Dragonbrand (since they’re in the same tier…the same logic can be applied to JQ and whatever other two servers it gets paired with). So at the beginning of round 3 (counter in the algorithm would actually now reset to 0), the history for our world matchups are as follows:

SoS: green, red
SBI: red, blue
Dragonbrand: red, blue

Again, randomly select an order for worlds to pick colors. Suppose the order this time is SoS, Dragonbrand, and SBI.

Based on the algorithm, SoS would get blue because it would retry if it rolls either green or red (since both are in its history). Now Dragonbrand can choose between green and red – and it will select green because green is not in its history, leaving SBI with red again. In this sequence of world selection, the algorithm was able to ensure that two worlds got different colors for all 3 rounds.

You can experiment with other scenarios. And while this algorithm doesn’t completely prevent repeated colors each round, it does help ensure that in any particular round, at least 1 world will get something different from what it has gotten in the previous two rounds – which is better than a pure random selection.

How will your algorithm work when ANET adds new servers that have no color history and they get placed against servers which have a color history ?
What are the initial values ?

What happens if the random number generator goes strange and gives one server a long run of only two colors ?

Another algorithm is one that remembers how many times each server has had a specific color. When it comes time to assign the colors, the algorithm finds the server and color combination that has come up the lowest number of times. That combination is then assigned for the upcoming round.
The algorithm then does the same for the remaining servers.

When there is a tie, use a tiebreaker method. How is unimportant. Randomness is not required.

This method guarantees that every server will go through all colors eventually. If the brackets don’t change, each server will go through the following:
Match 1: Random color
Match 2: Random color that wasn’t used in match 1
Match 3: Final color
Then the cycle repeats. Though the color for Match 4 is only guaranteed to be the Match 1 color if the tiebreaker method is a non-random method.

New servers are easy to add in, as their history values start at 0. Which means that they are going to be cycling their colors even more reliably than older servers, because the new servers will always have significantly lower history numbers.

If a server stays away from one color for a while, then the other servers history numbers for that color will exceed its one. So all servers are guaranteed to go through all colors in time.

Snoring Sleepwalker.9073:

How will your algorithm work when ANET adds new servers that have no color history and they get placed against servers which have a color history ?
What are the initial values ?

What happens if the random number generator goes strange and gives one server a long run of only two colors ?

Another algorithm is one that remembers how many times each server has had a specific color. When it comes time to assign the colors, the algorithm finds the server and color combination that has come up the lowest number of times. That combination is then assigned for the upcoming round.
The algorithm then does the same for the remaining servers.

When there is a tie, use a tiebreaker method. How is unimportant. Randomness is not required.

This method guarantees that every server will go through all colors eventually. If the brackets don’t change, each server will go through the following:
Match 1: Random color
Match 2: Random color that wasn’t used in match 1
Match 3: Final color
Then the cycle repeats. Though the color for Match 4 is only guaranteed to be the Match 1 color if the tiebreaker method is a non-random method.

New servers are easy to add in, as their history values start at 0. Which means that they are going to be cycling their colors even more reliably than older servers, because the new servers will always have significantly lower history numbers.

If a server stays away from one color for a while, then the other servers history numbers for that color will exceed its one. So all servers are guaranteed to go through all colors in time.

It’s not a problem if Anet adds new servers with no prior history. The algorithm will still work. The initial history, as described in the algorithm, is an empty list. At that state, if that server gets to pick its color first, it will select one at random – in which it won’t care because it has yet to see any colors. If that server gets to pick its color second, it will still have 2 colors left to pick from – of which it doesn’t care for the same reason as well. Same logic applies if it were to pick last. If that server now has 1 color in its history, it will now have a 100% chance of not picking a duplicate color if that server gets to pick either 1st or 2nd. Only in the case when it is selected last (1/3), will it have some probability of getting a color that it has already seen in the past 2 rounds. After that, it will be as fair as any old server.

RNGs breaking should be the least of your concerns as an algorithm designer when designing a randomized algorithm. There are many good ones out there in a myriad of libraries. If you’re arguing against the use of randomization at all, then that’s a different story – I was merely giving an example heuristic of what could be better than complete random selection – something you proposed in your response to my initial post.

I actually like your proposed algorithm just now…except there could be a problem of prolonged stagnation for older servers vs. newer servers if there is already some imbalance created among the older servers as a result of tier-changing and tie-breaking, whereas I think a more randomized (but not complete) algorithm that only looks at a small window of previous history is less likely to cause starvation/stagnation.

On a side note, I find this problem somewhat similar in nature to the ETA estimator problem…where a decision (or calculation) is to be made based on random events (e.g. sudden slow-down or speed-ups vs. new servers being created or servers jumping tiers) such that the outcome meets some expectation based on prior data.

While I hate the inclusion of WvW in world completion and the daily…(seriously the last thing WvW enthusiasts want are those who don’t want to be there taking up space from those who will contribute)…this is great to speed the process up.

Mystic, thank you as well for actually showign both the algorithm and what it would accomplish.

The only use of world completion is for the gifts of exploration. So, as long as you go through all the colors in less time than it takes to get all the other components of your Legendary weapon, you are getting through them fast enough. Faster won’t help. So randomizing them will be sufficient.

Randomizing the colors is a nice simple algorithm that will work in all cases. Rotating colors won’t work when matchups change, other algorithms proposed are too complex.