Game of Game of Life

Question

Game of Game of Life

Conway's Game of Life is a 0-player game. But that's okay! We can make it a multi-player game.

This game is played on the smallest square grid that will accommodate a 6x6 square for each player (12x12 for 2-4 players, 18x18 for 5-9 players, etc). This grid is actually a torus, so it wraps in both directions. The rules of Life are:

• If a cell has exactly 3 neighbours, it comes to life (or remains alive) in the next generation.
• If a cell has exactly 2 neighbours, it does not change in the next generation.
• If it does not have exactly 2 or 3 neighbours, it dies in the next generation.

A cell's neighbours are those cells adjacent to it orthogonally or diagonally; each cell has 8 neighbours. In this game, there are only a few differences from the standard Game of Life:

• Each player has a different colour of life, with dead cells being white and neutral living cells being black.
• When a cell becomes alive, it takes on the colour of its most common neighbour, or black (no player) if there are three different colours. Cells do not change colour as long as they are alive.
• Each generation, each bot can cause one nearby cell to come alive in their colour or one of their own cells to die. This happens before a generation is processed; a cell that is killed may come back to life and a cell brought to life may die in the subsequent generation.

Winning the game

The game lasts 1000 generations, or until there is only one colour of living cells remaining. If all coloured cells die on the same generation, the game is a draw, and no bot receives points. Each bot scores points equal to the percentage of living coloured cells it has at that time (out of the total number of coloured cells). 10000 games will be run, and the winner is the bot with the highest average score. Ties are broken with a 1v1 cage match.

Starting conditions

Each bot will start with the following layout of living cells:

......
......
..##..
..##..
......
......

These will be randomly arranged into the square playing area. Each 6x6 area without a bot will have the same configuration, but with black living cells.

Bot parameters

Your bot will be written in Javascript, and will not have an average call time of over 50ms (bots that do may be disqualified, but bots may use performance.now() to police their own time). It will accept as parameters:

grid - The grid on which the game is played.  This should not be modified.
botId - The bot's ID, corresponding to the colour on the grid.
lastMoves - An array of each bot's most recent move, as it's (usually) possible but computationally intensive to get this information otherwise.

Your bot will return an array with two elements, x and y. This is the cell that your bot wishes to play. It must be within 2 cells of one of your living cells. If the selected cell is alive and not one of your cells, it does nothing unless the bot whose colour it is removes it on the same generation, in which case it causes it to be your colour. If it is alive and one of your cells, that cell is killed before the next generation. If it is a dead cell, it comes alive before the next generation (it comes alive as your bot's colour unless some other bot also picks it, in which case it comes alive black).

A play too far away from one of your cells is a pass. Alternately, [-1,-1] is an explicit pass. A play off of the board in any other way is illegal and grounds for disqualification.

On the grid, -1 is black (neutral living), 0 is white (dead), and all other numbers are the id of the bot whose life is in that cell.

Other Restrictions

• You may make a maximum of 3 bots.
• If your bots uses random numbers you can use Math.random.
• Your bot may, if it wishes, store data on this. It will be cleared between games.
• You may not make a bot which targets a single, prechosen bot. Your bot may target the tactics of a class of bots.
• Cooperation is legal between bots, but communication is not - you can cooperate with a strategy, but not attempt to make a specific sequence of moves which identifies your bot. For example, identifying a bot based on specific starting sequence is not allowed, but knowing "target bot prefers moving up and left, all else equal" is okay. IDs are randomized and bots will not know in advance what other bots' IDs are.

Controller

This isn't quite complete, but it's a good start. I plan to keep track of scores, add a box so it's easy to test a new bot, etc. Of course, some of that is hard to test without real competitors, but I'll get around to it.

It seems that I made x the major axis and y the minor one, so if your bot is going a different way than you expect, that might be why. Sorry.

Code Run it here

Example bot

It seems traditional to include a bad bot in the competition to get things started. This bot is bad. It chooses uniformly at random from cells in the grid and tries to move there. I haven't yet had it survive 1000 generations.

function randomMovesBot(grid, botId, lastMoves){
    return [Math.floor(Math.random() * grid.length), Math.floor(Math.random() * grid.length)];
}

Winner

Two weeks after the last new submission (or a significant change to a bot), I'll close this by running 10000 games (number subject to possible revision). I'll leave the controller up afterward if someone wants to make a new submission, but official standings won't change.

Chat

Answer 1

Do-nothing

function rgs_do_nothing(grid, id, last_moves) {
    return [-1, -1];
}

As of the time of posting, this wins against all other bots in the competition fairly consistently.

This bot is funny because in the branch of numerical analysis where I did some research, sometimes we have partial differential equations with these do-nothing boundary conditions and for a method I implemented, it literally amounted to doing nothing to handle the boundary conditions... My best type of work is when it is legit to do nothing :')

Answer 2

planBbot

I took planBot as a blue print. With simple enhancements/changes:

Version 1.1

• improved move selection: never delete own colour cells
• improved scoring
• improved time management: used a PD-Controller to stay at 50ms
• changed policy: dropped endgame mode
• result of playing 100 games:

Name            Score
BestNowBot        0
planBbot v1.1   100
planBot           0
randomMovesBot    0
rgs_do_nothing    0

Version 1.0

• simple time management: Try to stay within 50 ms per move on average while using as much time as possible for lookaheads.

• some performance tweaks: Undone caching of results. (Identical board states are too unlikely.)

• scoring: The idea: Stay sparse and don't feed the opponent.

• endgame aware: If planBbot survived until generation 990 it starts to look deep ahead to generation 1000.

• result of playing 100 games:

Name            Score
BestNowBot        0.64
planBbot v1.0    85.40
planBot          13.94
randomMovesBot    0
rgs_do_nothing    0

// version 1.1
function planBbot(grid, botId, lastMoves) {
    let t0=performance.now();
    let best_cell = [-1, -1];
    let max_score = -10000000;
    let size = grid.length;
    let possible_moves = new Set();
    let dist = 1
    for (let x = 0; x < size; x++) {
        for (let y = 0; y < size; y++) {
            if (grid[x][y] == botId) {
                for (let dx = -dist; dx <= dist; dx++) {
                    for (let dy = -dist; dy <= dist; dy++) {
                        let x1 = (size + x + dx) % size;
                        let y1 = (size + y + dy) % size;
                        if (grid[x1][y1] == 0) {
                            possible_moves.add([x1, y1]);
                        }
                    }
                }
            }
        }
    }
    if (possible_moves.size == 0) {
        return best_cell;
    }

    let new_grid = Array(size).fill(0).map(() => new Array(size).fill(0));
    if (typeof this.A == "undefined" || typeof this.A.dtime == "undefined") {
        this.A={iters:4, dtime:49, count:0, e0:0};
        this.A.lookahead=function(old_grid, new_grid){
            let iscore = 0;
            let oscore = 0;
            let neighbours = [];
            for (let x = 0; x < size; x++) {
                for (let y = 0; y < size; y++) {
                    neighbours.length = 0;
                    for (let dx = -1; dx <= 1; dx++) {
                        for (let dy = -1; dy <= 1; dy++) {
                            if ((dx == 0) && (dy == 0)) {
                                continue;
                            }
                            let cell = old_grid[(size + x + dx) % size][(size + y + dy) % size];
                            if (cell != 0) {
                                neighbours.push(cell);
                            }
                        }
                    }

                    let next=old_grid[x][y];
                    switch(neighbours.length) {
                    case 2: break;
                    case 3: if (next == 0) {
                            if (neighbours[0] == neighbours[1] || neighbours[0] == neighbours[2]) {
                                next = neighbours[0];
                            } else if (neighbours[1] == neighbours[2]) {
                                next = neighbours[1];
                            } else {
                                next = -1;
                            }
                        }
                        break;
                    default: next = 0;
                    }

                    new_grid[x][y] = next;
                    if (next == botId) {
                        iscore++;
                    } else if (next != 0) {
                        oscore++;
                    }
                }
            }
            if (oscore==0) {
                return 100000
            }
            return (iscore)-4*(oscore);
        }
    }

    let me=this.A;
    me.count++;
    let e=49-me.dtime;
    me.iters+=0.05*e+0.0005*(e-me.e0);
    me.e0=e;
    let iters=0.3*size*size*Math.max(me.iters, 2)/possible_moves.size;
    iters=Math.min(Math.max(iters+0.5, 3), 7);
    for (cell of possible_moves) {
        let old_grid = grid.map(x => x.slice());
        old_grid[cell[0]][cell[1]] = botId - old_grid[cell[0]][cell[1]];
        let score = 0;
        for (let i = 0; i < iters; i++) {
            score += me.lookahead(old_grid, new_grid);
            let tmp = new_grid;
            new_grid = old_grid;
            old_grid = tmp;
        }

        if (score >= max_score) {
            max_score = score;
            best_cell = cell;
        }
    }
    me.dtime=performance.now() - t0;
    return best_cell;
}

Answer 3

Best Now Bot

function BestNowBot(grid, botId, lastMoves){
    let wrap = coord => coord < 0 ? coord + grid.length : coord >= grid.length ? coord - grid.length : coord;
    let adj_life = (x, y) => {
        let sum = 0, sum_mine = 0;
        for (let i = -1; i <= 1; i++){
            for (let j = -1; j <= 1; j++){
                if (!i && !j) continue;
                if (grid[wrap(x+i)][wrap(y+j)]) sum++;
                if (grid[wrap(x+i)][wrap(y+j)] == botId) sum_mine++;
            }
        }
        return [sum, sum_mine];
    }
    let my_cells = [];
    for (let i = 0; i < grid.length; i++){
        for (let j = 0; j < grid.length; j++){
            if (grid[i][j] == botId){
                my_cells.push([i, j]);
            }
        }
    }
    let legal_moves = my_cells.slice();
    my_cells.forEach(cell => {
        for (let i = -2; i <= 2; i++){
            for (let j = -2; j <= 2; j++){
                let x = wrap(cell[0] + i),
                    y = wrap(cell[1] + j);
                if (grid[x][y] == 0 && !legal_moves.some(m => m[0] == x && m[1] == y)){
                    legal_moves.push([x, y]);
                }
            }
        }
    });
    // Calculate results of each move.
    legal_moves.forEach(move => {
        let move_score = 0;
        if (grid[move[0]][move[1]] == botId) move_score--;
        for (let i = -1; i <= 1; i++){
            for (let j = -1; j <= 1; j++){
                let x = wrap(move[0] + i),
                    y = wrap(move[1] + j);
                let [adj, adj_mine] = adj_life(x, y);
                if (grid[x][y] == botId && adj == 3){
                    move_score--;
                } else if (grid[x][y] == 0 && adj == 2 && adj_mine > 0){
                    move_score++;
                }
            }
        }
        move.push(move_score);
    });
    let best = Math.max(...legal_moves.map(m => m[2]));
    let good_moves = legal_moves.filter(m => m[2] == best);
    return good_moves[Math.floor(Math.random() * good_moves.length)].slice(0, 2);
}

BestNowBot looks at all the available options and determines which of them are positive for it, and then selects randomly from them. Feel free to use BestNowBot as a basis for an answer - I figure it's kind of a baseline for an effective bot.

At time of posting, wins ~99% of games.

Answer 4

function advance(hash_grid, old_grid, new_grid){
    let hash = 0;
    let size = old_grid.length;
    let neighbours = [];
    for (let x = 0; x < size; x++) {
        for (let y = 0; y < size; y++) {
            neighbours.length = 0;
            for (let dx = -1; dx <= 1; dx++) {
                for (let dy = -1; dy <= 1; dy++) {
                    if ((dx == 0) && (dy == 0)) {
                        continue;
                    }
                    let cell = old_grid[(size + x + dx) % size][(size + y + dy) % size];
                    if (cell != 0) {
                        neighbours.push(cell);
                    }
                }
            }
            if (neighbours.length < 2 || neighbours.length > 3) {
                new_grid[x][y] = 0;
            } else if (neighbours.length == 3 && old_grid[x][y] == 0) {
                if (neighbours[0] == neighbours[1] || neighbours[0] == neighbours[2]) {
                    new_grid[x][y] = neighbours[0];
                } else if (neighbours[1] == neighbours[2]) {
                    new_grid[x][y] = neighbours[1];
                } else {
                    new_grid[x][y] = -1;
                }
            } else {
                new_grid[x][y] = old_grid[x][y];
            }
            hash += hash_grid[x][y] * new_grid[x][y];
        }
    }
    return hash;
}

function planBot(grid, botId, lastMoves) {
    let size = grid.length;
    let possible_moves = new Set();
    let count = 0;
    for (let x = 0; x < size; x++) {
        for (let y = 0; y < size; y++) {
            if (grid[x][y] == botId) {
                count++;
                for (let dx = -1; dx <= 1; dx++) {
                    for (let dy = -1; dy <= 1; dy++) {
                        let x1 = (size + x + dx) % size;
                        let y1 = (size + y + dy) % size;
                        if ((grid[x1][y1] == 0) || (grid[x1][y1] == botId)) {
                            possible_moves.add([x1, y1]);
                        }
                    }
                }
            }
        }
    }
    let possible_move_array = Array.from(possible_moves);
    if (possible_move_array.length == 0) {
        return [0,0];
    }
    let neighbor_scores = function(n) {
        if ((n >= 2) && (n <= 3)) {
            return 0;
        }
        return -1;
    }
    let best_cell = [0, 0];
    let max_score = -10000;
    let memo = new Map();
    let hash_grid = Array(size).fill(0).map(() => new Array(size).fill(0).map(() => Math.random()));
    let new_grid = Array(size).fill(0).map(() => new Array(size).fill(0));
    let iters = 4;
    for (cell of possible_move_array) {
        let old_grid = grid.map(x => x.slice());
        old_grid[cell[0]][cell[1]] = botId - old_grid[cell[0]][cell[1]];
        let hashes = []
        let score = 0;
        let hit = false;
        for (let i = 0; i < iters; i++) {
            let hash = advance(hash_grid, old_grid, new_grid);
            hashes.push(hash);
            if (memo.has(hash)) {
                score = memo[hash];
                hit = true;
                break;
            }
            let tmp = new_grid;
            new_grid = old_grid;
            old_grid = tmp;
        }
        if (!hit) {
            for (let x = 0; x < size; x++) {
                for (let y = 0; y < size; y++) {
                    if (old_grid[x][y] == botId) {
                        score++;
                    } else if (old_grid[x][y] > 0) {
                        score -= 1e-7;
                    }
                }
            }
        }
        for (hash of hashes) {
            memo.set(hash, score);
        }
        score += 1e-9 * Math.random();
        if (score >= max_score) {
            max_score = score;
            best_cell = cell;
        }
    }
    return best_cell;
}

Rolls ahead a few steps for each potential move and picks the move which resulted in the greatest area for itself, breaking ties by total opponent area. It also caches the results to avoid simulating identical board states.