What's the per-opponent vulnerability of a given territory in the online Risk-like game http://www.conquerclub.com? Is there an existing tool that solves this problem, albeit in a different context? Details:
I define vulnerability(t,x) as "the minimum number of troops opponent x must defeat in order to reach and conquer territory t". This calculation is non-trivial when x has no troops adjacent to t.
Sample JSON input data below (hideous), with a following explanation. The goal is to take JSON data in this format, and return per-territory per-opponent vulnerability.
map = {"killers":[],"countries":[{"name":"Baie de Henne","xS":240,"yS":86,"xL":304,"yL":108,"neutral":0,"bonus":0,"borders":[1,23],"bombardments":[]},{"name":"Port-de-Paix","xS":288,"yS":84,"xL":367,"yL":102,"neutral":0,"bonus":0,"borders":[0,2,8,7],"bombardments":[]},{"name":"Ile de la Tortue","xS":317,"yS":44,"xL":404,"yL":50,"neutral":0,"bonus":0,"borders":[1,4],"bombardments":[]},{"name":"Le Borgne","xS":337,"yS":78,"xL":434,"yL":96,"neutral":0,"bonus":0,"borders":[4],"bombardments":[]},{"name":"Cap-Haiten","xS":408,"yS":113,"xL":519,"yL":139,"neutral":0,"bonus":0,"borders":[3,2,5,9,6],"bombardments":[]},{"name":"Fort-Liberte","xS":462,"yS":126,"xL":587,"yL":156,"neutral":0,"bonus":0,"borders":[4,6],"bombardments":[]},{"name":"La Victoire","xS":434,"yS":146,"xL":555,"yL":186,"neutral":0,"bonus":0,"borders":[4,12,5],"bombardments":[]},{"name":"Gonaives","xS":302,"yS":119,"xL":385,"yL":146,"neutral":0,"bonus":0,"borders":[1,8,9],"bombardments":[]},{"name":"Cammon","xS":346,"yS":130,"xL":440,"yL":160,"neutral":0,"bonus":0,"borders":[1,7,9],"bombardments":[]},{"name":"Paul","xS":396,"yS":152,"xL":476,"yL":178,"neutral":0,"bonus":0,"borders":[7,8,4,10,11],"bombardments":[]},{"name":"Desdunes","xS":369,"yS":185,"xL":470,"yL":229,"neutral":0,"bonus":0,"borders":[9,11,15,16],"bombardments":[]},{"name":"Bouli","xS":421,"yS":214,"xL":535,"yL":266,"neutral":0,"bonus":0,"borders":[9,10,17,13],"bombardments":[]},{"name":"Los Posos","xS":483,"yS":207,"xL":576,"yL":230,"neutral":0,"bonus":0,"borders":[13,6],"bombardments":[]},{"name":"Hinche","xS":451,"yS":213,"xL":576,"yL":269,"neutral":0,"bonus":0,"borders":[11,12,14],"bombardments":[]},{"name":"Roseau","xS":480,"yS":255,"xL":606,"yL":318,"neutral":0,"bonus":0,"borders":[13],"bombardments":[]},{"name":"Ile de la Gonave","xS":278,"yS":250,"xL":354,"yL":311,"neutral":0,"bonus":0,"borders":[16,10,19,23],"bombardments":[]},{"name":"Saint-Marc","xS":365,"yS":241,"xL":465,"yL":299,"neutral":0,"bonus":0,"borders":[15,17,10],"bombardments":[]},{"name":"Monet","xS":411,"yS":279,"xL":523,"yL":346,"neutral":0,"bonus":0,"borders":[16,11,19,20,18],"bombardments":[]},{"name":"La Toison","xS":453,"yS":278,"xL":577,"yL":346,"neutral":0,"bonus":0,"borders":[17,20],"bombardments":[]},{"name":"Port-au-Prince","xS":395,"yS":308,"xL":503,"yL":387,"neutral":0,"bonus":0,"borders":[17,20,15],"bombardments":[]},{"name":"Kenscoff","xS":432,"yS":315,"xL":549,"yL":395,"neutral":0,"bonus":0,"borders":[17,19,28,29,18],"bombardments":[]},{"name":"Jeremie","xS":109,"yS":312,"xL":140,"yL":390,"neutral":0,"bonus":0,"borders":[23,22],"bombardments":[]},{"name":"Les Cayes","xS":141,"yS":359,"xL":180,"yL":450,"neutral":0,"bonus":0,"borders":[21,23,24],"bombardments":[]},{"name":"Pestel","xS":154,"yS":310,"xL":197,"yL":388,"neutral":0,"bonus":0,"borders":[21,22,24,15,0],"bombardments":[]},{"name":"Aquin","xS":177,"yS":341,"xL":220,"yL":422,"neutral":0,"bonus":0,"borders":[23,22,25],"bombardments":[]},{"name":"Cotes de Fer","xS":262,"yS":325,"xL":334,"yL":413,"neutral":0,"bonus":0,"borders":[24,26,27],"bombardments":[]},{"name":"Leogane","xS":344,"yS":326,"xL":438,"yL":408,"neutral":0,"bonus":0,"borders":[25,27,28],"bombardments":[]},{"name":"Bainet","xS":338,"yS":355,"xL":430,"yL":445,"neutral":0,"bonus":0,"borders":[25,26,28],"bombardments":[]},{"name":"Jacmel","xS":374,"yS":341,"xL":475,"yL":428,"neutral":0,"bonus":0,"borders":[29,20,26,27],"bombardments":[]},{"name":"Belle-Anse","xS":478,"yS":364,"xL":608,"yL":457,"neutral":0,"bonus":0,"borders":[28,20],"bombardments":[]}],"continents":[{"name":"Nord","bonus":4,"required":0,"territories":[0,1,2,3,4,6,5],"subcontinents":[],"overrides":[]},{"name":"Artibonite","bonus":3,"required":0,"territories":[7,8,9,10],"subcontinents":[],"overrides":[]},{"name":"Centre","bonus":2,"required":0,"territories":[11,12,13,14],"subcontinents":[],"overrides":[]},{"name":"Ouest","bonus":5,"required":0,"territories":[15,16,17,19,20,18],"subcontinents":[],"overrides":[]},{"name":"Sud","bonus":2,"required":0,"territories":[21,22,23,24],"subcontinents":[],"overrides":[]},{"name":"Sud-Est","bonus":3,"required":0,"territories":[25,26,27,28,29],"subcontinents":[],"overrides":[]}],"requirements":[],"objectives":[],"reinforcements":[],"positions":[],"title":"Haiti","large":"Haiti.L.jpg","small":"Haiti.S.jpg","widthS":"550","heightS":"407","widthL":"698","heightL":"517","min_reinforcement":0,"country_counter":30};
armies = [{"player":"4","quantity":1},{"player":"1","quantity":1},{"player":"1","quantity":1},{"player":"2","quantity":1},{"player":"2","quantity":1},{"player":"2","quantity":1},{"player":"2","quantity":1},{"player":"1","quantity":5},{"player":"4","quantity":1},{"player":"4","quantity":1},{"player":"4","quantity":1},{"player":"2","quantity":3},{"player":"2","quantity":1},{"player":"2","quantity":1},{"player":"2","quantity":1},{"player":"4","quantity":1},{"player":"4","quantity":1},{"player":"3","quantity":1},{"player":"3","quantity":1},{"player":"3","quantity":1},{"player":"3","quantity":1},{"player":"0","quantity":3},{"player":"4","quantity":1},{"player":"4","quantity":1},{"player":"4","quantity":3},{"player":"1","quantity":3},{"player":"1","quantity":1},{"player":"1","quantity":1},{"player":"3","quantity":1},{"player":"3","quantity":1}];
"map =" defines the fixed map. Each entry in "countries" represents a territory. For example, "Baie de Henne" is territory 0, "Port-de-Paix" is territory 1, "Ile de la Tortue" is territory 2, and so on.
The "borders" field tells which territories can attack each other. In more complex maps, some attacks are 1-way, but not here. For this map, if s can attack t, then t can attack s.
The "map =" line has lots more info, but nothing useful for this question.
The "armies =" line gives the owner and number of troops for each territory (changes each turn). For example, player 4 has 1 troop on territory 0 (which we know from above is "Baie de Henne"), player 1 has 1 troop on territory 1 ("Port-de-Paix"), and player 1 also has 1 troop on territory 2 ("Ile de la Tortue").
This information should be sufficient to calculate per-territory per-opponent vulnerability.
Note: a player may not attack his own troops. Example:
Opponent x has 1 troop on s, adjacent to t.
Opponent x has 100 troops on r, adjacent to s, but not adjacent to t.
The 100 troops or r cannot attack the 1 troop on s to get to t.
On the map below, player 1 is red, 2 is green, 3 is blue, and 4 is yellow. As with many conquerclub.com maps, it's not trivially obvious which territories border which: that's one reason I want this program.
This program (written for a completely different reason) may be helpful and/or confusing.
Even if no one's written a program specifically for conquerclub.com, is there a general tool that solves these kinds of problem?
I realize I could use networkx, treat this as a digraph, and use shortest paths, but is there something "higher level" I could use?
