webDip dev coordination forum / public access todo list
It is currently Fri May 25, 2018 4:26 pm

All times are UTC

Post new topic Reply to topic  [ 8 posts ] 
Author Message
PostPosted: Sun Feb 15, 2009 3:55 pm 
Site Admin

Joined: Sat Jun 28, 2008 6:24 am
Posts: 892
Id be interested to get some ideas on a country balancing algorithm idea, but to avoid repeating past problems I'll try and specify a bit more precisely what the algorithm should do:

Be non-deterministic
i.e. Knowing all the inputs doesn't mean you know who will get which country, randomness still plays a part. This way it's still random as the rules say, and you could still be Italy 5 times in a row, but it'd just be very, very unlikely (more so than it is now, that is)

Be fairly efficient
Speed isn't a huge deal, because it's only done once per game, but it shouldn't take too long or get massively longer as it deals with players who have played lots of games in the past

Be simple/understandable/elegant
Something that people will be able to quickly understand, and see why it works. It should also be simple to code and not too convoluted

Balance countries fairly
The more recently and frequently a player has played as a certain country the less likely they are to get it this time

(Probable) inputs: (Open to change if needed)
For each player a list of previous countries ordered from most recent to least recent (including countries in active games)

(Unfinished/internal) output:
For each player a country-by-country list of probabilities of the likelihood of that player being that country.
For each player the total probabilities add up to 1, and none of the player->country probabilities are 0
e.g. PlayerA: England: 0.1, France: 0.2, Germany: 0.1, Austria: 0.2, Italy: 0.3, Russia: 0.05, Turkey: 0.05
PlayerB: England: 0.2, France: 0.05, Germany: 0.2, Austria: 0.1, Italy: 0.05, Russia: 0.3, Turkey: 0.1

(Final) output:
For each player the country they'll be assigned to in the current game

Hiccups/potential problems:
  • It needs to account for Italy & Germany being taken in 5/6 player games
  • It needs to balance randomness with fairness; it can't say "Player X has played as country Y the least number of times therefore player X gets country Y"
  • It has to cope with new players, who have played as few countries. If a player has only played as Italy that doesn't mean they are definitely not going to get Italy next time, that would be deterministic

If algorithms/ideas are posted I may borrow pieces of them or use them whole, but I'm happy to implement it because the design will probably be trickier than the implementation (hopefully)

Thanks for any input

PostPosted: Sun Feb 15, 2009 5:22 pm 

Joined: Wed Oct 08, 2008 12:47 pm
Posts: 726
Well, thats a good setup. I was talking to Ghost about it, and I expect he'll submit his conclusions soon (hopefully including my comments!).
I'll try and give an individual response later on this evening

PostPosted: Sun Feb 15, 2009 7:31 pm 

Joined: Sun Feb 15, 2009 6:49 pm
Posts: 3
Quick thoughts on country balancing:

1. First, for each player, assign a number to each country based on how much they've played that country recently. Perhaps the easiest way is to use some kind of exponential damping: First pick a damping factor alpha < 1. (This is so more recent games are more heavily weighted.) Assign a "running total" for each country; the country played in the most recent game gets a value of 1. For the ith previous game, increase the total of the country played then by alpha^i.

If you pick alpha = 0.9, say, the country from your previous game gets its total increased by 0.9, while the one from the game before that gets its total increased by 0.81. The assignment from 10 games ago affects the total (roughly) 35% as much as your most recent country, one played 20 games ago affects it 12% as much, and one played 50 games ago only 0.5% as much. So all games affect the total, but the more recent ones do so more heavily. Higher values of alpha will increase the relative importance of older games, lower values will increase the relevance of more recent games. (alpha=0.5 will mean that the assignment from 10 games ago will affect the total less than 0.1% as much as the most recent game. I might pick alpha=0.95)

The other advantage of doing this is that after the first time, it's _very_ quick: for the next game, simply multiply _all_ country totals by alpha and then add 1 to the country played in the previous game.

2. So now we have a bunch of numbers like: T 1.4, E 1.6, R 2.1, F 2.3, G 2.7, A 2.9, I 3.2. (The higher numbers corresponding to countries played often recently.)

These can be converted into probabilities in a reasonable way (for instance, take reciprocals and scale so the sum is 1. Add a small fudge factor if you've never played a country, to avoid dividing by 0.)

3. The next concern is that it several players might end up with a high probability for (say) Turkey. (If a player has high probability for Turkey, I'll say she "wants" Turkey with that probability.) If you and I both want Turkey with probability 0.9, and nobody else does, there's still no fair way to assign it such that we both get it with probability 0.9, but a reasonably fair outcome would be for each of us to get it with probability roughly 1/2, right?
This is the step I thought through the least, but perhaps one option would be to order countries from most to least "wanted", and then use the following algorithm:
For (i = most wanted to least wanted country)
Scale uniformly so the sum of probabilities for country i is reduced to 1.
For (j = each player)
Let p_j denote the original probability for player j to get country i, and p'_j the new (reduced) probability.
Distribute the probability p_j - p'_j to the remaining countries (that is, country i+1 onwards) in proportion to their probabilities for those countries.

At the end of this process, you get a "doubly stochastic" matrix, which is one where all entries are between 0 and 1, and the sum of each row and column is 1. (So you can interpret the row for a country as the probability that the various players get that country, and the column for a player gives the probabilities for that player getting each country.) Now we have a natural probability distribution.

4. Finally, pick a random assignment such that the probability player j gets country i is the (i,j)th entry in the matrix. I'm not sure of the _best_ way to do this, but there are certainly ways it can be done. My concern with the way I have in mind is whether it correctly deals with correlations, but I can think about this, and ask some friends who work in related areas. (That is, ideally, my getting Austria should not be highly correlated with you getting Germany. Some correlation is unavoidable (after all, if I get Austria, you don't, so that means the probability that you get a country other than Austria is now slightly higher), but the question is how much it can be minimized.)

Anyway, those are just quick thoughts; I hope they make sense. I was in a hurry, so the ideas may be unclear in places. One may be able to improve them, and add some hacks to simplify computations. (For example, each probability could be a multiple of 0.05 because the difference between a 0.38 probability and 0.39 probability isn't terribly significant, right?)

For a (rough version of a) quick-and-dirty explanation on the forum, one could say that each player gets a number for each country, such that countries played more often and more recently have higher numbers. We use that to compute the probability you should get each country, with the countries with lower numbers having higher probabilities. So, when a new games starts we have a list of 7 sets of probabilities, one for each player; equivalently, we have a matrix of probabilities. There's one normalizing step to make sure that the total probability for each country is 1, and then we pick a random assignment such that you play a country with the probability from the matrix.

Oh, I forgot to add that removing Italy/Germany is easy; just ignore the relevant totals from the initial list for each player.

PostPosted: Sun Feb 15, 2009 9:49 pm 

Joined: Wed Oct 08, 2008 12:47 pm
Posts: 726
A nice idea. The only real I see is that would require 7 more database fields for each player, were you to cache those running totals. Obviously there isn't actually a need to cache them, but without it the script would surely be much slower.

As a possible alternative, perhaps you could just work out the probabilities for each country, one at a time:
First calculate the proportion of each players games that *haven't* been <nation_in_question> out of the total of all their games as nations that are still 'free', ie 1-<games_as_nation>/(<total_possible_games>+α) (where α is a small number, primarily to stop DIV0 errors, but it could be larger to increase the randomness of the system for newer players)
Then, sum these (will give a value between 0 and 7)
Randomly select a number between 0 and <sum>, and find out where it falls in the distribution.
Set this player as <nation_in_question>

For games with a CD start, just apply this first, removing the options from the valid nations.
This might not be perfect, and I haven't tested it thoroughly, but I can't see any obvious failings, and it would be very easy to implement.

PostPosted: Sun Feb 15, 2009 11:05 pm 

Joined: Sun Feb 15, 2009 6:49 pm
Posts: 3
Fig, you're right that it would need the 7 extra fields for each player to save time.

Does the database currently have, for each player, an entry for the number of games played as each nation? If not, then you would need to examine every game anyway. If that has to be done, then the damping trick isn't more expensive, and it has the nice feature that recent games count more, so you tend to avoid streaks.

I like the rest of your proposal; it's significantly less complex than mine. Since we only want rough balancing (after all, the precise probabilities are based on the tradeoff the developer chooses between randomness and balancing), it's not worth the whole "pick a random assignment from a doubly stochastic matrix" thing. I do research in algorithms, and tend to go overboard when I find a 'cute' question. My apologies for going on at such length. (It's actually quite an interesting research question in algorithms and machine learning: Find a probability distribution over assignments such that the probability of assigning player i to country j is entry (i,j), while maximizing the entropy (= randomness) of the distribution. Find an algorithm to efficiently pick an assignment from this distribution.)

In a setting where there's money riding on the outcome (for example, you want to design a "fair game" for a casino), then the precise probabilities matter, but not for phpDip.

PostPosted: Mon Feb 16, 2009 9:39 am 
Site Admin

Joined: Sat Jun 28, 2008 6:24 am
Posts: 892
Interesting ideas, the 2. part was what I was struggling with too; how to balance it out when two people want Turkey say. To be honest I don't get exactly what you mean in your explanation (or what a stochastic matrix is), I'll come back to look at that some more

For 1. I had an idea though (i.e. how to generate the per player per country probabilities):
(Looking at the attached pic below will probably explain it better than the pseudo-code)

For each player
    Each country starts with a probability of 1/7 of being selected

    For each country which has been played, oldest first
        The chance of being that country is divided by half
        The probabilities are scaled back up so they add up to 1

The attached doc shows how the probabilities would change for each country played in the past (in blue) going from 0 games to the final game

It also has the advantage that you can calculate and save the probabilities for the next game from the probabilities for the current game, without having to go over every game played for every member each time

For fig's idea I like that you can keep running totals and that it's simpler, and that it doesn't have a part-1/part-2 split, but it doesn't seem to make older games have less of an influence than more recent ones, and that's something that I think would be good to have

But that just gets the probabilities per member, I'm still not sure about the part-2 (converting probabilities per member into choices)

Anyway just throwing another idea out there, I've still not wrapped my head around the ideas posted so far so I'll have to get to grips with them all before I decide which I like (and I think nitish's part-2 is compatible with my part-1, so I'll have to check that out)

out.png [ 9.18 KiB | Viewed 3141 times ]
PostPosted: Mon Feb 16, 2009 1:37 pm 

Joined: Tue Aug 26, 2008 8:46 pm
Posts: 249
In response to nitish's idea.


Exactly what I had suggested to figlesquidge, Except I was dividing by 1.2 instead of multiplying by 0.9
Also, to avoid the "small fudge" when a country hasn't been played, you can begin each country on some constant (Would have to be decided, might be 0.000001 if you want to just make the code simple and get around the problems with zero, or 1 or more if you want to increase the randomness early on). That also means that you never get a probability of zero:

If you have E/F/G/I/A/R all not played, and one game as T, then under the originally suggested system P(T)=0

Or determinism:

E/F/G/I/A/R all played once, and no game as T, then under the originally suggested system P(T)=0


Yeah, reciprocals and then Scale to 1*. If you want to make a minimum chance of any nation in any game, just Scale to some number less than one, and then add a constant onto each.

*Could actually be any constant here.


Take the numbers for the probability of getting Austria, for each player, and assign Austria.
Then take the numbers for the probability of getting Russia, for each remaining player, and assign Russia.
et cetera...


I reckon however, it would be better if you made it so that the amount the current games mattered was disproportionately high, so you can do a similar thing to above, but at 2. instead of scaling to one, scale to some number less than one, then add on a function of the number of games being played as that country, having been scaled to make things sum to one of course.

PostPosted: Mon Feb 16, 2009 4:31 pm 

Joined: Sun Feb 15, 2009 6:49 pm
Posts: 3
Kestas, the stochastic matrix bit was overkill, so it probably doesn't matter. (For the record, if you're curious, a "doubly stochastic" matrix is a matrix in which all entries are between 0 and 1, the sum of the entries in each row is 1, and the sum of the entries in each column is 1. It's called "doubly stochastic" because it has this sum-of-entries=1 property for both rows and columns, as opposed to only columns, say. If you've done a Sudoku puzzle, then you'll notice that if you divided all the numbers by 45 (which is 1+2+3+...+9), the sum of each row and the sum of each column would be 1. So that would be an example of a doubly stochastic matrix, which also has the sum of the 3x3 sub-grids being 1. Stochastic and doubly-stochastic matrices come up quite naturally in the study of probability and distributions, since the sum of the probabilities associated with the possible outcomes of an event is always 1, right?)

All of these methods can be implemented by storing 7 more entries in the database for each player, or looking back at the entire game history for each player at the start of a new game, right?

Kestas, I agree that it would be good to weight recent games more than old ones; both your method and the idea TheGhostMaker and I had are nice that way. I hadn't seen your method before, and I think it's a nice idea.

For part 2, I don't think we can do much better than Fig's/TheGhostMaker's idea without making it much more complex.

Perhaps a good way to pick an algorithm is to run several simulations. They don't all have to be integrated with phpDip; they could be standalone tests. I may have some time to try this at the end of the week, though I don't know if that's soon enough for you.

Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC

Who is online

Users browsing this forum: No registered users and 1 guest

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group