LISP Homework Help, Project Help, LISP Assignment Solution

Lisp is an old programming language, that concerns processing of lists. It is very different than C++, there is very little to distinguish data and code.

Problem:

  1. Define a function ADD-LENGTH-TO-LIST, whose argument is a list. This function should insert the length of the list into the end of the list.

Answer:

(defun ADD-LENGTH-TO-LIST (l) (nconc l (list (length l))))

2. Lost and gain of not including C++ pointers and use references in Java.

Answer:

References in Java has less flexibility than pointers in C++. With dynamic runtime typecase in C++, pointers provide much flexibility to access data which is more convenient. However, the references in Java provides more security protection. For example, even functions or fields are declared as private in C++, we can still visit them by manipulating the pointers to the objects. It is impossible to do the same thing in Java.

3. How coercion rules can weaken the beneficial effects of strong typing.

Answer:

Compilers for strong typing languages usually can detect more typing related errors during the compile time. Compared to that, coercion rules
make the language less compile time reliable. In addition, it is considered easier for people to understand codes written in strong typing languages since coercion rules usually adds some logic implicitly behind the code itself.

Problem:

implement Tic Tac Toe game using LISP.
The program should ask the user at the beginning to choose EASY or DIFFICULT, which are the two levels of difficulty of playing against the computer.

EASY – should be easier to win the computer.

DIFFICULT – computer should win most of times.

Solution:

;;; TIC-TAC-TOE
;;
;; define a 2 players game, identify player behaviour as
;;  1) user choose on keyboard
;;  2) computer - play easy (select first available)
;;  3) random   - peek any valid
;;  4) computer - play best (minimax search of game tree)
;;
;; the board is represented by a 9 elements list, each element
;; can be either 'x, 'o, or '-
;;

;; printing a board' state
;;
(defun print-row (row)
  (format t "~a ~a ~a ~%" (car row) (cadr row) (caddr row))
)

(defun nl ()
 (write-char #\linefeed)
 (finish-output nil))

(defun print-board (board)
  (if (>= (length board) 3)
    (progn
     (print-row board)
     (print-board (cdddr board)))
    (nl)
  )
)

;; must match all 3 positions (0 index)
;;
(defun match3 (pos3 board player)
 (and (eq (nth (car pos3) board) player)
      (eq (nth (cadr pos3) board) player)
      (eq (nth (caddr pos3) board) player))
)

;; true if player wins on board
;;
(defun winner (player board)
 (or
  (match3 '(0 1 2) board player)
  (match3 '(3 4 5) board player)
  (match3 '(6 7 8) board player)
  (match3 '(0 4 8) board player)
  (match3 '(6 4 2) board player)
  (match3 '(0 3 6) board player)
  (match3 '(1 4 7) board player)
  (match3 '(2 5 8) board player)
 )
)

;;;;;;;;;; some tests ;;;;;;;;;;
#|
(print-row '(1 2 3 4))
(print-board '(
   - - x 
   o x -
   x o o
))

; test using nth for matching
(print (match3 '(0 1 2) '(x x x) 'x))
(print (match3 '(0 1 2) '(x x y) 'x))

; test winning position
(print (winner 'x '(
   - - x 
   o x -
   x o o
)))
|#

;; display a really simple menu:
;; show choices, take an input and verify
;;
(defun simple-menu (prompt choices)
 (mapcar 'print choices)
 (nl)
 (loop
   (format t "~a" prompt)
   (finish-output nil)
   (let
    ((v (read t)))
   (if (or (< v 1) (> v (length choices)))
    (print 'invalid)
    (return v)
   ))))

;; check that element of board at position move
;; is 'free position' marker
;;
(defun is-valid (move board)
 (eq (nth move board) '-))

;; swap player symbol
;;
(defun other-player (p)
 (if (eq p 'x) 'o 'x))

;; get index of move for player
;;  note: internal indexing is 0 based
;;  but user indexing is 1 based (easier to visualize)
;;
(defun get-user-move (board player)
 (loop
  (format t "~a move (1 to 9) ? " player)
  (finish-output nil)
  (let ((move (- (read t) 1)))
   (if (is-valid move board)
    (return move))
   (format t "invalid - please retry ~%")
  )
 )
)

;; just peek first free position available
;;
(defun get-easy-move (board)
 (position '- board))

;; Several optimized implementations of minimax are available, like
;; http://www-users.cs.umn.edu/~gini/aiprog/rich-knight/minimax.lisp
;;
;; Here I try to code a simpler minimax search,
;; loosely inspired by: http://en.wikipedia.org/wiki/Minimax
;; Actually, here the tree is 'implicit' in the move generation loop.
;;
(defun minmax (depth board player maxmin)
 "return best pair position . value"
 ;(format t "~v<~>{ ~a ~a ~a~%" depth board player maxmin)
 (let
  ((best (cons nil 0))  ; if no move available: a draw
   temp opponent
  )
  (loop for p from 0 to 8 do ; generate moves
   (when (is-valid p board)
     (setq temp (copy-list board))
     (setf (nth p temp) player)

     ;(print-board temp)    
     (if (not (car best)) ; first move
       (setq best (cons p maxmin)))

     (when (winner player temp)
      ;(format t "~v<~>w ~a ~a ~a ~%"  depth temp player (cons p maxmin))
      (return (cons p maxmin))
     )

     ;; recursive call: invert evaluation
     (setq opponent
        (minmax (+ 1 depth) temp (other-player player) (* -1 maxmin)))

     ;(format t "~v<~> ~a ~a ~%" depth opponent best)
     (if (= maxmin 1)
       (if (< (cdr opponent) (cdr best))
        (setq best opponent))
       (if (> (cdr opponent) (cdr best))
        (setq best opponent))
     )

     ;(when (or (= 0 depth) (= 2 depth)) (format t "~v<~> * ~a ~a ~%" depth opponent best))
   )
  )
  ;(format t "~v<~>} ~a ~a ~a ~a~%" depth board player maxmin best)
  best
 )
)

;; while debugging minimax,
;; here is a very simple heuristic, playing fairly well
;;
(defun win-first-move (board player)
  (loop for p from 0 to 8 do ; generate moves
   (when (is-valid p board)
     (let ((temp (copy-list board)))
      (setf (nth p temp) player)
      (when (winner player temp)
       (return p))))))

(defun silly (board player)
 "a silly heuristic: either a winning move (player or adversary)
  or the first available"
 (let
  ((move (win-first-move board player)))
  (progn
   (if (not move)
    (setq move (win-first-move board (other-player player))))
   (if (not move)
    (setq move (get-easy-move board)))
  )
  (cons move nil)
 ))

;; keep generating a (pseudo)random index and
;; accept when it's an empty position
;;
(defun get-rand-move (board)
  (loop
   (let ((move (random 9)))
   (if (is-valid move board)
    (return move)
   ))))

;; peek a move with most simple heuristic
;;
(defun get-silly-move (board player)
 (car (silly board player)))

;; invoke minimax search
;;
(defun get-best-move (board player)
 (car (minmax 0 board player 1)))

;; dispatch move selection on player' strategy
;;
(defun get-move (board behaviour player)
 (cond
  ((eq behaviour 1) (get-user-move board player))
  ((eq behaviour 2) (get-easy-move board))
  ((eq behaviour 3) (get-rand-move board))
  ((eq behaviour 4) (get-silly-move board player))
  ((eq behaviour 5) (get-best-move board player)) ))

#|
(if nil ; debugging minmax on patterns
 (let*
  ((b '(- - o 
        x o x 
        - x -))
   (b '(x x - 
        - - - 
        - o -))
    (p 'o)
    (m (get-best-move b p))
  )
    (print m) (nl)
    (setf (nth m b) p)
    (print-board b)
))
|#

;; play a game
;; loop until either a player wins or no more moves are available
;;
(defun TIC-TAC-TOE (mode_x mode_o)
 (let
  ( (board (list '- '- '- '- '- '- '- '- '-))
    (player 'x) ; always start with X
    move
  )
  (loop
    (nl)
    (print-board board)

    ;; select a move (must be valid)
    (setq move
      (get-move board
        (if (eq player 'x) mode_x mode_o) player))

    ;(setq board (update-board move board))
    (setf (nth move board) player)

    (when (winner player board)
      (print-board board)
      (return player))

    ;; check if no more moves
    (when (not (find '- board))
      (print-board board)
      (return 'draw))

    ;; switch players
    (setq player (other-player player))
  )))

;; game interface
;;
(let
    ((choices '(1=user 2=easy 3=random 4=silly 5=best))
     (firstp 3)
     (secondp 5)
    )
    (if t ; set nil to use default settings
     (progn
      (setq firstp (simple-menu  "play first  (x):" choices))
      (setq secondp (simple-menu "play second (o):" choices)) ))
    (if t ; set nil to skip game interface while debugging
     (let
      ((result (TIC-TAC-TOE firstp secondp)))
      (if (eq result 'draw)
       (format t "the game is draw")
       (format t "player ~a wins" result))
     )))

LISP assignment help is accorded by the experts that are highly qualified and accomplished in  their field of LISP programming. Our website is an online portal that puts forward a wide variety of services like LISP homework help. The LISP project help is one of the most reliable offering from our programmers.