[Lisp] Tic-Tac-Toe 게임 실습(1)

1. Tic-Tac-Toe 게임이란?

- 위와 같은 3*3 보드가 있을 때,

  O와 X가 차례대로 두면서 O나 X가 가로/세로/대각선으로 연속 3개를 두면 이기는 게임이다.

(자세한 설명은  : 틱택토 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)) 

 

2. 구현

1) 전역변수/ 상수 선언

(defconstant One 1) 
(defconstant TheOther 10)
(defvar *Opponent* One)
(defvar *Computer* TheOther)

 

2) makeBoard : 보드를 만드는 함수

(defun makeBoard ()
	(list ‘Board 0 0 0 0 0 0 0 0 0))

3) convert-to-letter : one을 0로, the other을 x로 바꾸는 함수

(defun convert-to-letter (v)
  (cond ((= v One) "O")
        ((= v TheOther) "X")
        (t " ")))

4) print-row : 1줄 출력하는 함수

(defun print-row (x y z)
  (format t "~&  ~A |  ~A  |  ~A"
    (convert-to-letter x) (convert-to-letter y) (convert-to-letter z)))
    //convert로 o와 x를 바꿔준다.

5) printBoard : 전체 보드를 출력하는 함수

(defun printBoard (board)
  (format t "~%")
  (print-row (nth 1 board) (nth 2 board) (nth 3 board))
  (format t "~& --------------")
  (print-row (nth 4 board) (nth 5 board) (nth 6 board))
  (format t "~& --------------")
  (print-row (nth 7 board) (nth 8 board) (nth 9 board))
  (format t "~%~%"))

6) 1(one)과 10(the other)을 움직이는 함수 

(defun makeMove (Player Pos Board)
  (setf (nth Pos Board) Player) Board)

  * 인자로 *Opponent*, 3 , MyBoard 이 들어오면 

board 리스트의 3번째 위치를 *Opponent* 로 지정, 그리고 Board의 리스트를 return하게 된다.

*Opponent*로 지정하면 *Opponent* = one = 1 이 된다.

 

7) *Triplets* : 점수계산을 위한 전역변수 선언

(defvar *Triplets*
	‘((1 2 3) (4 5 6) (7 8 9) ;; 가로
	(1 4 7) (2 5 8) (3 6 9) ;; 세로
	(1 5 9) (3 5 7))) ;; 대각선

8) sumTriplet : 점수계산하는 함수

(defun sumTriplet (Board Triplet)
	(+ (nth (first Triplet) Board)
	(nth (second Triplet) Board)
	(nth (third Triplet) Board)))

9) computeSums : 8개(triplets)의 더한 결과 값을 리턴한다.

(defun computeSums (Board)
	(mapcar #’(lambda (Triplet)
	(sumTriplet Board Triplet))
	*Triplets*))

10) winnerP : 승자가 있는지 체크하는 함수

(defun winnerP (Board)
	(let ((Sums (computeSums Board))) //sums라는 변수 선언(board의 모든 sum값이 있는 리스트)
	(or (member (* 3 *Computer*) Sums) //30((the other)이 sums의 멤버이거나 = the other가 연속 3개
	(member (* 3 *Opponent*) Sums)))) // 3(one)이 sum의 멤버 = one이 연속 3개

11) playOneGame : 게임 플레이하는 함수

(defun playOneGame ()
	(if (y-or-n-p “Do you like to go first? “)
	(opponentMove (makeBoard))
	(computerMove (makeBoard))))

12) opponentMove : 상대에게 이동을 요청하고 범위를 넘어간 곳에 이동했는지 확인하는 함수

(defun opponentMove (Board)
	(let* ((Pos (readALegalMove Board))
		(NewBoard (makeMove *Opponent* Pos Board)))
	(printBoard NewBoard)
	(cond ((winnerP NewBoard) ‘YouWin)
		((boardFullP NewBoard) ‘TieGame)
		(t (computerMove NewBoard)))))

13) readALegalMove : legal한 move인지 확인하는 함수

(defun readALegalMove (Board)
	(format t “~& Your move: “)
	(let ((Pos (read)))
	(cond ((not (and (integerp Pos) (<= 1 Pos 9)))
		(format t “~& Invalid input.”)
		(readALegalMove Board))
	((not (zerop (nth Pos Board)))
		(format t “~& Already occupied.”)
		(readALegalMove Board))
	(t Pos))))

14) boardFullP : 보드가 다 차있는지 확인하는 함수

(defun boardFullP (Board)
	(not (member 0 Board)))

15) computerMove : 컴퓨터가 움직이는 함수

(defun computerMove (Board)
	(let* ((BestMove (chooseBestMove Board))
		(Pos (first BestMove))
		(Strategy (second BestMove))
		(NewBoard (makeMove *Computer* Pos Board)))
	(format t “~&My move: ~S” Pos)
	(format t “~&My strategy: ~A~%” Strategy)
	(printBoard NewBoard)
	(cond ((winnerP NewBoard) ‘IWin)
		((boardFullP NewBoard) ‘TieGame)
		(t (opponentMove NewBoard)))))

16) chooseBestMove  : 어떤 전략(어떻게 움직일지)를 선택하는 함수

(defun chooseBestMove (Board)
	“1st version”
	(randomMoveStrategy Board)) ;랜덤전략 사용

17) randomMoveStrategy  : 랜덤으로 움직이는 전략

(defun randomMoveStrategy (Board)
	(list (pickRandomEmptyPosition Board) “Random Move”))

18) pickRandomEmptyPosition : 비어있는 곳에 둘수있는 함수

(defun pickRandomEmptyPosition (Board)
	(let ((Pos (+ 1 (random 9))))
	(if (zerop (nth Pos Board)) Pos
		(pickRandomEmptyPosition Board))))

=전체코드=

;; Case study - tic tac toe 


;; 전역변수 선언
;; defconstant : 상수 선언, defvar : 전역변수 선언
(defconstant One 1)
(defconstant TheOther 10)
(defvar *Opponent* One)
(defvar *Computer* TheOther)


(defun makeBoard ()
  "새로운 보드 만들기"
  (list 'Board 0 0 0 0 0 0 0 0 0))

(defun convert-to-letter (v)
  "one을 0로, the other을 x로 바꾸는 함수"
  (cond ((= v One) "O")
        ((= v TheOther) "X")
        (t " ")))

(defun print-row (x y z)
  "1줄 보드 출력하는 함수"
  (format t "~&  ~A |  ~A  |  ~A"
    (convert-to-letter x) (convert-to-letter y) (convert-to-letter z)))

(defun printBoard (board)
  "전체 보드 출력하는 함수"
  (format t "~%")
  (print-row (nth 1 board) (nth 2 board) (nth 3 board))
  (format t "~& --------------")
  (print-row (nth 4 board) (nth 5 board) (nth 6 board))
  (format t "~& --------------")
  (print-row (nth 7 board) (nth 8 board) (nth 9 board))
  (format t "~%~%"))

(defun makeMove (Player Pos Board)
  "1과 10을 움직이는 함수"
  (setf (nth Pos Board) Player) Board)

(defvar *Triplets*
    '((1 2 3) (4 5 6) (7 8 9) ;; Horizontal
      (1 4 7) (2 5 8) (3 6 9) ;; Vertical
      (1 5 9) (3 5 7))) ;;Diagonal

(defun sumTriplet (Board Triplet)
  (+ (nth (first Triplet) Board)
     (nth (second Triplet) Board)
     (nth (third Triplet) Board)))

(defun computeSums (Board)
  (mapcar #'(lambda (Triplet) (sumTriplet Board Triplet)) *Triplets*))

(defun winnerP (Board)
  (let ((Sums (computeSums Board)))
    (or (member (* 3 *Computer*) Sums)
        (member (* 3 *Opponent*) Sums))))

(defun playOneGame ()
  (if (y-or-n-p "Do you like to go first? ")
      (opponentMove (makeBoard)) (computerMove (makeBoard))))

(defun opponentMove (Board)
  (let* ((Pos (readALegalMove Board))
         (NewBoard (makeMove *Opponent* Pos Board)))
    (printBoard NewBoard)
    (cond ((winnerP NewBoard) 'YouWin)
          ((boardFullP NewBoard) 'TieGame)
          (t (computerMove NewBoard)))))

(defun readALegalMove (Board)
  (format t "~& Your move: ")
  (let ((Pos (read)))
    (cond ((not (and (integerp Pos) (<= 1 Pos 9))) (format t "~& Invalid input.")
           (readALegalMove Board))
          ((not (zerop (nth Pos Board))) (format t "~& Already occupied.")
           (readALegalMove Board))
          (t Pos))))

(defun boardFullP (Board)
  (not (member 0 Board)))

(defun computerMove (Board)
  (let* ((BestMove (chooseBestMove Board))
         (Pos (first BestMove))
         (Strategy (second BestMove))
         (NewBoard (makeMove *Computer* Pos Board)))
    (format t "~&My move: ~S" Pos)
    (format t "~&My strategy: ~A~%" Strategy)
    (printBoard NewBoard)
    (cond ((winnerP NewBoard) 'IWin)
          ((boardFullP NewBoard) 'TieGame)
          (t (opponentMove NewBoard)))))


(defun chooseBestMove (Board)
  "1st version"
  (randomMoveStrategy Board))

(defun randomMoveStrategy (Board)
  (list (pickRandomEmptyPosition Board) "Random Move"))

(defun pickRandomEmptyPosition (Board)
  (let ((Pos (+ 1 (random 9))))
    (if (zerop (nth Pos Board)) Pos (pickRandomEmptyPosition Board))))

 

 👉 첫번째 전략(랜덤) 으로 실행

 

- 좀더 똑똑한 버전

* 내가 2개 연속으로 놨을 때 막기, 컴퓨터가 2개 연속으로 놓았으면 3개 연속으로 두게하기

 

1) makeThree : 3개로 만드는 함수

(defun makeThree (Board)
	(let ((Pos (winOrBlock Board (* 2 *Computer*)))) ;; 2 * 10 
	(and Pos (list Pos “make three in a row”))))

2) blockOpponentWin : 이기는 걸 막는 함수

(defun blockOpponentWin (Board)
	(let ((Pos (winOrBlock Board (* 2 *Opponent*)))) ;; 2 * 1 
	(and Pos (list Pos “block the opponent”))))

3) winOrBlock : 이기거나 막거나

(defun winOrBlock (Board TargetSum)
	(let ((Triplet ;; Triplet – a specific triplet, e.g., (1 2 3)
		(find-if #’(lambda (Tri)
			(equal (sumTriplet Board Tri) TargetSum) *Triplets*)))
	(when Triplet (findEmptyPosition Board Triplet))))

4) findEmptyPosition : 비어있는공간을 찾는 함수

(defun findEmptyPosition (Board Cells) ;; Cells in a triplet, (1 2 3)
	(find-if #’ (lambda (Pos) (zerop (nth Pos Board))) Cells))

5) take-center : 센터에 두는 함수

(defun take-center (Board)
  (when (and (zerop (nth 5 Board))
             (or (= 1 (apply #'+ (cdr Board)))
                 (= 0 (apply #'+ (cdr Board)))))
    (let ((Pos 5))
      (list Pos "taking 5th Position"))))

 

6) chooseBestMove : 움직이는 전략 선택하는 함수

(defun chooseBestMove (Board)
	“2nd version”
	(or (makeThree Board) 
    	(take-center Board)
	(blockOpponentWin Board)
	(randomMoveStrategy Board))) 

 

 

 👉 두번째 전략(좀더 똑똑한ver) 으로 실행

위와 같이 좀더 똑똑하게 컴퓨터가 게임을 한다.