Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 2 [All]

Author Topic: Map Comparison Article  (Read 17689 times)

0 Members and 1 Guest are viewing this topic.

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Map Comparison Article
« on: May 08, 2013, 06:16:23 pm »
0

Some maps are more expensive than others. I can attempt some analysis of resource starting costs and refresh rates and compare maps for how much you can expect to spend on resources.

The connections, though, I'm wondering what a good metric is for determining which maps are "cheap" and which are "expensive." I know there will be a range of costs; remove the two most expensive regions, then the two cheapest and re-analyze. What I'm not sure about is what to use for a metric. I was thinking the average minimum connection cost between every pair of cities? I'll have to brush up on my graph theory and write a program that calculates this.

Are there any math people out there that might have some suggestions?

EDIT: All files I've used in the process of doing all this stuff can be found here and they are kept updated.

EDIT 2: First draft of the article for this can be found in this post.
« Last Edit: August 16, 2013, 09:56:10 am by AdamH »
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

Shiroiken

  • Swindler
  • ***
  • Offline Offline
  • Posts: 15
  • Respect: +4
    • View Profile
Re: Map Comparison Article
« Reply #1 on: May 08, 2013, 11:08:24 pm »
+1

You could total all costs and divide by number of connections. Make sure you ignore the "phantom" connections that would never be used.
Logged

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #2 on: May 14, 2013, 01:04:07 pm »
0

Math people, I know you're out there...

I've given this some more thought and a little bit of time with Python. I'm thinking a relevant computation to make would begin with the Floyd-Warshall algorithm, which computes the shortest path between all pairs of vertices (cities).

I want to do an analysis for 4+ Player games, which means that computing the extremes of how cheap/expensive the connections on a given map are means looking at four regions at a time. I want to analyze the four cheapest regions, and the four most expensive regions for each map; anything else (including boards with more regions) will be in between these extremes.

I originally thought that I could just average all of these numbers to come up with a good metric for how expensive a given map is. Unfortunately, I think this only a starting point at best. I've input the first four maps (USA, Germany, France, Italy) into a script that does this and I have a couple of concerns.

The most expensive part of Italy includes using all of the "boot" and cutting off the top, where most of the cheap connections are. This makes for a long, thin map, much like Japan, and the number I got was abnormally high. It was more than the highest for Germany, which seems to be a map where you'd expect to pay more. Floyd-Warshall puts a certain weight on connecting cities on opposite sides of the map, which you won't be doing in a game of Power Grid.

I'm wondering if there are some other metrics I can use, or some more sophisticated statistics I can apply to the Floyd-Warshall output that would be more effective than a simple arithmetic mean. Central Mean was suggested, which may be better.

Obviously I'll play around with a lot of numbers, but is there anything out there that could apply to this in a sound, theoretical way?
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2745
  • Shuffle iT Username: Watno
  • Respect: +2982
    • View Profile
Re: Map Comparison Article
« Reply #3 on: May 14, 2013, 05:13:35 pm »
+1

I think a good metric might be the weight of a minimum spanning tree (the cheapest way to connect all the cities). It can be found easily using Kruskal's algorithm (there are more efficient ways, but i doubt that's necessary).
An even better way to do it would be finding the cheapest way to connect k cities, which would also give information about the distribution of cost throughout the game. I can't think of any algorithms for that though.
Logged

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #4 on: May 14, 2013, 11:47:26 pm »
0

I wonder how much more work it would be to modify a MST algorithm to just simulate how much money 4 players would expect to spend while playing the game, factoring in the $5 cost for building the second house in each city... Once you build once in that city, increase all the connections in/out of it by $5 and let it go back into the MST until 3 cities have been built there.

...expect each player to build 17 cities. Hmm.... I think the algorithm should still hold, right?
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2745
  • Shuffle iT Username: Watno
  • Respect: +2982
    • View Profile
Re: Map Comparison Article
« Reply #5 on: May 15, 2013, 10:39:11 am »
0

For 4 players, just run the algorithm 4 times and add up (changing costs for the later runs). No idea how to get only 17 cities except for trying each combination of 17 cities, which takes  prohibitively long (n choose 17, better not).
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: Map Comparison Article
« Reply #6 on: May 15, 2013, 11:37:12 am »
0

An even better way to do it would be finding the cheapest way to connect k cities, which would also give information about the distribution of cost throughout the game. I can't think of any algorithms for that though.

It's NP-hard: http://en.wikipedia.org/wiki/K-minimum_spanning_tree
Logged

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2745
  • Shuffle iT Username: Watno
  • Respect: +2982
    • View Profile
Re: Map Comparison Article
« Reply #7 on: May 15, 2013, 12:16:56 pm »
+2

well, possibly P=NP, so it might not be that much of a problem. :P
Logged

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #8 on: May 15, 2013, 12:46:02 pm »
0

Hmm, well that makes things a little more difficult:

I wonder if we can get an approximation, though, since we eventually want more cities bought than vertices in the graph. Do you think it would work to construct a full MST, then just keep adding the lowest edge cost on the graph until we have 17*4 total cities bought. This could give a theoretical lowest-cost for 4 players all building to 17 cities, which seems like an OK metric to measure.

Problems: constructing the full MST to begin with assumes that one house is built in every city. I'm thinking of Benelux and Luxembourg, where I frequently see games where Luxembourg is never built. I'm wondering if this effect will be significant enough that we can't ignore it. My guess is we can. We could also just start from a cheap edge and assume we eventually end up with a connected graph that is actually minimum, since we're finding 68 houses in 28 cities...

Also, once three houses are built in a city, that vertex is effectively removed from the graph. I might have to think for a minute on how I want to perform that: I think you find all vertices connected to the one you want to remove by one edge, then for every combination of two of these vertices, you can overwrite the current cost to connect them with the sum of what it would take to go through the now-prohibited city, then just delete all of those edges.
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

Ratsia

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 168
  • Respect: +113
    • View Profile
Re: Map Comparison Article
« Reply #9 on: May 15, 2013, 01:22:31 pm »
+1

well, possibly P=NP, so it might not be that much of a problem. :P
A bit more relevant observation is that NP-hard does not mean impossible by any means. PG maps do not have that many nodes and in particular the in-degree of the nodes is very limited, so one could still be able to find the exact solution with feasible computational resources (too lazy to check the relevant literature). In practice good heuristic methods should also suffice here.

One possible measure for map cost would be to design a simple bot and let N of those play (a simplified PG where only building the cities matters) on the map at the same time. For example, a bot could always build 0-3 of the cheapest cities, with some balancing to make the bots with the least cities to be more likely to build more. This way the bots would (very roughly) simulate a proper game, and if you repeat the simulation L times you get some distribution representing the total cost the bots paid. Of course that's not a deterministic exact algorithm or even an approximative solution to any direct measure, but in practice such simulations can be quite useful. By modifying the bots one can verify how sensitive the measure is for the exact bot; if it is robust with respect to different kind of bots it should also be a good measure for real games.
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: Map Comparison Article
« Reply #10 on: May 15, 2013, 02:32:13 pm »
0

I don't know that game, but shouldn't the ST over all nodes be a reasonable approximation?
Logged

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #11 on: May 16, 2013, 12:18:44 pm »
0

Ratsia, what you are suggesting is probably very accurate...

First, that's a lot of work to implement all that -- are you volunteering to do it? :P (I'm kidding)

Second, that simulates competition between players. While that is likely a more accurate thing, it makes me wonder if I want to include that in this article.

Modifying the MST algorithm will create an approximation of a theoretical least total cost of building 68 cities. By its nature it assumes complete cooperation between players, or rather, absolutely zero competition for board position. So the number you want to compute is just a different number. Perhaps both numbers are useful?

So then can we assume, for instance, if we take the MST-based number, that competition over board position will not skew the relative cost of each map? Or must we say that competition over board position depends on other stuff (including the distribution of connection costs on the map independent of the MST)? I'm worried that it depends on so much stuff that has nothing to do with the connection costs on the map that it might vastly extend the scope of this article.

So what is the scope of the article? I guess the point was to give a general idea of how each map compared to the others in terms of overall connection cost. Is there something more specific we can be getting here?
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #12 on: May 17, 2013, 09:28:53 am »
0

I'm going to try and attach a file here. It contains all of the text files where I input the graphs for all the maps I have.

EDIT: The attachment to this post has been removed. The one linked in the OP is kept up-to-date

I'm still missing the two newest boards: Northern Europe/UK+Ireland and Quebec/Baden-Wurttemb​erg. I'm going to order them shortly; would you believe that I've only played two games on these boards (I've never even played Quebec/Baden-Whatchajoobie before!)

For each map, I looked at the board and decided using my powers of subjectivity which four regions would be the cheapest and which four would be the most expensive, and made a graph for each. In some cases it was difficult for me to tell, but I figure in those cases even if I'm wrong, it's not by much.

Also included is a Python script that I haven't touched in a week. It parses the text file, fills in all the connections that I didn't bother to put in (because my speedy implementation of Floyd-Warshall requires it, even though the graph does not have directional edges) then performs the All-Pairs shortest path analysis on it.

I'm planning to do what we've talked about with a modified MST, but haven't gotten around to it yet; but if anyone feels like doing anything with this stuff, go right ahead.
« Last Edit: June 05, 2013, 06:19:05 pm by AdamH »
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

theorel

  • Spy
  • ****
  • Offline Offline
  • Posts: 86
  • Shuffle iT Username: theorel
  • Respect: +57
    • View Profile
Re: Map Comparison Article
« Reply #13 on: May 29, 2013, 10:16:57 am »
+2

Okay, so I tried to do some stuff.
I made a tree in java, and did some simple hueristic MST-type stuff.

I've only done the US Map so far...but I might code up some more maps later.  I can't see the attachments AdamH put up, so I didn't bother to make a text parser...if I can get them visible, I could try to build a parser for it.

Anyways, the interesting bits are the results:
So, US Map including/excluding various regions.  I did a simple heuristic MST for it (just take the cheapest connection from the current MST and add that city).  I'm pretty sure this works for us because we're directionless, but I don't feel like proving it.

Here's the total costs for those trees for each possible 4-region set:
Green, Brown, Blue, Purple: ILLEGAL
Purple, Blue, Red, Brown: ILLEGAL
Green, Brown, Yellow, Blue: ILLEGAL

Green, Brown, Yellow, Red: 134
Green, Brown, Red, Purple: 147
Green, Brown, Yellow, Purple: 154
Green, Red, Yellow, Purple: 159
Brown, Red, Yellow, Purple: 163
Green, Brown, Red, Blue: 181
Green, Red, Blue, Purple: 191
Green, Red, Yellow, Blue: 193
Brown, Red, Yellow, Blue: 197
Brown, Yellow, Purple, Blue: 200
Green, Yellow, Purple, Blue: 201
Yellow, Red, Blue, Purple: 208

So, then I allowed you to visit each node 3 times, and built 68 cities.  There are several problems with this as an approximation of total costs but based on the later stuff it's not too bad.
Just cheapest and most expensive this time:
Green, Brown, Red, Yellow: 529
Red, Yellow, Blue, Purple: 663 (starting from phoenix)

Note: here starting city matters, and it's clearly not optimal.  I think the issue is probably that it builds some double-connections before single connections that open up cheaper regions.  In particular it's cheaper to build the SouthWest out before you triple-up in the fargo area.  Even though that first connection is more expensive.

Then I just had it do 4 of these simultaneously.  This goes 1-city at a time and builds out to 17 cities per "player" 
This is maybe the most interesting for analyzing starting positions although it's a far cry from a simulation.  Interestingly the total is cheaper than above...I'm supposing it's due to the 4 "free" connections for starting cities.
Green, Brown, Red, Yellow: 125, 130, 139, 128: 522
(Savannah, NewYork, OklahomaCity, Duluth)
Red, Yellow, Blue, Purple: 208, 144, 152, 154: 658
(LA, Fargo, Houston, Cheyenne)

For the cheap map, it's pretty stable regardless of where you start (though if you clump everyone together cost goes up a bit).  For the expensive map it is highly unstable.  It's really interesting to see how starting positions effect one another.  Especially the LA-player.  His starting position is obviously terrible using this method, but if you move him elsewhere he's too close to another player and only goes down to ~ 190 while driving them up to similar values.

Anyways, enjoy.
« Last Edit: May 29, 2013, 10:33:43 am by theorel »
Logged

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #14 on: May 30, 2013, 06:57:14 pm »
0

This is pretty awesome. I'm not sure what the problem is with the attachment, it seems to be working for me from different computers, but this weekend I'll be home and I should be able to upload it a different way if you want it. Text files for 12 maps are there, which would probably be useful.

I'd be interested in seeing your source. I don't have a way at the moment to compile Java but I shouldn't have much trouble getting one, and I could probably add in a text file parser.

So the simple MST stuff gives you certain numbers, and the game simulation stuff gives you different numbers. I think that's very interesting and I'm thinking they say two different things about each map. The first just gives you a general idea of how expensive it is to play on that map. The second gives you an idea of how important board position is on the map. All of it is relative, of course, and once all the numbers are in front of me I could probably write an article about interpreting it. If what you've made is what it sounds like, then it probably saved me from a lot of work implementing it myself  :P so thanks for the time you've put into it.
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #15 on: June 01, 2013, 02:42:58 pm »
0

another shot at uploading the map data. Now with the new maps included (they came in today!)

http://www.adamhorton.com/files/grid.zip
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

theorel

  • Spy
  • ****
  • Offline Offline
  • Posts: 86
  • Shuffle iT Username: theorel
  • Respect: +57
    • View Profile
Re: Map Comparison Article
« Reply #16 on: June 03, 2013, 06:52:14 am »
0

I'll try to get the code posted sometime this week.
Logged

theorel

  • Spy
  • ****
  • Offline Offline
  • Posts: 86
  • Shuffle iT Username: theorel
  • Respect: +57
    • View Profile
Re: Map Comparison Article
« Reply #17 on: June 03, 2013, 06:55:23 am »
0

Um...when I open that zip file it contains grid.lnk.  Maybe some sort of shortcut to the folder that you intended to zip?  Maybe you used windows' Recent Files thing somehow in a file browser?
Logged

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #18 on: June 03, 2013, 07:23:11 am »
0

ha, yeah I totally messed that up. I fixed it, that same link should work now.
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2745
  • Shuffle iT Username: Watno
  • Respect: +2982
    • View Profile
Re: Map Comparison Article
« Reply #19 on: June 03, 2013, 07:54:34 am »
0

Adjacency matrices?
That's O(n^2) for reading alone. Probably doesn't matter for that size though, but the programmer in me is pained.
Logged

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #20 on: June 03, 2013, 08:09:23 am »
0

uhh... do tell me what I'm supposed to use instead?
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2745
  • Shuffle iT Username: Watno
  • Respect: +2982
    • View Profile
Re: Map Comparison Article
« Reply #21 on: June 03, 2013, 08:26:21 am »
+1

Adjacency lists. But you really shouldn't.
Logged

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #22 on: June 03, 2013, 08:29:50 am »
0

Oh hey, that would have been a lot easier to input! Obvs. I shouldn't change it now that I have the lists, but this is good to know. Thanks.
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #23 on: June 04, 2013, 09:33:34 am »
+1

FIRST RESULTS

I've changed the grid.zip link (from adamhorton.com) to reflect updates to files I've made. I upgraded my graph.py to implement a modified MST algorithm. It should be extensible to an actual game simulation but I haven't implemented that yet. All it does is spit out a total cost to build 68 cities on each map. I want to play with this some more because I think there can be some interesting tidbits about each map gathered from this analysis. I'm wondering if Luxembourg ever gets built in Benelux :P

I compiled the results into the MSTCompare spreadsheet and made an introductory graph out of them. It's not exactly the format I want but whatever. Here's a screenshot of it:

EDIT: image removed, a better one is in a future post. Also, this discussion needs some revision after refining my results.

Japan and Spain/Portugal are very low-variance maps, it turns out. I may or may not have switched the min/max for those :-[ . I was recently informed, though, that because of the two-network rule of Japan, though, that it's possible to cut out one of the middle regions, leading to a potentially more expensive map, but that might break this analysis (or I could just do what I did for UK/Ireland, but the more I think about that the more it won't work. I didn't even bother messing with city costs for this anyways, it's supposed to be an approximation).

Turns out that by this analysis, the most expensive map possible is on China, and Germany isn't even the most expensive map on average! Of course Benelux is the cheapest on average, but under the right circumstances, Italy can be cheaper.
« Last Edit: June 05, 2013, 07:01:49 pm by AdamH »
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #24 on: June 04, 2013, 11:11:00 pm »
0

So I implemented a system to input starting positions for Players 1 through 4 and output total costs for each of them. It seems to work and I want to iterate through all possible combinations and get some statistics. I'm trying to think of some meaningful numbers to get from this.

Any stats-y people out there have some suggestions? Perhaps something to do with the differences between the total cost for each player?
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #25 on: June 05, 2013, 07:00:56 pm »
0

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 :P 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.
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

theorel

  • Spy
  • ****
  • Offline Offline
  • Posts: 86
  • Shuffle iT Username: theorel
  • Respect: +57
    • View Profile
Re: Map Comparison Article
« Reply #26 on: June 07, 2013, 08:44:24 am »
0

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.
« Last Edit: June 07, 2013, 08:45:32 am by theorel »
Logged

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #27 on: June 07, 2013, 08:54:07 am »
0

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.
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

theorel

  • Spy
  • ****
  • Offline Offline
  • Posts: 86
  • Shuffle iT Username: theorel
  • Respect: +57
    • View Profile
Re: Map Comparison Article
« Reply #28 on: June 11, 2013, 10:39:48 am »
0

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.

« Last Edit: June 11, 2013, 12:34:48 pm by theorel »
Logged

theorel

  • Spy
  • ****
  • Offline Offline
  • Posts: 86
  • Shuffle iT Username: theorel
  • Respect: +57
    • View Profile
Re: Map Comparison Article
« Reply #29 on: June 11, 2013, 12:35:40 pm »
0

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
« Last Edit: June 11, 2013, 01:20:31 pm by theorel »
Logged

theorel

  • Spy
  • ****
  • Offline Offline
  • Posts: 86
  • Shuffle iT Username: theorel
  • Respect: +57
    • View Profile
Re: Map Comparison Article
« Reply #30 on: June 11, 2013, 01:20:54 pm »
0

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.
Logged

philosophyguy

  • Minion
  • *****
  • Offline Offline
  • Posts: 575
  • Respect: +299
    • View Profile
Re: Map Comparison Article
« Reply #31 on: June 11, 2013, 06:36:14 pm »
0

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.
Logged

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #32 on: June 11, 2013, 07:37:30 pm »
0

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.
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

theorel

  • Spy
  • ****
  • Offline Offline
  • Posts: 86
  • Shuffle iT Username: theorel
  • Respect: +57
    • View Profile
Re: Map Comparison Article
« Reply #33 on: June 12, 2013, 10:12:48 am »
0

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.
« Last Edit: June 12, 2013, 10:17:31 am by theorel »
Logged

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #34 on: June 14, 2013, 07:40:17 am »
0

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.
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Map Comparison Article
« Reply #35 on: August 16, 2013, 09:55:30 am »
0

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.
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.
Pages: 1 2 [All]
 

Page created in 0.061 seconds with 22 queries.