Skip to content

Instantly share code, notes, and snippets.

@personalcomputer
Last active September 23, 2021 14:02
Show Gist options
  • Save personalcomputer/9e383b46932bed1a9bfcd0e380f5a7d8 to your computer and use it in GitHub Desktop.
Save personalcomputer/9e383b46932bed1a9bfcd0e380f5a7d8 to your computer and use it in GitHub Desktop.
generals.io initial bot building analysis

FACTS ABOUT GENERALS.IO 1v1

ACTIONS

  • You can move one space per turn (manhattan distance 1)
  • Each move can move either 100% of 50% of men

ENVIRONMENT

  • Map is 19x19 grid
  • Neutral cities spawn with 41-49 men ea.
  • Neutral cities will regenerate men if they are attacked up until 40 men
  • Very rough mountain probability 4/19
  • Very rough city probability 1/19

DYNAMICS

  • Turns last 0.5 seconds
  • Castles & cities get +1 men at the start of each 2nd turn
  • Every owned square gets +1 men every 50th turn (so on turn 50, turn 100, turn 150, etc)
  • You have fog of war, can only see the tiles directly surrounding your tiles (chebyshev distance 1). However, can see difference between land tiles and mountain/city/king tiles without vision.
  • Capture an unclaimed tile by moving 1 men onto it
  • Capture a manned tile by moving more men onto it than are already men on it

ENEMY

  • Has same actions available as you
  • You can see his crown if in vision

OBJECTIVE

  • Capture enemy king tile

ANALYSIS

RESOURCES

  • Turns (movements) t
  • Land l
  • Cities c
  • Score ("men") m
  • Vision / scouting information v

ACTIONS DEFINED AS RESOURCE TRANSFORMS

  • move to unoccupied tile. t:-1, l:1, c:0, m:0, v:3
  • move to enemy tile. t:-1, l:1, c:0, m:-1, v:3
  • move to city. t:-1, l:0, c:1, m:-45, v:3
  • move to own tile. t:-1, l:0, c:0, m:0, v:0
  • replenish turn. t:0, l:0, c:0, m:l, v:0

ECONOMY

  • Captured cities are worth 0.5 men / turn
  • Captured land is worth 0.02 men / turn
  • It takes 25 land tiles to be worth one city tile, in terms of income
  • It costs 25 men to claim 25 land tiles, but 40-50 men to claim 1 city tile

So, in pure men P/L analysis, ignoring other resources, land beats out cities. In actuality, the movement rate limit will limit a land-only strategy fairly quickly, making city tiles a good option.

COMBAT LOGISTICS

  • Cities have an advantage over land because of the relatively higher cost land has on movements (requires more movements to aggregate army), cities have all army available without any movements needed.
  • Land has an advantage over cities because of the much higher vision offered, roughly 25x more vision

STRATEGY

  • Attack enemy territory or build own territory?
  • Raid?
  • Cities or land?
  • Where to expand to?
  • Should you scout? When? Where?
  • When to aggregate up army built from land?

AI DETAILS

The best perspective on this problem that I have yet is it is a combinatorial optimization problem. We need to use heuristics to explore the solution space because of how many options there are. Cost function may also require some heuristics for long term prediction, because of expense. But it also might not, depending on the cost functions defined.

I want to strategically partition the goal into 3 different objectives that can each have specialized solvers written for:

  • Economy objective
    • Maximize men generation rate ("gdp")
      • Can alternatively maximize total men to have at given turn x, but my first approach will instead be budgeting GDP versus offensive action resource allocation at a high level, requiring them to schedule behavior on their own, not having the two initiatives coordinate on scheduling.
      • May make more sense to instead maximize future GDP, eg compute for gdp ~10 turns in the future.
  • Raid objective
    • Conquer enemy king position [needs to be defined better - needs to be optimizable, ie not a boolean. No logistic functions.]
  • Scout objective
    • Maximize the convolution of once-visioned-tiles and the probability distribution of enemy king positions + (with lower weight) the probability distribution of city positions.

I want to ignore everything but the economic goal for quite a while. Technically the game should be able to be won with an economic goal solver alone, raiding just would give it an extra edge.

AI PLAN

Milestone 1: Exploration.

Expand pointlessly, track gamestate, and inform world knowledge. Set up persistent data collection for world gen probabilities.

Milestone 2: Land Economy.

Budget 100% into economy built up by claiming large amounts of land. No cities, no defence, no enemy interaction.

Milestone 3: Full Economy.

Same as milestone #2, but include cities as an option.

Milestone 4: Defense.

Predict enemy, and as part of budgeting 100% into economy, put resources into preventing enemy from taking out economy / defense as the enemy can hurt optimizing economic objective.

Milestone 5: Economic & King Raiding.

Incorporate raiding. There is often a path available to strike through enemy territory and hit their king undefended. Requires luck and some way to to evaluate how much / when to invest in raiding.

Milestone 6: Strategic territory.

It is easier/cheaper to raid if economic infrastructure is focused closer to enemy territory, requires less movements to assemble a raid party. It is also a much better idea to expand into enemy cities than neutral cities, even if they have more men defending them, because it both achieves economic improvement and hurts the enemy economy.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment