Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[AdamH]

SECOND ROUND OF RESULTS

I've made some slight tweaks to the MST algorithm to charge the cheapest connection to a city you've already built in instead of just making it free. I also fixed a couple of error cases/bugs in the underlying functions while I extended their use...

...by simulating a 4-player game, similarly to what theorel has done. Turns out it wasn't that much work. In doing this I've thought of some interpretations of this data.

The simulation should be seen as a more accurate version of the MST. For the purposes of what I envisioned for this article, I'm going to use the Simulation data. On the other hand, I think there may be some information we can get from the differences we see between MST and simulation, so I computed some extra numbers. Anyways, here's a screenshot of the spreadsheet, which is available in the grid.zip file (linked to in the OP) along with all of the source and associated files that went into making this.



The bars on the graphs represent the range of total map costs you can expect to see in a 4P game. The green dots are just the midpoints of those bars, and the maps are sorted by that value. This should give not only an ordering of the maps but also an idea of the variance in those costs you can expect to see in different games on those maps. As expected, the maps with only five regions have lower variance (Benelux, Baden-W..., and Japan) but hey, look and Spain/Portugal! Who would have thought?

Some more on the numbers behind this, for those who are interested:

So the starting positions of the four players affect the total cost of the map. I thought long and hard for how to deal with this, and while I think there can be some knowledge gained from playing around with this, for the scope of this article I thought it only right to take the minimum of all of those results, to simulate players who are actually playing well. If there are better ideas out there, I'd love to hear them.

So let's try every permutation of starting positions! Well this thing simulates one game in about a half second, so that will take... 85 hours per map. OK then....

I decided to just take 500 random permutations and find the minimum overall cost out of all of them. After letting it do this for about an hour, 500 seemed like it got close enough so there it is. Maybe I could have optimized this thing for performance, but hey normally I get paid to do this stuff so yeah I saved the particular set of starting locations and costs for each player in the spreadsheet for reference.

The way the cities are bought. Well, they just take turns building their cheapest connection. I decided Step 2 would start at 6 cities and Step 3 would start at 12. In Step 1 or 2, if a player has no legal building options or their only legal connections cost too much, they'll just skip buying that round and buy extra the next chance they get. If it's Step 3 and there are no legal options left, then that particular game is thrown out of the analysis.

The difference between the MST and Simulation results: well there were some changes. Of course the algorithms were different so we expect different results, but from a high level here's what I came up with:

"The MST Analysis simulates 100% collusion by all players to spend as little money on cities as possible. The Simulation Analysis takes a baby step towards simulating competition between players."

So maybe that means we can get a result from looking at the differences between the two sets of data. I feel like we could be going beyond the scope of this article here, but whatevs.

Every number went up here, so how much it went up reflects the effect of competition on that map; the more it increased, the more important board position must be on that map, so that's what the "%chg avg" column means. I computed how much the min+max score should have gone up based on an average of all maps and compared that to the result from that particular map. The big numbers (green) here mean that competition on that board did not result in a huge increase. These maps are where board position is less important (if I'm interpreting this correctly). The big negative numbers (red) are where we expect competition over board position to play a larger role.

The "%chg var" column (uhh... that ended up not being a percentage. Hmh.) measures how much those Range-Bars grew or shrunk, since I noticed a big change on some of them. The green numbers mean the bars got bigger and the red numbers mean the bars got smaller. I don't know what this means, so maybe there's a more useful number to calculate here. I might need to think about this some more, but suggestions are welcome.

[theorel]

I coded stuff at the office during down-time.  And worked from home all week (due to illnesses), so I still don't have the code.

I'm trying to figure out the differences in our US results though.

For starters, I assume you're actually charging for cities, which I didn't do.  So, you have to add 680 to my costs, straightforward enough.
For min-cost map that takes it to: 1209 for me vs. 1207 for you.  Okay, that's reasonably close, starting city could have an impact there, I didn't try all of them, maybe even which route you took in ties could have had an impact.

For the max-cost US map though, you've got 1406, while I got 1343.  That's substantial.  So, I'm wondering where the bugs are.  I can chart you the connections used once I have the code again to help find them...could even just be in the connections matrix you've done.  Or it could be in my connections stuff somewhere.

For the competitive version, what did you minimize?  Total cost, or maximum cost?  Total cost is still collusion in start position.  Even maximum cost is to some extent.

If you minimized over total cost though, then I'm confused again as to why my min-cost is some 50-points lower here.  Again, I can get all the connections used to verify when I'm back in the office, hopefully next week sometime.

[AdamH]

Once I get information from you I can take a look at my code to see where differences are.

For the competitive version I minimized total cost, if you look in the .xlsx below where that image was taken you can see the starting positions and the individual player costs that correspond to the total cost seen there, in case that helps.

The text files contain edge lists for each map. I didn't denote which regions I used or which cities correspond to the different rows/columns but it's not too hard to figure it out if you want to. I didn't check these for accuracy so if we suspect that's the issue then I can verify it.

OTOH, it's easy to see if that's the issue, either you use my text files as input or I use whatever input you used and we run our programs.

[theorel]

Okay, I'm sick again and not at work...so I just implemented it at home.

I found an error in your min-cost map.  You have the New Orleans-Jacksonville connection at cost 6 instead of 16.

[theorel]

Okay, I've got it all in place now.  So, let's see:
1. For the quasi-competitive implementation I was allowing a single player to build a city multiple times.  Removing that results in things similar to your results.

2. For USA-Max, non-competitive.  If I choose index 14 to start with I get your result.  However, choosing something like San Diego (index 27) results in the costs I saw before.  I noted this already in my write-up earlier.  Starting city matters if you're not doing a straight MST.  (P.S. that means that your max for USA should be 1343, not 1406)
(here's the full transcript for the 1343 build: text file)

3. For competitive, I'm still getting better results than you though.  I realized I wasn't allowing to build through cities (which gave better results, because competition was lessened).  But with that in place, I'm getting the following results for USA.
USA_Max
Santa Fe
Phoenix
San Francisco
Kansas City
1421

USA_Min
Minneapolis
New Orleans
Dallas
Houston
1245

[theorel]

Oh, and here's the code if you want it.

It should parse all of the files that you posted.  If you add a name line above each line, it will then name all the cities.  If you add a "Name, Color" line it will parse that, and then you can enable/disable the various sections of the map using the enum.

[philosophyguy]

Now that we have some data, are there any discoveries that should influence how I play? I'm not sure what to do with these graphs. Don't get me wrong—they're quite pretty. I just don't know how they impact the ideal playstyle.

[AdamH]

theorel - I'll take a closer look at your code when I get a chance

philosophyguy - I'm thinking of two things that can be gained from these results. First, a gauge on how expensive a map can be, meaning expensive maps will lead to longer games where efficiency may be valued more than just powering lots of cities. Also maybe we can figure how important board position can be, since there are times when you want to buy a plant and you also want to build more cities; this may help prioritize.

[theorel]

So, there's several things we could potentially analyze here...and several ways to achieve that analysis.  We should probably have a bit more discussion on the matter of how to achieve the analysis we're looking for.

Note on including city costs:
If we're building 68 cities, then every map has $680 added in.  This results in maps appearing more similar than they actually are.  I personally think that this is bad.  Unless you're trying to figure out how much money a player is expected to spend on cities for a given map, it's not useful to include it.  (Note: that is potentially useful).  So, the question is: are we analyzing the maps relative to each other, or as absolute quantities.  If relative to each other, then I believe we should reduce the commonalities in the maps.  This will highlight their differences which is what we're interested in.

(Note: regardless all the analyses will be relative, so it's more a question of if we're comparing say 1.55 and 1.3 or comparing 1.11 and 1.06)

So, that's all I have to say about the city costs, I prefer leaving them out.
Let's talk a bit about analyzing the maps:
1. Relative Cost:
We could use the true MST here.  It gives nice consistent numbers, and it gives generally smaller numbers.  They're easy to compute, and "cleaner" to compare.
Disadvantage: you only build each city once, and must build each city once.  It doesn't take into account maps where some city might not get built.
That takes us to the 68-city "MST".  This does not give consistent numbers, so we should technically compute it for all starting cities and find the minimum in order to introduce consistency.  The numbers are bigger.  The result seems less "clean".

I don't think that the disadvantage on the MST is really there.  I think the 68-city MST will build every city at least once.  A "cheap" area getting built 3 times isn't that different from 2 moderately expensive areas being built twice.  I like the clean truth of a true MST over the simulated mess of a 68-city quasi-MST.

2. The impact of competition:
This is where the 68-city MST is really useful.  If we take it as an approximation of a "cooperative" game.  Then we can use the 4x17-city MST as an approximation of a "competitive" game.  I think that's a fairly accurate prediction of the impact of competition.

Currently we're doing 1 city at a time (I think that's what AdamH did?).  If we did 1 player at a time that might give information about value of turn order (how big is the difference between player 1 and player 4).  This could give a feel for impact of board position.

We could also analyze the actual board positions, seeing where the optimal starting positions are.  We don't do this when we minimize total cost, but if we minimize individual costs we can determine "ideal" starting positions for each player (note: this would still assume either completely equal or completely unequal development, which is not true in game and could certainly impact the value of starting positions.  It also ignores whether certain bits of expansion are affordable).  Anyways, it's not perfect but I think it could be an interesting basis for some discussion.

[AdamH]

Thoughts on this:

I think it would be useful for me to go back and figure out the city names for each of my USA maps, that way it will be easier to compare results, specifically talking about starting positions. I'll work on providing this list.

I can take a look at the way starting position affects MST results. It might be interesting to see what the final board looks like in terms of what's occupied -- I remember printing it out for USA when I was debugging the script and saw they all had at least two cities built, but if it's the same network we end up with, then our results should be similar. I think our results are similar enough as it is, since our algorithms for computing the MST are still slightly different.

I think the interesting discussion left revolves around the numbers we can get out of this stuff:

The $680 we begin with: in the cases where it matters, I can subtract it out in Excel if needed.

Answering the question "which maps are more expensive?" I think is pretty much done by the numbers we have already. Which one to use? I suppose the simulation is the closest thing we have to a real game of Power Grid so far, so I guess we can use that one.

Answering the question "how important is board position on a given map?" may benefit from a little more number crunching. Part of me wants to use the numbers I have already to get some more results, and I think I might be able to do that, but what are the other numbers we can talk about?

Given three other players have started in certain locations, where do you build that minimizes your total cost? This number could be interesting, but I wonder how accurate it would be without a more robust simulation of the game? How do you more robustly simulate the game without factoring in other parts of the game (resource/power plant cost)? I wonder if we can get a useful number here.

[AdamH]

Well this hasn't been touched in a while, I'm wanting to get it moving again so I tried writing a draft of the article that I'd put on the blog. I'll probably post it in a week or so, so if there are any clarifications or suggestions, they are welcome.

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

Some maps have more expensive connections than others. Sure, this may affect everyone equally (or does it?) but adjusting your game to account for this can mean the difference between a win an a loss. This article will help you identify which maps are cheaper and more expensive, and give you a push in the right direction for how to prioritize efficiency in power plants and board position. A more detailed discussion of this can be found here [TODO: make this a link to this thread], but be warned, the math can be a little much for the faint of heart.

Results:

I'll start by showing you the chart that I now carry around in my Power Grid box with my other cheat sheets:

http://www.adamhorton.com/files/Map_Compare.png [TODO: make sure formatting is correct here]

Out of the 16 maps for the game, each are compared and ranked for their connection cost in two different ways explained in the thread. If you just want to look at one of them, I suggest the bottom one labled "Simulation Analysis", which was created by actually simulating many games of Power Grid.

There's a green line in the middle of all the bars, which is how the maps are sorted. This is an approximation of the average cost of building cities and connections on each board. The bars show a range of how much this number can vary depending on which regions of the board are being used in a particular game. If you take nothing else away from this article, know that this is a decent way to rank the boards according to how much money you'll be spending on cities and connections.

What does it mean? Well more expensive maps tend to lead to longer games; slower development of cities and more turns until the game is over. In the most general sense, efficient plants are better here because you'll be able to benefit from them for more turns, so expensive map -> efficient plants are better.

The other number that I feel OK stating a result for is the "%chg avg" number. This number was derived by comparing the two different methods used to calculate total board cost, with one of those methods attempting to simulate some competition between players. The numbers are an attempt to quantify the impact of competition on each board.

Generally speaking, the positive (green) numbers mean that competition was a larger factor, and the opposite for the red numbers. It's a loose conclusion, but it seems that prioritizing board position on the green boards will give you more benefits than the red boards.

This topic is still open to some discussion, of course. We can surely calculate more numbers and try to find some meaning to these numbers that applies to game play, so I encourage you to visit the thread if you want to read more detail or contribute.