6
$\begingroup$

I'm trying to figure out optimal round 1 openings for this game: http://generals.io/.

For the purposes of this question, I've simplified some of the rules and mechanics of the game, and I assume that there are no opponents.

Here are the basic rules/mechanics/assumptions:

  • The game is played on a board of size m * n, 16 <= m, n <= 20 (m and n are random).
  • A tile on the board can be one of:
    • City: The player starts the game owning 1 City. The City generates 1 Unit every 2 turns (on even-numbered turns). For the purposes of this, assume that there are no other Cities on the board.
    • Land: A Land tile can be occupied by moving at least 1 Unit onto it.
    • Mountain: Impassable tile.
  • Assume that about a third of the tiles are Mountains at random locations, and that all Lands are orthogonally connected to at least one Land or City (and so are all reachable from your City).
  • Every turn, the player can do one of two actions:
    • Idle: Nothing is done on this turn.
    • Move: The player chooses a tile where they have at least 2 Units. They then choose an orthogonally adjacent tile, which cannot be a Mountain, to Move the Units to. All but 1 of the Units will be transferred to this new tile. Only one Move action can be issued on each turn.
  • At the beginning of the game, it is turn 0. The City starts with 1 Unit, and will generate its first Unit on turn 2.
  • Each round consists of 50 turns. At the start of each round, all Lands generate 1 Unit.

Here is an example from Generals.io of a section of the game board on turn 22: An example from Generals.io of a section of the game board on turn 22, showing a City, unoccupied Lands, occupied Lands and Mountains In the above image, the player Idled until turn 20, then on turn 21 Moved (with 10 Units) east from the City. On turn 22 they Moved east again (with 9 Units) from the Land they occupied on turn 21.

Since the City generates 1 Unit every 2 turns, by turn 48 it will have generated 24 Units. So the theoretical maximum number of Lands that could be occupied by turn 50 is 24.

And so, the goal is to figure out an approach that can be used to find a set of actions (or whether any even exist) that would allow the player to occupy 24 Lands by turn 50, given a starting configuration of the game board. Ideally this would be an approach that a human could quickly use to calculate what the actions would have to be, since the game is played in semi-realtime (each turn lasts about 1 second, during which you can issue a Move action or not do anything and just Idle).

QUESTION: Can you come up with a method that a human could use (within ~20 seconds) to get 24 Lands on round 1 whenever a board configuration makes it possible?


I was trying to write myself a "cheat-sheet" to achieve the above. Here's what I have so far.

Basic observations:

  • In order to have 24 Lands by turn 50, we must have spent 24 of the 50 turns Moving Units onto unoccupied Lands.
  • Therefore, we have 26 turns left that we can use to either Idle or Move Units onto occupied Lands.
  • Knowing this, we could generate some "action plans" and see if one of them fits our game board starting configuration.

Here's the template/strategy that these "action plans" follow:

  • Begin by idling for I turns, I <= 26, I divisble by 2. (I divisible by 2 as the purpose of Idling at the start is to build up a sizeable number of Units in your City before Moving out with them to occupy Lands in a chain.)
  • You will now have floor(I / 2) + 1 Units in your City. Move out with these Units and occupy floor(I / 2) Lands over the next floor(I / 2) turns.
  • Since you've Idled for I turns, you now only have 26 - I turns left during which you can Idle or Move over occupied Lands. The rest of the turns must all be used to Move over (and so occupy) unoccupied Lands. The "action plan" lists the permutations in which you could utilize these 26 - I turns, given I.

So here are some explained "action plan" examples of the easiest cases, that seem to allow one to find a solution for quite a few starting board configurations. Once one is familiar with how these work, more concise/readable versions can be utilized as a cheat-sheet.

  • I## = "Idle". Idle for ## turns.
  • M## = "Move". Move all (but 1) Units (from your City) over ## occupied Lands, over the next ## turns.
  • O## = "Occupy". Move all (but 1) Units (from your City or from an occupied Land) over ## unoccupied Lands (thereby occupying them), over the next ## turns.
  • @## = One of the above three actions will prefix this @## notation. Here, ## indicates the turn at which you start executing the prefixed action.

I = 26: You Idle for 26 turns, and thereafter you cannot Idle or Move over occupied Lands.

  • The only set of actions that works after Idling for 26 turns at the start is: I26@0, O13@26, O6@39, O3@45, O2@48.
  • This plan requires your City to be adjacent to 4 separate Land chains, of minimum lengths of 13, 6, 3 and 2.
  • It is easy enough to manually identify whether your starting City location satisfies the above.

I = 24: You Idle for 24 turns, and thereafter you have the following set of options for your last 2 I|M actions:

  • {{2}, {1, 1}}. (Meaning you could either do 2x I1|M1 actions, or 1x I2|M2 action.)
  • I've found that in general, one will rarely Idle after the initial long Idling phase. Mostly the above options would be used for M actions.
  • So one possible way of playing out this plan would be: I24@0, O12@24, O6@36, M1@42, O3@43, M1@46, O2@47, O1@49.
  • This plan could be used to get 24 Lands if your City spawns with one orthogonal side blocked by a Mountain, for instance. The other three sides would need to have the following lengths of separate chains of Lands: 13, 6, 1, 3 (connected to the 13 or 6 chain at a distance of 1 from the City), and 2 (connected to the 13 or 6 chain at a distance of 1 from the City).

Here is the concise version of the cheat-sheet that I've been using for round 1 openings in Generals.io:

  • I24:
    • {2}
    • {1, 1}
  • I22
    • {4}
    • {3, 1}
    • {2, 2}
    • {2, 1, 1}
    • {1, 1, 1, 1}
  • I20:
    • {6}
    • {5, 1}
    • {4, 2}
    • {4, 1, 1}
    • {3, 3}
    • {3, 2, 1}
    • {3, 1, 1, 1}
    • {2, 2, 2}
    • {2, 2, 1, 1}
    • {2, 1, 1, 1, 1}
    • {1, 1, 1, 1, 1, 1}

Before explaining my approach at using the cheat-sheet, there's another important observation:

  • In order to have occupied 24 Lands by turn 50, the Unit that is generated by the City on turn 48 must Move to occupy a new Land. It only has 2 turns to do so. I assume that by this point, all 26 non-occupy turns have been used. And so, both of these turns would be used for new Land occupation (using the Units generated on turns 46 and 48).
  • This requires that at turn 48 your City would still have either an adjacent size 2 unoccupied Land chain or two separate adjacent (to the City) unoccupied Lands.
  • This helps narrow down the possibilities I look at in using the cheat-sheet.

So, here is how I use the cheat-sheet (keep in mind that all of the below has to be planned out within ~20 seconds, which is the length of time before the game reaches turn 20):

  • I identify the 2 Lands I will occupy using the Units generated on turns 46 and 48. (As mentioned above, these 2 Land tiles have to either be in a chain adjacent to the City, or be both separately adjacent to the City.)
  • These 2 Land tiles cannot be occupied before turn 46, narrowing down our occupation paths at the start.
  • I then identify the path that the initial (biggest) set of Units will take (after the long initial Idling time). Ideally, I try to choose a path that can scout towards the center of the board, but I prioritize not blocking potential future occupation paths.
  • For the remainder of the occupation paths, I repeat the following:
    1. I note the minimum number of occupied Lands that Units would have to Move through from the City in order to occupy a new Land chain.
    2. Using the above, I plan out a simple path that would obstruct further occupation paths as little as possible.
  • Finally, I check the cheat-sheet for a set of Move counts that satisfy the list of "minimum number of occupied Lands to Move through".
    • If I find a matching set, then by following its initial Idle time, I should be able to execute the plan I made and get 24 Lands by turn 50.
    • If I don't find an exactly matching set, I will try to find one that matches the list as much as possible, and go with that one. I go for a set where the numbers are smaller than required. The overall sum difference (between the required and the picked set) equals the number of Lands you miss out on.

I realize that some of the options on the cheat-sheet are fairly useless (such as I20: {1, 1, 1, 1, 1, 1}) and that the list of possible permutations would start to get too large for human use for smaller initial Idle lengths. This is why I am asking this question, in hopes of learning of a better method.

$\endgroup$
  • 1
    $\begingroup$ Since you are only interested in methods that human can use, I think this is better suited for math.se. $\endgroup$ – Yuval Filmus Jun 29 '17 at 1:25
  • $\begingroup$ Are you sure that 24 tiles is reachable maximum? Try to take board with no mountains and see if it even possible to fulfill Von Neumann neighborhood of order 3, which has 23 tiles (22 without counting city) $\endgroup$ – rus9384 Jun 29 '17 at 4:38
  • 1
    $\begingroup$ @YuvalFilmus I don't follow that logic. Algorithms are a CS thing more than a mathematics thing; it's not necessary to want a machine to run them. $\endgroup$ – Raphael Jun 29 '17 at 5:08
  • $\begingroup$ Look at these replays of mine: generals.io/replays/B9cmvufNb generals.io/replays/HYdY5OfEW generals.io/replays/BKOO6_GEZ $\endgroup$ – enedil Jun 29 '17 at 14:55
  • $\begingroup$ @rus9384 It's definitely possible to occupy 24 Lands tiles by turn 50 (sometimes you occupy the 24th on 49, and sometimes on 50 - both give you the Land's 1 Unit generation for round 2). The basic method that I outlined in the second part of the post allows you, for some starting board configurations, to find a way to occupy 24 Lands by turn 50. $\endgroup$ – SpiritFryer Jun 29 '17 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.