4.Práctica: Búsqueda ciega, heurística y en juegos con dos jugadores

  4.1 Objetivo de la práctica
El objetivo de esta práctica es adquirir experiencia en la utilización de estrategias de búsqueda y diferenciar sus características.

En esta práctica el alumno utilizará una serie de programas hechos en Common Lisp que implementan distintas estrategias de búsqueda. Tu trabajo consistirá básicamente en realizar experimentos y recopilar información relevante de la búsqueda relacionada con aspectos de eficiencia y optimalidad. Realizaremos dos tipos de búsquedas, primero búsquedas ciegas y heurísticas y posteriormente experimentaremos en juegos.

En esta práctica no se exige que el alumno entienda el funcionamiento de todo el código. Sin embargo, recomendamos que se eche un vistazo a los listados y se localicen por encima las funcionalidades principales (p.e. puntos del 1 al 7) y las estructuras de datos utilizadas.
 

  4.2 Comparación de estrategias de búsqueda ciegas y heurísticas
En esta parte el alumno establecerá una comparación entre varias estrategias de búsqueda ciegas y heurísticas utilizando para las pruebas el problema del 8-puzzle.

  4.2.1 Ficheros con las estrategias de búsqueda
 

Dichas estrategias están implementadas en tres ficheros:
(1) El fichero blind_search.lsp dispone de las funciones Breadth-first-search y depth-first-search para hacer búsquedas primero en anchura y primero en profundidad respectivamente. Dentro de la estrategia en profundidad estan también las funciones depth-first-search-with-duplicate-node-detection y depth-first-search-with-depth-limit.
Estas funciones asumen que se tienen definidos:
1. Un conjunto de operadores como funciones Lisp.
1. La función solution-state? que determina si un estado es la solución.
Todas las funciones de búsqueda tienen como parámetros el estado inicial y la lista de operadores.

Todas las funciones de búsqueda llevan también contabilidad de algunas informaciones de interés para las comparaciones objeto de la práctica. Estos resultados quedan al final de cada búsqueda en la estructura que se encuentra en *stats* (no se debe olvidar inicializar esta estructura al comienzo de cada búsqueda con reset-stats).
 

(defstruct search-statistics
  (nodes-visited 0)
  (maximum-length-of-node-list 0)
  (length-of-solution 0)
  (maximum-depth 0)
  (cost-of-solution 0))

(defparameter *stats* (make-search-statistics))

(defun reset-stats()
  (setq *stats* (make-search-statistics)))
 

Las funciones de búsqueda devuelven el nodo objetivo desde el que se puede acceder al resto de nodos que forman el camino de la solución. Las estadísticas de la búsqueda se encuentran en el parámetro *stats*.

(2) El fichero heuristic_search.lsp contiene las estratégias steepest-ascent-hill-climbing-search, best-first-tree-search y best-first-graph-search (es una búsqueda primero el mejor con chequeo de nodos duplicados).

Estas funciones asumen que se tienen definidos (además de las asumpciones anteriores):

1. Una función que evalúa el camino que queda para alcanzar el objetivo: estimated-distance-from-goal.
2. Una función que indica el coste de aplicar un operador cost-of-operator(Current-state, operator).
(3) El fichero a_star.lsp contiene la función a-star que implementa el algoritmo A*.
 
  4.2.2 Fichero con el problema del 8-puzzle
El fichero puzzle8.lsp contiene todas las estructuras de datos y funciones del problema del 8-puzzle necesarias para aplicar las estrategias anteriores.

1. - Repasa detenidamente este fichero y localiza la representación del estado, los operadores y el resto de funciones que serán de interés más adelante.

2. - Crea otra definición de la función estimated-distance-from-goal para que en lugar de utilizar la distancia Manhattan utilice la heurística de piezas fuera de lugar.
 

  4.2.3 Comparación experimental de las estrategias de búsqueda
 
Una de las tareas principales de esta práctica consiste en hacer una comparación experimental de las distintas estrategias de búsqueda aplicándolas al problema del 8-puzzle.
1. - Se pide realizar una serie de 20 experimentos del 8-puzzle partiendo de distintas posiciones iniciales y llegando a un estado del puzzle en el que están todos los números seguidos. Cada experimento consiste en encontrar la situación inicial y aplicar las funciones de búsqueda: Breadth-first-search (cuando sea posible), depth-first-search (cuando sea posible), depth-first-search-with-duplicate-node-detection, depth-first-search-with-depth-limit, steepest-ascent-hill-climbing-search, best-first-tree-search, best-first-graph-search y a-star (con la distancia Man búsquedas. El fichero que has de someter debe incluir de cada experimento el estado inicial y para cada una de las estratégias: el número de nodos visitados, la profundidad de la solución, el factor de ramificación efectivo y máxima longitud de la lista de nodos.
2. - Con los datos anteriores se mostrarán tres tablas con filas ordenadas por la profundidad de la solución y una columna por cada estrategia y contendrán: 1ª) N, el número de nodos visitados; 2ª) b*, el factor de ramificación efectivo y 3ª) la máxima longitud de la lista de nodos.

• Ejemplo de tabla:

• Para crear distintos estados iniciales del 8-puzzle puedes utilizar la función random-moves.
• Se ha de tener cuidado con las estrategias que crean muchos nodos pues puede fallar la aplicación por falta de memoria (se puede mirar primero con un A* cual es la profundidad de la solución y hacer una búsqueda en anchura sólo si esa profundidad es menor que un valor dado (p.e. 8)).
• Para hacer esta práctica lo más práctico es crear una función en Lisp que realice el encadenadamente todos los experimentos con todas las estrategias y recoja todos los datos necesarios de forma automática. (Es una función relativamente sencilla y elimina todo el trabajo pesado.)
 
4.3 Estrategias de búsqueda para juegos con dos jugadores
Esta segunda parte de la práctica está dedicada a adquirir experiencia con la búqueda en juegos de dos jugadores, concretamente utilizando el algoritmo MiniMax y su versión con la poda AlfaBeta.

4.3.1 Ficheros suministrados para la búsqueda en juegos
 

Dichas estrategias están implementadas en tres ficheros:
(1) El fichero minimax.lsp contiene funciones para minimax (minimax) y minimax con poda alfabeta (minimax-a-b). Estas funciones asumen que se encuentran definidas una serie de funciones y datos específicos del dominio del problema y que se encuentran documentadas a lo largo del código:

(print-board b)
 (movegen pos player)
 (opposite player)
 (static pos player)
 (won? pos player)
 (drawn? pos)
 (deep-enough pos depth)
 (make-move pos player move)
 *start*
Para jugar puede utilizarse la función play.

(2) El fichero tictactoeSinNombres.lsp contiene las funciones que necesita minimax para poder jugar al clásico juego de los tres en raya.

(3) El fichero connect_four.lsp contiene las funciones que necesita minimax para poder jugar al juego conecta cuatro que ya se utilizó en la práctica primera.
 

4.3.2 Tareas
 
(4) Cargar y evalúar los ficheros minimax.lsp y tictactoeSinNombres.lsp. Leer los comentarios de las funciones para tener información de cual es su funcionalidad. Se ha quitado el nombre de algunas de las definiciones de funciones de este fichero, estas funciones corresponden con las que va a utilizar la función minimax (y que están adecuadamente documentadas en algunos de los ficheros proporcionados). Se pide evaluar y ejecutar brevemente el juego (con la función play), para lo cual será necesario poner los nombres adecuados en sus defuns.

(5) Modificar las funciones pertinentes del fichero tictactoeSinNombres.lsp para que se pueda jugar a los cuatro en raya (en lugar de tres).

(6) Cargar ahora el fichero connect_four.lsp. Evaluar el fichero y jugar brevemente con play. El computador va informando de los nodos que va evaluando para cada tirada (número antes de escribir el texto "Your move: "). Por otra parte, se puede modificar la profundidad de búsqueda para elegir la jugada modificando el valor del parámetro *max-connect-four-depth*. Se pide realizar una tabla comparativa de los nodos evaluados en los cuatro primeros movimientos del computador en 6 juegos distintos donde se modifique la profundidad (3, 4 y 5) primero haciendo poda alfabeta y luego sin ella (modificar la función play para que en lugar de llamar a minimax-a-b llame a minimax).

(7) Documentar de forma clara la función heurística de evaluación utilizada en el juego conecta cuatro.

4.4 Información a entregar

Meter en un fichero la mínima información necesaria para realizar todas las tareas separándolas claramente y poniendo el número de la tarea. No olvidar que en el encabezamiento debe aparecer el autor y su correo electrónico. Se deberá someter un único archivo P4NXXIII.lsp.
 

  4.5 Ficheros suministrados

blind_search.lsp
heuristic_search.lsp
a_star.lsp
minimax.lsp
puzzle8.lsp
tictactoesinnombres.lsp
connect_four.lsp

4.5.1 Código del fichero puzzle8.lsp

 ;;A problem description consists of
;;;1. A structure to represent the state description: 3x3 array
;;;2. A list of operators: *eight-puzzle-operators*
;;;3. A definition of each operator: fill-four etc
;;;   An operator is a lisp function, that given a state description, returns
;;;   A new state description (Or nil if the operator can't be applied)

;;; A particular problem requires
;;;1. A start state
;;;2. A function to deterimine whether a state is the goal state.
;;;   By covention, we'll call this (solution-state? x)

;;In addition, this particular problem has a function called estimated-distance-from-goal(state)
;;that indicates how close a given state is from a solution
;;and a function cost-of-applying-operator(State Operator) that indicates
;;the cost of applying an operator

;;;00 01 02
;;;10 11 12
;;;20 21 22

(defparameter *goal-state*
  (make-array '(3 3)
              :initial-contents '((1 2 3)(4 5 6)(7 8 space))))

(defun copy-board(board)
  (let ((new-board (make-array '(3 3))))
    (loop for i from 0 to 2
        do (loop for j from 0 to 2
                 do (setf (aref new-board i j)
                          (aref board i j) )))
    new-board))

(defun print-board(board)
  (format t "~%-------")
  (loop for i from 0 to 2
        do (format t "~%|")
        (loop for j from 0 to 2
              do (format t "~A|" (if (eq (aref board i j) 'space)
                                   " "
                                   (aref board i j))))
        (format t "~%-------")))

(defun find-square(x board)
"return a list with the x y coordinates of the piece x in board"
  (loop for i from 0 to 2
      thereis (loop for j from 0 to 2
                  thereis
                    (when (eq (aref board i j) x)
                      (list i j)))))

(defun move-up(state)
  (let* ((at-space (find-square 'space state))
         (i (first at-space))
         (j (second at-space))
         (new-state (copy-board state)))
    (when (> i 0)
      (setf (aref new-state i j) (aref new-state (- i 1) j))
      (setf (aref new-state (- i 1) j) 'space)
      new-state)))

(defun move-down(state)
  (let* ((at-space (find-square 'space state))
         (i (first at-space))
         (j (second at-space))
         (new-state (copy-board state)))
    (when (< i 2)
      (setf (aref new-state i j) (aref new-state (+ i 1) j))
      (setf (aref new-state (+ i 1) j) 'space)
      new-state)))

(defun move-left(state)
  (let* ((at-space (find-square 'space state))
         (i (first at-space))
         (j (second at-space))
         (new-state (copy-board state)))
    (when (> j 0)
      (setf (aref new-state i j) (aref new-state  i (- j 1)))
      (setf (aref new-state  i (- j 1)) 'space)
      new-state)))

(defun move-right(state)
  (let* ((at-space (find-square 'space state))
         (i (first at-space))
         (j (second at-space))
         (new-state (copy-board state)))
    (when (< j 2)
      (setf (aref new-state i j) (aref new-state  i (+ j 1)))
      (setf (aref new-state  i (+ j 1)) 'space)
      new-state)))
 
 

(defun random-move(state)
  "randomly pick one of 4 operators. If it returns nil, choose again"
  (let ((r (random 4)))
    (or (cond ((= r 0)(move-left state))
        ((= r 1) (move-right state))
        ((= r 2) (move-up state))
        ((= r 3) (move-down state)))
      (random-move state))))

(defun random-moves (n state)
  "make N random moves"
  (loop for i from 1 to n
        do (setq state (random-move state)))
  state)

(defparameter *start-state*
  (random-moves 20 *goal-state*))

 (defun solution-state?(state)
  "A state description is the solution if it matches the goal state"
  (equalp state *goal-state*))

 (defparameter *eight-puzzle-operators*
  '(move-up move-down move-left move-right))

 (defun estimated-distance-from-goal (board)
"Compute Manhattan distance for each tile (except space)"
  (loop for i from 1 to 8
        summing (manhattan-distance (find-square i board)
                                    (find-square i *goal-state*))))

(defun manhattan-distance (p1 p2)
"given two lists of x-y coords, sum the difference between x's and y's"
  (+ (abs (- (first p1) (first p2)))
     (abs (- (second p1) (second p2)))))

(defun cost-of-applying-operator (state operator)
  1)
 
 
 

  4.5.2 Código del fichero tictactoeSinNombres.lsp

#|-----------------------------------------------------------------------------
Artificial Intelligence, Second Edition
Elaine Rich and Kevin Knight
McGraw Hill, 1991

This code may be freely copied and used for educational or research purposes.
All software written by Kevin Knight.
Comments, bugs, improvements to knight@cs.cmu.edu

    26-11-97   muro   modificado para quitar los nombres de funciones para la practica 4
----------------------------------------------------------------------------|#

#|----------------------------------------------------------------------------
                            TIC-TAC-TOE GAME
                            "tictactoe.lisp"
----------------------------------------------------------------------------|#

#|-----------------------------------------------------------------------------

This file contains code for the game of tic-tac-toe.
The important functions are:

 (deep-enough pos depth)        t if the search has proceeded deep enough.
 (static pos player)            evaluation of position pos from player's
                                point of view.
 (movegen pos player)           generate all successor positions to pos.
 (opposite player)              return the opposite player.
 (print-board pos)              print board position pos.
 (make-move pos player move)    return new position based on old position and
                                player's move.
 (won? pos player)              t if player has won.
 (drawn? pos)                   t if pos is a drawn position.

The important variables are:

 *start*                        the initial board configuration.

These functions and variables are all called from minimax.lisp.

----------------------------------------------------------------------------|#

;; Function NULL-BOARD creates an empty tic-tac-toe board. The board is
;; stored as a list of nine elements.  Elements are either 'x, 'o, or nil
;; (empty).

(defun null-board ()
  (list nil nil nil nil nil nil nil nil nil))

;; Variable *START* is the starting board position.

(defvar *start* nil)
(setq *start* (null-board))
 

;; Function ?????????? takes a board position (pos), a player (player, which
;; is 'x or 'o), and a move (which is a number between 0 and 8). It returns
;; a new board position.

(defun ?????????? (pos player move)
  (unless (nth move pos)
    (let ((b (copy-list pos)))
      (setf (nth move b) player)
      b)))
 

;; Function ?????????? takes a position and a player and generates all legal
;; successor positions, i.e., all possible moves a player could make.

(defun ?????????? (pos player)
  (loop for m from 0 to 8
        unless  (nth m pos)
        collect (make-move pos player m)))
 

;; Function ?????????? returns t is pos is a winning position for player,
;; nil otherwise.

(defun ?????????? (pos player)
  (setq player (opposite player))
  (or (and (eq (first pos) player)
           (eq (second pos) player)
           (eq (third pos) player))
      (and (eq (fourth pos) player)
           (eq (fifth pos) player)
           (eq (sixth pos) player))
      (and (eq (seventh pos) player)
           (eq (eighth pos) player)
           (eq (ninth pos) player))
      (and (eq (first pos) player)
           (eq (fourth pos) player)
           (eq (seventh pos) player))
      (and (eq (second pos) player)
           (eq (fifth pos) player)
           (eq (eighth pos) player))
      (and (eq (third pos) player)
           (eq (sixth pos) player)
           (eq (ninth pos) player))
      (and (eq (first pos) player)
           (eq (fifth pos) player)
           (eq (ninth pos) player))
      (and (eq (third pos) player)
           (eq (fifth pos) player)
           (eq (seventh pos) player))))

;; Function ?????????? returns t if pos is a drawn position, i.e., if there are
;; no more moves to be made.

(defun ?????????? (pos)
  (not (member nil pos)))
 

;; Function ?????????? returns 'x when given 'o, and vice-versa.

(defun ?????????? (player)
  (if (eq player 'x) 'o 'x))
 

;; Function ?????????? evaluates a position from the point of view of a
;; particular player.  It returns a number -- the higher the number, the
;; more desirable the position.  The simplest static function would be:
;;
;;        (defun ?????????? (pos player)
;;          (cond ((won? pos player) 1)
;;                ((won? pos (opposite player)) -1)
;;                (t 0)))
;;
;; However, this heuristic suffers from the problem that minimax search
;; will not "go in for the kill" in a won position.  The following static
;; function weighs quick wins more highly than slower ones; it also
;; ranks quick losses more negatively than slower ones, allowing the
;; program to "fight on" in a lost position.

(defun ?????????? (pos player)
  (cond ((won? pos player)
         (+ 1 (/ 1 (length (remove nil pos)))))
        ((won? pos (opposite player))
         (- (+ 1 (/ 1 (length (remove nil pos))))))
        (t 0)))
 

;; Function ?????????? takes a board position and a depth and returns
;; t if the search has proceeded deep enough.  The implementation below
;; causes the search to proceed all the way to a finished position.  Thus,
;; minimax search will examine the whole search space and never make a
;; wrong move.  A depth-limited search might look like:
;;
;;         (defun ?????????? (pos depth)
;;          (declare (ignore pos))
;;          (if (> depth 3) t nil))

(defun ?????????? (pos depth)
  (declare (ignore depth))
  (or (won? pos 'x)
      (won? pos 'o)
      (drawn? pos)))
 

;; Function ?????????? prints a two-dimensional representation of the board.

(defun ?????????? (b)
  (format t "~% ~d ~d ~d   0 1 2~% ~d ~d ~d   3 4 5~% ~d ~d ~d   6 7 8~%~%"
          (or (first b) ".") (or (second b) ".") (or (third b) ".")
          (or (fourth b) ".") (or (fifth b) ".") (or (sixth b) ".")
          (or (seventh b) ".") (or (eighth b) ".") (or (ninth b) ".")))
))
 

4.5.3  Código del fichero connect_four.lsp
 
(defparameter *max-connect-four-depth* 4)
(defun deep-enough(state depth)
  (>= depth *max-connect-four-depth*))

(defun make-move (pos player move)
  (move-i pos player move))
 

(defparameter *start*
  (make-array '(7 6)
              :initial-element 'empty))

(defun copy-board(board)
  (let ((new-board (make-array '(7 6))))
    (loop for i from 0 to 6
        do (loop for j from 0 to 5
                 do (setf (aref new-board i j)
                          (aref board i j) )))
    new-board))

(defun print-board(board)
  (format t "~%")
  (loop for j from 5 downto 0
      do (format t "===============~%" )
     (loop for i from 0 to 6
           do (format t "|~A" (if (eq (aref board i j) 'empty)
                                     " "
                              (aref board i j))))
     (format t "|~%"))
  (format t "===============~%" )
  (loop for i from 0 to 6
      do (format t " ~A" i))
  (format t "~%"))

(defun move-i(state player i)
  (loop for j from 0 to 5
      when (eq (aref state i j) 'empty)
      do (let ((new-state (copy-board state)))
         (setf (aref new-state i j) player)
         (return-from move-i new-state))))

#| Trying the middle first makes it easier for a-b
(defun movegen (state player)
  (unless (or (won? state player)
              (won? state (opposite player)))
  (loop for i from 0 to 6
    when (eq 'empty (aref  state i 5))
    collect (move-i state player i))))
|#

(defun movegen (state player)
  (unless (or (won? state player)
              (won? state (opposite player)))
  (loop for i in '(3 4 2 1 5 6 0)
    when (eq 'empty (aref  state i 5))
    collect (move-i state player i))))
 
 

(defun won?(state player)
  "A state description is the solution if it matches the goal state"
  (or (vertical-line state player)
      (horizontal-line state player)
      (diagonal-up-line state player)
      (diagonal-down-line state player)))

(defun drawn?(state)
 (loop for i from 0 to 6
    never (eq 'empty (aref  state i 5))))
 
 

(defun vertical-line (state player)
  (loop for i from 0 to 6
      thereis (loop for j from 0 to 2
              thereis (and (eq player (aref state i j))
                          (eq player (aref state i (+ j 1)))
                          (eq player (aref state i (+ j 2)))
                          (eq player (aref state i (+ j 3)))))))

 (defun horizontal-line (state player)
  (loop for i from 0 to 3
      thereis (loop for j from 0 to 5
              thereis (and (eq player (aref state i j))
                          (eq player (aref state (+ i 1) j))
                          (eq player (aref state (+ i 2) j))
                          (eq player (aref state (+ i 3) j))
                          ))))
 

(defun diagonal-up-line (state player)
  (loop for i from 0 to 3
      thereis (loop for j from 0 to 2
              thereis (and (eq player (aref state i j))
                          (eq player (aref state  (+ i 1) (+ j 1)))
                          (eq player (aref state  (+ i 2)(+ j 2)))
                          (eq player (aref state  (+ i 3)(+ j 3)))))))
 

(defun diagonal-down-line (state player)
  (loop for i from 0 to 3
      thereis (loop for j from  3 to 5
              thereis (and (eq player (aref state i j))
                          (eq player (aref state  (+ i 1)(- j 1)))
                          (eq player (aref state  (+ i 2)(- j 2)))
                          (eq player (aref state  (+ i 3)(- j 3)))))))
 
 

(defun test-play(state player)
  (let ((next (get-move state player)))
    (if (or (won? next player)
            (drawn? next))
    (print-board next)
      (test-play next (opposite player)))))

(defun opposite(x)
  (cond ((eq x 'x) 'o)
    ((eq x 'o) 'x)
    (t (error "~%Illegal player ~a" X))))

(defun get-move(state player)
  (print-board state)
  (format t "~%~a> " player)
  (let ((n (read)))
    (cond ((and (numberp n)
            (>= n 0)
            (<= n 6)
            (move-i state player n)))
      (t (format t "~%TRY AGAIN")
         (get-move state player)))))

 
 
 
 

(defun print-board(board)
  (format t "~%")
  (loop for j from 5 downto 0
      do (format t "---------------~%" )
     (loop for i from 0 to 6
           do (format t "|~A" (if (eq (aref board i j) 'empty)
                                     " "
                              (aref board i j))))
     (format t "|~%"))
  (format t "---------------~%" )
  (loop for i from 0 to 6
      do (format t " ~A" i))
  (format t "~%"))
 

(defun static(board player)
  (- (rank-board board player)
     (rank-board board (opposite player))))

(defun rank-board(state player)
  (+ (possible-vertical-line state player)
      (possible-horizontal-line state player)
      (possible-diagonal-up-line state player)
      (possible-diagonal-down-line state player)))

(defun neq (a b)
   (not (eq a b)))

(defun rank-line (player opposite s1 s2 s3 s4)
  (let ((matches 0))
    (when (and (neq opposite s1)
               (neq opposite s2)
               (neq opposite s3)
               (neq opposite s4))
      (when (eq player s1)
        (setq matches (+ matches 1)))
      (when (eq player s2)
        (setq matches (+ matches 1)))
      (when (eq player s3)
        (setq matches (+ matches 1)))
      (when (eq player s4)
        (setq matches (+ matches 1))))
    (cond ((<= matches 2) matches)
          ((= matches 3) 4)
          ((= matches 4) 1000))))

(defun possible-vertical-line (state player)
  (let ((score 0)
        (opposite (opposite player)))
    (loop for i from 0 to 6
          do (loop for j from 0 to 2
                   maximize (setq score (+ score
                                     (rank-line player opposite
                                             (aref state i j)
                                             (aref state i (+ j 1))
                                             (aref state i (+ j 2))
                                             (aref state i (+ j 3)))))))
 
 
    score))

(defun possible-horizontal-line (state player)
  (let ((score 0)
        (opposite (opposite player)))
    (loop for i from 0 to 3
          do (loop for j from 0 to 5
                    do (setq score (+ score
                                          (rank-line player opposite
                                                     (aref state i j)
                                              (aref state (+ i 1) j)
                                                (aref state (+ i 2) j)
                                                (aref state (+ i 3) j)
                                )))))
    score))
 

(defun possible-diagonal-up-line (state player)
  (let ((score 0)
        (opposite (opposite player)))
    (loop for i from 0 to 3
          do (loop for j from 0 to 2
                   do (setq score (+ score
                                     (rank-line player opposite
                                               (aref state i j)
                                          (aref state  (+ i 1) (+ j 1))
                                          (aref state  (+ i 2)(+ j 2))
                                        (aref state  (+ i 3)(+ j 3)))))))
    score))
 

(defun possible-diagonal-down-line (state player)
  (let ((score 0)
        (opposite (opposite player)))
    (loop for i from 0 to 3
          do (loop for j from  3 to 5
                    do (setq score (+ score
                                          (rank-line player opposite
                                                    (aref state i j)
                                               (aref state  (+ i 1)(- j 1))
                                                (aref state  (+ i 2)(- j 2))
                                                (aref state  (+ i 3)(- j 3)))))))
    score))