How to manipulate complex data structures made of lists?

I am trying to represent a 3D Connect 4 board game:

For example, I have the following list of lists structure:

(
(
(NIL NIL NIL NIL)
(NIL NIL NIL NIL)
(NIL NIL NIL NIL)
(NIL NIL NIL NIL)
)
(1 1 1 1 1 1 1 1 1 1 1 1 10 10 10 10 10 10 10 10 10 10 10 10)
)

Each NIL represents a position in it. For example, if I put two pieces (one black and another white) in the first position it would look like this:

(
(
((B W) NIL NIL NIL)
(NIL NIL NIL NIL)
(NIL NIL NIL NIL)
(NIL NIL NIL NIL)
)
(1 1 1 1 1 1 1 1 1 1 1 1 10 10 10 10 10 10 10 10 10 10 10 10)
)

Which means W would be the one on the bottom. I would also need to compare them to each other in order for the program to say when a winner has been found.

How can add pieces in each position? And how would I compare them since they are lists with the NIL value?

Whatever the implementation you choose to use, it is best to define an interface to manipulate your objects. Here below, I define make-board, push-token and pop-token functions. There are other accessor functions you could define, such taking the value at coordinate (x y z).

Then, you only manipulate your data through this interface so that your code is readable and easy to maintain. I am using a 2D matrix of vectors, where the inner vectors are used as stacks thanks to their fill-pointers (see MAKE-ARRAY for details).

Board class and token type

(defclass board ()
  ((matrix :reader board-matrix :initarg :matrix)
   (size :reader board-size :initarg :size)))

(deftype token-type () '(member white black))

Constructor

(defun make-board (size)
  (let ((board
         (make-array (list size size))))
    (dotimes (i (array-total-size board))
      (setf (row-major-aref board i)
            (make-array size
                        :element-type 'symbol
                        :fill-pointer 0)))
    (make-instance 'board :matrix board :size size)))

Custom printer

(defmethod print-object ((b board) stream)
  (print-unreadable-object (b stream :type t)
    (let ((matrix (board-matrix b))
          (size (board-size b)))
      (dotimes (row size)
        (fresh-line)
        (dotimes (col size)
          (let* ((stack (aref matrix row col)))
            (dotimes (z size)
              (princ (case (aref stack z)
                       (white #\w)
                       (black #\b)
                       (t #\.))
                     stream)))
          (princ #\space stream))))))

Push at (x,y)

(defun push-token (board x y token)
  (check-type token token-type)
  (vector-push token (aref (board-matrix board) y x)))

Pop from (x,y)

(defun pop-token (board x y)
  (ignore-errors
    (let ((stack (aref (board-matrix board) y x)))
      (prog1 (vector-pop stack)
        ;; we reset the previous top-most place to NIL because we
        ;; want to allow the access of any cell in the 3D
        ;; board. The fill-pointer is just here to track the
        ;; position of the highest token.
        (setf (aref stack (fill-pointer stack)) nil)))))

Test

(let ((board (make-board 4)))
  (flet ((@ (&rest args) (print board)))
    (print board)
    (@ (push-token board 1 2 'white))
    (@ (push-token board 1 2 'black))
    (@ (push-token board 1 2 'white))
    (@ (push-token board 1 2 'black))
    (@ (push-token board 1 2 'black))
    (@ (push-token board 0 3 'white))
    (@ (pop-token board 1 2))
    (@ (pop-token board 1 2))))

Output

#<BOARD 
.... .... .... .... 
.... .... .... .... 
.... .... .... .... 
.... .... .... .... > 
#<BOARD 
.... .... .... .... 
.... .... .... .... 
.... w... .... .... 
.... .... .... .... > 
#<BOARD 
.... .... .... .... 
.... .... .... .... 
.... wb.. .... .... 
.... .... .... .... > 
#<BOARD 
.... .... .... .... 
.... .... .... .... 
.... wbw. .... .... 
.... .... .... .... > 
#<BOARD 
.... .... .... .... 
.... .... .... .... 
.... wbwb .... .... 
.... .... .... .... > 
#<BOARD 
.... .... .... .... 
.... .... .... .... 
.... wbwb .... .... 
.... .... .... .... > 
#<BOARD 
.... .... .... .... 
.... .... .... .... 
.... wbwb .... .... 
w... .... .... .... > 
#<BOARD 
.... .... .... .... 
.... .... .... .... 
.... wbw. .... .... 
w... .... .... .... > 
#<BOARD 
.... .... .... .... 
.... .... .... .... 
.... wb.. .... .... 
w... .... .... .... >