Simulating multi-agent survival using Neuroevolution/Genetic Algorithms [Python] PART 1

This is Part 1 of a multi-part series. SAMPLE VIDEOS BELOW!

I’m a gamer, and one of the games that took a chunk of my time back in the day was Ragnarok Online, a MMORPG that took the Philippines, Asia, and Europe by storm. This side project was inspired by the recent announcement that Ragnarok Online will be re-launched back home in the next few months. It’s currently in closed-beta. That being said, I had the ingenious idea of mimicking the RO game play in a closed environment using autonomous agents running on neural nets and genetic algorithms. All the math for stats, damage, etc. will still be there, but this time, autonomous agents will try to level up as much as they can by killing monsters or, maybe later on, PK. I will be taking this project step-by-step so as not to miss out on important learning points along the way. Check out the code in this Github page. For references, check out the credits section below. 

Current bugs:

  • Some agents are eating themselves… weird. lol. Darn sprites.

Before we start:

  • Python 2.7
  • Pygame – for visualization
    • Most of the projects that we
  • Pybrain – for the neural net design and implementation

Let’s get right into it.

The project needs the following:

  • a Character class
  • an Enemy class
  • the environment
  • and the Genetic Algorithm

Character class

When you think about it, what are the things that a character has to have to be able to function properly?

  • Image (currently, it’s just a box sprite. The aesthetics will come in the future)
  • Physical position (or coordinates)
  • Field of vision (to simulate visual perception which will feed inputs into the neural net)
  • Stats (currently, it’s just HP) and Fitness
  • An Update function which contains the ff:
    • Thinking (input assessment)
    • Movement functions (velocity, steering, etc.)
  • and of course, the Brain (which is a neural net)

Character | Brain

Let’s start with the brain. The brain is basically a FeedForward Neural Net. It has an input layer with 11 nodes, a hidden layer with 7 nodes, and an output layer (for the actions) with 10 nodes. This means that there are 11 things that a character will consider before choosing from 10 different action types.

Currently, actions consist of directional movement (8), no movement (1), and attacking (1).

This brain was implemented using pybrain. What’s good about this is it’s low-level code doesn’t force you to use back propagation as an optimizer. As you can see, inputs (data) pass through the neural net only once, which allows the character to instantly make a decision. It took me a while to realize how Genetic Algorithms can optimize such a neural net, but when it clicked, I went through a good minute of ‘Oooohs’ and ‘Aaaahs’. lol. This will be discussed in greater length later.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def newBrain():
    ''' initialize brain'''
    brain = FeedForwardNetwork()

    ''' specify layer sizes and types'''
    inLayer = LinearLayer(11, name = 'input')
    hiddenLayer1 = SigmoidLayer(7, name = 'hidden1')
    # hiddenLayer2 = SigmoidLayer(5, name = 'hidden1')
    outLayer = SoftmaxLayer(10, name = 'output')

    ''' integrate layers into brain'''
    brain.addInputModule(inLayer)
    brain.addModule(hiddenLayer1)
    # brain.addModule(hiddenLayer2)
    brain.addOutputModule(outLayer)

    ''' connect layers '''
    in_to_hidden = FullConnection(inLayer, hiddenLayer1)
    # hidden1_to_hidden2 = FullConnection(hiddenLayer1, hiddenLayer2)
    hidden_to_out = FullConnection(hiddenLayer1, outLayer)
    brain.addConnection(in_to_hidden)
    # brain.addConnection(hidden1_to_hidden2)
    brain.addConnection(hidden_to_out)

    ''' 
        This call does some internal initialization which 
        is necessary before the net can finally be used: for 
        example, the modules are sorted topologically.
    '''
    brain.sortModules()
    
    return brain

Character | Field of Vision

Since I was brute forcing my study for pygame, and because  a lot of the tutorials and documentations that I found at first were either outdated or were just not working for me, I decided to think hard about it. What I came up with was a 360 degree Field of Vision that would allow the character to sense anything within a given area.

The Field of Vision takes its position and size from the Character class (which will be discussed later). This field of vision has 3 basic functions: see other agents, see enemies, and see walls. My goal for this is to allow the Character to make decisions whenever it sees another agent (attack or flee), an enemy (move towards and kill), and a wall (avoid).

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class FoV(pygame.sprite.Sprite):
	def __init__(self, sprite):
		pygame.sprite.Sprite.__init__(self)

		self.sprite = sprite
		self.size = self.sprite.maximumSightDistance
		self.image = pygame.Surface([self.size, self.size])
		self.rect = self.image.get_rect()
		self.image.fill((255,245,202))

		self.pos = self.sprite.pos
		self.type = 'fov'
		self.sprite.fov = self

	def update(self, enemies, boxes):
		self.sprite.image.fill((0,0,0))
		self.pos = self.sprite.pos
		self.rect.centerx = round(self.pos[0],0)
		self.rect.centery = round(self.pos[1],0)
		self.sprite.seeAgent = 0
		self.sprite.seeEnemy = 0
		self.sprite.seeWall = 0
		self.sprite.enemy_distance = 0
		self.sprite.wall_distance = 0
		self.sprite.otherAgent_distance_x = 0
		self.sprite.otherAgent_distance_y = 0
		self.sprite.otherAgentdiffsize = 0

		enemy_direction_x = 1
		wall_direction_x = 1
		enemy_direction_y = 1
		wall_direction_y = 1
		wall_dx = 0
		wall_dy = 0
		enemy_direction = 1
		wall_direction = 1
		otherAgent_direction_x = 1
		otherAgent_direction_y = 1

		'''see other agents'''
		nearest_distance = self.sprite.maximumSightDistance
		other_agent = pygame.sprite.spritecollideany(self, boxes)
		if other_agent:
			#self.sprite.image.fill((255,162,0))
			self.sprite.seeAgent = 1
			otherAgent_dx = abs(self.sprite.pos[0] - other_agent.pos[0])
			otherAgent_dy = abs(self.sprite.pos[1] - other_agent.pos[1])

			if otherAgent_dx > 0:
				pass
			else:
				otherAgent_direction_x = -1
			if otherAgent_dy > 0:
				pass
			else:
				otherAgent_direction_y = -1

			distance_from_otherAgent = math.sqrt(otherAgent_dx ** 2 + otherAgent_dy ** 2)
			self.sprite.otherAgent_distance = distance_from_otherAgent
			self.sprite.otherAgent_distance_x = otherAgent_dx * otherAgent_direction_x
			self.sprite.otherAgent_distance_y = otherAgent_dy * otherAgent_direction_y

			self.sprite.otherAgentdiffsize = self.sprite.size - other_agent.size

		'''see enemy'''
		j = pygame.sprite.spritecollideany(self, enemies)

		if j:
			self.sprite.image.fill((255,0,0))
			self.sprite.seeEnemy = 1
			enemy_dx = abs(self.sprite.pos[0] - j.pos[0])
			enemy_dy = abs(self.sprite.pos[1] - j.pos[1])

			if enemy_dx > 0:
				pass
			else:
				enemy_direction_x = -1
			if enemy_dy > 0:
				pass
			else:
				enemy_direction_y = -1

			distance_from_enemy = math.sqrt(enemy_dx ** 2 + enemy_dy ** 2)
			self.sprite.enemy_distance = distance_from_enemy
			self.sprite.enemy_distance_x = enemy_dx * enemy_direction_x
			self.sprite.enemy_distance_y = enemy_dy * enemy_direction_y

		'''see walls'''
		if self.pos[0] + self.sprite.maximumSightDistance > self.sprite.area.width:
			self.sprite.image.fill((213, 0, 255))
			self.sprite.seeWall = 1
			wall_dx = self.sprite.area.width - self.sprite.pos[0]
			wall_direction_x = 1

		elif self.pos[0] - self.sprite.maximumSightDistance<0:
			self.sprite.image.fill((213, 0, 255))
			self.sprite.seeWall = 1
			wall_dx = self.sprite.pos[0] 
			wall_direction_x = -1

		if self.pos[1] + self.sprite.maximumSightDistance > self.sprite.area.height:
			self.sprite.image.fill((213, 0, 255))
			self.sprite.seeWall = 1
			wall_dy = self.sprite.area.height - self.sprite.pos[1]
			wall_direction_y = 1

		elif self.pos[1] - self.sprite.maximumSightDistance <0:
			self.sprite.image.fill((213, 0, 255))
			self.sprite.seeWall = 1
			wall_dy = self.sprite.pos[1] 
			wall_direction_y = -1
		
		if self.sprite.seeWall == 1:
			distance_from_wall = math.sqrt(wall_dx ** 2 + wall_dy ** 2)
			self.sprite.wall_distance = distance_from_wall
			self.sprite.wall_distance_x = wall_dx * wall_direction_x
			self.sprite.wall_distance_y = wall_dy * wall_direction_y

Character | Class

Now for the Character itself. This character, contrary to what you may have expected in the earlier parts of this article, is currently just a block with a 13 x 13 area. It contains attributes that allow it to see, think, and move accordingly (steering needs to be improved). In order to enforce behavior, it also has reinforcement attributes that make it lose HP (idling, hitting walls, attacking bigger agents, gain HP (attacking smaller agents, attacking enemies), accumulate additional stats for the next generation of Characters (kill agent, kill enemy), and lose accumulated stats (negative stats) for the next gen (get killed).

It’s update function is called for each iteration in the main loop. As mentioned earlier, every time the update function gets called, the Character takes in inputs, thinks (using the brain), decides on an action, and acts on it.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
class Character(pygame.sprite.Sprite):
	characters = {}
	number = 0
	def __init__(self, area = screen, x = 1, y = 1, color = (0,0,0)):
		pygame.sprite.Sprite.__init__(self)
		self.charID = id(self)
		''' image '''
		self.size = 13.0
		self.nextsize = self.size
		self.image = pygame.Surface([self.size,self.size])
		self.rect = self.image.get_rect()
		self.image.fill(color)
		self.colorcount = 0
		self.movecount = 0
		self.type = 'character'
		self.number = Character.number
		Character.number += 1
		Character.characters[self.number] = self

		''' movement constants '''
		self.wallCollisionThreshold = 4
		self.moveSpeed = 10.0
		self.nextmoveSpeed = self.moveSpeed


		''' position '''
		self.area = area.get_rect()
		self.pos = [0.0,0.0]
		self.pos[0] = random.random() * (self.area.width - 2 * self.wallCollisionThreshold - 2 * 5)
		self.pos[1] = random.random() * (self.area.height - 2 * self.wallCollisionThreshold - 2 * 5)

		''' view constants '''
		self.maximumSightDistance = 70
		self.nextmaximumSightDistance = self.maximumSightDistance
		self.fieldOfViewSurface = pygame.Surface([self.maximumSightDistance, self.maximumSightDistance])
		self.fieldOfViewSurface.fill((255,0,0))
		self.fieldOfViewSurface.convert()
		self.fieldofViewrect = self.fieldOfViewSurface.get_rect()
		self.fieldofViewrect.clamp_ip(self.rect)
		self.fov = 0
		self.actionbar = 0
		self.hpbar = 0
		
		'''brain'''
		self.brain = 0
		self.brain_check()

		'''inputs'''
		self.seeEnemy = 0
		self.seeWall = 0
		self.enemy_distance = self.maximumSightDistance
		self.enemy_distance_x = self.maximumSightDistance
		self.enemy_distance_y = self.maximumSightDistance
		self.wall_distance = self.maximumSightDistance
		self.wall_distance_y = self.maximumSightDistance
		self.wall_distance_x = self.maximumSightDistance
		self.seeAgent = 0
		self.otherAgent_distance_x = self.maximumSightDistance
		self.otherAgent_distance_y = self.maximumSightDistance
		self.otherAgentdiffsize = 0


		'''fitness'''
		self.score = 0.0
		self.fitness = 0.0
		self.idle_damage = 1.0
		self.wall_damage = 5.0

		'''outputs'''
		self.outputs = ['U','D','L','R','UL','UR','DL','DR','dM','Attack']
		self.action = ''

		'''stats'''
		
		self.maxHP = 200.0
		self.nextmaxHP = self.maxHP
		self.currentHP = self.maxHP
		self.fitness = 0.0


	def brain_check(self):
		if isinstance(self.brain,pybrain.structure.networks.feedforward.FeedForwardNetwork) == True:
			pass #should mutate here... or not? weight training and mutation
		else:
			self.brain = newBrain()
    
	def think(self, boxes):
		inputs = self.getInputs()
		actions = self.brain.activate(inputs)
		actions = actions.tolist()
		action = self.outputs[actions.index(max(actions))]
		self.action = action
		#print self.charID, '| seeEnemy:', inputs[0], '| enemy_distance:', inputs[1], '| seeWall:', inputs[2], '| wall_distance:', inputs[3], '| currentHP:', inputs[4], '|| Score:', self.score, ' > Action:', action
		self.move(action, boxes)

	def getInputs(self):
		inputs = []
		inputs.append(self.seeEnemy)
		inputs.append(self.enemy_distance_x)
		inputs.append(self.enemy_distance_y)
		inputs.append(self.seeWall)
		inputs.append(self.wall_distance_x)
		inputs.append(self.wall_distance_y)
		inputs.append(self.seeAgent)
		inputs.append(self.otherAgent_distance_x)
		inputs.append(self.otherAgent_distance_y)
		inputs.append(self.otherAgentdiffsize)
		inputs.append(self.currentHP)
		return inputs

	def move(self,action, boxes):		
		if action == 'R':
			self.pos[0] += self.moveSpeed
			#print 'R'
			
		elif action == 'L':
			self.pos[0] += self.moveSpeed * -1
			#print 'L'
			
		elif action == 'D':
			self.pos[1] += self.moveSpeed
			#print 'U'
			
		elif action == 'U':
			self.pos[1] += self.moveSpeed * -1
			#print 'D'
		elif action == 'DL':
			self.pos[1] += self.moveSpeed
			self.pos[0] += self.moveSpeed * -1

		elif action == 'DR':
			self.pos[1] += self.moveSpeed
			self.pos[0] += self.moveSpeed

		elif action == 'UL':
			self.pos[1] += self.moveSpeed * -1
			self.pos[0] += self.moveSpeed * -1

		elif action == 'UR':
			self.pos[1] += self.moveSpeed * -1
			self.pos[0] += self.moveSpeed
		elif action == 'Attack':
			#jump
			self.pos[0] = self.otherAgent_distance_x
			self.pos[1] = self.otherAgent_distance_y

			# self.rect.centerx = self.otherAgent_distance_x
			# self.rect.centery = self.otherAgent_distance_y

			j = pygame.sprite.spritecollideany(self, boxes)
			
			if j.type == 'character':
				
				if self.size > j.size:
					
					self.colorcount = 1
					self.score += 10.0
					self.currentHP -= 1
					self.nextmoveSpeed += 5
					self.nextsize += 12
					self.nextmaxHP += 20
					self.nextmaximumSightDistance += 17	
					screen.blit(dead_pix, (j.pos[0]-j.size, j.pos[1]-j.size))
					j.kill()
					j.fov.kill()
					#j.actionbar.kill()
					#j.hpbar.kill()
					#print 'EAT!'
				elif self.size == j.size:
					if random.random() > 0.5:
						self.colorcount = 1
						self.score += 10.0
						self.currentHP -= 1
						self.nextmoveSpeed += 5
						self.nextsize += 12
						self.nextmaxHP += 20
						self.nextmaximumSightDistance += 17	
						screen.blit(dead_pix, (j.pos[0]-j.size, j.pos[1]-j.size))
						j.kill()
						j.fov.kill()
						#j.actionbar.kill()
						#j.hpbar.kill()
						#print 'EAT!'
					else:
						self.colorcount = 1
						self.score -= 5.0
						self.nextmoveSpeed -= 1
						self.nextsize -= 5
						self.nextmaxHP -= 10
						self.nextmaximumSightDistance -= 5
						self.score /= 2
						screen.blit(dead_pix, (self.pos[0]-self.size, self.pos[1]-self.size))
						self.kill()
						self.fov.kill()
						#self.actionbar.kill()
						#self.hpbar.kill()
						#print 'EATEN!!'

				else:
					self.colorcount = 1
					self.score -= 5.0
					self.nextmoveSpeed -= 1
					self.nextsize -= 5
					self.nextmaxHP -= 10
					self.nextmaximumSightDistance -= 5
					self.score /= 2
					screen.blit(dead_pix, (self.pos[0]-self.size, self.pos[1]-self.size))
					self.kill()
					self.fov.kill()
					#self.actionbar.kill()
					#self.hpbar.kill()
					#print 'EATEN!!'

		else:
			#not moving double damage
			if self.currentHP > 0:
				self.currentHP -= self.idle_damage
				#self.size -= 0.1
				#self.moveSpeed -= 0.1
			elif self.currentHP <= 0:
				self.currentHP = 0
				if self.nextsize <= 5:
					self.nextsize = 5
				else:
					self.nextsize -= 1
				if self.nextmaximumSightDistance <= self.nextsize + 10:
					self.nextmaximumSightDistance = self.nextsize + 10
				else:
					self.nextmaximumSightDistance -= 10
				if self.nextmoveSpeed <= 2:
					self.nextmoveSpeed = 2
				else:
					self.nextmoveSpeed -= 1
				self.score /= 2
				self.kill()
				self.fov.kill()
				#self.actionbar.kill()
				#self.hpbar.kill()

		'''wall management'''

		if self.pos[0] - self.size / 2< 0:
			self.pos[0] = 0
			self.pos[0] += self.size / 2
			if self.currentHP > 0:
				self.currentHP -= self.wall_damage
				#self.size -= 0.1
				#self.moveSpeed -= 0.1
			elif self.currentHP <= 0:
				self.currentHP = 0
				if self.nextsize <= 5:
					self.nextsize = 5
				else:
					self.nextsize -= 1
				if self.nextmaximumSightDistance <= self.nextsize + 10:
					self.nextmaximumSightDistance = self.nextsize + 10
				else:
					self.nextmaximumSightDistance -= 10
				if self.nextmoveSpeed <= 2:
					self.nextmoveSpeed = 2
				else:
					self.nextmoveSpeed -= 1
				self.score /= 2
				self.kill()
				self.fov.kill()
				#self.actionbar.kill()
				#self.hpbar.kill()

		elif self.pos[0] + self.size / 2 > self.area.width:
			self.pos[0] = self.area.width
			self.pos[0] -= self.size / 2
			if self.currentHP > 0:
				self.currentHP -= self.wall_damage
				#self.size -= 0.1
				#self.moveSpeed -= 0.1
			elif self.currentHP <= 0:
				self.currentHP = 0
				if self.nextsize <= 5:
					self.nextsize = 5
				else:
					self.nextsize -= 1
				if self.nextmaximumSightDistance <= self.nextsize + 10:
					self.nextmaximumSightDistance = self.nextsize + 10
				else:
					self.nextmaximumSightDistance -= 10
				if self.nextmoveSpeed <= 2:
					self.nextmoveSpeed = 2
				else:
					self.nextmoveSpeed -= 1
				self.score /= 2
				self.kill()
				self.fov.kill()
				#self.actionbar.kill()
				#self.hpbar.kill()

		if self.pos[1] - self.size / 2< 0:
			self.pos[1] = 0
			self.pos[1] += self.size / 2
			if self.currentHP > 0:
				self.currentHP -= self.wall_damage
				#self.size -= 0.1
				#self.moveSpeed -= 0.1
			elif self.currentHP <= 0:
				self.currentHP = 0
				if self.nextsize <= 5:
					self.nextsize = 5
				else:
					self.nextsize -= 1
				if self.nextmaximumSightDistance <= self.nextsize + 10:
					self.nextmaximumSightDistance = self.nextsize + 10
				else:
					self.nextmaximumSightDistance -= 10
				if self.nextmoveSpeed <= 2:
					self.nextmoveSpeed = 2
				else:
					self.nextmoveSpeed -= 1
				self.score /= 2
				self.kill()
				self.fov.kill()
				#self.actionbar.kill()
				#self.hpbar.kill()

		elif self.pos[1] + self.size / 2 > self.area.height:
			self.pos[1] = self.area.width
			self.pos[1] -= self.size / 2
			if self.currentHP > 0:
				self.currentHP -= self.wall_damage
				#self.size -= 0.1
				#self.moveSpeed -= 0.1
			elif self.currentHP <= 0:
				self.currentHP = 0
				if self.nextsize <= 5:
					self.nextsize = 5
				else:
					self.nextsize -= 1
				if self.nextmaximumSightDistance <= self.nextsize + 10:
					self.nextmaximumSightDistance = self.nextsize + 10
				else:
					self.nextmaximumSightDistance -= 10
				if self.nextmoveSpeed <= 2:
					self.nextmoveSpeed = 2
				else:
					self.nextmoveSpeed -= 1
				self.score /= 2
				self.kill()
				self.fov.kill()
				#self.actionbar.kill()
				#self.hpbar.kill()


		self.rect.centerx = round(self.pos[0],0)
		self.rect.centery = round(self.pos[1],0)
		# self.currentHP -= self.idle_damage

	def update(self, enemies, boxes):
		self.think(boxes)
		if self.colorcount != 0:
			self.movecount += 1
			if self.movecount == 4:
				self.image.fill((0,0,0))
				self.movecount = 0
		j = pygame.sprite.spritecollideany(self, enemies)
		if j:

			screen.blit(dead_pix, (j.pos[0]-self.size, j.pos[1]-self.size))
			j.kill()

			self.image.fill((0,255,0))
			self.colorcount = 1
			self.score += 1.0
			self.currentHP += 10
			self.nextmoveSpeed += 5
			self.nextsize += 10
			self.nextmaximumSightDistance += 15

Enemy class

The enemy class is basically just a dumber version of the Character class. As of the moment, it does not have any motor or visual skills. This makes it easier for simulation to happen.

 

The Environment

It’s a simple 800×600 screen with no obstacles aside from the walls around it.

1
2
3
4
5
6
7
canvasWidth = 800
canvasHeight = 600
screen = pygame.display.set_mode((canvasWidth, canvasHeight))
background = pygame.Surface(screen.get_size())
background.fill((255,255,255))     # fill white
background = background.convert()  # jpg can not have transparency
screen.blit(background, (0,0))     # blit background on screen (overwriting all)

 

Genetics Algorithm

Creating this algorithm took many trials, as there are many different methods of doing natural selection, crossovers, and mutations. (Thanks to the people in the Credits section below for shedding light on how this actually works!) Selecting these methods will depend on how fast or slow (in terms of evolution), and diverse or limited (mutation and crossovers) you want the next generation of Characters to be.

Let’s take it step by step.

Fitness Calculation

After every step iteration in each generation, the fitness of all Characters has to be calculated. This is important to do because it allows us to determine which among the Characters are fit and unfit, which, as you might have guessed already, is used for the natural selection part of the algorithm.

Below you can see that if the Character ends up dying before the timer runs out, then it doesn’t have a bonus score (I might have to include a penalty there… maybe not, because there’s a penalty for dying already). If it is still alive when time’s up, it gets a bonus for surviving, but it gets a small penalty for losing HP.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def calcFitness(population):
	topFitness = []
	for i in population:
		if i.currentHP >= 0:
			i.fitness = .8 * 20 * i.score + .1 * 1  - 0.1 * .01 * (i.maxHP - i.currentHP)
		else:
			i.fitness = .8 * 20 * i.score
		topFitness.append(round(i.fitness, 2))
	topFitness = sorted(topFitness, reverse = True)
	#print topFitness

	avegenfitness = mean(topFitness)
	return topFitness, avegenfitness

Natural Selection

This section has three methods. You can see the 1st two commented below. I tried them first, but after examining the three methods separately, the third one made the more sense for my needs.

The first was taught by Daniel Shiffman in his Nature of Code book and series on Youtube. It explicitly allows the fittest agents to have more chances of getting picked from the population.

The second one and third one, I can’t seem to remember where I learned about them. I’m sure one was from a flappy bird example and the other was from another of Daniel Shiffman’s examples. (will update soon.)

At the very end, this function returns a mating pool, which is a list that contains all the potential parents for the next generation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def naturalSelection(population):
	matingpool = []
	maxFitness = 0.01
	r = 1.0
	'''VERSION1'''
	for i in range(len(population)):
		if population[i].fitness > maxFitness:
			maxFitness = population[i].fitness

	# for i in range(len(population)):
	# 	population[i].normFitness = int(population[i].fitness/maxFitness * 100)

	# 	for j in range(population[i].normFitness):
	# 		matingpool.append(population[i])
	'''VERSION2'''
	# for i in range(len(population)):
	# 	if population[i].fitness > maxFitness:
	# 		maxFitness = population[i].fitness

	# fitlist = []
	# for i in range(len(population)):
	# 	population[i].normFitness = population[i].fitness/maxFitness 

	# fitlist = sorted(population, key = lambda x: x.normFitness)
	
	# for i in range(len(fitlist)):
	# 	if r >0:
	# 		r -= fitlist[i].normFitness
	# 		matingpool.append(fitlist[i])
	# 	else: 
	# 		break
	'''VERSION3'''
	mutationRate = 0.1
	fitlist = []
	for i in range(len(population)):
		population[i].normFitness = population[i].fitness/maxFitness 

	fitlist = sorted(population, key = lambda x: x.normFitness)
	retain = int(len(fitlist)*.3)
	parents = fitlist[:retain]
	retained = 0
	for unfit in fitlist[retain:]:
		if 0.1 > random.random():
			parents.append(unfit)
			retained += 1
	#print 'Retained:', retained
	for i in parents:
		i = mutate(i.brain, mutationRate)

	matingpool = parents


	return matingpool

Generation of New Population

This part of the algorithm is where the magic happens. Version 1 is a purely random implementation of the generation (c/o Daniel Shiffman’s re: Shakespeare’s Monkey algorithm — which I have also practiced on and ported to python here.)

The second one is, I’m sure, from a flappy bird example. The main difference from the first version is that, even though it’s still random, it disallows the mating (Crossover) of the same parent, and it allows a male-female combination 3 times to mate. If it’s not successful, then a new pair of parents will be selected. This, for me, is more geared towards fitter children than the first one, which is what I want to have. Each child has a chance of mutating a bit.

Once the population is full again, the cycle continues.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def generate(population, matingpool, mutationRate):
	evolvedPop = []
	'''VERSION1'''
	# for i in range(len(population)):
	# 	male = random.randint(0, len(matingpool) - 1)
	# 	female = random.randint(0, len(matingpool) - 1)

	# 	male = matingpool[male]
	# 	female = matingpool[female]
	# 	child = crossover(male, female)
	# 	child.brain = mutate(child.brain, mutationRate)
	# 	evolvedPop.append(child)

	'''VERSION3 of naturalSelection'''
	parents_length = len(matingpool)
	desired_length = len(population) - parents_length
	children = []
	#print parents_length, desired_length
	while len(children) < desired_length:
		male = random.randint(0, len(matingpool) - 1)
		female = random.randint(0, len(matingpool) - 1)
		if male != female:
			male = matingpool[male]
			female = matingpool[female]
			for _ in range(2):
				if mutationRate > random.random():
					child = crossover(male, female)
					child.brain = mutate(child.brain, mutationRate)
					if len(children) < desired_length:
						children.append(child)

	matingpool.extend(children)

	evolvedPop = matingpool

	return evolvedPop

Crossover of DNA

The crossover portion has 2 versions:

  1. The first one being  a clean mid split beween the brain DNA of the parents, where the child gets the 1st half of its DNA from the male and the 2nd half from the female. This is easy to implement, but it kinda goes against the randomness of nature.
  2. The second one is where I tried segmented crossovers. The first segment was for the brain DNA. The second was for size, followed by maximum sight, max speed, then maxHP. This gave me more variety when it comes to the later generations of Characters. By using this version, I was able to create a more dynamic type of child, one that has a split probability of receiving each neuron either from the male or female.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def crossover(male, female):
	child = Character()

	maleDNA = male.brain.params
	femaleDNA = female.brain.params

	maleDNA = maleDNA.tolist()
	femaleDNA = femaleDNA.tolist()
	'''VERSION1'''
	# split = int(len(male.brain.params) / 2)

	# maleDNA = maleDNA[:split]
	# femaleDNA = femaleDNA[split:]

	# maleDNA.extend(femaleDNA)

	# for i in range(len(child.brain.params)):
	# 	print child.brain.params[i]
	# 	child.brain.params[i] = maleDNA[i]
	# 	print child.brain.params[i], maleDNA[i]
	'''VERSION2'''
	newDNA = []
	for i in range(len(maleDNA)):
		if random.random() > 0.5:
			newDNA.append(maleDNA[i])
		else:
			newDNA.append(femaleDNA[i])	

	for i in range(len(child.brain.params)):
		child.brain.params[i] = newDNA[i]

	if random.random() > 0.5:
		child.size = male.nextsize
	else:
		child.size = female.nextsize

	if random.random() > 0.5:
		child.maximumSightDistance = male.nextmaximumSightDistance
	else:
		child.maximumSightDistance = female.nextmaximumSightDistance

	if random.random() > 0.5:
		child.moveSpeed = male.nextmoveSpeed
	else:
		child.moveSpeed = female.nextmoveSpeed

	if random.random() > 0.5:
		child.maxHP = male.nextmaxHP
	else:
		child.maxHP = female.nextmaxHP



	return child

Mutation of DNA

Last but not the least, this mutation function gives a certain randomness to how the brain DNA (and how the Character makes its decisions) changes.

1
2
3
4
5
6
7
8
def mutate(brain, mutationRate):
	for i in range(len(brain.params)):
		if mutationRate > random.random():
			if random.random() > 0.5:
				brain.params[i] += 0.01
			else:
				brain.params[i] -= 0.01
	return brain

 

Samples:

  1. Implementation without Characters attacking each other. I found out that if they don’t attack each other, at around generation 500, they stagnated in terms of behavior. There was no reason for them to deviate because everyone was doing the same thing. I think this type of implementation needs a bit higher mutation rate.
  2. Implementation with Characters attacking each other. I could look at this for hours. It was fascinating to see smaller Characters avoiding the bigger ones. However, at around generation 900, for whatever reason, majority of the Characters were small fast critters, hinting that the crossover function was a success in creating new species. (VIDEO TO FOLLOW)

Credits:

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s