#| 
External documentation and recommendations on the use of this code is
available at http://www.cs.umass.edu/~rich/tiles.html.

This is an implementation of grid-style tile codings, based originally on
the UNH CMAC code (see http://www.ece.unh.edu/robots/cmac.htm). 
Here we provide a function, "get-tiles", that maps real
variables to a list of tiles. This function is memoryless and requires no
setup. We assume that hashing colisions are to be ignored. There may be
duplicates in the list of tiles, but this is unlikely if memory-size is
large. 

The input variables will be gridded at unit intervals, so generalization
will be by approximately 1 in each direction, and any scaling will have 
to be done externally before calling tiles.

It is recommended by the UNH folks that num-tilings be a power of 2, e.g., 16. 
|#

(defparameter *MAX-NUM-VARS* 10)      ; maximum number of variables used in one grid
(defparameter *MAX-NUM-HASHES* 10)    ; maximum number of optional hashing arguments
;The following are temporary variables used by tiles.
(defvar qstate (make-array *MAX-NUM-VARS* :initial-element 0))
(defvar base (make-array *MAX-NUM-VARS* :initial-element 0))
(defvar coordinates (make-array (+ 1 *MAX-NUM-HASHES* *MAX-NUM-VARS*) :initial-element 0))

(defun get-tiles (variables num-tilings memory-size &rest hashes)
  "returns list of tiles corresponding to variables, hashed down to memory-size"
  (let* ((num-variables (length variables))
         (num-coordinates (+ 1 num-variables (length hashes))))
    (loop for hash in hashes
          for i from (+ 1 num-variables) 
          do (setf (aref coordinates i) hash))
    (loop for i from 0                   ; quantize state to integers
          for variable in variables do 
          (setf (aref base i) 0)
          (setf (aref qstate i) (floor (* variable num-tilings))))
    (loop for j below num-tilings 
          collect (progn
                    (loop for i below num-variables do 
                          (setf (aref coordinates i) 
                                (- (aref qstate i)
                                   (mod (- (aref qstate i) (aref base i))
                                        num-tilings)))
                          (incf (aref base i) (+ 1 (* 2 i))))
                    (setf (aref coordinates num-variables) j)
                    (hash-coordinates 
                     coordinates num-coordinates memory-size)))))

(defparameter random-table 
  (make-array 2048 :initial-contents (loop repeat 2048 collect (random 65536))))

(defun hash-coordinates (coordinates num-coordinates memory-size)
  "Returns tile in [0,memory-size) corresponding to first part of coordinates (an array)"
  (mod (loop for i below num-coordinates
             for coordinate = (aref coordinates i)
             sum (aref random-table (mod (+ coordinate (* 449 i)) 2048)))
       memory-size))

(defun load-tiles (tiles starting-element num-tilings variables memory-size &rest hashes)
  "returns list of tiles corresponding to variables, hashed down to memory-size"
  (let* ((num-variables (length variables))
         (num-coordinates (+ 1 num-variables (length hashes))))
    (loop for hash in hashes
          for i from (+ 1 num-variables) 
          do (setf (aref coordinates i) hash))
    (loop for i from 0                   ; quantize state to integers
          for variable in variables do 
          (setf (aref base i) 0)
          (setf (aref qstate i) (floor (* variable num-tilings))))
    (loop for j below num-tilings do 
          (loop for i below num-variables do 
                (setf (aref coordinates i) 
                      (- (aref qstate i)
                         (mod (- (aref qstate i) (aref base i))
                              num-tilings)))
                (incf (aref base i) (+ 1 (* 2 i))))
          (setf (aref coordinates num-variables) j)
          (setf (aref tiles (+ starting-element j))
                (hash-coordinates 
                 coordinates num-coordinates memory-size)))))