<file_sep>import numpy
import numpy.random
from multiprocessing import Queue


class State(object):
    " Abstract class to define an state. "

    def __hash__(self):
        raise NotImplementedError("__hash__ function must be implemented.")

    @staticmethod
    def getfromhash(hash):
        raise NotImplementedError("__hash__ function must be implemented.")

    def __eq__(self, other):
        raise NotImplementedError("__eq__ function must be implemented.")

    def next_state(self, state):
        raise NotImplementedError("A tuple (new state, reward) must be returned.")

    def is_terminal(self):
        raise NotImplementedError("Check if the current state is terminal.")

    def actions(self):
        raise NotImplementedError("List of actions in the state.")

    
class Sarsa(object):

    def __init__(self, start_state, epsilon=0.1, alpha=0.1, gamma=0.8):
        self.start_state = start_state

        # Keep the estimates for Q(s, a)
        self.q_estimates = {}

        # Epsilon for the E-greedy policy.
        self.epsilon = epsilon

        # Alpha/
        self.alpha = alpha

        # Lambda
        self.gamma = gamma
        
    def seed(self, seed):
        numpy.random.seed(seed)

    def update_q(self, state, action, correction):
        q = self.get_q(state, action)
        self.q_estimates[(state, action)] = q + self.alpha * correction

    def get_q(self, state, action):

        if (state, action) not in self.q_estimates:
            self.q_estimates[(state, action)] = numpy.random.random()
            
        return self.q_estimates[(state, action)]

    def greedy_action(self, state, epsilon=None):
        " Compute the E-greedy action. "

        if epsilon is None:
            epsilon = self.epsilon

        # List of actions.
        actions = state.actions()

        # List of tuples (action, value)
        actions_value = [(a, self.get_q(state, a)) for a in actions]
        actions_value.sort(key=lambda x: -x[1])

        # We now have the state-actions values in order, add the probability.
        actions_p = [1 - epsilon + epsilon / len(actions)] + [epsilon / len(actions)]

        s = numpy.random.random()

        if s < 1 - epsilon:
            return actions_value[0][0]

        # Choose one between the rest.
        s -= 1 - epsilon
        s *= (len(actions) - 1) / epsilon
        return actions_value[1 + int(s)][0]

    def iterate(self):
        " Execute a single episode. "

        state = self.start_state
        action = self.greedy_action(state)

        # Save the history.
        history = [state]
        corrections = []

        while not state.is_terminal():

            # Take the greedy action.
            next_state, r = state.next_state(action)

            # Second pair.
            next_action = self.greedy_action(next_state)

            # Update Q(first_state, first_action)
            correction = r + self.gamma * self.get_q(next_state, next_action) - self.get_q(state, action)
            self.update_q(state, action, correction)

            # Save history.
            corrections.append(correction)
            history.append(next_state)

            # Update state.
            state = next_state
            action = next_action

        return history, corrections

            
    def eval(self, max_iter=100):
        """ Just evaluate the current policy."""

        # Save the history in different array.
        history = [self.start_state]
        state = self.start_state
        reward = 0

        for it in range(max_iter):

            # Complete greedy action, no exploration!.
            action = self.greedy_action(state=state, epsilon=0)

            # Take the greedy action.
            state, r = state.next_state(action)
            reward += r

            # Save the state.
            history.append(state)

            if state.is_terminal():
                break

        return history, reward


class SarsaTraces(Sarsa):

    def __init__(self, start_state, epsilon=0.1, alpha=0.1, gamma=0.8, Lambda=0.1):

        self.start_state = start_state

        # Keep the estimates for Q(s, a)
        self.q_estimates = {}

        # Keep the traces
        self.traces = {}

        # Epsilon for the E-greedy policy.
        self.epsilon = epsilon

        # Alpha/
        self.alpha = alpha

        # Gamma
        self.gamma = gamma

        # Lambda
        self.Lambda = Lambda

        self.reset()

    def reset(self):
        " Reset the state of the machine."
        self.history = [self.start_state]
        self.corrections = []
   
        # This is not part of the algorithm but I don't see the point in keeping this on
        # different episodes, and cleaning this will increase the performance.
        self.traces = {}

    def update_trace(self, state, action):
        # Update and get acts as an sparsed matrix based on key-value.
        # Check on:
        # http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.dok_matrix.html
        self.traces[(state, action)] = self.gamma * self.Lambda * self.get_trace(state, action)

    def get_trace(self, state, action):
        if (state, action) not in self.traces:
            self.traces[(state, action)] = 0
        return self.traces[(state, action)]

    def update_iter(self, state, action, correction):
        self.update_q(state, action, correction)
        self.update_trace(state, action)        

    def iterate(self):
        " Execute a single episode. "

        self.reset()
        
        state = self.start_state
        action = self.greedy_action(state)

        while not state.is_terminal():

            # Take the greedy action.
            next_state, r = state.next_state(action)

            # Second pair.
            next_action = self.greedy_action(next_state)

            # Update Q(first_state, first_action)
            correction = r + self.gamma * self.get_q(next_state, next_action) - self.get_q(state, action)
            self.traces[(state, action)] = self.get_trace(state, action) + 1
            
            # Update just the states with non-zero trace.
            for key, value in self.traces.items():
                self.update_q(key[0], key[1], correction * value)
                self.update_trace(*key)

            self.history.append(next_state)
            state = next_state
            action = next_action
        


class SarsaPartition(Sarsa):
    """
    Sarsa with partition
    ====================

    I will try to implement a patitioned sarsa based on ideas of the paper:
    http://www.ejournal.org.cn/Jweb_cje/EN/article/downloadArticleFile.do?attachType=PDF&id=7638
    The basic idea is that we can define a partition in the space state with some nice properties that I will try to express nicely if this works.

    I will try to implement a way to split the big problem in little problems adding a method
    *part* in the state class which says to which part the state belongs, if we hit a
    `next_state` in a different class we are going to need to add a problem starting on
    that state to the scheduler, and mark it to update, then any other subproblem that hit
    this one will wait for the update mark it again and add a new subproblem starting in the
    same point.

    We need to add a mark to the Q values, this mark will control that a value of Q in
    the boundary of a partition will be used just once by a subsolver.

    
    """

    def __init__(self, *args, **kwargs):
        super(SarsaPartition, self).__init__(*args, **kwargs)

        # We're going to store the states in this queues.
        self.queues = {}

        # We need to add the queues of the parts.
        for p in kwargs['parts']:
            self.queues[p] = Queue()

    def iterate(self, part):
        " Execute a single episode. "

        # Fetch a problem from part 
        history, corrections, state = self.queue[part].get()

        self.reset()
        
        state = self.start_state
        action = self.greedy_action(state)

        while not state.is_terminal():

            # Take the greedy action.
            next_state, r = state.next_state(action)

            # Second pair.
            next_action = self.greedy_action(next_state)

            # Update Q(first_state, first_action)
            correction = r + self.gamma * self.get_q(next_state, next_action) - self.get_q(state, action)
            self.traces[(state, action)] = self.get_trace(state, action) + 1
            
            # Update just the states with non-zero trace.
            for key, value in self.traces.items():
                self.update_q(key[0], key[1], correction * value)
                self.update_trace(*key)

            self.history.append(next_state)
            state = next_state
            action = next_action
<file_sep>import time
from sarsa import State, Sarsa
from itertools import izip_longest
import pylab

class BarnState(State):
    """
    State in the Barn
    =================

    An state in the barn is defined by the position of the rat and the food still in the barn.

    :position: must be a 2-tuple of x,y coord.
    :food: a list of 2-tuples with the coord of the food.

    """

    def __init__(self, position, food, max_size):
        self.position = position
        self.food = food

        self.max_size = max_size

    def __hash__(self):
        h = "%d:" % self.max_size
        h += "%d:%d:" % self.position
        h += ":".join("%d:%d" % f for f in self.food)
        return  hash(h)

    def __eq__(self, other):            
        return (self.position == other.position) and (self.food == other.food) and (self.max_size == other.max_size)

    def next_state(self, action):

        if action == 'right':
            next_position = ((self.position[0] + 1) % self.max_size, self.position[1])

        elif action == 'left':
            next_position = ((self.position[0] - 1) % self.max_size, self.position[1])

        elif action == 'up':
            next_position = (self.position[0], (self.position[1] + 1) % self.max_size)

        elif action == 'down':
            next_position = (self.position[0], (self.position[1] - 1) % self.max_size)

        next_food = [f for f in self.food if f != next_position]
        reward = -1 if (len(next_food) == len(self.food)) else 1

        return BarnState(next_position,  next_food, self.max_size), reward
            
    def is_terminal(self):
        return (self.food == []) and (self.position == (self.max_size-1, self.max_size-1))

    def actions(self):
        actions = ["up", "down", "left", "right"]

        if self.position[0] == 0:
            actions.pop(actions.index("left"))
        if self.position[1] == 0:
            actions.pop(actions.index("down"))
        if self.position[0] == self.max_size - 1:
            actions.pop(actions.index("right"))
        if self.position[1] == self.max_size - 1:
            actions.pop(actions.index("up"))

        return actions

def plot_path(path):

    pylab.clf()
    pylab.xlim(-2, max_size + 1)
    pylab.ylim(-2, max_size + 1)
    pylab.axis('off')

    # Start.
    pylab.annotate('start', xy=(0, 0), xytext=(-1, -1), size=10, bbox=dict(boxstyle="round4,pad=.5", fc="0.8"), arrowprops=dict(arrowstyle="->"))
    pylab.annotate('stop', xy=(max_size-1, max_size-1), xytext=(max_size, max_size), size=10, bbox=dict(boxstyle="round4,pad=.5", fc="0.8"), arrowprops=dict(arrowstyle="->"))

    # Show the food.
    for f in food:
        pylab.annotate('food', xy=f, size=5, bbox=dict(boxstyle="round4,pad=.5", fc="0.8"), ha='center')
    
    
    for i in range(len(path) - 1):
        pylab.arrow(path[i][0], path[i][1], path[i+1][0] - path[i][0], path[i+1][1] - path[i][1])


# Parameters.
max_size = 20
food = [(0,8), (4,4), (1,1), (8,8), (6,2), (12, 15), (17,2), (4, 12), (17, 17), (12, 1)]

# Start the algorithm.
sarsa = Sarsa(BarnState((0,0), food, max_size), epsilon=0.1, alpha=0.1, gamma=0.2)
sarsa.seed(int(100* time.time()))

plot_in = [10, 100, 200, 400, 600, 1000, 1500, 2000, 4000, 5000, 6000, 8000, 10000, 12000, 15000, 20000] 
for i in range(max(plot_in) + 1):
    sarsa.iterate()

    if i % 10 == 0:
        print i
    
    if i in plot_in:
        plot_path([s.position for s in sarsa.history])
        pylab.savefig('/tmp/simple-path-4-%d.png' % i)
        print i



<file_sep>"""
The Barn and the Rat
====================

First we create a squaed Barn with size n x n, and we place m pieces
of food on it.

From the barn we can get the number of possible states of the problem.
Given a barn of size n by n with m pices of food located on it, the number
of states of the system is given by all the possible locations of the rat
in the barn and the foo still in the barn, there are n^2 locations, and
there are 2^m states for the pieces of food, then roughlt speaking there are
n^2 * 2^m states. An state is defined by the location of the rat and the
pieces of food still in the barn, once we choose one location, there are
2 ^ m possibilities for the food. Also, if we choose a possition with food
(there are m of them) we can choose only 2 ^ (m-1), so the real number of states are:

 States: (n ^ 2 - m) * 2 ^ m + m * 2 ^ (m - 1) = (2 * n ^ 2 - m ) * 2 ^ (m -1)

Now, a policy is a map from the states to actions, we have at most 4 actions:
left, right, up and down. In some cases just 3 or 2.

We can compute the Value (in terms of the book) of each action given a state,
we estimate that the value is one in any state with no food,
and zero in any state with all the food on it.The Rat will learn to eat the food.

"""
import time
import numpy as np
from random import choice
import matplotlib.pyplot as plt
    

class Barn(object):

    def __init__(self, n, m, alpha=0.1, epsilon=0.1):

        # Save the epsilon.
        self.epsilon = epsilon

        # Save alpha parameter.
        self.alpha = alpha

        # Save the size and the food.
        self.size = n
        self.food_size = m

        # Locate the food.
        self.food = set()
        while len(self.food) < self.food_size:
            self.food.add(tuple(np.random.random_integers(0, self.size - 1, 2)))
        self.food = list(self.food)

        # Dynamically save the values.
        self._values = {}

        # Current state.
        self.current = "0:0:" + "1" * self.food_size

        # Remember the actions.
        self.positions = [(0, 0)]
        

    # def __repr__(self):
    #     # Create a nice representaiton of the barn.

    #     # Rat position.
    #     pos = int(self.current.split(':')[0])
    #     rat_i = pos / self.food_size
    #     rat_j = pos % self.food_size

    #     msg = "+" + "-" * 3 * self.size + "+\n"
        
    #     for i in range(self.size):
    #         msg += "|"
            
    #         for j in range(self.size):

    #             if rat_i == i and rat_j == j:
    #                 msg += " R "
    #             else:
    #                 msg += " * " if (self.matrix[i, j] == 1) else "   "

    #         msg += "|\n"

    #     msg += "+" + "-" * 3 * self.size + "+\n"
    #     msg += " Current State: %s\n" % self.current
    #     msg += " Number of states: %d\n" % ((2 * self.size ** 2 - self.food_size ) * 2 ** (self.food_size - 1))
    #     msg += " Actions: %s\n" % (", ".join(self.actions(self.current)))
    #     for action in self.actions(self.current):
    #         msg += "   %s: next:%s\n" % (action, self.next_state(action))
    #     return msg


    def value(self, id):
        " We encode any value as: {i * n + j}:{p0}{p1}{p2}... and so on, then "

        if id not in self._values:

            if id.endswith(":" + "0" * self.food_size):
                # There is no food in the barn.
                return 1.0

            if id.endswith(":" + "1" * self.food_size):
                # There is no food in the barn.
                return 0.0

            return 0.0

        return self._values[id]

    def update_value(self, id, correction):
        if id not in self._values:
            self._values[id] = 0.0
            
        self._values[id] += self.alpha * correction

    def actions(self, id):
        """ Given some state we compute the possible actions. """

        # Possible actions.
        actions = set(['left', 'right', 'up', 'down'])

        # Rat position.
        x, y = map(int, self.current.split(':')[:2])

        if x == 0:
            actions.remove('left')
        if y == 0:
            actions.remove('down')
        if x == self.size - 1:
            actions.remove('right')
        if y == self.size - 1:
            actions.remove('up')

        return actions              

    def next_state(self, action):
        """ Compute the next state given an action. """

        x, y, food = self.current.split(':')
        x = int(x)
        y = int(y)
        
        if action == 'left':
            x -= 1
        if action == 'right':
            x += 1
        if action == 'up':
            y += 1
        if action == 'down':
            y -= 1

        # Any food in the place.
        if (x, y) in self.food:
            index = self.food.index((x, y))
            food = food[:index] + '0' + food[index + 1:]

        return '%d:%d:%s' % (x, y, food)
                        
    def choose_action(self):
        """ Given the curent state we choose an action. """

        values = []
        
        for action in self.actions(self.current):

            # Compute the next state.
            next_state = self.next_state(action)

            # Get the value of this actions.
            values.append((action, next_state, self.value(next_state)))

        # Greedy guy.
        max_value = sorted(values, lambda x, y: int(y[2] - x[2]))[0][2]

        # Get the epsilon close states and choose one.
        states = [v for v in values if abs(v[2] - max_value) < self.epsilon]
        action, next_state = choice(states)[:2]

        # Update values.
        self.update_value(self.current, self.value(next_state) - self.value(self.current))        
        self.current = next_state

        # Store the action.
        self.positions.append(map(int, self.current.split(':')[:2]))

    def clear(self):
        " Clear the memory for a new run."

        # Current state.
        self.current = "0:0:" + "1" * self.food_size
        self.positions = []

    def run(self, maxit=1000):
        " Run until the rat finish the food"

        for i in range(maxit):
            self.choose_action()
            
            if self.current.endswith(":" + "0" * self.food_size):
                print "done!"
                break

        # Return the list of x, y of positions.
        x = []
        y = []
        for pos in self.positions:
            x.append(pos[0])
            y.append(pos[1])

        x = np.array(x)
        y = np.array(y)
        
        return x, y


if __name__ == "__main__":
    
    b = Barn(3, 2, epsilon=0.4)

    for i in range(100):
        
        x, y = b.run(1000)
        b.clear()

    x, y = b.run(1000)


    
    plt.figure()
    plt.quiver(x[:-1], y[:-1], x[1:]-x[:-1], y[1:]-y[:-1], scale_units='xy', angles='xy', scale=10)
    x, y = zip(*b.food)
    plt.plot(x, y, 'ro')
    plt.show()
<file_sep>import numpy
import numpy.random
from random import randint, choice
from UserDict import UserDict
from multiprocessing import Process, Manager, Pool
from Queue import Queue
import pylab


class StateActionValues(UserDict):
    """
    We should handle the blocking in here, if we know that there is not going to be any
    problem (interior of the set) we can use the normal dict api, otherwise, the get and set
    methods are the one that checks for blocks.
    """

    def __getitem__(self, key):
        if key not in self.data:
            #self.data[key] = numpy.random.random()
            self.data[key] = 0
        return self.data[key]    


class SarsaAgent(Process):
    """
    This object will run the iterative process needed in sarsa.
    
    """

    def __init__(self, part, inbox, outbox, max_iter=20, Epsilon=0.8, Alpha=0.1, Gamma=0.8):
        Process.__init__(self)

        # Save the parameters.
        self.Epsilon = Epsilon
        self.Alpha = Alpha
        self.Gamma = Gamma

        # Keep track of all the parts.
        self.part = part

        # We receive jobs in this queue.
        self.inbox = inbox

        # We sent stopping states in this box.
        self.outbox = outbox

        # Max number of iterations.
        self.max_iter = max_iter

    def run(self):

        while True:

            # Get a job from the queue.
            job = self.inbox.get()

            # Stop condition.
            if job is None:
                break

            # Job is just a pair state-action to start.
            state, action, own_Q, extra_Q = job

            # Recover the Q values.
            self.own_Q = StateActionValues(own_Q)
            self.extra_Q = StateActionValues(extra_Q)

            # Compute greedy action
            if action is None:
                action = self.greedy_action(state)

            # Iterate a bunch of times with this condition.
            res = []
            for it in range(self.max_iter):                
                res.append(self.iterate(state, action))
                
            # A message from the agent to the scheduler.
            self.outbox.put({'part': self.part, 'extra_Q': self.extra_Q.data, 'own_Q': self.own_Q.data, 'results': res})

    def greedy_action(self, state, Epsilon=None):
        " Compute the E-greedy action. "

        # Get the current epsilon or the stored one (to control the ??greedyness??)
        Epsilon = Epsilon or self.Epsilon 

        # List of actions.
        actions = state.actions()

        # List of tuples (action, value)
        if state.part == self.part:
            actions_value = [(a, self.own_Q[(state, a)]) for a in actions]
        else:
            actions_value = [(a, self.extra_Q[(state, a)]) for a in actions]
            
        actions_value.sort(key=lambda x: -x[1])

        # We now have the state-actions values in order, add the probability.
        actions_p = [1 - Epsilon + Epsilon / len(actions)] + [Epsilon / len(actions)]

        # Check if we're greed in this case.
        s = numpy.random.random()
        if s < 1 - Epsilon:
            return actions_value[0][0]

        # Choose one between the rest.
        s -= 1 - Epsilon
        s *= (len(actions) - 1) / Epsilon
        return actions_value[1 + int(s)][0]

    def iterate(self, initial_state, initial_action):

        state = initial_state
        action = initial_action

        while (not state.is_terminal()) and (state.part == self.part):

            # Take the greedy action.
            next_state, reward = state.next_state(action)
            
            # Second action.
            next_action = self.greedy_action(next_state)
            
            # If next state is in different part the reward is the estimated value.
            # We still use the value in this part, since is job of the scheduler to
            # update the value with the possible result in the other part.
            if next_state.part != self.part:
                reward = self.extra_Q[(next_state, next_action)]
                next_q = reward
            else:
                next_q = self.own_Q[(next_state, next_action)]
            
            # Update Q(first_state, first_action)
            correction = reward + self.Gamma * next_q - self.own_Q[(state, action)]
            self.own_Q[(state, action)] += self.Alpha * correction
            
            # Update state.
            state = next_state
            action = next_action

        
        return state, action

                

class Sarsa(object):
    """
    In the state space we can define some nice concept:

     - Neighbor of a state x: all the state reacheble from the state after an action.
     - Interior of X: the set of states with neigbhors in X.
     - Closure of X: the union of neigbhors of the state x for all x in X.
     - Boundary of X: Closure of X - Interior of X.
     
    If we let sarsa to act on the interior of a set X we have no problems, we need to check
    if an state x in X is in the boundary of X.

    A subproblem starts when is fetched from the queue of subproblems, there must be a
    master process checking to add more starting problems which is just the starting state.

    Once the iterative algorithm hit a state in the boundary we check if next_state is outside
    the set, in that case we check if there is a block in the Q(next_state, next_action) and
    we wait for it, otherwise we get the value and put a block, in both cases the next step
    is to add a subproblem starting in (next_state, next_action).

    We need to ensure that the number of starting subproblems is considerable big that the
    max of the size of the boundaries.

    """

    def __init__(self, manager, initial_state, Epsilon=0.8, Alpha=0.1, Gamma=0.8):

        # Save the parameters.
        self.Epsilon = Epsilon
        self.Alpha = Alpha
        self.Gamma = Gamma

        # Keep track of all the parts.
        self.parts = initial_state.parts

        # Create the queues for the passing jobs.
        self.outbox = dict((p, manager.Queue()) for p in self.parts)
        self.inbox = manager.Queue()

        # Keep the global state-action values in here.
        self.Q = dict((p, StateActionValues()) for p in self.parts)
        
        # Create the processes for each part.
        self.agents = dict((p, SarsaAgent(p, self.outbox[p], self.inbox, Epsilon=Epsilon, Gamma=Gamma, Alpha=Alpha)) for p in self.parts)

        # Each part has an unknown set of states in other parts.
        self.needed_Q = dict((p, set([])) for p in self.parts)

        # Initial states.
        self.initial_states = []

        # Save the initial state.
        self.initial_state = initial_state

        # Start all the agents.
        [self.agents[a].start() for a in self.agents]


    def seed(self, seed):
        numpy.random.seed(seed)


    def select_jobs(self, n):
        " Select n jobs to be scheduled."
        return set([choice(self.initial_states) for i in range(n)])

        return sorted(self.initial_states, key=lambda x: x[0].part)[:n]

    def iterate(self, max_iter=100):
        " Execute a single episode. "

        # Start the iterations counter, iterations are counted each time we reacheble
        # a global stopping state.
        it = 0

        # Start by sending an initial state.        
        self.outbox[self.initial_state.part].put((self.initial_state, None, {}, {}))

        # Running now
        running = 1

        while it < max_iter:

            if len(self.initial_states) > 0:

                # Get the jobs to send
                # jobs = set([choice(self.initial_states) for i in range(10 - running)])
                jobs = self.select_jobs(max(4 - running, 0))
                
                for job in jobs:
                    
                    state, action = job
                    part = state.part

                    # Get own and extra Q values.
                    own_Q = self.Q[part].data
                    extra_Q = dict((k, self.Q[k[0].part][k]) for k in self.needed_Q[part])

                    # Submit job with Q values.
                    self.outbox[part].put((state, action, own_Q, extra_Q))

                    # One more is running.
                    running += 1
            
            # Read a message.
            msg = self.inbox.get()

            # One less is running.
            running -= 1
            
            # Get part.
            part = msg['part']
            print part, running

            # A message bring results and needed fridges.
            self.needed_Q[part] = self.needed_Q[part].union(set(msg['extra_Q'].keys()))

            # Update the Q values.
            self.Q[part].data.update(msg['own_Q'])

            # And we add possible jobs for the future.
            for result in msg['results']:
                state, action= result

                # If final state count iteration, if not save intermidiate job.
                if not state.is_terminal():
                    self.initial_states.append(result)
                else:

                    # Get the Q values from the initial state.
                    own_Q = self.Q[self.initial_state.part].data
                    extra_Q = dict((k, self.Q[k[0].part][k]) for k in self.needed_Q[self.initial_state.part])

                    # Send the job.
                    self.outbox[self.initial_state.part].put((self.initial_state, None, own_Q, extra_Q))
                    
                    running += 1
                    it += 1
                    print "Iteration: ", it                
                                                       

    def greedy_action(self, state, Epsilon=None):
        " Compute the E-greedy action. "

        # Get the current epsilon or the stored one (to control the ??greedyness??)
        Epsilon = Epsilon or self.Epsilon 

        # List of actions.
        actions = state.actions()

        # List of tuples (action, value)
        actions_value = [(a, self.Q[state.part][(state, a)]) for a in actions]            
        actions_value.sort(key=lambda x: -x[1])

        # We now have the state-actions values in order, add the probability.
        actions_p = [1 - Epsilon + Epsilon / len(actions)] + [Epsilon / len(actions)]

        # Check if we're greed in this case.
        s = numpy.random.random()
        if s < 1 - Epsilon:
            return actions_value[0][0]

        # Choose one between the rest.
        s -= 1 - Epsilon
        s *= (len(actions) - 1) / Epsilon
        return actions_value[1 + int(s)][0]

            
    def eval(self, max_iter=100):
        """ Just evaluate the current policy."""

        # Save the history in different array.
        history = [self.initial_state]
        state = self.initial_state
        reward = 0

        for it in range(max_iter):

            part = state.part

            # Complete greedy action, no exploration!.
            action = self.greedy_action(state=state, Epsilon=0)

            # Take the greedy action.
            state, r = state.next_state(action)
            reward += r

            # Save the state.
            history.append(state)

            if state.is_terminal():
                break

        return history, reward


class BarnState(object):
    """
    State in the Barn
    =================

    An state in the barn is defined by the position of the rat and the food still in the barn.

    :position: must be a 2-tuple of x,y coord.
    :food: a list of 2-tuples with the coord of the food.

    """

    def __init__(self, position, food, size, amount_food):
        self.position = position
        self.food = food
        self.size = size
        self.amount_food = amount_food
        
        self.part = len(food)
        self.parts = range(self.amount_food + 1)

    def __hash__(self):
        h = "%d:" % self.size
        h += "%d:%d:" % self.position
        h += ":".join("%d:%d" % f for f in self.food)
        return  hash(h)

    def __eq__(self, other):            
        return (self.position == other.position) and (self.food == other.food) and (self.size == other.size)

    def next_state(self, action):

        if action == 'right':
            next_position = ((self.position[0] + 1) % self.size, self.position[1])

        elif action == 'left':
            next_position = ((self.position[0] - 1) % self.size, self.position[1])

        elif action == 'up':
            next_position = (self.position[0], (self.position[1] + 1) % self.size)

        elif action == 'down':
            next_position = (self.position[0], (self.position[1] - 1) % self.size)

        elif action == 'stay':
            next_position = (self.position[0], self.position[1])

        next_food = [f for f in self.food if f != next_position]
        reward = -1 if (len(next_food) == len(self.food)) else 1

        if (next_food == []) and (next_position == (self.size-1, self.size-1)):
            reward = 10

        return BarnState(next_position,  next_food, self.size, self.amount_food), reward
            
    def is_terminal(self):
        return (self.food == []) and (self.position == (self.size-1, self.size-1))

    def actions(self):
        actions = ["up", "down", "left", "right", "stay"]

        if self.position[0] == 0:
            actions.pop(actions.index("left"))
        if self.position[1] == 0:
            actions.pop(actions.index("down"))
        if self.position[0] == self.size - 1:
            actions.pop(actions.index("right"))
        if self.position[1] == self.size - 1:
            actions.pop(actions.index("up"))

        return actions

    @classmethod
    def initial_state(cls, size):

        # Randomly locate the food on the ba<rn.
        amount_food = randint(size / 2, 2 * size)
        food = []

        while len(food) < amount_food:

            # Add a new piece of food.
            food.append((randint(0, size-1), randint(0, size-1)))

            # Ensure uniqueness.
            food = list(set(food) - set([(0, 0)]))

        return cls((0 ,0), food, size, amount_food)
        

def plot_evaluation(history, title, max_size, food, filename):
    " Plot an evaluation. "

    pylab.clf()
    pylab.xlim(-2, max_size + 1)
    pylab.ylim(-2, max_size + 1)
    pylab.axis('off')

    # Start.
    pylab.title(title)
    pylab.annotate('start', xy=(0, 0), xytext=(-1, -1), size=10, bbox=dict(boxstyle="round4,pad=.5", fc="0.8"), arrowprops=dict(arrowstyle="->"))
    pylab.annotate('stop', xy=(max_size-1, max_size-1), xytext=(max_size, max_size), size=10, bbox=dict(boxstyle="round4,pad=.5", fc="0.8"), arrowprops=dict(arrowstyle="->"))

    # Show the food.
    for f in food:
        pylab.annotate('food', xy=f, size=5, bbox=dict(boxstyle="round4,pad=.5", fc="0.8"), ha='center')

    # Create the x and y locations.
    x = [s.position[0] for s in history]
    y = [s.position[1] for s in history]    
    pylab.plot(x, y)

    # Save the figure
    pylab.savefig(filename)


if __name__ == '__main__':

    # Create the manager for the multiprprocessing.
    manager = Manager()

    # Size.
    size = 2

    # Intial state.
    initial_state = BarnState.initial_state(size)

    # Create a single sarsa.
    sarsa = Sarsa(manager, initial_state, Epsilon=0.8)

    # Iterate 1000 times using the pool.
    it = 0
    per_it = 10
    for i in range(100):
        sarsa.iterate(per_it)
        it += per_it
        history, reward = sarsa.eval()        
        plot_evaluation(history, "Parallel: iteration %d with reward %d" % (it, reward), size, initial_state.food, "parallel-iteration-%d.png" % (it, ))

<file_sep>from UserDict import UserDict
from pybrain.tools.shortcuts import buildNetwork
from pybrain.datasets import SupervisedDataSet
from pybrain.supervised.trainers import BackpropTrainer
from pybrain.structure import TanhLayer, LinearLayer
from random import random
import sys
import argparse
import json


class EligibilityTraces(UserDict):
    def __getitem__(self, key):
        if key not in self.data:
            self.data[key] = 0
        return self.data[key]    


class StateActionCache(UserDict):
    """
    This class will implement the cache described in
    section 5.4 in Nissen Thesis [1].
    [1] http://leenissen.dk/rl/Steffen_Nissen_Thesis2007_Print.pdf
    """

    def __init__(self, input_size, hidden_size=10, cache_size=1000):
        self.data = {}
        self.cache_size = cache_size
        self.fifo = []

        # Create the network in here.
        self.net = buildNetwork(input_size, hidden_size, 1, outclass=LinearLayer, bias=True)

    def __getitem__(self, key):
        if key not in self.data:            
            self.data[key] = (1, self.net.activate(key[0]._to_ann(key[1]))[0])
        return self.data[key][1]

    def __delitem__(self, key):

        # Get current number of appearances,
        n, v = self.data.get(key, (0, None))

        if n <= 1:
            del self.data[key]
        else:
            self.data[key] = (n - 1, v)
        
        
    def __setitem__(self, key, value):

        if self.filled():
            del self[self.fifo.pop(0)]

        n = 1
        if key in self.data:
            n = self.data[key][0] + 1            

        self.data[key] = (n, value)
        self.fifo.append(key)
        
    def filled(self):
        return len(self.fifo) > self.cache_size

    def train(self):
        " Train the network. "
        
        ds = SupervisedDataSet(self.net.indim, self.net.outdim)
        n = len(self.fifo)
        for k, v in self.data.items():
            d = (k[0]._to_ann(k[1]), [v[1]])
            for i in range(v[0]):
                ds.addSample(*d)

        ret = None
        if len(ds) != 0:
            trainer = BackpropTrainer(self.net, ds)
            ret = trainer.train()
            
        # Clean the inner data.
        self.data = {}
        self.fifo = []
        
        return ret

class QSarsa(object):

    def __init__(self, state, cache_size=20000, hidden_size=8, Epsilon=0.8, Alpha=0.1, Gamma=0.8, Tao=0.1, Sigma=0.5, Lambda=0.3):

        # Starting state.
        self.initial_state = state

        # Save the parameters.
        self.Epsilon = Epsilon
        self.Gamma = Gamma
        self.Alpha = Alpha
        self.Tao = Tao
        self.Sigma = Sigma
        self.Lambda = Lambda

        # Q Cache.
        self.Q = StateActionCache(state._to_ann_size(), cache_size=cache_size, hidden_size=hidden_size)

        # Eligibility traces.
        self.e = EligibilityTraces()

    def select_action(self, state):
        " Select an action on the state."

        # List of tuples (action, value)
        actions = [(a, self.Q[(state, a)]) for a in state.actions]
        actions.sort(key=lambda x: -x[1])

        # Check if we're greed in this case.
        s = random()
        if s <= 1 - self.Epsilon:
            return actions[0]

        # Choose one between the rest.
        s -= 1 - self.Epsilon
        s *= (len(actions) - 1) / self.Epsilon
        return actions[1 + int(s)][0], actions[0][1]

    def select_best_action(self, state):
        " Select an action on the state."

        # List of tuples (action, value)
        actions = [(a, self.Q[(state, a)]) for a in state.actions]
        actions.sort(key=lambda x: -x[1])

        # Check if we're greed in this case.
        return actions[0]

    def evaluate(self):
        " Evaluate the system."

        state = self.initial_state
        it = 0

        history = [state]
        reward_total = 0

        while not state.is_terminal and it < self.initial_state.size ** 2:
            action, best_reward = self.select_best_action(state)
            state, reward = state.next_state(action)
            reward_total += reward
            history.append(state)
            it += 1

        return reward_total, history

    def run(self, it):
        " Run a episode."

        # Clear the traces.
        self.e = EligibilityTraces()

        # Starting state.
        state = self.initial_state

        # Select action.
        action, reward = self.select_action(state)

        while not state.is_terminal:

            # print len(self.Q.fifo), state.position, len(state.food)

            # Iterate.
            state, action = self.iterate(state, action)

            if self.Q.filled():

                # Train the neural network,
                print json.dumps({'iteration': it, 'train': self.Q.train()})                       
        print json.dumps({'iteration': it, 'train': self.Q.train()})       
#        self.evaluate()

    def iterate(self, state, action):
        " Do a single iteration from pair to pair."

        # Take the greedy action.
        next_state, reward = state.next_state(action)

        # Second action.
        next_action, max_reward = self.select_action(next_state)

        # compute the correction.
        delta = reward + self.Gamma *((1 - self.Sigma) * max_reward + self.Sigma * self.Q[(next_state, next_action)]) - self.Q[(state, action)]

        # Update eligibility.
        self.e[(state, action)] += 1

        # # Update the Q and e.
        for s, a in self.e.data.keys():
             if self.e[(s, a)] < (self.Gamma * self.Lambda) ** 20:
                 self.e.data.pop((s, a))
             else:
                 self.Q[(s, a)] += self.e[(s, a)] * delta * self.Lambda * self.Alpha
                 self.e[(s, a)] *= self.Gamma * self.Lambda
             
        # Return the next state and actions.
        return next_state, next_action


if __name__ == '__main__':

    
    parser = argparse.ArgumentParser(description='Combine Sarsa with Neural Networks.')
    parser.add_argument('--size', type=int, dest="size", help='Size of the barn.', default=10)
    parser.add_argument('--cache-size', type=int, dest="cache_size", help='Size of the cache.', default=1000)
    parser.add_argument('--hidden-size', type=int, dest="hidden_size", help='Size of the hidden layer of neurons.', default=25)
    parser.add_argument('--epsilon', type=float, dest="Epsilon", help="Epsilo value, close to one is complete random, 0 is greedy", default=0.6)
    parser.add_argument('--alpha', type=float, dest="Alpha", help="Step paramenter, 1 is fast close to zero is slow but secure.", default=0.1)
    parser.add_argument('--gamma', type=float, dest="Gamma", help="0 is no memory, 1 is funes.", default=0.2)    
    parser.add_argument('--lambda', type=float, dest="Lambda", help="Control the eligibility traces.", default=0.2)    
    parser.add_argument('--iter-step', type=int, dest="iter_step", help="Evaluate and print each number of steps.", default=100)    
    parser.add_argument('--iter-total', type=int, dest="iter_step", help="Stop at this steps", default=50000)    
    args = parser.parse_args()

    # Intial state.
    from state import BarnState
    initial_state = BarnState.initial_state(args.size)

    # Print to stdout.
    print json.dumps(vars(args))
    print json.dumps({"initial": {"food": initial_state.food, "position": initial_state.position}})

    # Create a single sarsa.
    sarsa = QSarsa(initial_state, cache_size=args.cache_size, hidden_size=args.hidden_size, Epsilon=args.Epsilon, Alpha=args.Alpha,
                   Gamma=args.Gamma, Lambda=args.Lambda, Sigma=1)
    for i in range(100000):
        sarsa.run(i)
        if i % args.iter_step == 0:
            reward, history = sarsa.evaluate()
            # print reward_total, [(s.position, len(s.food)) for s in history]
            print json.dumps({"iteration": i, "eval": {"reward": reward, "history": [(s.position, len(s.food)) for s in history]}})
<file_sep>import time
from sarsa import State, Sarsa
from itertools import izip_longest
from random import randint
from math import log10
import pylab
import sys
import numpy


class BarnState(State):
    """
    State in the Barn
    =================

    An state in the barn is defined by the position of the rat and the food still in the barn.

    :position: must be a 2-tuple of x,y coord.
    :food: a list of 2-tuples with the coord of the food.

    """

    def __init__(self, position, food, max_size):
        self.position = position
        self.food = food

        self.max_size = max_size

    def __hash__(self):
        h = "%d:" % self.max_size
        h += "%d:%d:" % self.position
        h += ":".join("%d:%d" % f for f in self.food)
        return  hash(h)

    def __eq__(self, other):            
        return (self.position == other.position) and (self.food == other.food) and (self.max_size == other.max_size)

    def next_state(self, action):

        if action == 'right':
            next_position = ((self.position[0] + 1) % self.max_size, self.position[1])

        elif action == 'left':
            next_position = ((self.position[0] - 1) % self.max_size, self.position[1])

        elif action == 'up':
            next_position = (self.position[0], (self.position[1] + 1) % self.max_size)

        elif action == 'down':
            next_position = (self.position[0], (self.position[1] - 1) % self.max_size)

        next_food = [f for f in self.food if f != next_position]
        reward = -1 if (len(next_food) == len(self.food)) else 1

        return BarnState(next_position,  next_food, self.max_size), reward
            
    def is_terminal(self):
        return (self.food == []) and (self.position == (self.max_size-1, self.max_size-1))

    def actions(self):
        actions = ["up", "down", "left", "right"]

        if self.position[0] == 0:
            actions.pop(actions.index("left"))
        if self.position[1] == 0:
            actions.pop(actions.index("down"))
        if self.position[0] == self.max_size - 1:
            actions.pop(actions.index("right"))
        if self.position[1] == self.max_size - 1:
            actions.pop(actions.index("up"))

        return actions

    


def plot_evaluation(history, title, max_size, food, filename):
    " Plot an evaluation. "

    pylab.clf()
    pylab.xlim(-2, max_size + 1)
    pylab.ylim(-2, max_size + 1)
    pylab.axis('off')

    # Start.
    pylab.title(title)
    pylab.annotate('start', xy=(0, 0), xytext=(-1, -1), size=10, bbox=dict(boxstyle="round4,pad=.5", fc="0.8"), arrowprops=dict(arrowstyle="->"))
    pylab.annotate('stop', xy=(max_size-1, max_size-1), xytext=(max_size, max_size), size=10, bbox=dict(boxstyle="round4,pad=.5", fc="0.8"), arrowprops=dict(arrowstyle="->"))

    # Show the food.
    for f in food:
        pylab.annotate('food', xy=f, size=5, bbox=dict(boxstyle="round4,pad=.5", fc="0.8"), ha='center')

    # Create the x and y locations.
    x = [s.position[0] for s in history]
    y = [s.position[1] for s in history]    
    pylab.plot(x, y)

    # Save the figure
    pylab.savefig(filename)


if __name__ == "__main__":

    # We want 5 scenarios.
    number_of_scenarios = 5

    # Fixed size.
    max_size = 10

    # Global parameters.
    epsilon = 0.1
    alpha = 0.1
    gamma = 0.2

    # Number of iterations.
    max_iters = 20000

    for n in range(1, number_of_scenarios + 1):

        # Randomly locate the food on the barn.
        amount_food = randint(max_size / 2, 2 * max_size)
        food = []

        while len(food) < amount_food:

            # Add a new piece of food.
            food.append((randint(0, max_size-1), randint(0, max_size-1)))

            # Ensure uniqueness.
            food = list(set(food))

        # Start the algorithm.
        sarsa = Sarsa(BarnState((0,0), food, max_size), epsilon=epsilon, alpha=alpha, gamma=gamma)
        sarsa.seed(int(100 * time.time()))

        # keep track of how much do we move the q.
        track = []

        for it in range(1, max_iters + 1):

            if it % 10 == 0:
                print "Scenario %d: %d/%d\r" % (n, it, max_iters) ,
                sys.stdout.flush()

            history, corrections = sarsa.iterate()
            track.append(numpy.sqrt(sum(map(lambda x: x*x, corrections))))
            
            # We're just selecting nice places to evaluate the current policy and create a picture.
            if (it % 10 ** int(log10(it)) == 0) and (it / 10 ** int(log10(it)) in [1, 2, 4, 8]):
                print " evaluationg current policy at %d ..." % it                    
                history, reward = sarsa.eval(max_size ** 2)
            
                # Plot this.
                plot_evaluation(history, "Scenario %d at iteration %d with reward %d" % (n, it, reward), max_size, food, "scenario-%d-iteration-%d.png" % (n, it))

        pylab.clf()
        pylab.plot(track)
        pylab.savefig("scenario-%d-learning.png" % (n, ))
                
            
<file_sep>import sys
import numpy
import numpy.random
import random
from UserDict import UserDict
from multiprocessing import Process
from multiprocessing import Manager
import time
from state import BarnState
import matplotlib
matplotlib.use('Agg')
import pylab



class StateActionValues(UserDict):
    def __getitem__(self, key):
        if key not in self.data:
            self.data[key] = 0
        return self.data[key]    

    def update(self, data):
        return self.data.update(data)

class SarsaBase(object):

    def greedy_action(self, state, Epsilon=None):
        " Compute the E-greedy action. "

        # Get the current epsilon or the stored one (to control the ??greedyness??)
        Epsilon = Epsilon or self.Epsilon 

        # List of tuples (action, value)
        actions = [(a, self.Q[(state, a)]) for a in state.actions]
        actions.sort(key=lambda x: -x[1])

        # Check if we're greed in this case.
        s = numpy.random.random()
        if s <= 1 - Epsilon:
            return actions[0][0]

        # Choose one between the rest.
        s -= 1 - Epsilon
        s *= (len(actions) - 1) / Epsilon
        return actions[1 + int(s)][0]



class SarsaAgent(Process, SarsaBase):
    " All the sarsa agents are processes."

    def __init__(self, part, inbox, outbox, max_it=500, Epsilon=0.8, Alpha=0.1, Gamma=0.8):
        Process.__init__(self)

        # Save the parameters.
        self.Epsilon = Epsilon
        self.Alpha = Alpha
        self.Gamma = Gamma

        # Keep running flag.
        self.keep_running = True

        # Inbox to receive the jobs.
        self.inbox = inbox

        # Outbox.
        self.outbox = outbox

        # Save the own part.
        self.part = part

        # State value.
        self.Q = StateActionValues()

        # Maximum amount of iteration per time.
        self.max_it = max_it


        self.running_time = 0

    def iterate(self, state, action):

        # Take the greedy action.
        next_state, reward = state.next_state(action)

        # Second action.
        next_action = self.greedy_action(next_state)

        # Next Q(state, action).
        next_q = self.Q[(next_state, next_action)]

        # If the next state is in another part we use an estimate for the reward.
        if next_state.part != self.part:
            reward += next_q

        # Update Q(first_state, first_action)
        correction = reward + self.Gamma * next_q - self.Q[(state, action)]
        self.Q[(state, action)] += self.Alpha * correction

        return next_state, next_action

    def handle_control(self, control):

        if control == 'stop':
            self.keep_running = False

        if 'seed' in control:
            numpy.random.seed(control['seed'])
            
    def handle_problem(self, problem):
        " Handle the problem. "

        # print("Problem received for part: %d %s" % (self.part, problem))

        # Get the fringe data.
        self.Q.update(problem['Q'])

        it = 0

        start = time.clock()

        jobs = []

        while it < self.max_it:

            # Get the state-action.
            state = problem['state']
            action = problem['action']
            
            while state.part == self.part and not state.is_terminal:

                # Iterate
                state, action = self.iterate(state, action)

                it += 1

            if not state.is_terminal:
                # Send a new job.
                jobs.append((state.part, state, action))
            else:            
                # Send a done message.
                self.outbox.put({'done': state})

        # Send the jobs.        
        self.send_jobs(jobs)

        # Save the running time.
        self.running_time += time.clock() - start

    def send_jobs(self, jobs):
     
        fringe = {}

        for s, a in self.Q.data:

            if s.part != self.part:
                continue

            for sn in s.neighbors():
                if sn.part != self.part:
                    if sn.part not in fringe:
                        fringe[sn.part] = {}
                    fringe[sn.part][(s, a)] = self.Q[(s, a)]

        # Own Q.
        own_Q = dict(((s, a), self.Q[(s, a)]) for s, a in self.Q.data if s.part == self.part)

        msg = {
            'problem': {
                'jobs': jobs,
                'fringe': fringe,
                'Q': own_Q
                }
            }

        # Send a new job.
        print "Running Time %d: %f" % (self.part, self.running_time)
        self.outbox.put(msg)
            
    def run(self):

        print("Start agent for part: %d" % self.part)

        # Start requesting a problem.
        self.outbox.put({'request': {'part': self.part}})

        while self.keep_running:

            # Get a job to process.
            job = self.inbox.get()
                    
            if 'control' in job:
                self.handle_control(job['control'])
                continue

            if 'problem' in job:
                self.handle_problem(job['problem'])
                self.outbox.put({'request': {'part': self.part}})


class Sarsa(SarsaBase):
    
    def __init__(self, initial_state, Epsilon=0.7, Alpha=0.2, Gamma=0.5, prefix=None):

        # Save the parameters.
        self.Epsilon = Epsilon
        self.Alpha = Alpha
        self.Gamma = Gamma

        # Save the initial state.
        self.initial_state = initial_state

        # Save the parts.
        self.parts = self.initial_state.parts

        manager = Manager()

        # Create the inbox.
        self.inbox = manager.Queue()

        # Create the boxes.
        self.outboxes = dict((p, manager.Queue()) for p in self.parts)

        # Create the agents.
        self.agents = dict((p, SarsaAgent(p, self.outboxes[p], self.inbox, Epsilon=Epsilon, Gamma=Gamma, Alpha=Alpha)) for p in self.parts)

        # Keep running flag.
        self.keep_running = True

        # Keep track of who is requesting problems.
        self.requests = []        

        # Current jobs.
        self.jobs = dict((p, []) for p in self.parts)

        # State-Action values in the boundaries.
        self.fringe_Q = dict((p, {}) for p in self.parts)

        # Own state-action for evaluation.
        self.Q = StateActionValues()

        # Save prefix for created files.
        self.prefix = prefix or str(int(time.time()))

    def seed_all(self):
        for outbox in self.outboxes.values():
            outbox.put({'control': {'seed': int(time.time())}})

    def handle_problem(self, problem):

        # Save the fringe data.
        for p in problem['fringe']:
            self.fringe_Q[p].update(problem['fringe'][p])

        # Update the local copy of Q.
        self.Q.update(problem['Q'])

        # Save jobs.
        for job in problem['jobs']:
            part, state, action = job
            self.jobs[part].append({'state': state, 'action': action})

            # In case there is someone waiting for this job send it immediately.
            if part in self.requests:
                self.send_job(part)
                        
    def send_job(self, part):

        if part in self.requests:
            self.requests.pop(self.requests.index(part))
        
        # Select a job randomly. Choose between the last 10
        job = random.choice(self.jobs[part][-10:])

        # print("Send job to %d" % part)
        self.outboxes[part].put({
            'problem': {
                'action': job['action'],
                'state': job['state'],
                'Q': self.fringe_Q[part]
                }
            })    

    def handle_request(self, request):

        part = request['part']

        if len(self.jobs[part]) > 0:
            self.send_job(part)
        else:
            self.requests.append(part)

    def add_initial_job(self):
        self.jobs[self.initial_state.part].append({'state': self.initial_state, 'action': random.choice(self.initial_state.actions)})

    def run(self):

        start = time.clock()

        # Start all the agents.
        for agent in self.agents.values():
            agent.start()

        # Add an initial_state problem.
        self.add_initial_job()

        # Count the done.
        done_counter = 0

        while self.keep_running:

            # Get a message.
            msg = self.inbox.get()

            if 'request' in msg:                
                self.handle_request(msg['request'])

            if 'problem' in msg:
                self.handle_problem(msg['problem'])

            if 'done' in msg:
                
                done_counter += 1

                self.add_initial_job()

                print done_counter
                if done_counter % 10 == 0:
                    self.eval(done_counter)

    def greedy_action(self, state):
        " Compute the E-greedy action. "

        # List of tuples (action, value)
        actions = [(a, self.Q[(state, a)]) for a in state.actions]
        actions.sort(key=lambda x: -x[1])
        return actions[0][0]

    def eval(self, counter, max_it=100):
        " Do an evaluation with the current values."

        #     print "(%d, %d) %s %2.1f" % (k[0].position[0], k[0].position[1], k[1], v)
        # print ""

        state = self.initial_state
        it = 0
        
        history = [state]
        reward_total = 0

        while not state.is_terminal and it < self.initial_state.size ** 2:
            action = self.greedy_action(state)
            state, reward = state.next_state(action)
            reward_total += reward
            history.append(state)
            it += 1

        print reward_total, [s.position for s in history]
            
        pylab.clf()
        pylab.xlim(-2, self.initial_state.size + 1)
        pylab.ylim(-2, self.initial_state.size + 1)
        pylab.axis('off')

        # Start.
        pylab.title("Iteration: %d (Size %d with reward %d)" % (counter, self.initial_state.size, reward_total))
        pylab.annotate('start', xy=(0, 0), xytext=(-1, -1), size=10, bbox=dict(boxstyle="round4,pad=.5", fc="0.8"), arrowprops=dict(arrowstyle="->"))
        pylab.annotate('stop', xy=(self.initial_state.size-1, self.initial_state.size-1), xytext=(self.initial_state.size, self.initial_state.size), size=10, bbox=dict(boxstyle="round4,pad=.5", fc="0.8"), arrowprops=dict(arrowstyle="->"))

        # Show the food.
        for f in self.initial_state.food:
            pylab.annotate('food', xy=f, size=5, bbox=dict(boxstyle="round4,pad=.5", fc="0.8"), ha='center')

        # Create the x and y locations.
        x = [s.position[0] for s in history]
        y = [s.position[1] for s in history]    
        pylab.plot(x, y)

        # Save the figure        
        pylab.savefig("%s-%d.png" % (self.prefix, counter))
    
        

if __name__ == '__main__':

    # Size.
    size = int(sys.argv[1])
    prefix = sys.argv[2]

    # Intial state.
    initial_state = BarnState.initial_state(size)

    # Create a single sarsa.
    sarsa = Sarsa(initial_state, Epsilon=0.6, Alpha=0.1, Gamma=0.8, prefix=prefix)

    # Seed all the agents.
    sarsa.seed_all()

    sarsa.run()
