Game of Game of Life

15

2

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

Spitemaster

Posted 2020-02-17T17:31:41.550

Reputation: 695

Hm, I don't understand how to advance to the next turn… I just see this (Chrome on Mac).

– Lynn – 2020-02-17T18:46:42.660

2@Lynn The game stops when there's only one player alive - you'll need to define your own bot to get it to keep going. Either clone the repo and edit directly or create a bot function (in the console) and then push the function into the bots array. – Spitemaster – 2020-02-17T18:48:29.843

You said we can use 'Math.random'. I assume you mean we can use whatever built-in implementation specific to our language? – ouflak – 2020-02-18T08:24:05.050

1@Spitemaster You should specify that x is the major index and y the minor index of the grid; this is the opposite of the usual convention. – user1502040 – 2020-02-18T10:09:13.870

@ouflak The controller is in Javascript, and your bot will be written in Javascript (as stated), so no, you can use Math.random. I specifically stated that because there are ways to seed Math.random, and I want to leave that option open so that I can potentially have reproducible results. – Spitemaster – 2020-02-18T14:22:38.527

@user1502040 Honestly, I didn't even think about that. It's a square grid and it wraps so the directions are indistinguishable. But I'll make a note of it. – Spitemaster – 2020-02-18T14:24:05.840

Glad to see this finally posted! – Alion – 2020-02-18T18:42:57.420

@Spitemaster Contradiction - you want to have reproducible results but allow entries to police their run time with performance.now(). – Alion – 2020-02-18T18:46:43.407

@Alion Fair point. I'm not super concerned about either time or reproducibility - I don't think anyone is going to write a bot that goes over 50ms call time and if nobody does, we can have reproducibility. If someone does, we can't, but that's not a big deal. – Spitemaster – 2020-02-18T18:49:54.177

Can you switch off neutral cells? My guess is "no", but the sentence that is closest to covering this case then goes on to refer to "the bot whose color it is". – Alion – 2020-02-18T22:32:52.303

How do neutral cells affect the color of a born cell? For example, what does 1 red + 2 neutral (black) do? – Alion – 2020-02-18T22:57:05.603

@Alion You cannot kill living neutral cells. Red+Black+Black=Black – Spitemaster – 2020-02-19T02:01:34.733

@Spitemaster In nextGeneration the condition if (k == l) continue; is incorrect; it skips the main diagonal. You should check if k and l are both 0 instead. – user1502040 – 2020-02-19T09:50:44.433

@user1502040 dur. I'll have that fixed soon. – Spitemaster – 2020-02-19T13:50:08.117

May I suggest creating a dedicated chat room for this KotH? I always love to talk about strategies with other contestants in challenges such as this one. – Alion – 2020-02-19T19:26:12.570

@Alion Yep, created. https://chat.stackexchange.com/rooms/104667/game-of-game-of-life

– Spitemaster – 2020-02-19T19:33:47.670

I'm getting flashbacks to the last time we did a KOTH Game of Life, but thankfully, the restriction of only spawning one square, within a certain distance from your existing clusters, means that this challenge is not a dupe

– Value Ink – 2020-02-22T00:28:51.347

Also, you should disallow bots that modify the grid directly. I know it should go without saying, but there are technically no rules in place (yet) that prevent me from making a bot that modifies grid directly.... – Value Ink – 2020-02-22T00:47:42.887

@ValueInk I did say the grid should not be modified... I guess someone might not read that as a restriction, but I think it's clear enough. I'll adjust the controller to pass in a copy if necessary. – Spitemaster – 2020-02-23T00:33:32.137

Answers

6

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 :')

RGS

Posted 2020-02-17T17:31:41.550

Reputation: 5 047

(⩺ ͟ʖ⩹) How does this consistently win against the random moves bot? +1 from me. – Lyxal – 2020-02-19T04:56:01.933

@Lyxal I dunno. For the times I hit "run game" it always won against the random bot. – RGS – 2020-02-19T07:28:58.580

1Bad news: when I fixed the problem mentioned by @user1502040 (missing the main diagonal), randomMovesBot now beats rgs_do_nothing a full 28% of the time. – Spitemaster – 2020-02-19T13:59:52.887

Nice arguments! – S.S. Anne – 2020-02-19T16:47:37.830

2

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.

Spitemaster

Posted 2020-02-17T17:31:41.550

Reputation: 695

2

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.

user1502040

Posted 2020-02-17T17:31:41.550

Reputation: 2 196

I've improved the time tracking on the controller. You're going to have time troubles with more opponents - 75+ms on my computer against 4 opponents. – Spitemaster – 2020-02-19T17:49:29.410

2

planBbot

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

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

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

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

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

// version 1.0
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) || (grid[x1][y1] == botId)) {
                            possible_moves.add([x1, y1]);
                        }
                    }
                }
            }
        }
    }
    let possible_move_array = Array.from(possible_moves);
    if (possible_move_array.length == 0) {
        return best_cell;
    }

    let new_grid = Array(size).fill(0).map(() => new Array(size).fill(0));
    if (typeof this.iters == "undefined") {
        this.iters=2;
        this.sum=0;
        this.count=1;
        this.lookahead=function(old_grid, new_grid){
            let iscore = 0;
            let oscore = 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);
                            }
                        }
                    }
                    let next=old_grid[x][y];
                    if (neighbours.length < 2 || neighbours.length > 3) {
                        next = 0;
                    } else if (neighbours.length == 3 && old_grid[x][y] == 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;
                        }
                    }
                    new_grid[x][y] = next;
                    if (next == botId) {
                        iscore++;
                    } else if (next != 0) {
                        oscore++;
                    }
                }
            }
            return (iscore)-3*(oscore);
        }
    } else {
        let avg=this.sum/this.count;
        this.count++;
        if (avg>49 && this.iters>1) {
            this.iters--;
        } else if (avg<49) {
            this.iters++;
        }
    }
    if (this.count>990) {
        this.iters=1000-this.count;
    }
    if (this.count<200 && this.iters>6) {
        this.iters=6;
    }
    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 score = 0;
        for (let i = 0; i < this.iters; i++) {
            score += this.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;
        }
    }
    let time=performance.now() - t0;
    if (this.sum==0) {
        this.sum=time;
    } else {
        this.sum+=time;
    }
    return best_cell;
}

Bob Genom

Posted 2020-02-17T17:31:41.550

Reputation: 846