Removes obsolete Fig dictionary and modifies the codebase accordingly (aimacode#208)

SnShine · norvig · commit 64fa05b1868c · 2016-04-10T00:21:22.000-07:00
* removes obsolete Fig dictionary from utils.py

* modified rl notebook according to the new Figure conventions

* removes 'import Fig' and changed the names of Figures

* fixes a small error (by me) in executing the cells in rl notebook
diff --git a/learning.py b/learning.py
@@ -3,7 +3,7 @@
 from utils import (
     removeall, unique, product, argmax, argmax_random_tie, mean, isclose,
     dotproduct, vector_add, scalar_vector_product, weighted_sample_with_replacement,
-    weighted_sampler, num_or_str, normalize, clip, sigmoid, print_table, DataFile, Fig
+    weighted_sampler, num_or_str, normalize, clip, sigmoid, print_table, DataFile
 )
 
 import copy
@@ -886,7 +886,11 @@ def T(attrname, branches):
                     for value, child in list(branches.items()))
     return DecisionFork(restaurant.attrnum(attrname), attrname, branches)
 
-Fig[18, 2] = T('Patrons',
+""" [Figure 18.2]
+A decision tree for deciding whether to wait for a table at a hotel.
+"""
+
+waiting_decision_tree = T('Patrons',
                {'None': 'No', 'Some': 'Yes', 'Full':
                 T('WaitEstimate',
                   {'>60': 'No', '0-10': 'Yes',
@@ -910,7 +914,7 @@ def SyntheticRestaurant(n=20):
     "Generate a DataSet with n examples."
     def gen():
         example = list(map(random.choice, restaurant.values))
-        example[restaurant.target] = Fig[18, 2](example)
+        example[restaurant.target] = waiting_decision_tree(example)
         return example
     return RestaurantDataSet([gen() for i in range(n)])
 
diff --git a/logic.py b/logic.py
@@ -33,7 +33,7 @@
 
 from utils import (
     removeall, unique, first, every, argmax, probability, num_or_str,
-    isnumber, issequence, Symbol, Expr, expr, subexpressions, implies, Fig
+    isnumber, issequence, Symbol, Expr, expr, subexpressions, implies
 )
 import agents
 
@@ -499,7 +499,7 @@ def clauses_with_premise(self, p):
 def pl_fc_entails(KB, q):
     """Use forward chaining to see if a PropDefiniteKB entails symbol q.
     [Fig. 7.15]
-    >>> pl_fc_entails(Fig[7,15], expr('Q'))
+    >>> pl_fc_entails(horn_clauses_KB, expr('Q'))
     True
     """
     count = dict([(c, len(conjuncts(c.args[0]))) for c in KB.clauses
@@ -518,13 +518,18 @@ def pl_fc_entails(KB, q):
                     agenda.append(c.args[1])
     return False
 
-# Wumpus World example [Fig. 7.13]
-Fig[7, 13] = expr("(B11 <=> (P12 | P21))  &  ~B11")
+""" [Figure 7.13]
+Simple inference in a wumpus world example
+"""
+wumpus_world_inference = expr("(B11 <=> (P12 | P21))  &  ~B11")
+
 
-# Propositional Logic Forward Chaining example [Fig. 7.16]
-Fig[7, 15] = PropDefiniteKB()
+""" [Figure 7.16]
+Propositional Logic Forward Chaining example
+"""
+horn_clauses_KB = PropDefiniteKB()
 for s in "P==>Q; (L&M)==>P; (B&L)==>M; (A&P)==>L; (A&B)==>L; A;B".split(';'):
-    Fig[7, 15].tell(expr(s))
+    horn_clauses_KB.tell(expr(s))
 
 # ______________________________________________________________________________
 # DPLL-Satisfiable [Fig. 7.17]
@@ -690,7 +695,7 @@ def SAT_plan(init, transition, goal, t_max, SAT_solver=dpll_satisfiable):
     def translate_to_SAT(init, transition, goal, time):
         clauses = []
         states = [state for state in transition]
-        
+
         #Symbol claiming state s at time t
         state_counter = itertools.count()
         for s in states:
diff --git a/mdp.py b/mdp.py
@@ -6,7 +6,7 @@
 dictionary of {state:number} pairs.  We then define the value_iteration
 and policy_iteration algorithms."""
 
-from utils import argmax, vector_add, print_table, Fig
+from utils import argmax, vector_add, print_table
 from grid import orientations, turn_right, turn_left
 
 import random
@@ -97,8 +97,10 @@ def to_arrows(self, policy):
                 dict([(s, chars[a]) for (s, a) in list(policy.items())]))
 
 # ______________________________________________________________________________
-
-Fig[17, 1] = GridMDP([[-0.04, -0.04, -0.04, +1],
+""" [Figure 17.1]
+A 4x3 grid environment that presents the agent with a sequential decision problem.
+"""
+sequential_decision_environment = GridMDP([[-0.04, -0.04, -0.04, +1],
                       [-0.04, None,  -0.04, -1],
                       [-0.04, -0.04, -0.04, -0.04]],
                      terminals=[(3, 2), (3, 1)])
@@ -163,17 +165,17 @@ def policy_evaluation(pi, U, mdp, k=20):
     return U
 
 __doc__ += """
->>> pi = best_policy(Fig[17,1], value_iteration(Fig[17,1], .01))
+>>> pi = best_policy(sequential_decision_environment, value_iteration(sequential_decision_environment, .01))
 
->>> Fig[17,1].to_arrows(pi)
+>>> sequential_decision_environment.to_arrows(pi)
 [['>', '>', '>', '.'], ['^', None, '^', '.'], ['^', '>', '^', '<']]
 
->>> print_table(Fig[17,1].to_arrows(pi))
+>>> print_table(sequential_decision_environment.to_arrows(pi))
 >   >      >   .
 ^   None   ^   .
 ^   >      ^   <
 
->>> print_table(Fig[17,1].to_arrows(policy_iteration(Fig[17,1])))
+>>> print_table(sequential_decision_environment.to_arrows(policy_iteration(sequential_decision_environment)))
 >   >      >   .
 ^   None   ^   .
 ^   >      ^   <
diff --git a/rl.ipynb b/rl.ipynb
diff --git a/search.py b/search.py
@@ -700,7 +700,7 @@ def distance_to_node(n):
                 g.connect(node, neighbor, int(d))
     return g
 
-""" [Fig. 3.2]
+""" [Figure 3.2]
 Simplified road map of Romania
 """
 romania_map = UndirectedGraph(dict(
@@ -726,7 +726,7 @@ def distance_to_node(n):
     Sibiu=(207, 457), Timisoara=(94, 410), Urziceni=(456, 350),
     Vaslui=(509, 444), Zerind=(108, 531))
 
-""" [Fig. 4.9]
+""" [Figure 4.9]
 Eight possible states of the vacumm world
 Each state is represented as
    *       "State of the left room"      "State of the right room"   "Room in which the agent is present"
@@ -750,9 +750,8 @@ def distance_to_node(n):
     State_8 = dict(Suck = ['State_8', 'State_6'], Left = ['State_7'])
     ))
 
-""" [Fig. 4.23]
+""" [Figure 4.23]
 One-dimensional state space Graph
-
 """
 one_dim_state_space = Graph(dict(
     State_1 = dict(Right = 'State_2'),
@@ -770,7 +769,9 @@ def distance_to_node(n):
     State_5 = 4,
     State_6 = 3)
 
-# Principal states and territories of Australia
+""" [Figure 6.1]
+Principal states and territories of Australia
+"""
 australia_map = UndirectedGraph(dict(
     T=dict(),
     SA=dict(WA=1, NT=1, Q=1, NSW=1, V=1),
diff --git a/tests/test_logic.py b/tests/test_logic.py
@@ -1,6 +1,6 @@
 import pytest
 from logic import *
-from utils import InfixOp, expr_handle_infix_ops, Fig, count, implies, equiv
+from utils import InfixOp, expr_handle_infix_ops, count, implies, equiv
 
 
 def test_expr():
@@ -109,15 +109,15 @@ def test_dpll():
             == {B: False, C: True, A: True, F: False, D: True, E: False})
     assert dpll_satisfiable(A&~B) == {A: True, B: False}
     assert dpll_satisfiable(P&~P) == False
-    
+
 
 def test_unify():
     assert unify(x, x, {}) == {}
     assert unify(x, 3, {}) == {x: 3}
 
 def test_pl_fc_entails():
-    assert pl_fc_entails(Fig[7,15], expr('Q'))
-    assert not pl_fc_entails(Fig[7,15], expr('SomethingSilly'))
+    assert pl_fc_entails(horn_clauses_KB, expr('Q'))
+    assert not pl_fc_entails(horn_clauses_KB, expr('SomethingSilly'))
 
 def test_tt_entails():
     assert tt_entails(P & Q, Q)
@@ -146,7 +146,7 @@ def test_move_not_inwards():
     assert repr(move_not_inwards(~(~(A | ~B) | ~~C))) == '((A | ~B) & ~C)'
 
 def test_to_cnf():
-    assert (repr(to_cnf(Fig[7, 13] & ~expr('~P12'))) == 
+    assert (repr(to_cnf(wumpus_world_inference & ~expr('~P12'))) ==
             "((~P12 | B11) & (~P21 | B11) & (P12 | P21 | ~B11) & ~B11 & P12)")
     assert repr(to_cnf((P&Q) | (~P & ~Q))) == '((~P | P) & (~Q | P) & (~P | Q) & (~Q | Q))'
     assert repr(to_cnf("B <=> (P1 | P2)")) == '((~P1 | B) & (~P2 | B) & (P1 | P2 | ~B))'
@@ -203,7 +203,7 @@ def test_SAT_plan():
     transition = {(0, 0):{'Right': (0, 1), 'Down': (1, 0)},
                   (0, 1):{'Left': (1, 0), 'Down': (1, 1)},
                   (1, 0):{'Right': (1, 0), 'Up': (1, 0), 'Left': (1, 0), 'Down': (1, 0)},
-                  (1, 1):{'Left': (1, 0), 'Up': (0, 1)}} 
+                  (1, 1):{'Left': (1, 0), 'Up': (0, 1)}}
     assert SAT_plan((0, 0), transition, (1, 1), 4) == ['Right', 'Down']
 
 
diff --git a/tests/test_mdp.py b/tests/test_mdp.py
@@ -2,7 +2,7 @@
 from mdp import *  # noqa
 
 def test_value_iteration():
-    assert value_iteration(Fig[17, 1], .01) == {(3, 2): 1.0, (3, 1): -1.0,
+    assert value_iteration(sequential_decision_environment, .01) == {(3, 2): 1.0, (3, 1): -1.0,
                                         (3, 0): 0.12958868267972745, (0, 1): 0.39810203830605462,
                                         (0, 2): 0.50928545646220924, (1, 0): 0.25348746162470537,
                                         (0, 0): 0.29543540628363629, (1, 2): 0.64958064617168676,
@@ -11,14 +11,14 @@ def test_value_iteration():
 
 
 def test_policy_iteration():
-    assert policy_iteration(Fig[17, 1]) == {(0, 0): (0, 1),  (0, 1): (0, 1), (0, 2): (1, 0),
+    assert policy_iteration(sequential_decision_environment) == {(0, 0): (0, 1),  (0, 1): (0, 1), (0, 2): (1, 0),
                                             (1, 0): (1, 0),                  (1, 2): (1, 0),
                                             (2, 0): (0, 1),  (2, 1): (0, 1), (2, 2): (1, 0),
                                             (3, 0): (-1, 0), (3, 1): None,   (3, 2): None}
 
 
 def test_best_policy():
-    pi = best_policy(Fig[17, 1], value_iteration(Fig[17, 1], .01))
-    assert Fig[17, 1].to_arrows(pi) == [['>', '>', '>', '.'], 
+    pi = best_policy(sequential_decision_environment, value_iteration(sequential_decision_environment, .01))
+    assert sequential_decision_environment.to_arrows(pi) == [['>', '>', '>', '.'],
                                         ['^', None, '^', '.'],
                                         ['^', '>', '^', '<']]
diff --git a/utils.py b/utils.py
@@ -81,7 +81,7 @@ def shuffled(iterable):
     "Randomly shuffle a copy of iterable."
     items = list(iterable)
     random.shuffle(items)
-    return items    
+    return items
 
 
 
@@ -345,16 +345,16 @@ def unimplemented():
 # See https://docs.python.org/3/reference/expressions.html#operator-precedence
 # See https://docs.python.org/3/reference/datamodel.html#special-method-names
 
-class Expr(object): 
+class Expr(object):
     """A mathematical expression with an operator and 0 or more arguments.
     op is a str like '+' or 'sin'; args are Expressions.
     Expr('x') or Symbol('x') creates a symbol (a nullary Expr).
     Expr('-', x) creates a unary; Expr('+', x, 1) creates a binary."""
-    
-    def __init__(self, op, *args): 
+
+    def __init__(self, op, *args):
         self.op = str(op)
         self.args = args
-        
+
     # Operator overloads
     def __neg__(self):      return Expr('-', self)
     def __pos__(self):      return Expr('+', self)
@@ -374,10 +374,10 @@ def __matmul__(self, rhs):   return Expr('@',  self, rhs)
 
     def __or__(self, rhs):
         if isinstance(rhs, Expression) :
-            return Expr('|',  self, rhs) 
+            return Expr('|',  self, rhs)
         else:
             return NotImplemented # So that InfixOp can handle it
-    
+
     # Reverse operator overloads
     def __radd__(self, lhs): return Expr('+',  lhs, self)
     def __rsub__(self, lhs): return Expr('-',  lhs, self)
@@ -393,20 +393,20 @@ def __rlshift__(self, lhs):   return Expr('<<',  lhs, self)
     def __rtruediv__(self, lhs):  return Expr('/',  lhs, self)
     def __rfloordiv__(self, lhs): return Expr('//',  lhs, self)
     def __rmatmul__(self, lhs):   return Expr('@', lhs, self)
-    
-    def __call__(self, *args): 
+
+    def __call__(self, *args):
         "Call: if 'f' is a Symbol, then f(0) == Expr('f', 0)."
         return Expr(self.op, *args)
 
     # Equality and repr
-    def __eq__(self, other):   
+    def __eq__(self, other):
         "'x == y' evaluates to True or False; does not build an Expr."
-        return (isinstance(other, Expr) 
-                and self.op == other.op 
+        return (isinstance(other, Expr)
+                and self.op == other.op
                 and self.args == other.args)
-    
+
     def __hash__(self): return hash(self.op) ^ hash(self.args)
-    
+
     def __repr__(self):
         op   = self.op
         args = [str(arg) for arg in self.args]
@@ -450,7 +450,7 @@ def arity(expression):
 
 class InfixOp:
     """Allow 'P |implies| Q, where P, Q are Exprs and implies is an InfixOp."""
-    def __init__(self, op, lhs=None): self.op, self.lhs = op, lhs      
+    def __init__(self, op, lhs=None): self.op, self.lhs = op, lhs
     def __call__(self, lhs, rhs):     return Expr(self.op, lhs, rhs)
     def __or__(self, rhs):            return Expr(self.op, self.lhs, rhs)
     def __ror__(self, lhs):           return InfixOp(self.op, lhs)
@@ -489,7 +489,7 @@ class defaultkeydict(collections.defaultdict):
     def __missing__(self, key):
         self[key] = result = self.default_factory(key)
         return result
-            
+
 
 # ______________________________________________________________________________
 # Queues: Stack, FIFOQueue, PriorityQueue
@@ -591,9 +591,3 @@ def __delitem__(self, key):
         for i, (value, item) in enumerate(self.A):
             if item == key:
                 self.A.pop(i)
-
-# Fig: The idea is we can define things like Fig[3,10] = ...
-# TODO: However, this is deprecated, let's remove it,
-# and instead have a comment like # Figure 3.10
-
-Fig = {}
