novelty search vs random walk

wander.py

#!/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)