Topology of maps

[giuppi]

Question for the cartographers around here: do you guys have a topological graph of the maps? One in some kind of matrix form that would tell basically which region is connected to which other region.
I would like to run some analysis to identify the most convenient clusters of regions... and it would be great if I didn't have to create a graph for each map on my own...

 

[RjBeals]

I don't for my maps, and I don't think WM or Shep would either. I'm not even sure I understand what you're after, but my maps are all graphics.

 

[giuppi]

That's what I mean (look at the picture). That is the North America subset of the Classic Evolved map. Every 1 in the matrix corresponds to a connection between the region in the respective row and the region in the respective column. The matrix is of course symmetric because if you can move from one region A to region B, you can also move from region B to region A. By the way, has anybody ever thought about borders that can be crossed only in one direction? That would be cool! Imagine a map where a fort in the valley is surrounded by mountains, and where the attack can only be carried out from the mountains down to the fort... but I digress here.

The topological map can also be in the form of a graph (nodes that represent regions connected by arcs that represent passageways), or in other fancy ways, but it should be easy to translate it into the matrix form here.
I suspect the programmers have this matrix somewhere, because I'm thinking it's functional to the algorithms in the games.

Anyway, if nobody has it, I'm gonna create one, at least for the Massive map, when i have time, and I'll share it with whoever wants it.

 

[RjBeals]

By the way, has anybody ever thought about borders that can be crossed only in one direction? That would be cool!

your wish will be coming true in the next set of maps due out soon

But if you're willing to put the effort into that spreadsheet - I'm sure users would love to have a peek.

 

[Badorties]

WidowMakers is our spreadsheet guru. He might be interested or could comment further.

 

[WidowMakers]

I know of no place that this exists.
When we make maps we must identify the borders but it is not output in any matrix as you have posted above.

Evan would be the guy to ask to see if the system can generate the desired output.

 

[Pizzetto]

Since the world maps represent a round world (North America to Asia=1 move), shouldn't you also be able to go from one end of Antarctica to the other?

It is accurate but maybe that would be confusing.

 

[ORBOTRON]

Not everything in the maps can be based on reality, things need to be tweaked for gameplay.

 

[Evan]

We have the data. Not quite in the flat format you're looking for (we're using a normalized relational database, of course). I could probably output it for you, but given the current schedule I;m afraid it wouldn't be a terribly high priority. I know I know, it'll only take 20 minutes to do. But its 20 minutes better spent elsewhere, currently. If you'd like, I will add it to my queue as a lower-priority item.

(The response isn't meant to sound rude, but its hard to convey my polite tone via text)

Thanks,
Evan

 

[giuppi]

Don't worry Evan, it doesn't sound rude and of course you'd better be working on higher priority stuff, all players appreciate it. I am anyway half-way through the Massive map.

 

[giuppi]

Ok people, after a whopping 180 minutes of hard work spread over 3 weeks, I've managed to arrange all the 0s and the 1s in a nice matrix for the Massive Map. In the attached files you see the spreadsheet and a graphical representation of it.

Next step is to perform some analysis. I've already got something in my mind that I want to study, but if you guys want to contribute with inputs and ideas you are very welcome. My first interest is to identify the connected sets of regions with the highest yield/#boundaries ratio. In other words: what are the regions that give me the highest command bonus with the minimum defense effort? Intuitively we can say that for instance, all other things being equal, it is more convenient to hold the Indian Subcontinent than Eastern Europe. In both cases the bonus is 2 troops, but the Indian Subcontinent can be defended allocating troops over 2 regions, whereas defending Eastern Europe requires defense troops spread over 4 regions.
Performing this calculation over the 25 commands is easy, but I want to extend it to ANY subset of regions.

Another idea I'm playing with is to identify the regions that are strategically important and that might make sense to occupy first or at least observe for different reasons. For instance there are regions in the map that are more 'central' than others, either because they are 'closer' to any other region (can be reached with the minimum number of steps) or because they happen to be on the path of least distance between any other two regions.
Maybe (all other things being equal, again) certain strategies work better (or worse) if you occupy central regions rather than peripheral ones, I don't know yet.

Is anybody else interested in this stuff?

 

[Chilly]

Great work. Stuff I'm sure a lot of us synthesize intuitively, but are sometimes shocked to see the empirical data. Especially when it shows us something contrary to what we "know".

Well done!

 

[coolname]

Excellent work! As a research project down the road, I'd be interested in comparing the theoretical best strategy with empirical data from actual games. One hypothesis would be that MajComs spend too much energy on Eastern Europe.

I'd also be interested to know when it -theoretically- would make sense to "go for" a certain bonus (mid/long term strategy after initial deployment). From the above, I'd say that having 2 out of 4 territories in Indian subcontinent would suffice to make a real push for that area, whilst for Eastern Europe, you would like to have 3 out of 4 territories.

I'm also surprised there are this many dead ends, territories with only 1 connection (quick count yields 5; Madagascar, Sri Lanka, Guyana, Sulawesi, Dominican Republic).

 

[giuppi]

I'm also surprised there are this many dead ends, territories with only 1 connection (quick count yields 5; Madagascar, Sri Lanka, Guyana, Sulawesi, Dominican Republic).

It's 7, including Taiwan and Uruguay.

 

[giuppi]

As a research project down the road, I'd be interested in comparing the theoretical best strategy with empirical data from actual games.

Yeah, I had the same idea. At this point, I'm not sure it can be done (need data that might not be easily available, take too much time, might not have the right know-how), but if we could, the results wouldn't probably be that surprising: we would find out that the best players consistently use the the best strategies, whether or not they get the theory behind, whatever that is.

 

[coolname]

we would find out that the best players consistently use the the best strategies, whether or not they get the theory behind, whatever that is.

Or the other way around; the best players exploit mistakes by worse players. I don't know if this makes sense, but when playing players with a sub-optimal strategy, a sub-optimal strategy might actually be better than the theoretical best strategy (because that assumes other players also use optimal strategies)

[side note: In 2004 someone published a PhD thesis on optimal Clue (board game) strategy. Article on that (translated from Dutch, PhD thesis in English I think); http://translate.google.nl/translat.../www.kennislink.nl/publicaties/killing-cluedo

BTW: what program did you use to make the graph?

 

[giuppi]

Or the other way around; the best players exploit mistakes by worse players. I don't know if this makes sense, but when playing players with a sub-optimal strategy, a sub-optimal strategy might actually be better than the theoretical best strategy (because that assumes other players also use optimal strategies)

[side note: In 2004 someone published a PhD thesis on optimal Clue (board game) strategy. Article on that (translated from Dutch, PhD thesis in English I think); http://translate.google.nl/translat.../www.kennislink.nl/publicaties/killing-cluedo

BTW: what program did you use to make the graph?

Maybe there are articles about Risk too?

The program I used for the graph is NetDraw, originally developed to represent social networks. It is free to use. (http://www.analytictech.com/netdraw/netdraw.htm)

 

[coolname]

Maybe there are articles about Risk too?

I found this one: http://www4.stat.ncsu.edu/~jaosborn/research/RISK.pdf

Has a nice graph on winning probabilities (math has me stumped thought) [nice odds calculator: http://www.dandrake.com/risk.html].

Conclusion: "The chances of winning a battle are considerably more favorable for the attacker than was originally suspected. The logical recommendation is then for the attacker to be more aggressive"

And apparently Blitzing is called "The Markovian property of a given battle" in this paper.

[update: Wikipedia also has some links http://en.wikipedia.org/wiki/Risk_(game)]