如何修复未正确复制的蜂窝 automata/spatial 囚徒困境
How to fix cellular automata/spatial prisoners dilemma that is not replicating properly
我正在尝试复制一篇论文的结果（如果你有兴趣，它是诺瓦克和梅，1992 年：进化游戏和空间混沌）通过 运行 囚徒困境创建一组分形一个 n x n 网格（例如，
https://www.researchgate.net/figure/Spatial-version-of-the-Prisoners-Dilemma-for-symmetrical-initial-conditions-Nowak_fig3_277476479), 但我的结果不是他们应该的。
这个想法是网格完全由 Cooperators 填充，除了放置在网格中心的单个 Defector 对象。不同的互动会产生不同的回报：相互背叛者的回报为 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 的建议更新了代码。尽管结果看起来更好，并且实时返回了实际的分形，但结果仍然不是最佳的，这让我认为其他地方可能存在错误，因为单元格似乎正在正确更新。下面是更新后的代码 added/replaced 到以前的代码。
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()
查看您的代码，发现了一些问题：
你永远不会在几代之间重置 last_gen 数组，所以你不断地向它添加新的（空）行并使第一个 row 行越来越长。这几乎可以肯定是一个错误。
除了生成热图之外，您也永远不会将 last_gen 数组用于任何其他用途。特别是，您的 replace_pop() 函数正在修改它从中读取邻居状态的同一个数组（创造性地命名为 array）。
第二个问题意味着您的代码的行为将取决于您在每一代中循环调用 replace_pop() 的单元格的顺序，因为用不同的邻居替换一个单元格会影响邻域在这一代尚未更新的所有邻居中。
在您引用的论文中描述的元胞自动机中，所有元胞都应该同时有效地更新它们的状态，这样每个元胞状态的变化在下一代之前不会被其邻居看到。
实际上，实现这种 "simultaneous" 更新的最简单方法是使用双缓冲，首先将所有单元格的状态复制到第二个数组中，然后根据第一个数组更新在你刚刚制作的副本上。或者，更有效地，只需交换数组（对）的引用，而不是将一个数组复制到另一个数组中。代码看起来像这样：
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() 函数 returns 格子上给定单元格的分数基于其邻居的类型，best_neighbor_id() 函数 returns 类型晶格上单元格 highest-scoring 邻居的 ID。
附录：您在更新代码中实施 calculate_score() 有一些错误：
- 你从之前的分值开始计算（由于双缓冲，实际上是两代之前的分值），
- 您将分数直接写入函数内的网格，而不是仅仅将分数返回给调用者，并且
- 您还冗余地更新了单元格邻居的分数，导致某些交互被有效计算了两次。
然而，您得到的结果与 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 如何处理格子的边缘，这可能会导致图案一旦碰到边缘就会发散。您的实施有效地从分数计算中排除了边缘之外的任何邻居，就好像格子被 non-spreading 个叛逃者包围一样。
我正在尝试复制一篇论文的结果（如果你有兴趣，它是诺瓦克和梅，1992 年：进化游戏和空间混沌）通过 运行 囚徒困境创建一组分形一个 n x n 网格（例如， https://www.researchgate.net/figure/Spatial-version-of-the-Prisoners-Dilemma-for-symmetrical-initial-conditions-Nowak_fig3_277476479), 但我的结果不是他们应该的。 这个想法是网格完全由 Cooperators 填充，除了放置在网格中心的单个 Defector 对象。不同的互动会产生不同的回报：相互背叛者的回报为 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 的建议更新了代码。尽管结果看起来更好，并且实时返回了实际的分形，但结果仍然不是最佳的，这让我认为其他地方可能存在错误，因为单元格似乎正在正确更新。下面是更新后的代码 added/replaced 到以前的代码。
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()
查看您的代码，发现了一些问题：
你永远不会在几代之间重置
last_gen数组，所以你不断地向它添加新的（空）行并使第一个row行越来越长。这几乎可以肯定是一个错误。除了生成热图之外，您也永远不会将
last_gen数组用于任何其他用途。特别是，您的replace_pop()函数正在修改它从中读取邻居状态的同一个数组（创造性地命名为array）。
第二个问题意味着您的代码的行为将取决于您在每一代中循环调用 replace_pop() 的单元格的顺序，因为用不同的邻居替换一个单元格会影响邻域在这一代尚未更新的所有邻居中。
在您引用的论文中描述的元胞自动机中，所有元胞都应该同时有效地更新它们的状态，这样每个元胞状态的变化在下一代之前不会被其邻居看到。
实际上，实现这种 "simultaneous" 更新的最简单方法是使用双缓冲，首先将所有单元格的状态复制到第二个数组中，然后根据第一个数组更新在你刚刚制作的副本上。或者，更有效地，只需交换数组（对）的引用，而不是将一个数组复制到另一个数组中。代码看起来像这样：
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() 函数 returns 格子上给定单元格的分数基于其邻居的类型，best_neighbor_id() 函数 returns 类型晶格上单元格 highest-scoring 邻居的 ID。
附录：您在更新代码中实施 calculate_score() 有一些错误：
- 你从之前的分值开始计算（由于双缓冲，实际上是两代之前的分值），
- 您将分数直接写入函数内的网格，而不是仅仅将分数返回给调用者，并且
- 您还冗余地更新了单元格邻居的分数，导致某些交互被有效计算了两次。
然而，您得到的结果与 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 如何处理格子的边缘，这可能会导致图案一旦碰到边缘就会发散。您的实施有效地从分数计算中排除了边缘之外的任何邻居，就好像格子被 non-spreading 个叛逃者包围一样。