;例題1
(defconstant Board-Size 8) ;盤面の大きさ
(defconstant Board-Dimensions (list Board-Size Board-Size)) ;盤面配列の次元
(defconstant Board-Sente 1) ;盤面配列で先手の石を示す数
(defconstant Board-Gote -1) ;盤面配列で後手の石を示す数
(defconstant Board-Empty 0) ;盤面配列で空きを示す数
(defconstant Board-Sente-String “*”) ;先手の石を示す表示文字列
(defconstant Board-Gote-String “o”) ;後手の石を示す表示文字列
(defconstant Board-Empty-String “-“) ;空きを示す表示文字列
(defconstant Board-Initial ;盤面の初期状態
#2A((0 0 0 0 0 0 0 0) (0 0 0 0 0 0 0 0) (0 0 0 0 0 0 0 0) (0 0 0 -1 1 0 0 0) (0 0 0 1 -1 0 0 0) (0 0 0 0 0 0 0 0) (0 0 0 0 0 0 0 0) (0 0 0 0 0 0 0 0)))
;——————————————————————————————————–
;例題2 次の手番を返す関数 引数:手番
(defun change-turn (turn)
(cond ((equal turn Board-Sente) Board-Gote)
(t Board-Sente)))
;実行例
;(change-turn Board-Sente)
;-1
;(change-turn Board-Gote)
;1
;——————————————————————————————————–
;練習1 対応する石の表示文字列を返す関数 引数:手番
(defun symbol-turn (turn)
(cond ((equal turn Board-Sente) Board-Sente-String)
((equal turn Board-Gote ) Board-Gote-String )
(t Board-Empty-String)))
;実行例
;(symbol-turn Board-Sente)
;”*”
;(symbol-turn Board-Empty)
;”-”
;——————————————————————————————————–
;例題3 1-3の関数を定義する
(defun make-board () (make-array Board-Dimensions)) ;新しい盤を生成する
(defun ref-board (board row col) ;盤面board上のrow行col列の石を参照する
(aref board row col))
(defun set-board (board row col turn) ;盤面board上のrow行col列の石turnを設定する
(setf (aref board row col) turn))
;——————————————————————————————————–
;例題4 盤面boardをコピーした新しい盤面を生成して返す関数 引数:盤面
(defun copy-board (board)
(let ((new-board (make-board)))
(dotimes (row Board-Size new-board) ;new-boardをletの値として返す
(dotimes (col Board-Size)
(set-board new-board row col (ref-board board row col))))))
;実行例
;(copy-board Board-Initial)
;#2A((0 0 0 0) (0 -1 1 0) (0 1 -1 0) (0 0 0 0)) ;Board-Initial そのものではない
;——————————————————————————————————–
;練習2 盤面boardの状態を表示する関数 引数:盤面
(defun print-board (board)
(format t “R/C 0 1 2 3 4 5 6 7” )
(let ((x 0))
(dotimes (x (* Board-Size Board-Size))
(if (zerop (mod x Board-Size)) (format t “~% ~A” (/ x 8)) )
(format t ” ~A” (symbol-turn (ref-board board (mod x Board-Size) (floor x Board-Size)))))))
;実行例
;(print-board Board-Initial)
;R/C 0 1 2 3
; 0 – – – –
; 1 – o * –
; 2 – * o –
; 3 – – – –
;——————————————————————————————————–
;例題5 8方向を表す定数Board-Directionsを設定する
(defconstant Board-Directions ;8方向の定義
‘((0 1) (1 1) (1 0) (1 -1) (0 -1) (-1 -1) (-1 0) (-1 1)))
;——————————————————————————————————–
;例題6 連続して並んでいる石の個数を数え、その値を返す関数 引数:盤面、行、列、行方向、列方向
(defun sample-scan (board row0 col0 row-inc col-inc)
(do ((row row0 (+ row row-inc)) ;変数rowをrow0からrow-incずつ変える
(col col0 (+ col col-inc)) ;変数colをcol0からcol-incずつ変える
(length 0 (1+ length))) ;変数lengthを0から1ずつ増やす
((or (< row 0) (= row Board-Size) (< col 0) (= col Board-Size)
(equal (ref-board board row col) Board-Empty))
length))) ;盤面の外から石が置かれているなければ、length返す
;実行例
;(sample-scan Board-Initial 2 2 -1 -1)
;2
;(sample-scan Board-Initial 2 2 0 1)
;1
;--------------------------------------------------------------------------------------------------------
;練習3 turnの石とはさんで反転できる石の数を返す関数 引数:盤面、行、列、行方向、列方向、手番
(defun board-scan (board row0 col0 row-inc col-inc turn)
(do ((row (+ row0 row-inc) (+ row row-inc))
(col (+ col0 col-inc) (+ col col-inc))
(length 0 (1+ length)))
((or (< row 0) (= row Board-Size) (< col 0) (= col Board-Size)
(equal (ref-board board row col) turn)
(and (equal (ref-board board row col) Board-Empty) (/= (ref-board board (- row row-inc) (- col col-inc)) turn) (setq length 0))
(equal (ref-board board row col) Board-Empty))
length)))
;実行例
;(board-scan Board-Initial 1 0 0 1 Board-Sente)
;1
;(board-scan Board-Initial 2 0 0 1 Board-Sente)
;0
;(board-scan Board-Initial 1 0 -1 -1 Board-Gote)
;0
;(board-scan Board-Initial 0 0 1 1 Board-Sente)
;0
;--------------------------------------------------------------------------------------------------------
;例題7 盤面に石をおけるかどうかを判定する関数 引数:盤面、行、列、手番
(defun board-movable (board row col turn)
(and (equal (ref-board board row col) Board-Empty)
(dolist (dir Board-Directions nil)
(cond ((> (board-scan board row col (car dir) (cadr dir) turn) 0)
(return t))))))
;実行例
;(board-movable Board-Initial 0 1 Board-Sente)
;T
;(board-movable Board-Initial 0 1 Board-Gote)
;NIL
;——————————————————————————————————–
;練習4 どこかに手番の石を置けるかどうかを判定する関数 引数:盤面、手番
(defun board-movable-any (board turn)
(let ((row 0) (col 0) (product 0))
(dotimes (row Board-Size (if (= product 1) (return t)))
(dotimes (col Board-Size)
(if (equal (board-movable board row col turn) t) (setq product 1))))))
;実行例
;(board-movable-any Board-Initial Board-Sente)
;T
;——————————————————————————————————–
;例題8 オセロゲームの基本的な流れを実現する関数
(defun othello-by-human ()
(do ((board (copy-board Board-Initial)) ;初期盤面の複製を作る
(turn Board-Sente (change-turn turn)) ;手番を交代する
(count 1 (1+ count)) ;手数を増加させる
state)
((numberp (setq state (board-state board turn))) ;終局ならば
(game-result board state)) ;終了処理
(print-board board) ;盤面を表示
(cond ((equal state ‘pass) ;パスの処理
(format t “(~A) Pass.~%” count))
(t (play-by-human board turn count))))) ;人間が石を置く
;——————————————————————————————————–
;練習5 盤面を判定する関数 引数:盤面、手番
(defun board-state (board turn)
(let ((sente nil) (gote nil))
(dotimes (row Board-Size sente)
(dotimes (col Board-Size)
(if (board-movable-any board turn) (setq sente t))))
(dotimes (row Board-Size gote)
(dotimes (col Board-Size)
(if (board-movable-any board (* -1 turn)) (setq gote t))))
(cond ((equal sente t) ‘nil)
((and (equal sente nil) (equal gote t)) ‘pass)
(t (board-eval board)))))
;実行例
;(board-state Board-Initial Board-Sente)
;NIL
;(board-state #2A((1 -1 -1 1) (-1 -1 -1 0) (-1 1 -1 -1) (1 0 1 -1) Board-Sente)
;PASS
;(board-state #2A((1 -1 -1 1) (-1 -1 -1 1) (-1 1 -1 -1) (1 1 1 -1) Board-Sente)
;-1/4
;——————————————————————————————————–
;練習6 盤面の評価関すとして、石の関すを数え、(先手ー後手)/(先手+後手)を返す関数 引数:盤面
(defun board-eval (board)
(let ((sente 0) (gote 0))
(dotimes (row Board-Size (/ (- sente gote) (+ sente gote)))
(dotimes (col Board-Size)
(cond ((equal (ref-board board row col) Board-Sente)
(setq sente (1+ sente)))
((equal (ref-board board row col) Board-Gote)
(setq gote (1+ gote))))))))
;実行例
;(board-eval Board-Initial)
;0
;——————————————————————————————————–
;練習7 ゲームの結果を表示する関数 引数:盤面、状態
(defun game-result (board state)
(cond ((> state 0) (print-board board) (format t “~%Game won by ~A ~%” Board-Sente-String))
((zerop state) (print-board board) (format t “Draw ~%”))
((< state 0) (print-board board) (format t "~%Game won by ~A ~%" Board-Gote-String)))
(let ((sente 0) (gote 0))
(dotimes (row Board-Size (format t "Score is ~A - ~A" sente gote))
(dotimes (col Board-Size)
(cond ((equal (ref-board board row col) Board-Sente)
(setq sente (1+ sente)))
((equal (ref-board board row col) Board-Gote)
(setq gote (1+ gote))))))))
;実行例
;(game-result #2A((-1 -1 -1 1)(-1 -1 -1 0)(-1 -1 -1 -1)(1 -1 -1 -1)) -11/15)
;R/C 0 1 2 3
; 0 o o o *
; 1 o o o o
; 2 o o o o
; 3 * - o o
;Game won by o
;Score is 2 - 13
;--------------------------------------------------------------------------------------------------------
;例題9 盤面を更新する関数 引数:盤面、手番、手数
(defun play-by-human (board turn count)
(format t "~%(~A) Enter row and col for ~A: " count (symbol-turn turn))
(do ((row (read) (read))
(col (read) (read)))
((and (board-number-check row col)
(board-movable board row col turn))
(board-move board row col turn))
(format t "~%Re-enter row and col for ~A: " (symbol-turn turn))))
;--------------------------------------------------------------------------------------------------------
;練習8 更新された盤面を返す関数 引数:盤面、行、列、手番
(defun board-move (board row col turn)
(let ((row0 row) (col0 col))
(set-board board row col turn)
(dolist (dir Board-Directions board)
(cond ((> (board-scan board row col
(car dir) (cadr dir) turn) 0) ;(car dir)=row-inc (cadr dir)=col-inc
(setq row0 (+ row0 (car dir)))
(setq col0 (+ col0 (cadr dir)))
(dotimes (num (board-scan board row col
(car dir) (cadr dir) turn))
(set-board board row0 col0 turn)
(setq row0 (+ row0 (car dir)))
(setq col0 (+ col0 (cadr dir)))
)
(setq row0 row) ;起点
(setq col0 col)
)))))
;実行例
;(setq board (copy-board Board-Initial))
;#2A((0 0 0 0) (0 -1 1 0) (0 1 -1 0) (0 0 0 0))
;(board-move board 0 1 Board-Sente)
;#2A((0 1 0 0) (0 1 1 0) (0 1 -1 0) (0 0 0 0))
;——————————————————————————————————–
;練習9 行、列の値を判定する関数 引数:行、列
(defun board-number-check (row col)
(cond ((and (numberp row) (numberp col))
(if (and (and (<= 0 row) (>= (1- Board-Size) row))
(and (<= 0 col) (>= (1- Board-Size) col)))
‘t ‘nil))
(t ‘nil)))
;実行例
;(board-number-check 0 0)
;T
;(board-number-check ‘a ‘b)
;NIL
;(board-number-check 4 0)
;NIL
;——————————————————————————————————–
;練習10
;実行例
;(othello-by-human)
;R/C 0 1 2 3
; 0 – – – –
; 1 – o * –
; 2 – * o –
; 3 – – – –
;(1) Enter row and col for *: 0 1
;R/C 0 1 2 3
; 0 – * – –
; 1 – * * –
; 2 – * o –
; 3 – – – –
;略
;(14) Enter row and col for o: 3 0
;R/C 0 1 2 3
; 0 o * * o
; 1 o * o *
; 2 o o * *
; 3 o * * *
;Game won by *
;Score is 9 – 7
;——————————————————————————————————–
;例題10 木の節点を表現するデータ構造をストラクチャで定義
(defstruct node
row col ;この盤面に至るための手
board ;ノードに対応する盤面
val ;盤面の評価値
)
;実行例
;>(setq node (make-node :board board-initial))
;#S(NODE ROW NIL COL NIL BOARD #2A((0 0 0 0) (0 -1 1 0) (0 1 -1 0) (0 0 0 0)) VAL NIL)
;>(node-val node)
;NIL
;>(setf (node-val node) 0)
;0
;>node
;#S(NODE ROW NIL COL NIL BOARD #2A((0 0 0 0) (0 -1 1 0) (0 1 -1 0) (0 0 0 0)) VAL 0)
;——————————————————————————————————–
;例題11 手番、手数において節点の盤面の評価値を返す関数 引数:節点、手番、手数
(defun eval-node (node turn count) 0)
;——————————————————————————————————–
;練習11 手数において節点の子節点のリストを返す関数 引数:節点、手番
(defun expand-node (node turn)
(let ((result nil))
(dotimes (row0 Board-Size (reverse result))
(dotimes (col0 Board-size)
(cond ((equal t (board-movable (node-board node) row0 col0 turn))
(setq result (cons (make-node :row row0 :col col0 :board (board-move (copy-board (node-board node)) row0 col0 turn)) result))))))))
;実行例
;>(expand-node (make-node :board Board-Initial) Board-Sente)
;(#S(NODE ROW 0 COL 1 BOARD
; #2A((0 1 0 0) (0 1 1 0) (0 1 -1 0) (0 0 0 0)) VAL NIL)
; #S(NODE ROW 1 COL 0 BOARD
; #2A((0 0 0 0) (1 1 1 0) (0 1 -1 0) (0 0 0 0)) VAL NIL)
; #S(NODE ROW 2 COL 3 BOARD
; #2A((0 0 0 0) (0 -1 1 0) (0 1 1 1) (0 0 0 0)) VAL NIL)
; #S(NODE ROW 3 COL 2 BOARD
; #2A((0 0 0 0) (0 -1 1 0) (0 1 1 0) (0 0 1 0)) VAL NIL))
;——————————————————————————————————–
;例題12 終局の状態を返す関数 引数:節点、手番、評価値
(defun node-state (node turn count) (board-state (node-board node) turn))
;——————————————————————————————————–
;練習12 minimax法により最良の次の節点を求める関数 引数:節点、手番、評価値、先読みを行う深さ
(defun minimax (node turn count depth)
(let ((state (node-state node turn count)))
(cond ((numberp state) (setf (node-val node) state) node)
((zerop depth) (setf (node-val node) (eval-node node turn count)) node)
((equal state ‘pass) (minimax node (change-turn turn) count depth))
(t (minimax-children (expand-node node turn)
turn count depth)))))
(defun minimax-children (children turn count depth)
(let ((new-turn (change-turn turn))
(new-depth (1- depth))
(new-count (1+ count)))
(do ((val nil) v (product nil))
((null children) product)
(setq v (node-val (minimax (car children) new-turn new-count new-depth)))
(cond ((or (null val)
(and (equal turn Board-Sente) (> v val))
(and (equal turn Board-Gote) (< v val)))
(setq val v)
(setq product (make-node
:row (node-row (car children))
:col (node-col (car children))
:board (node-board (car children))
:val val))))
(setq children (cdr children)))))
;実行例
;>(minimax (make-node :board Board-Initial) Board-Sente 1 2)
;#S(NODE ROW 0 COL 1 BOARD #2A((0 1 0 0) (0 1 1 0) (0 1 -1 0) (0 0 0 0)) VAL 0)
;——————————————————————————————————–
;例題13 人間とコンピュータが対戦するオセロゲーム関数 引数:手番、先読みを行う深さ
(defun othello (sente-gote yomi-depth)
(do ((board (copy-board Board-Initial))
(turn Board-Sente (change-turn turn))
(count 1 (1+ count))
state)
((numberp (setq state (board-state board turn)))
(game-result board state))
(print-board board)
(cond ((equal state ‘pass)
(format t “(~A) Pass.~%” count) (setq count (1- count)))
((or (equal sente-gote Board-Empty) (equal turn sente-gote))
(play-by-machine board turn count yomi-depth))
(t (play-by-human board turn count)))))
;——————————————————————————————————–
;練習13 次に打つ手をboardに設定する関数 引数:盤面、手番、手数、先読みを行う深さ
(defun play-by-machine (board turn count depth)
(let ((node (minimax (make-node :board board) turn count depth)))
(board-move board
(node-row node)
(node-col node)
turn
)
(format t “~% (~A) My move is ~A ~A~%” count
(node-row node)
(node-col node)
)))
;実行例
;>(setq board (copy-board Board-Initial))
;#2A((0 0 0 0) (0 -1 1 0) (0 1 -1 0) (0 0 0 0))
;>(play-by-machine board Board-Sente 1 2)
; (1) My move is 0 1
;>board
;#2A((0 1 0 0) (0 1 1 0) (0 1 -1 0) (0 0 0 0))