如何修复未正确复制的元胞自动机/空间囚徒困境问题

Question

我试图重现一篇论文（如果您感兴趣，它是Nowak＆May，1992年的《进化博弈和空间混沌》），通过在n x n网格上运行囚徒困境来创建一组分形（例如， https://www.researchgate.net/figure/Spatial-version-of-the-Prisoners-Dilemma-for-symmetrical-initial-conditions-Nowak_fig3_277476479），但我的结果与预期不符。 想法是网格完全由合作者填满，除了位于网格中心的单个背叛者对象。不同的相互作用会产生不同的回报：互相背叛者的回报为0，互相合作者的回报为1，而一个背叛者对抗一个合作者的回报为背叛者b，合作者为0，其中b>1。网格中的所有对象都相互对抗，并根据上述回报结构获得分数。每一代之后，节点上的每个对象都将被具有最高分数的邻居对象替换。由于背叛者策略是优越的策略，它应该侵入合作者群体并产生所述的分形图像，就像细胞自动机一样。

我尝试过的主要方法（也是我遇到困难的主要领域）是通过下面展示的replace_pop函数。每轮之后，程序循环遍历网格，并用得分更高的邻居对象替换任何节点上的对象。我认为这应该已经足够了，但是即使经过几代之后，可以看出存在某种形式的复制，但并不是按照应该发生的方式，这使得很难确定究竟出了什么问题。在N = 1（N是代数）时，结果似乎是正确的，因为相邻（邻居是左边，右边，上面和下面）的合作者变成了背叛者，但是随着N变得更大，图像就会迷失方向。

我还重新初始化了每个对象的分数，以确保可以进行适当的复制。但是如果不这样做，则人口将以与上述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的建议更新了代码。虽然结果看起来更好，在实时返回一个真实的分形的同时，结果仍然不理想，这让我认为可能存在其他bug，因为单元格似乎更新正确。下面是我添加/替换到以前代码中的更新代码。

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()

- Sasquatch

Answer 1

看到你的代码，有几个问题需要解决:

1. 你从未在不同的代之间重置 last_gen 数组，因此你一直在向其中添加新的(空的)行，并且让前 row 行变得越来越长。这几乎肯定是一个错误。

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. 您还重复更新了单元格邻居的分数，导致某些相互作用被有效计数两次。

但是，您与Nowak和May的论文得到不同结果的真正原因是概念上的差异：该论文假设细胞也与自身进行游戏，有效地为合作者提供一点得分提升。 您的实现没有包括其中，导致相同参数值的不同动态。

无论如何，这是我如何重新编写该函数的方式：

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论文非常相似的模式：

顺便说一下，我不确定Nowak & May如何处理格子的边缘，这可能会导致一旦它们触及边缘，模式就会发散。 你的实现有效地从得分计算中排除了边缘之外的任何邻居，就好像普通人围绕着不传播的防御者一样。

- Ilmari Karonen

---

感谢您的建议/更正，它们非常有道理。您可以查看我的编辑以获取更新后的代码，但现在发生的情况是分形图像在一开始以类似于论文中的方式创建，但在几代之后仍然明显分歧（尽管它们看起来比以前更“连贯”）。奇怪的是，当我写lattice[r][c].id = best_neighbor_type(dbl_buf, r, c)而不是dbl_buf[r][c].id = best_neighbor_type(lattice[r][c], r, c)时，分形似乎更接近于论文中的分形，即使后者更有意义？ - Sasquatch

你的 calculate_score() 实现中有一些错误。请参见上面的附录。 - Ilmari Karonen