生命游戏

Question

生命博弈的

博弈

康威的生命游戏是一款0人游戏.但没关系！我们可以让它成为一个多人游戏。

这个游戏是在最小的方格上进行的，每个玩家可以容纳6x6平方( 2-4个玩家12x12，5-9个玩家18x18，等等)。这个网格实际上是一个环面，所以它是双向的。“生活规则”是：

• 如果一个细胞恰好有3个邻居，它就会在下一代活下来(或者仍然活着)。
• 如果一个细胞恰好有两个邻居，那么它在下一代中不会改变。
• 如果它没有两个或三个邻居，它就会在下一代中死去。

一个细胞的邻居是那些正交或对角相邻的细胞；每个细胞有8个邻接。在这个游戏中，与标准的生命游戏只有几个不同：

• 每个玩家都有不同的生命颜色，死细胞是白色的，中性活细胞是黑色的。
• 当一个细胞变得活跃时，它就会呈现出它最常见的邻居的颜色，如果有三种不同的颜色，它就会变成黑色(没有玩家)。细胞只要活着就不会改变颜色。
• 每一代，每一个机器人都能使附近的细胞以自己的颜色活下来，或者使自己的细胞死亡。这种情况发生在一代人被处理之前；一个被杀死的细胞可能会复活，而一个被赋予生命的细胞可能会在下一代中死去。

赢了比赛

游戏持续1000代，或者直到只有一种颜色的活细胞。如果所有有色细胞都在同一代死亡，那么游戏就是一张平局，没有机器人能收到积分。每个机器人得分等于它当时拥有的活彩色细胞的百分比(占有色细胞总数的百分比)。比赛将进行10000场，优胜者是平均得分最高的机器人。领带是用1v1网箱的火柴打破的。

启动条件

每个机器人将从以下活细胞布局开始：

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

这些将被随机安排到广场游乐场。没有机器人的每个6x6区域将具有相同的配置，但具有黑色活细胞。

机器人参数

您的机器人将用Javascript编写，平均调用时间不会超过50 to (机器人可能会被取消资格，但机器人可以使用performance.now()来管理自己的时间)。它将接受下列参数：

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.

你的机器人将返回一个包含两个元素的数组，x和y。这是你的机器人想要播放的单元格。它必须在你的一个活细胞的两个细胞内。如果所选的细胞是活的，而不是你的一个细胞，它什么也不做，除非它的颜色是移除它在同一代，在这种情况下，它使它是你的颜色。如果它是活的，并且是你的一个细胞，那么这个细胞在下一代之前就会被杀死。如果它是一个死细胞，它会在下一代之前存活(它会像你的机器人的颜色一样活着，除非其他机器人也会选择它，在这种情况下，它会变成黑色)。

一个离你的细胞太远的游戏就是传球。或者，-1，-1是一个显式传递。以任何其他方式在董事会外玩都是非法的，是取消资格的理由。

在网格上，-1是黑色(中性活的)，0是白色(死的)，所有其他数字都是在该单元格中的机器人的id。

其他限制

• 你最多可以制造3个机器人。
• 如果你的机器人使用随机数，你可以使用Math.random。
• 如果您的机器人愿意，它可以在this上存储数据。会在两场比赛之间被清除。
• 你不能制造一个机器人，目标是一个单一的，预选的机器人。你的机器人可能会瞄准一类机器人的战术。
• 机器人之间的合作是合法的，但是交流不是--你可以用一个策略来合作，但不能试图做出一个具体的动作序列来识别你的机器人。例如，不允许根据特定的启动顺序来识别一个机器人，但是知道“目标机器人更喜欢向上和离开，其他一切都是相等的”是可以的。ID是随机的，机器人事先不会知道其他机器人的ID是什么。

控制器

这还不是很完整，但这是一个好的开始。我计划记录分数，添加一个盒子，这样就可以很容易地测试一个新的机器人等等。当然，如果没有真正的竞争对手，其中的一些很难测试，但我会绕开它。

看起来我把x变成了长轴，y是次要轴，所以如果你的机器人走的方式和你预期的不一样，那可能就是原因。抱歉的。

代码 在这里运行它

示例bot

在比赛中加入一个糟糕的机器人似乎是传统的做法。这个机器人太坏了。它均匀地从网格中的细胞中随机选择，并试图移动到那里。我还没有让它活过1000代。

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

获胜者

在上一次新提交(或对机器人的重大更改)两周后，我将运行10000个游戏(数量可能会修改)来结束这个过程。如果有人想提交一份新的报告，我会在之后离开控制器，但是官方的排名不会改变。

聊天

Answer 1

-nothing

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

截至发帖之时，这与竞争中的所有其他机器人相当一致。

这个机器人很有趣，因为在数值分析的分支中，我做了一些研究，有时我们有一些不需要做边界条件的偏微分方程，而对于我所实现的方法，它实际上等于不做任何处理边界条件的事情。我最好的工作是什么都不做是合法的:')

Answer 2

planBbot

我把planBot当作蓝图。通过简单的增强/更改：

1.1版

• 改进移动选择:永远不要删除自己的颜色单元格
• 改进记分
• 改进的时间管理:使用PD-控制器保持在50 to。
• 更改策略:退出结束游戏模式
• 100场比赛结果：

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

1.0版

• 简单的时间管理:尝试保持在50毫秒内的平均移动，同时尽可能多的时间为看头。
• 一些性能调整:取消对结果的缓存。(相同的董事会状态太不可能了。)
• 得分:想法:保持稀疏，不要给对手喂食。
• 最终意识到:如果planBbot能活到第990代，它就会开始向更远的方向看，直到1000代。
• 100场比赛结果：

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

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会查看所有可用选项，并确定哪些选项是阳性的，然后从它们中随机选择。可以随意使用BestNowBot作为一个答案的基础--我认为它是一个有效的机器人的基线。

在发帖的时候，赢99%的游戏。