Formic Functions - Ant Queen of the Hill Contest

Question

Watch live | Active answers | Add new answer | Chat room | Source code | Leaderboard

New tournaments whenever needed. New players and new updates very welcome.

^{Not actual game footage.}

Each player starts with one ant - a queen, who collects food. Each piece of food can be held or used to produce a worker. Workers also collect food to be brought back to the queen.

16 players compete in one arena. The winner is the queen holding the most food after she has taken 30,000 turns. The catch is that the ants can only communicate by changing the colors of the arena squares, which may also be changed by rival ants...

Watching the game

This is a JavaScript competition, which means you can watch the game play out live in your browser by clicking the link below.

Click here to watch the game being played live

Many thanks to Helka Homba for the original Stack Snippet King of the Hill contests, Red vs. Blue - Pixel Team Battlebots, and Block Building Bot Flocks, which provided the idea of a web browser hosted KotH and heavily informed the code for this one.

Huge thanks also for all the feedback and testing from the wonderful people in the Sandbox and in Chat.

Leaderboard

(Click the image to see the full leaderboard and joint places explanation - only a few players are showing here to save space.)

This leaderboard is based on the players as they were on Sunday 2^nd September 2018.

Screenshots

Some images of how the arena looks towards the end of a game. Click images to view full size.

To get an idea of what is happening in the arena and how all these patterns form, you can run the game and hover the mouse over the arena to zoom in and see the ants at work. Also see the fascinating explanations in the answers.

The arena

The arena is a toroidal (edge wrapping) grid of square cells. It has width 2500 and height 1000. All cells start as color 1.

Initially exactly 0.1% of cells will contain food. The 2500 pieces of food will be scattered uniformly randomly. No new food will be introduced during the game.

The queens will be placed randomly on empty cells, with no guarantee that they will not be adjacent to each other (although this is very unlikely).

Ant abilities

• Sight: Each ant sees the 9 cells in its 3 by 3 neighbourhood. It has no knowledge of any other ants outside this neighbourhood. It sees the contents of each of the 9 cells (other ants and food), and also each cell's color.
• No memory: Each ant makes its decisions based on what it sees - it does not remember what it did in the previous turn and has no way of storing state other than in the colors of the arena cells.
• No orientation: An ant does not know where it is or which way it faces - it has no concept of North. The 3 by 3 neighbourhood will be presented to it at a randomly rotated orientation that changes each turn so it cannot even walk in a straight line unless it has colors to guide it. (Making the same move every turn will result in a random walk rather than a straight line.)
• Moving, color marking and producing workers: See Output below.
• Immortality: These are highland ants that cannot die. You can confuse rival ants by changing the colors around them, or constrain them from moving by surrounding them with 8 ants of your own, but they cannot be harmed apart from this.
• Carrying food: A worker can carry up to 1 piece of food. A queen can carry an arbitrary amount of food.
• Transferal of food: If a worker is adjacent to a queen (in any of the 8 directions), food will be automatically transferred in one of the following ways:
  • A laden worker adjacent to its own queen will transfer its food to its queen.
  • An unladen worker adjacent to an enemy queen will steal 1 piece of food, if present.

A worker cannot steal from a worker, and a queen cannot steal from a queen. Also a worker cannot take food from its own queen, and a queen cannot steal from an enemy worker.

Note that ants take turns sequentially and food transferral occurs at the end of each ant's individual turn and does not take up a turn. It happens regardless of whether a worker moves next to a queen or a queen moves next to a worker, and still happens if both ants involved stand still for their move.

Coding

Provide a function body

Each ant is controlled by an ant function. Each turn the player's ant function is called separately for each ant (not just once per player, but once for the queen and once for each worker that player controls). Each turn, the ant function will receive its input and return a move for that particular ant.

Post an answer containing a code block showing the body of a JavaScript function, and it will be automatically included in the controller (just refresh the controller page). The name of the player forms the title of the answer, in the form # PlayerName (which will be truncated to a maximum of 40 characters in the controller tables).

No state, no time, no random

A function must not access global variables and must not store state between turns. It may use built in functions that do not involve storing state. For example, the use of Math.abs() is fine, but Date.getTime() must not be used.

An ant function may only use a pseudo random number generator that it supplies itself, that does not store state. For example, it may use the colors/food/ants visible as the seed each turn. Math.random() is explicitly forbidden, since like nearly all pseudorandom number generators, it stores state in order to progress to the next number in sequence.

A simple random strategy is still possible due to the random orientation of the input - an ant that always chooses the same direction will perform a random walk rather than a straight line path. See the example answers for simple ways of using this randomness and avoiding this randomness.

An ant function is permitted to contain further functions within its body. See the existing answers for examples of how this can be useful.

Console.log

You can log to the console during testing a new challenger player, but once posted as an answer here the player will have no access to console.log. Attempting to use it will result in an error and disqualification until edited. This should help to keep leaderboard tournaments fast, while still allowing debugging code pasted into the new challenger text area.

Input and output

Input

The orientation of the input will be chosen at random for each ant and for each turn. The input will be rotated by 0, 90, 180 or 270 degrees, but will never be reflected.

Cells are numbered in English reading order:

0 1 2
3 4 5
6 7 8

The ant function will receive an array called view, containing an object for each of the 9 visible cells. Each object will have the following:

color: a number from 1 to 8
food: 0 or 1
ant: null if there is no ant on that cell, or otherwise an ant object

If a cell contains an ant, the ant object will have the following:

food: 0 or more (maximum 1 for a worker)
type: 1 to 4 for a worker, or 5 for a queen
friend: true or false

The ant can determine its own details by looking at the ant in the central cell, view[4].ant. For example, view[4].ant.type is 5 for a queen, or a number from 1 to 4 for a worker (indicating its type).

Output

Output is returned as an object representing the action to take. This can have any of the following:

cell: a number from 0 to 8 (mandatory)
color: a number from 1 to 8 (optional)
type: a number from 1 to 4 (optional)

If color and type are omitted or zero, then cell indicates the cell to move to.

If color is non-zero, the indicated cell is set to that color.

If type is non-zero, a worker ant of that type is created on the indicated cell. Only a queen can create a new worker, and only if she has food, as this costs one piece of food per worker.

Example outputs:

{cell:0}: move to cell 0
{cell:4}: move to cell 4 (that is, do nothing, as 4 is the central cell)
{cell:4, color:8}: set own cell to color 8
{cell:6, type:1}: create a type 1 worker on cell 6
{cell:6, color:1}: set cell 6 to color 1
{cell:6, color:0}: equivalent to just `{cell:6}` - move rather than set color
{cell:6, type:0}: equivalent to just `{cell:6}` - move rather than create worker
{cell:6, color:0, type:0}: move to cell 6 - color 0 and type 0 are ignored

Invalid outputs:

{cell:9}: cell must be from 0 to 8
{cell:0, color:9}: color must be from 1 to 8
{cell:0, type:5}: type must be from 1 to 4 (cannot create a new queen)
{cell:4, type:1}: cannot create a worker on a non-empty cell
{cell:0, color:1, type:1}: cannot set color and create worker in the same turn

An ant moving onto a cell containing food will automatically pick up the piece of food.

Worker type

Each worker has a type, a number from 1 to 4. This has no meaning to the controller, and is for the player to do with as they wish. A queen could produce all her workers as type 1, and give them all the same behaviour, or she could produce several types of workers with different behaviours, perhaps type 1 as foragers and type 2 as guards.

The worker type number is assigned by you when a worker is created, and cannot be changed thereafter. Use it however you see fit.

Turn order

Ants take turns in a set order. At the start of a game the queens are assigned a random order which does not change for the rest of the game. When a queen creates a worker, that worker is inserted into the turn order at the position before its queen. This means that all other ants belonging to all players will move exactly once before the new worker takes its first turn.

Limit on number of players

Obviously an unlimited number of players cannot fit into the arena. Since there are now more than 16 answers, each game will feature a randomly chosen 16 of them. The average performance over many games will give a leaderboard featuring all the players, without ever having more than 16 in a single game.

Time limit per turn

Each time the ant function is called, it should return within 15 milliseconds. Since the time limit may be exceeded due to fluctuations outside the ant function's control, an average will be calculated. If at any point the average is above 15 milliseconds and the total time taken by that particular ant function across all calls so far is more than 10 seconds, the relevant player will be disqualified.

Disqualification

This means the player will not be eligible to win and their ant function will not be called again during that game. They will also not be included in any further games. If a player is disqualified on the tournament machine during a leaderboard game then it will be excluded from all future leaderboard games until edited.

A player will be disqualified for any of the following for any of its ants (queen or worker):

• Exceeding the time limit as described (averaged over 10 seconds).
• Returning an invalid move as described under Output.
• The cell to move to contains an ant.
• The cell to move to contains food and the ant is already a laden worker.
• The cell to produce a worker on is not empty (contains food or an ant).
• A worker is trying to produce a worker.

It may seem harsh to disqualify for invalid moves, rather than simply interpreting this as no move. However, I believe that enforcing correct implementations will lead to more interesting strategies over time. This is not intended to be an additional challenge, so a clear reason will be displayed when a player is disqualified, with the specific input and output alongside to aid in fixing the code.

Multiple answers and editing

You may provide multiple answers, provided that they do not team up against the others. Provided each answer is working solely towards its own victory, you are permitted to tailor your strategy to take advantage of weaknesses in specific other strategies, including changing the color of the cells to confuse or manipulate them. Bear in mind that as more answers come in, the likelihood of meeting any particular player in a given game will diminish.

You may also edit your answers whenever you choose. It is up to you whether you post a new answer or edit an existing one. Provided the game is not flooded with many near-identical variations, there should be no problem.

If you make a variation of another person's answer, please remember to give them credit by linking to their answer from yours.

Scoring

At the end of each game, a player's score is the number of other players who have less food carried by their queen. Food carried by workers is not counted. This score is added to the leaderboard, which is displayed in order of average score per game.

Joint places indicate that the order of players is not yet consistent between 6 subsets of the games played so far. The list of games is split into 6 subsets because this is the minimum number that will give a probability of less than 5% that a given pair of players will be assigned distinct places in the wrong order.

Chat

To keep the comments section clear here, please use the dedicated chat room for any questions and discussion. Comments on this post are likely to be cleared after a while, whereas messages in the chat room will be kept permanently.

Just to let you know, I'll be more inclined to upvote answers that include a clear and interesting explanation of how the code works.

Answer 1

Straighter

var i, j
var orthogonals = [1, 3, 7, 5]  // These are the non-diagonal cells
// Color own cell if white
if (view[4].color != 6) {
    return {cell:4, color:6}
}
var specified = null;
// Otherwise move to a white cell opposite a colored cell
for (i=0; i<4; i++) {
    j = (i+2) % 4
    if (view[orthogonals[i]].color !== 6 &&
        view[orthogonals[j]].color == 6 && !view[orthogonals[i]].ant) {
        specified = {cell:orthogonals[i]};
    } else if (view[orthogonals[i]].food) {
        return {cell:orthogonals[i]}
    }
}
if(specified) { return specified; }
// Otherwise move to one of the vertical or horizontal cells if not occupied
for (i=1; i<9; i+=2) {
    if (!view[i].ant) {
        return {cell:i}
    }
}

// Otherwise move to one of the diagonal cells if not occupied
for (i=0; i<9; i+=2) {
    if (!view[i].ant) {
        return {cell:i};
    }
}

// Otherwise don't move at all
return {cell:4};

Since, while testing trail eraser, I noticed that it sometimes nears the top of the leaderboard when it doesn't find any trails, I'm posting an ant using the same movement but no workers. Basicaly a repost of smart straight line from meta, except ignores other colors and doesn;t make workers (thereby avoiding disqualification)

Answer 2

Antdom Walking Artist

This is a fancy queen-only random walk entry with a slight twist-- the queen ant wanders around coloring cells if she feels that there aren't enough non-colored cells nearby. If she sees food, she'll instantly grab it. Hopefully she could gather some food, unless other ants steal them away.

A lot of worker ants would stop by and be appalled at the "marvelous" art. This means that other worker ants may eventually forget to return to their own queen ants.

Workers can be spawn occasionally. They walk along horizontal or vertical lines if they haven't found any food yet, and will walk on diagonal lines once they found some food. Unfortunately, there is little coordination between the queen and the workers, and the workers will forever roam free.

How it works

1. If this is a Queen ant (type 5):

   a. If there is food in either of the 8 neighboring cells, fetch food.

   b. Otherwise, if there are strictly less than 4 colored cells in the 8 neighboring cells, color the lowest-indexed white cell with the color code next_color = (8 - #colored).

   c. Otherwise, when time is just right, (i.e. if seed = 666 mod 2333 and me['food'] = 2 mod 3), spawn a worker of random type.

   d. Otherwise, walk to the lowest-indexed neighboring cell that contains no ant.

2. If this is a Worker ant (type 1-4):

   a. If the worker is unladen (does not carry food) and if there is food in either of the 8 neighboring cells, fetch food.

   b. Otherwise, if the worker is walking on a white cell, it gets colored by Math.abs(next_color - 2) + 2.

   c. Otherwise, attempt to walk along a straight line in the vertical or horizontal direction. If this is not possible, walk to the lowest-indexed neighboring cell that contains no ant (and no food if the worker is laden).

Code

var action = { cell: 4, color: 0, type: 0 },
    colors = view.map((v) => v.color),
    foods = view.map((v) => v.food === 1),
    ants = view.map((v) => v.ant),
    me = ants[4];

var seed = colors.reduce((s, v) => s * 8 + (v - 1));

// Search the neighboring cells for food and walk on to them.
var next_food = foods.indexOf(true);

// As the last measure, find a move that avoids other ants and food.
var get_direction = (view) => {
    var direction = 4, complete = false;
    for (var i = 0; !complete && i < 4; ++i) {
        if (view[i]['ant'] === null && view[i]['food'] === 0) {
            complete = true;
            direction = i;
        }
    }
    for (var i = 5; !complete && i < 9; ++i) {
        if (view[i]['ant'] === null && view[i]['food'] === 0) {
            complete = true;
            direction = i;
        }
    }
    return direction;
};

// Attempt to walk along a diagonal.
var get_diagonal_opposite = (view, food) => {
    var direction = null;
    if (view[0]['color'] === 1 && view[8]['color'] > 1 && view[0]['ant'] === null && view[0]['food'] <= food) {
        direction = 0;
    } else if (view[8]['color'] === 1 && view[0]['color'] > 1 && view[8]['ant'] === null && view[8]['food'] <= food) {
        direction = 8;
    } else if (view[2]['color'] === 1 && view[6]['color'] > 1 && view[2]['ant'] === null && view[2]['food'] <= food) {
        direction = 2;
    } else if (view[6]['color'] === 1 && view[2]['color'] > 1 && view[6]['ant'] === null && view[6]['food'] <= food) {
        direction = 6;
    }
    return direction;
};

// Attempt to walk along a horizontal or vertical line.
var get_lateral_opposite = (view, food) => {
    var direction = null;
    if (view[1]['color'] === 1 && view[7]['color'] > 1 && view[1]['ant'] === null && view[1]['food'] <= food) {
        direction = 1;
    } else if (view[7]['color'] === 1 && view[1]['color'] > 1 && view[7]['ant'] === null && view[7]['food'] <= food) {
        direction = 7;
    } else if (view[3]['color'] === 1 && view[5]['color'] > 1 && view[3]['ant'] === null && view[3]['food'] <= food) {
        direction = 3;
    } else if (view[5]['color'] === 1 && view[3]['color'] > 1 && view[5]['ant'] === null && view[5]['food'] <= food) {
        direction = 5;
    }
    return direction;
};

// A random color. Starts from 8. Reduce 1 if any neighboring cells are colored.
var next_color = 8 - colors.reduce((s, v, i) => s + ((i !== 4 && v > 1) ? 1 : 0), 0);
if (me['type'] === 5) {
    // Queen Ant
    if (next_food !== -1) {
        // Moves onto food.
        action['cell'] = next_food;
    } else if (next_color > 4) {
        // If not enough colored cells, go around and color.
        var target = colors.indexOf(1);
        action['cell'] = target;
        action['color'] = next_color;
    } else if (seed % 2333 === 666 && me['food'] % 3 === 2) {
        // If queen has (3k + 2) food pellets, randomly spawn worker ants.
        var type = seed % 4 + 1;
        if (ants[1] === null) {
            action['type'] = type;
            action['cell'] = 1;
        } else if (ants[0] === null) {
            action['type'] = type;
            action['cell'] = 0;
        }
    } else {
        action['cell'] = get_direction(view);
    }
} else if (me['type'] <= 4) {
    // Gatherers
    if (me['food'] === 0) {
        // 1. Collect food if one is nearby.
        // 2. Color current cell.
        // 3. Move in a vertical/horizontal line.
        if (next_food !== -1) {
            action['cell'] = next_food;
        } else if (colors[4] < 2) {
            action['cell'] = 4;
            action['color'] = Math.abs(next_color - 2) + 2;
        } else {
            // Do not color everything.  That will expose oneself.
            action['cell'] = get_lateral_opposite(view, 1) || get_direction(view);
        }
    } else {
        // 1. Color current cell.
        // 2. Move diagonally.
        if (colors[4] < 2) {
            // Color current cell.
            action['cell'] = 4;
            action['color'] = Math.abs(next_color - 2) + 2;
        } else {
            action['cell'] = get_diagonal_opposite(view, 0) || get_direction(view);
        }
    }
}

if (action['color'] === 0) {
    delete action['color'];
}
if (action['type'] === 0) {
    delete action['type'];
}

return action;