Ants Game Specification

Contents:

  1. Turns and Phases
  2. Scoring
  3. Cutoff Rules
  4. Food Harvesting
  5. Ant Spawning
  6. Food Spawning
  7. Battle Resolution
    1. Focus Battle Resolution
  8. Battle Resolution
  9. Bot Input
  10. Bot Output
  11. Map Format
  12. Replay Format

Turns and Phases

Setup

Each bot is sent some starting information for the game, including map size, max turns and turn timings. After the bot has processed this data, it should return a 'go'. After all bots are ready, the game will start.

Turns

Once each of the bots has indicated it has finished setting up, the game engine performs the following steps repeatedly:

  1. Send the game state to the players
  2. Receive orders from the players
  3. Perform the phases and update the game state
  4. Check for endgame conditions

There is a specified maximum turn limit for each map. This will be adjusted continuously during the contest.

A turn is defined as the above steps. They are performed up to the maximum number of turns times and then the game stops.

Phases

After receiving complete orders from the players, the engine then updates the game state, advancing the game to the next turn. This happens in 6 phases:

  • move (execute orders)
  • attack
  • raze hills
  • spawn ants
  • gather food
  • spawn food

Endbot Conditions

Any of the following conditions will cause a player to finish participating in a game:

  • The player has no live ants left remaining on the map.
  • The bot crashed.
  • The bot exceeded the time limit without completing its orders.
  • A bot attempts to do something that the tournament manager deems a security issue and is disqualified.

If a bot stops participating due to a crash or timeout, their ants remain on the board and can still collide and battle with other ants. Their ants just do not make any future moves and opponents are not explicitly told those ants' owners are no longer participating.

If a bot crashes or times out on a given turn then none of the moves received from that bot will be executed for that turn.

Ranking

At the end of the game, each player is ranked based off the final scores, with a tie resulting in each player having the same ranking. The difference in scores is not reflected in the general ranking of bots, only the relative positions for each game.

Scoring

The objective of the game is to get the highest score. Points are awarded by attacking and defending hills.

  • Each bot starts with 1 point per hill
  • Razing an enemy hill is 2 points
  • Losing a hill is -1 points

This means if you don't attack and lose all your hills, you will end up with 0 points.

If the game ends with only 1 bot remaining, any enemy hills not razed will be awarded to the remaining bot. This is done so that if another bot crashes or times out the remaining bot isn't denied the points for attacking. These are called bonus points.

  • 2 bonus points per remaining hill to the remaining bot
  • -1 point per remaining hill to the owner

Cutoff Rules

To ensure meaningful games are being played on the server, there are several rules in place to cut games short for various reasons.

  • Food Not Being Gathered

If a game consists of bots that aren't capable of gathering food, then the game is cutoff. It is assumed that these are starter bots or very unsophisticated bots. If the total amount of food is 90% of the count of food and ants for 150 turns then the cutoff is invoked.

  • Ants Not Razing Hills

If a game consists of a dominant bot that isn't razing enemy hills, then the game is cutoff. It is assumed that the bot would probably not lose the lead and just isn't sophisticated enough to go in for the kill. If the total amount of live ants for the dominant bot is 90% of the count of food and ants for 150 turns then the cutoff is invoked. Update: Because a bot with a large hive count cannot be taken if they do not move off of the hill, we will stall this cutoff if there is any dead ant on top of a hill not owned by the dominant bot. This gives the dominant bot time to drain the hive count to 0 and score for razing the hill.

  • Lone Survivor

If there is only 1 bot left alive in the game, then the game is cutoff. All other bots have been completely eliminated (no ants on the map) or have crashed or timed out. Remaining enemy hills are awarded to the last bot and points subtracted from the hill owners.

  • Rank Stabilized

If there is no bot with hills left that can gain enough points to gain in rank, then the game is cutoff. Even though bots without hills left could still possibly gain in rank, the game is not extended them, only those with hills. For each bot with a hill, it's maximum score (calculated assuming it could capture all remaining enemy hills) is compared to each opponents minimum score (calculated assuming it would lose all remaining hills). If any score difference can overtake or break a tie then the game continues. If no bot meets this criteria, the game is stopped.

(e.g. For a 4 player game, if bot A razes the hills of bot B and C, the scores are A=5, B=0, C=0 and D=1. Even if bot D razes the hill of bot A the score would be A=4 and D=3, so D can't possible do better than 2nd place and the game ends.)

(e.g. For the same 4 player game, if bot A razes the hill of bot B and bot B still has ants, it is free to attempt to gain points. But after bot A razes the hill of bot C it is no longer given the opportunity even though it could end with a score of A=4, B=2, C=0, D=0.)

  • Turn Limit Reached

There is a maximum turn limit for each map. Each bot is given the limit. The game ends at this point. The limit will be adjusted so about 90%-95% of the games will be ended by this cutoff.

Food Harvesting

Harvesting of food occurs each turn after the battle resolution process. If there are ants located within the spawn radius of a food location one of two things will occur:

  • If there exist ants within the spawn radius belonging to more than one distinct bot then the food is destroyed and disappears from the game.
  • If the ants within the spawn radius all belong to the same bot then the food is harvested and placed into the hive for that bot.

Ant Spawning

As food is harvested, it is placed in the "hive". Each food will spawn 1 ant. Ants are only spawned at hills.

  • The hill must not have been razed.
  • The hill must not be occupied by an ant.

Only 1 ant can be spawned on a hill each turn.

For maps with multiple hills, 1 ant can be spawned at each hill if there is enough food in the hive. If there is less food in the hive than there are hills, each hill is given a priority. The last hill to have an ant on top is chosen last or the hill to have been touched the longest ago is chosen first. In case of a tie, a hill is chosen at random.

This means that if you always move ants off of the hill right away, the spawned ants should be evenly spread between the hills.

You can control which hill to spawn at by keeping an ant nearby to block the hill when you don't want it to spawn ants.

Food spawning

Food spawning is done symmetrically. Every map is symmetric, meaning each bot's starting position looks like every other bots starting position.

  • Each game will start with a few food items placed within the bots starting vision, about 2-5.
  • Starting food will be placed randomly on the map as well, symmetrically.
  • Each game has a hidden food rate that will increase the amount of food in the game. Then the amount to be spawned is divisible by the number of players, then that amount of food will spawn symmetrically.
  • The entire map is divided into sets of squares that are symmetric. The sets are shuffled into a random order. When food is spawned, the next set is chosen. When all the sets have been chosen, they are shuffled again.
  • Every set will spawn at least once before a set spawns a second time. This means if you see food spawn, it may be awhile before it spawns again, unless it was the last set of the random order and was then shuffled to be the first set of the next random order.
  • Sometimes squares are equidistant to 2 bots. This makes for a set that is smaller than normal. The food rate takes this into account when spawning food.
  • Some maps have mirror symmetry so that a set of symmetric squares are touching. It would be unfair to spawn so much food in one place, so these sets are not used. If you can find a mirror symmetry after exploring the map, then you can avoid those spots when looking for food.

The best way to gather the most food is to explore the map and cover the most area.

Battle Resolution

    // how to check if an ant dies
    for every ant:
        for each enemy in range of ant (using attackadius2):
            if (enemies(of ant) in range of ant) >= (enemies(of enemy) in range of enemy) then
                the ant is marked dead (actual removal is done after all battles are resolved)
                break out of enemy loop
  • Ants within the attack radius of each other kill each other (sometimes).
  • If you have more ants than another bot in the area, you won't die (usually).
  • The battle resolution is locally deterministic, meaning
    • you only need to know an ants surroundings
    • and it is easy for the computer to solve.
  • The battle resolution is:
    • fun!
    • means killing your foe without taking loses
    • enables defending your hill with a few ants and inflicting massive losses to the enemy (Sparta!)
    • allows for awesome formations yet to be discovered
    • gets really weird with 3 or more bots in the fight (wait for the other guys to kill each other?)
    • doesn't need to concern you if you use Ender's method of winning the game (the ant hill is down)
    • is the most fun part of this game!

You should read more about it on the Focus Battle Resolution Page

Hill Razing

The objective of the game is to raze your opponents hills and defend your own hill.

A hill is razed (destroyed) when:

  • An enemy ant is at the same location as the hill after the attack phase.

Razed hills do not spawn ants anymore. If all your hills have been razed, but you still have ants, your bot is still alive and your ants can still move, attack, gather food and raze hills.

Bot Input

Parameter Information:
At the start of a game, each bot is passed general parameters about the game, this begins with "turn 0" on its own line. Parameters will then be passed on separate lines with the following format:

type value

The type of a value is determined by the parameter type. Currently all values, except for player_seed, are 32bit signed integers. player_seed is a 64bit signed integer. If the bot encounters an unknown parameter it should treat the value as an opaque string and not try to parse it in any way.

The set of parameter types may be added to the spec in the future, but none will be removed once they have been added. Here is the current list of parameters that will be passed to the bots:

"loadtime"       # in milliseconds, time given for bot to start up after it is given "ready" (see below)
"turntime"       # in milliseconds, time given to the bot each turn
"rows"           # number of rows in the map
"cols"           # number of columns in the map
"turns"          # maximum number of turns in the game
"viewradius2"    # view radius squared
"attackradius2"  # battle radius squared
"spawnradius2"   # food gathering radius squared (name is an unfortunate historical artifact)
"player_seed"    # seed for random number generator, useful for reproducing games

All numbers are a string representation of the number.

Once all parameters have been passed you will receive "ready" on a separate line, at which point you are free to set up for as long as the loadtime specifies.

Turn Information:
Each following turn begins with one of the following lines:

turn turnNo
end

"end" indicates that the game is over, the winner of the game will receive information for the final state of the game following this, should they wish to use it for local testing.

If the game is over, bots will then receive two lines giving the number of players and scores in the following format:

players noPlayers
score p1Score ... pnScore

You are then passed information about the squares you can currently see with the following format:

w row col                            # water
f row col                            # food
h row col owner                      # ant hill
a row col owner                      # live ant
d row col owner                      # dead ant

The end of input for a turn is indicated by receiving "go" on its own line.

You are always passed information as though you are player zero, the first enemy you see always appears as player one, and so on. This helps to ensure that you do not know how many players started in the game.

Information about a water square will only be sent the first turn in which it is visible by one of your live ants (to reduce the amount of data transferred).

You will be passed information for live ant, food and hill squares every turn they are within sight of one of your live ants. Food and hills do not move. They will be sent every turn. If a food is gathered or a hill is razed out of your view radius, you will not be notified. When your ant move back into range it will not receive any info about missing food or razed hills.

Information is given for ants that died during the collision or battle resolution of the previous turn if it is in a square currently visible by one of your live ants. Information is always given about your own dead ants even if you can't see the square. These are merely for your information if you wish to use them, they can otherwise be thought of as land and moved into that turn.

Sample Input:

# [ { "embedded": true, "decorated": false }, 200, 200, {} ]
rows 20 
cols 20 
players 2
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................
m .....*..............
m ......%..b..1.......
m ....................
m ....................
m ........aa..........
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................

Below is sample input for player 'a' in the above game:

turn 0
loadtime 3000  
turntime 1000  
rows 20  
cols 20  
turns 500  
viewradius2 55  
attackradius2 5  
spawnradius2 1  
player_seed 42
ready

turn 1
f 6 5
w 7 6
a 7 9 1 
a 10 8 0
a 10 9 0
h 7 12 1
go

end
players 2
score 1 0
f 6 5
d 7 8 1 
a 9 8 0
a 9 9 0
go

Below is sample input for player 'b' in the above game, starting from the first turn:

turn 1
f 6 5
w 7 6
a 7 9 0 
a 10 8 1
a 10 9 1
go

end
players 2
score 1 0
go

Fog of War

Each bot is passed a parameter at the start of the game indicating the square of each ants visibility, which is how far each ant can see around them. At the moment this is set at 55, giving a view radius of approximately 7.4.

Each turn you are only given current information for the squares that your live ants can currently see.

Distance

Distances are used for the view radius, attack radius and spawn radius. You are given the radii squared in order to avoid floating point numbers and keep to integers.

Distances are calculated using the Euclidean metric, which gives the straight line distance between two points. For two locations a and b, this can be calculated as follows:

drminabsarowbrowtextrowsabsarowbrow dcminabsacolbcoltextcolsabsacolbcol distanceabsqrtdr2dc2

Two locations a and b are considered to be within a distance of r if distanceableqr.

Bot Output

Once the bot has been passed the parameters at the start of the game and it has finished setting up, it is to indicate this to the engine by outputting "go" on its own line.

Each bot may move any number of their ants each turn either north, east, south or west, provided the destination square is not water. Each move should be on a separate line with the following format:

o row col direction

Grid indexes start from zero and directions are to be passed as either 'N', 'E', 'S' or 'W'. At the end of each turn, bots are to output "go" to indicate to the engine that it has finished issuing moves.

Sample Output:

# [ { "embedded": true, "decorated": false }, 200, 200, {} ]
rows 20 
cols 20 
players 2
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................
m .....*..............
m ......%..b..........
m ....................
m ....................
m ........aa..........
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................

Below is sample output from player 'a' in the above game:

go  
o 10 8 N 
o 10 9 N
go

Below is sample output from player 'b' in the above game:

go  
o 7 9 W 
go

Blocking

Only movement is blocked by water. Ants can see and attack over water. If a bot issues a move for an ant onto water, it is considered an invalid move and therefore ignored.

Food will also block an ants movement. This can happen if food spawns next to an ant. Don't move the ant and it will be gathered the next turn.

Collisions

You can order 2 ants to the same space. If you do this, both ants will die. You can order your ant to go to the same space as an enemy ant, both ants will die before the attack radius is considered. This can happen if an ant spawns near an enemy. (You might also be close to losing your hill if enemies are right next to where you spawn!)

Map Format

A map consists of a rectangular grid. Each square can contain land, water, food, a live ant, multiple dead ants or an ant hill. Ants can also be on top of their own hill. The edges of the map are wrapped, meaning if you walk off the top of the map, you will appear at the bottom, or if you walk off the right, you will appear on the left, assuming water doesn't block your path.

A map file is like an ordinary text file, except the extension is ".map" rather than ".txt", with the following format:

rows noRows
cols noCols
players noPlayers
score s1 s2 ...
hive h1 h2 ...
m [.%*!?a-jA-J0-9]

The symbols used have the following meaning:

.   = land
%   = water
*   = food
!   = dead ant or ants
?   = unseen territory
a-j = ant
A-J = ant on its own hill
0-9 = hill

Maps can almost describe the start of any turn of the game, except for multiple dead ants on the same square and who the owner(s) are.

For running games, the maps generated only need describe the start of the game and use only a subset of the full map specification. Food, ants, dead ants are thrown out. No square should be unseen. No score or hive amounts should be included. Maps for games should be symmetric.

Sample Map:

rows 20 
cols 20 
players 2
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................
m .....*..............
m ......%..b..........
m ....................
m ....................
m ........aa..........
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................
m ....................

Map Generators

Maps are generated randomly using a program which is designed to try and result in interesting games while not allowing for people to hard code strategies.

  • Maps are limited to 2 to 10 players
  • Maps must be symmetric
  • Hills must be between 20 and 150 steps away from other enemy hills (friendly hills can be closer)
  • Hills may not be within close range, euclidean distance no less than 6
  • Must be a path through all hills traversable by a 3x3 block
  • Maps must not contain islands
  • Maps are limited to at most 200 in each direction
  • Maps are limited in area to 900 to 5000 area per player, with a total area limit of 25,000.

There are currently no further restrictions on what form the map generator for the final contest will take. New map generators will be welcomed by anyone who wishes to write one. Generators should do the following:

  • Produce a map with the above qualities
  • Can be written in any language

Formats in use

There are two formats the engine can write. The first format is a streaming format that outputs data turn by turn. It is about ten times larger, but can be used to view games in progress (see 'Streaming format' below). The other format is used to store replays on the disk (see 'Storage format' below).

Storage format

Replays you can download from servers are likely the storage format which is replay data and meta data in JavaScript object notation (JSON). Here is an example file (with the replay data truncated):

{
    "challenge": "ants",
    "date": "11-11-1111",
    "playernames": ["amstan", "a1k0n", "mega1"],
    "playerstatus": ["timeout", "crash", "Some other message"],
    "submitids": [6, 3, 7],
    "user_ids": [94, 813, 39],
    "user_url": "http://aichallenge.org/profile.php?user_id=~",
    "game_id": "12345",
    "game_url": "http://aichallenge.org/ants/visualizer.php?game_id=~",
    "replayformat": "json",
    "replaydata": {
        "revision": 2,
        "players": 3,
        "turns": 200,
        <...>
    }
}

Meta data

This format was designed to be future proof, so it contains additional information to distinguish it from other replays as well as meta data

  • challenge is the name of the challenge or game that this replay is for. If it doesn't read "ants" you don't need to parse anything else.
  • replayformat for ants should be "json"
  • replaydata is the replay in the format set by "replayformat". As only "json" is in use, the replay data will automatically be parsed by your JSON library of choice.
  • user_url and user_ids can be used to get a link to each user's page on the respective server. The ~ is replaced by the id.
  • game_url and game_id can be used to find the original game.
  • playerstatus explains what happened to a player after its last turn. The status could be any string with spaces, but the following predefined strings should be used it appropriate: 'timeout' (could be displayed as '... did not respond in time' or '... timed out') = the bot did not respond in time and was disqualified, 'crash' = the bot program crashed, 'eliminated' = no ants survived. 'survived' = the bot survived to the end of the game. Other status messages could also be used and must be displayed literally. E.g.: 'The bot tried to install a root kit'.
  • submitids Each ant bot code submitted to the contest is assigned a unique id. For reference this can be included in the metadata. In case player's submissions are made available after the contest, the id from a downloaded replay can be used to find the code.
  • playercolors <array of html color codes> The replay file can set player colors in html notation. This is either #rrggbb or #rgb where r, g and b are upper- or lowercase hexadecimal digits. A visualizer must be prepared to select default colors for the players if the replay lacks them. An example can be found here [[http://martin.ankerl.com/2009/12/09/how-to-create-random-colors-programmatically/]] same color.
  • antvalue <bounty> The score value for a dying ant.

A visualizer is required to understand and check the "challenge" key, then check the "replayformat" and finally read the "replaydata". The other keys are optional information.

Replay data

The "replaydata" field is an object made up of a list of all ants in the game, the map, the scores for each player and turn and some game settings.

  • revision 2 The revision of this specification that was used to generate the replay.
  • players <number> This sets up the number of players in the replay. It can be anywhere from 1 to 26.
  • loadtime <time in ms> This time was given to the bot executables to load up before the match started.
  • turntime <time in ms> This time was given to the bot for each turn.
  • turns <number> The turn limit that was set for the match, which may have ended earlier.
  • viewradius2 <number> The squared ant view radius.
  • attackradius2 <number> The squared attack radius.
  • spawnradius2 <number> The squared spawn radius.
  • <parameter name> <value> Other parameters can have arbitrary names and are meant for an easy extension of the format.
  • map <object> This object contains the map.
    • rows <number> The number of rows in the map.
    • cols <number> The number of columns in the map.
    • data <array> An array of strings, one for each row. Every string in the array must contain as many characters as there are columns. The used characters in maps are: . = land, % = water, * = food. If a player has a starting ant, instead of '.' the map will show a letter from 'a' to 'z' = player 1 to 26. These spawns and the food locations are not authorative for the visualizer, but can be used as a preview in a replay browser application. That said a visualizer should assume all squares to be land if their character is not '%'.
  • ants <array> An array of all ants in the game. Food and the ant it is eventually converted into is also a single element of this array. Food can be considered an ant which doesn't have an owner yet. There are some cases to be considered: Some food is never converted, some ants are there from the beginning of the game, some ants survive, some food could be removed from the game if the rules allow two enemy ants to come close enough to the food item. Each element of the ants array is itself an array with either 4 elements (food, which is not converted) or 7 elements: <row> <col> <start turn> <conversion turn> <end turn> <player> <moves> Each object has an initial <row> and <col> on the map as well as the <start turn> in which they first appear on the map. For the <conversion turn> and the <end turn> there is a special rule that makes parsing easier: The turn number is the total number of turns +1 if the food or ant survives the game. The <conversion turn> tells the visualizer when the food is converted into an ant or disappears from the map. The parameter list may end here if the food is not converted to a player (i.e. it disappears or survives the whole game). If the food is converted, the following parameters exist. <end turn> is basically the same as <conversion turn>. It is either total turns +1 or the turn in which the ant is dead. <player> is the 0 based player number and <moves> is a string of commands issued by the bot for the ant. Each character is either '-' = do nothing or a move order ('n', 'e', 's', 'w') for a turn starting with <conversion turn>. Note: For ants that are there from the beginning of the game both <start turn> and <conversion turn> are 0!
  • scores <array> There will be exactly as elements in this array as there are players. The first element is for player 1, the second for player 2 and so on. Each element is an array of floating point score values, where each value represents the player's score for the start of a turn. If a player crashed before completing its first turn there will be one score entry (usually 0). If a player survived a 200 turns game, there will be 201 values including the end game score. A reason why a certain player did not make it to the end may be given in the meta data.
  • bonus <array> An optional field that holds the "food bonus" value for each player. Any number which is not 0 is added to the score after the last turn in the game.

Streaming format

The streaming format can be used to visualize games in progress. It produces a lot more data than the storage format, but has the benefit of being turn based. That means that each turn can be visualized as soon as the engine completed it. Details of the format follow...

Miscellaneous

In order to ensure that people are able to see how well their bot performs relative to the other people who decide to participate in the contest, we encourage people not to share bot code that goes beyond the functionality of a starter bot until final submissions are closed.

It is still alright, in fact highly encouraged, for people to share strategy ideas and general tools that people can use, both to improve their bot or enable easier development and debugging.

More Information

If you have a question about the game mechanics, you may ask in the forums, in the #aichallenge IRC channel on Freenode, or go straight to the contest's source code.