Dominion Strategy Forum

Please login or register.

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

Author Topic: Map Comparison Article  (Read 9680 times)

0 Members and 1 Guest are viewing this topic.

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2785
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3793
    • 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
I respond to PMs.

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: 2785
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3793
    • 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
I respond to PMs.

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2687
  • Shuffle iT Username: Watno
  • Respect: +2867
    • 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: 2785
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3793
    • 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
I respond to PMs.

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2687
  • Shuffle iT Username: Watno
  • Respect: +2867
    • 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: +1484
    • 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: 2687
  • Shuffle iT Username: Watno
  • Respect: +2867
    • 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: 2785
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3793
    • 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
I respond to PMs.

Ratsia

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 168
  • Respect: +112
    • 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: +1484
    • 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: 2785
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3793
    • 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
I respond to PMs.

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2785
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3793
    • 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
I respond to PMs.

theorel

  • Salvager
  • ****
  • Offline Offline
  • Posts: 60
  • Shuffle iT Username: theorel
  • Respect: +27
    • 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: 2785
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3793
    • 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
I respond to PMs.

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2785
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3793
    • 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
I respond to PMs.

theorel

  • Salvager
  • ****
  • Offline Offline
  • Posts: 60
  • Shuffle iT Username: theorel
  • Respect: +27
    • 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

  • Salvager
  • ****
  • Offline Offline
  • Posts: 60
  • Shuffle iT Username: theorel
  • Respect: +27
    • 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: 2785
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3793
    • 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
I respond to PMs.

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2687
  • Shuffle iT Username: Watno
  • Respect: +2867
    • 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: 2785
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3793
    • 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
I respond to PMs.

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2687
  • Shuffle iT Username: Watno
  • Respect: +2867
    • 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: 2785
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3793
    • 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
I respond to PMs.

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2785
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3793
    • 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
I respond to PMs.

AdamH

  • Board Moderator
  • *
  • Offline Offline
  • Posts: 2785
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3793
    • 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
I respond to PMs.
Pages: [1] 2  All
 

Page created in 0.116 seconds with 20 queries.