Skip to content

Instantly share code, notes, and snippets.

@ejheil
Created June 15, 2016 19:51
Show Gist options
  • Save ejheil/a0379775b4338154df30c30e0a67753d to your computer and use it in GitHub Desktop.
Save ejheil/a0379775b4338154df30c30e0a67753d to your computer and use it in GitHub Desktop.
novelty search vs random walk
#!/usr/bin/env python
import random
from collections import Counter
class Room():
def __init__(self, dimensions, start, egress, walls):
self.dims = dimensions
self.egress = egress
self.walls = walls
if start == 'random':
self.start = self.get_random_start()
else:
self.start = start
def is_wall(self, position):
for wall in self.walls:
if (wall[0][0] <= position[0] <= wall[1][0]) and (wall[0][1] <= position[1] <= wall[1][1]):
return True
return False
def is_start(self, position):
return position == self.start
def get_start(self):
return self.start
def get_random_start(self):
position = (random.randint(0, self.dims[0] - 1), random.randint(0, self.dims[1] - 1))
if self.is_wall(position):
return self.get_random_start()
else:
return position
def is_in_bounds(self, position):
return ((0 <= position[0] < self.dims[0]) and (0 <= position[1] < self.dims[1]))
def result_of_move(self, position, move):
newpos = (position[0]+move[0], position[1]+move[1])
if not self.is_in_bounds(newpos):
newpos = position # nope
if self.is_wall(newpos):
newpos = position # nope
return newpos
def is_egress(self, position):
return position == self.egress
def available_moves(self, position):
possible_moves = [
(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1),
]
avail = []
for m in possible_moves:
r = self.result_of_move(position, m)
if self.is_in_bounds(r) and not self.is_wall(r):
avail.append(r)
return avail
class Robot():
def __init__(self, room, mode):
self.mode = mode
self.room = room
self.position = self.room.get_start()
self.position_memory = {}
def been_there(self, position):
return self.position_memory.get(position, 0)
def remember(self, position):
self.position_memory[position] = self.position_memory.get(position, 0) + 1
def least_boring_of(self, avail):
mins = avail[0:1]
for position in avail[1:]:
if self.been_there(position) < self.been_there(mins[0]):
mins = [position]
if self.been_there(position) == self.been_there(mins[0]):
mins.append(position)
return mins
def make_move(self):
if self.mode == 'novelty':
self.novelty_move()
else:
self.random_move()
def take_position(self, position):
self.position = position
self.remember(position)
def random_move(self):
avail = self.room.available_moves(self.position)
self.take_position(random.choice(avail))
def novelty_move(self):
avail = self.room.available_moves(self.position)
least = self.least_boring_of(avail)
self.take_position(random.choice(least))
def report_room(self):
for y in range(0, self.room.dims[1]):
for x in range(0, self.room.dims[0]):
times = self.been_there((x, y))
if self.room.is_egress((x, y)):
print ' X',
elif self.room.is_wall((x, y)):
print ' #',
elif self.room.is_start((x, y)):
print ' @',
elif times == 0:
print ' ',
else:
print '%3d' % times,
print
def escape_attempt(self):
steps = 0
while not self.room.is_egress(self.position):
steps = steps + 1
self.make_move()
return steps
walls = [
((4, 0), (4, 10)),
((4,10), (14,10)),
((14, 8), (14, 14)),
((3, 14), (14, 14)),
((6, 6), (20, 6)),
((4, 3), (18, 4)),
((5, 18), (9, 20))
]
dims = (20, 20)
start = (0, 0)
egress = (10, 0)
#room = Room(dims, 'random', egress, walls)
room = Room(dims, start, egress, walls)
r = Robot(room, 'random')
steps = r.escape_attempt()
r.report_room()
print steps, 'steps!'
print
r2 = Robot(room, 'novelty')
steps2 = r2.escape_attempt()
r2.report_room()
print steps2, 'steps!'
print 'ratio: ', (1.0 * steps / steps2)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment