Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

Optimal Build Paths in Travian

Travian is a real-time strategy browser game. You build a village, raise armies, ally with or conquer other players... the usual RTS sort of thing. There are four types of resources; each improvement (whether to a production field or one of the other building types) takes a certain amount of the four resources as well as a fixed amount of time to complete. Construction cannot take place in parallel (except in a limited way for one of the tribes, which we'll ignore.)

An interesting question in this game is "what is the best sequence of improvements to build"? You have to make scheduling tradeoffs between building additional production capacity and leaving yourself undefended. So, I wanted to look at a simple version of this problem: what is the fastest construction path that will produce a level 10 residence? (This level allows you to build settlers and found new villages.)


I first thought about using A* search. But this turns out not to work all that well. It's hard to come up with an admissible heuristic, and there is a combinatorial explosion in the number of states. Basically any heuristic good enough to narrow down the search would probably be good enough to give you an answer.

So, I looked at using dynamic programming. The problem is that two paths to the same set of improvements, say wheat-clay-iron or clay-iron-wheat, are not directly comparable. The build time for the first is shorter, but the second leaves you with a different inventory of leftover resources. That inventory might be relevant when you make the fourth build. But, if you can't collapse those two states, you can't do dynamic programming!

Some small-scale tests seemed to suggest that the build time usually dominated over leftover inventory--- the best 2-improvement builds were prefixes to the best 3-improvement builds. So I went ahead and built the dynamic programming solver based purely on minimizing build time, aware that it might occasionally return a non-optimal build.

But, how do you tell when to exit? It's hard to tell whether a given build path is actually minimal, or whether a "longer" one (in terms of # of improvements) would actually reduce the build time. I decided to just keep running to larger and larger number of improvements (generations) and eyeball it. ;) The paths that reach the goal state are removed so that we don't explore building past the goal.



Here's the results of running the solver on a level-2 residence:

Generation 1 size 7
Generation 2 size 27
Generation 3 size 78
start -> warehouse -> residence -> residence ->
    Village 181.98hours r2 w1 g0 wheat[0, 0, 0, 0, 0, 0] clay[0, 0, 0, 0] wood[0, 0, 0, 0] iron[0, 0, 0, 0] inv[  5 245 565 377]
Generation 4 size 185
start -> wood0 -> residence -> warehouse -> residence ->
    Village 164.48hours r2 w1 g0 wheat[0, 0, 0, 0, 0, 0] clay[0, 0, 0, 0] wood[1, 0, 0, 0] iron[0, 0, 0, 0] inv[189   5 375 375]
Generation 5 size 363
start -> clay0 -> wood0 -> residence -> warehouse -> residence ->
    Village 147.91hours r2 w1 g0 wheat[0, 0, 0, 0, 0, 0] clay[1, 0, 0, 0] wood[1, 0, 0, 0] iron[0, 0, 0, 0] inv[  8 246 163 374]
Generation 6 size 636
start -> clay0 -> wood0 -> wood1 -> residence -> warehouse -> residence ->
    Village 135.29hours r2 w1 g0 wheat[0, 0, 0, 0, 0, 0] clay[1, 0, 0, 0] wood[1, 1, 0, 0] iron[0, 0, 0, 0] inv[114   8  12 171]
Generation 7 size 1045
start -> clay0 -> wood0 -> wood1 -> residence -> warehouse -> wheat0 -> residence ->
    Village 143.47hours r2 w1 g0 wheat[1, 0, 0, 0, 0, 0] clay[1, 0, 0, 0] wood[1, 1, 0, 0] iron[0, 0, 0, 0] inv[159   8   7 347]
Generation 8 size 1641
start -> clay0 -> wood0 -> wood1 -> residence -> warehouse -> wheat0 -> iron0 -> residence ->
    Village 150.74hours r2 w1 g0 wheat[1, 0, 0, 0, 0, 0] clay[1, 0, 0, 0] wood[1, 1, 0, 0] iron[1, 0, 0, 0] inv[161   8 198 175]
Generation 9 size 2482
start -> clay0 -> wood0 -> wood1 -> residence -> warehouse -> wheat0 -> iron0 -> wheat1 -> residence ->
    Village 158.93hours r2 w1 g0 wheat[1, 1, 0, 0, 0, 0] clay[1, 0, 0, 0] wood[1, 1, 0, 0] iron[1, 0, 0, 0] inv[205   8 218 351]
Generation 10 size 3653
start -> clay0 -> wood0 -> iron0 -> clay1 -> wheat0 -> wood1 -> warehouse -> wheat1 -> residence -> residence ->
    Village 151.04hours r2 w1 g0 wheat[1, 1, 0, 0, 0, 0] clay[1, 1, 0, 0] wood[1, 1, 0, 0] iron[1, 0, 0, 0] inv[ 10 239 267 118]
Generation 11 size 5247
start -> clay0 -> wood0 -> iron0 -> clay1 -> wheat0 -> wood1 -> warehouse -> wheat1 -> residence -> wheat2 -> residence ->
    Village 156.04hours r2 w1 g0 wheat[1, 1, 1, 0, 0, 0] clay[1, 1, 0, 0] wood[1, 1, 0, 0] iron[1, 0, 0, 0] inv[ 10 219 252 284]
Generation 12 size 7374
start -> clay0 -> wood0 -> iron0 -> clay1 -> wheat0 -> wood1 -> wheat1 -> wood2 -> residence -> warehouse -> wheat2 -> residence ->
    Village 148.27hours r2 w1 g0 wheat[1, 1, 1, 0, 0, 0] clay[1, 1, 0, 0] wood[1, 1, 1, 0] iron[1, 0, 0, 0] inv[112  10 117  36]
Generation 13 size 10170
start -> clay0 -> wood0 -> iron0 -> clay1 -> wheat0 -> wood1 -> wheat1 -> wood2 -> residence -> warehouse -> wheat2 -> wheat3 -> residence ->
    Village 154.69hours r2 w1 g0 wheat[1, 1, 1, 1, 0, 0] clay[1, 1, 0, 0] wood[1, 1, 1, 0] iron[1, 0, 0, 0] inv[151  10 117 183]
Generation 14 size 13825
start -> clay0 -> wood0 -> iron0 -> clay1 -> wheat0 -> wood1 -> wheat1 -> wood2 -> wheat2 -> clay2 -> residence -> warehouse -> wheat3 -> residence ->
    Village 151.98hours r2 w1 g0 wheat[1, 1, 1, 1, 0, 0] clay[1, 1, 1, 0] wood[1, 1, 1, 0] iron[1, 0, 0, 0] inv[ 35 195   8  84]
Generation 15 size 18484
start -> clay0 -> wood0 -> iron0 -> clay1 -> wheat0 -> wood1 -> wheat1 -> wood2 -> wheat2 -> clay2 -> residence -> warehouse -> wheat3 -> wheat4 -> residence ->
    Village 158.34hours r2 w1 g0 wheat[1, 1, 1, 1, 1, 0] clay[1, 1, 1, 0] wood[1, 1, 1, 0] iron[1, 0, 0, 0] inv[ 73 214   8 233]
Generation 16 size 24387
start -> clay0 -> wood0 -> iron0 -> clay1 -> wheat0 -> wood1 -> wheat1 -> wood2 -> wheat2 -> clay2 -> wheat3 -> iron1 -> wheat4 -> residence -> warehouse -> residence ->
    Village 159.47hours r2 w1 g0 wheat[1, 1, 1, 1, 1, 0] clay[1, 1, 1, 0] wood[1, 1, 1, 0] iron[1, 1, 0, 0] inv[ 12 153 244 186]
Generation 17 size 31750
start -> clay0 -> wood0 -> iron0 -> clay1 -> wheat0 -> wood1 -> wheat1 -> wood2 -> wheat2 -> clay2 -> wheat3 -> iron1 -> wheat4 -> residence -> warehouse -> wood3 -> residence ->
    Village 157.06hours r2 w1 g0 wheat[1, 1, 1, 1, 1, 0] clay[1, 1, 1, 0] wood[1, 1, 1, 1] iron[1, 1, 0, 0] inv[ 37  12 161  38]
Generation 18 size 40862
start -> clay0 -> wood0 -> iron0 -> clay1 -> wheat0 -> wood1 -> wheat1 -> clay2 -> warehouse -> wheat2 -> iron1 -> wheat3 -> wheat4 -> wood2 -> wheat5 -> wood3 -> residence -> residence ->
    Village 160.77hours r2 w1 g0 wheat[1, 1, 1, 1, 1, 1] clay[1, 1, 1, 0] wood[1, 1, 1, 1] iron[1, 1, 0, 0] inv[ 14  18 145 142]


The residence cost is (580,460,350,180)+(740,590,450,230) so this result makes sense. The order is ( wood, clay, iron, wheat ) which I know is not consistent with the improvement levels in the output. Warehouse and granary provide more storage, which is necessary to build something with more than 600 of any given resource. The path shows which "slot" gets improved--- there are 6 wheat fields and 4 fields for each of the other resources.

21 improvements is about the max I can do here, but the A* solver could not find the best build path for a level 2 residence in any reasonable amount of time and memory.

The best path I can find to a level 3 residence takes 13 steps and 202 hours:

start -> clay0 -> wood0 -> iron0 -> clay1 -> wheat0 -> wood1 -> wheat1 -> wood2 -> residence -> warehouse -> wheat2 -> residence -> residence -> Village 202.39hours r3 w1 g0 wheat[1, 1, 1, 0, 0, 0] clay[1, 1, 0, 0] wood[1, 1, 1, 0] iron[1, 0, 0, 0] inv[ 82 12 137 66]

Both this and the search for a level 4 residence show several false minima. I thought that the best for level 4 was this 15-step, 286 hour solution:


Generation 15 size 22311

start -> clay0 -> wood0 -> iron0 -> clay1 -> wheat0 -> wood1 -> wheat1 -> wood2 -> residence -> warehouse -> wheat2 -> residence -> residence -> warehouse -> residence -> Village 286.20hours r4 w2 g0 wheat[1, 1, 1, 0, 0, 0] clay[1, 1, 0, 0] wood[1, 1, 1, 0] iron[1, 0, 0, 0] inv[127 16 209 144]


and there is actually an 18-step build that comes very close:


Generation 18 size 50891

start -> clay0 -> wood0 -> iron0 -> clay1 -> wheat0 -> wood1 -> wheat1 -> wood2 -> wheat2 -> clay2 -> residence -> warehouse -> wheat3 -> residence -> residence -> warehouse -> wood3 -> residence -> Village 286.50hours r4 w2 g0 wheat[1, 1, 1, 1, 0, 0] clay[1, 1, 1, 0] wood[1, 1, 1, 1] iron[1, 0, 0, 0] inv[155 457 12 110]


But a 21-step build does slightly better:


Generation 21 size 104370
start -> clay0 -> wood0 -> iron0 -> clay1 -> wheat0 -> wood1 -> wheat1 -> clay2 -> warehouse -> wheat2 -> iron1 -> wheat3 -> wheat4 -> wood2 -> wheat5 -> wood3 -> residence -> residence -> residence -> warehouse -> residence ->
Village 277.70hours r4 w2 g0 wheat[1, 1, 1, 1, 1, 1] clay[1, 1, 1, 0] wood[1, 1, 1, 1] iron[1, 1, 0, 0] inv[ 23 81 357 234]


So, it looks like a solution to the level 10 problem remains out of reach, and there is no particular reason to believe the 21-step solution above is the best achievable for level 4.
Tags: games, programming
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 3 comments