如何解决不能正确复制的元胞自动机/空间囚徒困境

Question

我试图复制一篇论文的结果(如果您感兴趣的话，它是Nowak & May，1992:进化论游戏和空间混沌)，它通过在n×n网格(例如，277476479)上运行一个囚徒困境来创建一组分形，但我的结果并不是它们应该达到的结果。其思想是，网格完全由协作者填充，除了放置在网格中心的单个叛逃者对象之外。不同的交互产生不同的收益:相互叛逃者产生0的收益，相互合作者各产生1的收益，而针对合作者的叛逃者产生b的收益，而对合作者的收益为0，其中b>1。网格中的所有对象都相互博弈，并根据上述的回报结构获得一个分数。每次生成后，节点上的每个对象都被得分最高的邻居替换。由于叛逃者策略是最优的策略，它应该像元胞自动机那样入侵协算子种群并生成所述分形图像。

我尝试这样做的主要方法(也是我遇到问题的主要区域)是通过下面所示的replace_pop函数。每一轮之后，程序循环穿过网格，用得分较高的邻接对象替换节点上的任何对象。我认为这已经足够了，但正如我们几代人所看到的那样，已经有了某种形式的复制，但并不是以应有的方式发生的，因此很难确定到底出了什么问题。当N=1 (N是世代数)时，结果似乎是正确的，因为相邻的(邻居是左、右、上、下)合作者变成了叛逃者，但是随着N的增长，图像就误入歧途了。

我还在每一代之后将每个对象的分数重新初始化为0，以确保能够进行适当的复制。然而，如果不这样做，人口就会以与上面N=1的情况相同的方式进化，但对于所有后代来说，这是很特殊的，因为应该有比周围合作者分数更高的叛逃者。我不知道我哪里出了问题？下面是我的代码(很抱歉包含了所有的代码，但我不知道问题到底在哪里)。我对Python和Stack非常陌生，因此任何帮助都将不胜感激。

import random
import matplotlib.pyplot as plt

row = 99
col = 99

class Cooperator:
    def __init__(self):
        self.score = 0
        self.id = 'C'

class Defector:
    def __init__(self):
        self.score = 0
        self.id = 'D'

class Grid:
    def __init__(self, rowsize, colsize):
        self.rowsize = rowsize
        self.colsize = colsize

    def make_grid(self):
        n = self.rowsize
        m = self.colsize
        arr = [[0 for j in range(m)] for i in range(n)]
        return arr

    def populate_grid(self):
        empty_grid = self.make_grid()
        for i in range(self.rowsize):
            for j in range(self.colsize):
                empty_grid[i][j] = Cooperator()
        empty_grid[i//2][j//2] = Defector()
        return empty_grid

    def shuffle_population(self):
        populated_grid = self.populate_grid()
        for i in range(self.rowsize):
            random.shuffle(populated_grid[i])
        return populated_grid

def von_neumann_neighbourhood(array, row, col, wrapped=True):
    """gets von neumann neighbours for a specfic point on grid with or without wrapping"""
    neighbours = []
    #conditions for in bound points
    if row + 1 <= len(array) - 1:
        neighbours.append(array[row + 1][col])

    if row - 1 >= 0:
        neighbours.append(array[row - 1][col])

    if col + 1 <= len(array[0]) - 1:
        neighbours.append(array[row][col + 1])

    if col - 1 >= 0:    
        neighbours.append(array[row][col - 1])
    #if wrapped is on, conditions for out of bound points
    if row - 1 < 0 and wrapped == True:
        neighbours.append(array[-1][col])

    if col - 1 < 0 and wrapped == True:
        neighbours.append(array[row][-1])

    if row + 1 > len(array) - 1 and wrapped == True:
        neighbours.append(array[0][col])

    if col + 1 > len(array[0]) - 1 and wrapped == True:
        neighbours.append(array[row][0])

    return neighbours

def play_round(array, row, col):
    b = 1.70
    player = array[row][col]
    neighbours = von_neumann_neighbourhood(array, row, col)
    for neighbour in neighbours:
        if player.id == 'C' and neighbour.id == 'C':
            player.score += 1
            neighbour.score += 1
        if player.id == 'D' and neighbour.id == 'D':
            player.score += 0
            neighbour.score += 0
        if player.id == 'D' and neighbour.id == 'C':
            player.score += b
            neighbour.score += 0
        if player.id == 'C' and neighbour.id == 'D':
            player.score += 0
            neighbour.score += b

def replace_pop(array, row, col):   
    neighbour_score = 0
    type_neighbour = ""
    neighbours = von_neumann_neighbourhood(array, row, col)
    player_score = array[row][col].score

    for neighbour in neighbours:
        if neighbour.score > neighbour_score:
            neighbour_score = neighbour.score
            type_neighbour = neighbour.id
    if player_score < neighbour_score:
        if type_neighbour == "C":
            array[row][col] = Cooperator()
        if type_neighbour == "D":
            array[row][col] = Defector()

N = 1
last_gen = []

def generations(N, row, col, array):
    for gen in range(N):    
        for z in range(row):
            for x in range(col):
                play_round(array, z, x)

        for r in range(row):
            last_gen.append([])
            for c in range(col):
                last_gen[r].append(lattice[r][c].id)
                replace_pop(array, r, c)

        for obj in lattice:
            for ob in obj:
                ob.score = 0

lattice = Grid(row, col).populate_grid()
generations(N, row, col, lattice)

heatmap_stuff = []
for z in range(row):
    heatmap_stuff.append([])
    for v in range(col):
        if lattice[z][v].id == 'C' and last_gen[z][v] == 'C':
            heatmap_stuff[z].append(1)
        if lattice[z][v].id == 'D' and last_gen[z][v] == 'D':
            heatmap_stuff[z].append(0)
        if lattice[z][v].id == 'C' and last_gen[z][v] == 'D':
            heatmap_stuff[z].append(3)
        if lattice[z][v].id == 'D' and last_gen[z][v] == 'C':
            heatmap_stuff[z].append(4)

plt.imshow(heatmap_stuff, interpolation='nearest')
plt.colorbar()
plt.show()

编辑:我已经按照Ilmari的建议更新了代码。虽然结果看起来更好，并且实时地返回了一个实际的分形，但结果仍然不是最优的，这使我认为其他地方可能有错误，因为这些细胞似乎在正确地更新。下面是我在前面的代码中添加/替换的更新代码。

def get_moore_neighbours(grid, row, col):
    neighbours = []
    for x, y in (
            (row - 1, col), (row + 1, col), (row, col - 1),
            (row, col + 1), (row - 1, col - 1), (row - 1, col + 1),
            (row + 1, col - 1), (row + 1, col + 1)):
        if not (0 <= x < len(grid) and 0 <= y < len(grid[x])):
            # out of bounds
            continue
        else:
            neighbours.append(grid[x][y])
    return neighbours

def calculate_score(grid, row, col):
    b = 1.85
    player = grid[row][col]
    neighbours = get_moore_neighbours(grid, row, col)
    for neighbour in neighbours:
        if player.id == 'C' and neighbour.id == 'C':
            player.score += 1
            neighbour.score += 1
        if player.id == 'D' and neighbour.id == 'D':
            player.score += 0
            neighbour.score += 0
        if player.id == 'D' and neighbour.id == 'C':
            player.score += b
            neighbour.score += 0
        if player.id == 'C' and neighbour.id == 'D':
            player.score += 0
            neighbour.score += b
    return player.score

def best_neighbor_type(grid, row, col): 
    neighbour_score = 0
    type_neighbour = ""
    neighbours = get_moore_neighbours(grid, row, col)
    player_score = grid[row][col].score

    for neighbour in neighbours:
        if neighbour.score > neighbour_score:
            neighbour_score = neighbour.score
            type_neighbour = neighbour.id
    if player_score < neighbour_score:
        if type_neighbour == "C":
            return 'C'
        if type_neighbour == "D":
            return 'D'
    if player_score >= neighbour_score:
        return grid[row][col].id

N = 15
heatmap_data = Grid(row, col).make_grid()
lattice = Grid(row, col).populate_grid()
dbl_buf = Grid(row, col).populate_grid()

for gen in range(N):    
    for r in range(row):
        for c in range(col):
            lattice[r][c].score = calculate_score(lattice, r, c)

    for r in range(row):
        for c in range(col):
            dbl_buf[r][c].id = best_neighbor_type(lattice, r, c)

    for r in range(row):
        for c in range(col):
            if lattice[r][c].id == 'C' and dbl_buf[r][c].id == 'C':
                heatmap_data[r][c] = 1
            if lattice[r][c].id == 'D' and dbl_buf[r][c].id == 'D':
                heatmap_data[r][c] = 2
            if lattice[r][c].id == 'C' and dbl_buf[r][c].id == 'D':
                heatmap_data[r][c] = 3
            if lattice[r][c].id == 'D' and dbl_buf[r][c].id == 'C':
                heatmap_data[r][c] = 4

    plt.imshow(heatmap_data, interpolation='nearest')
    plt.pause(0.01)

    (lattice, dbl_buf) = (dbl_buf, lattice)

plt.show()

Answer 1

看一看您的代码，有几个问题会跳出：

1. 您从不在几代之间重置last_gen数组，因此您不断地向其添加新的(空的)行，并使第一个row行越来越长。这几乎可以肯定是个bug。
2. 除了生成热图之外，您也从不使用last_gen数组进行任何操作。特别是，您的replace_pop()函数正在修改它读取邻居状态的同一个数组(创造性地命名为array)。

第二个问题意味着代码的行为将取决于在每个代中循环单元格调用replace_pop()的顺序，因为用不同的邻居替换一个单元将影响到该代中尚未更新的所有邻居的邻域。

在你在文章中描述的元胞自动机中，所有的细胞都应该同时有效地更新它们的状态，这样在下一代之前，每个细胞状态的变化都不会被邻居看到。

在实践中，实现这种“同时”更新的最简单方法是使用双重缓冲，首先将所有单元格的状态复制到第二个数组中，然后根据刚刚复制的副本更新第一个数组。或者，更有效地，只需交换(对)数组的引用，而不是将其中一个复制到另一个数组中。代码应该如下所示：

lattice = Grid(row, col).populate_grid()
dbl_buf = Grid(row, col)

for gen in range(N):    
    for r in range(row):
        for c in range(col):
            lattice[r][c].score = calculate_score(lattice, r, c)

    # This is probably the best spot for generating output, since both
    # buffers contain consistent and up-to-date IDs and scores here.

    for r in range(row):
        for c in range(col):
            dbl_buf[r][c].id = best_neighbor_type(lattice, r, c)

    (lattice, dbl_buf) = (dbl_buf, lattice)

其中，calculate_score()函数根据其邻居类型返回给定单元格的分数，而best_neighbor_id()函数返回格上得分最高的单元格的类型ID。

增编:您在更新后的代码中实现的calculate_score()存在一些缺陷：

1. 从前面的分数值开始计算(由于双缓冲，实际上是从两代人开始计算的)，
2. 您正在冗余地将分数直接写入函数内的网格，而不仅仅是将分数返回给调用方，并且
3. 你也在重复更新单元的邻居的分数，导致一些互动被有效计算了两次。

然而，你得到的结果与诺瓦克&梅论文不同的真正原因是概念上的差异:论文假设细胞也会和自己玩游戏，有效地给合作者一个分数的提升。您的实现不包括这一点，这会导致相同参数值的不同动态。

总之，下面是我重写函数的方式：

def calculate_score(grid, row, col):
    neighbours = get_moore_neighbours(grid, row, col)
    player = grid[row][col]
    score = 0
    if player.id == 'C': score += 1  # self-interaction!
    for neighbour in neighbours:
        if player.id == 'C' and neighbour.id == 'C':
            score += 1
        if player.id == 'D' and neighbour.id == 'C':
            score += b
    return score

通过这种更改，您的代码产生了非常类似于Nowak & May论文中的模式：

​

​

顺便说一句，我不知道诺瓦克&梅如何处理点阵的边缘，这可能会导致图案一碰到边缘就会发散。您的实现实际上将边缘之外的任何邻居排除在分数计算之外，就好像格被不扩散的叛逃者包围一样。