プログラミングを頑張る日記

プログラミングを勉強して、ハッカーになろう

Common Lispを頑張る(56)

2019年はいっぱい勉強します。頑張ります。
「Land of Lisp」のダイス・オブ・ドゥームの作成を続けます。

ゲーム盤を表現する部分は前に書きました。核となる部分に着手していきます。
そこでは関数型プログラミングテクニックの力を活用していくようです。
つまりゲーム盤の表現を含むデータの塊を受けとり、新たなゲーム盤の状態を返す
関数呼び出しの連鎖としてゲームを構築していきます。
そしてそれによりゲームルールエンジンは他の部分から完全に独立させることができます。
この手法の強力さを理解するためにまずはAIプレイヤーから作るようです。

と、実際に手を動かす前にこれから作る必要があるものについてもっとよく考えます。
まずは人間のターンを処理してくれる部分、AIのターンを処理する部分の2つは絶対に必要です。
2つは両方ともゲームのルールをその部分が理解してくれている必要があります。
つまり、ルールエンジンを作り、人間とAIのターンを司るものがそこにアクセスするようにすれば
ゲームエンジン部分は3個の大きな塊に綺麗に分離できるのではないでしょうか、
そして関数型プログラミングならその分離が綺麗に行えるようです。
ルールコードを遅延ゲームツリーとやらに展開することがそれが可能になるそうです、やった!
といいたいところですが、この章で作るゲームツリーはまだ遅延評価を使わないそう。
後々学んで実装するときにこの設計がもの凄いことを思いしるそうなのでお楽しみですね。

ゲームツリーの生成

ゲームのルールセットの全てを表現する関数がこちら。

CL-USER> (defun game-tree (board player spare-dice first-move)
           (list player
                 board
                 (add-passing-move board
                                   player
                                   spare-dice
                                   first-move
                                   (attacking-moves board player spare-dice))))
; in: DEFUN GAME-TREE
;     (ADD-PASSING-MOVE BOARD PLAYER SPARE-DICE FIRST-MOVE
;      (ATTACKING-MOVES BOARD PLAYER SPARE-DICE))
; 
; caught STYLE-WARNING:
;   undefined function: ADD-PASSING-MOVE

;     (ATTACKING-MOVES BOARD PLAYER SPARE-DICE)
; 
; caught STYLE-WARNING:
;   undefined function: ATTACKING-MOVES
; 
; compilation unit finished
;   Undefined functions:
;     ADD-PASSING-MOVE ATTACKING-MOVES
;   caught 2 STYLE-WARNING conditions
GAME-TREE
CL-USER>

…? 難しいなあ。
game-treeは、与えられた初期条件から全ての可能な指し手を表現する木構造を作るそう。
ああ、こんなことをするから最初のバージョンは2*2マスでの実装なんですかね。
引数は、盤面の状態、現在ターンのプレイヤー、現在のターンで獲得されたサイコロの数、
現在のプレイヤーのターンになってから行動したかどうか、の4つです。
プレイヤーが取れる手は2つ、ターンを終了するか、攻撃するか。
ターン終了はadd-passing-moveで、攻撃はattacking-movesです。
ターン終了するには最低一回は攻撃している必要あります。
だから攻撃の関数がターン終了の関数の中にあるんですかね。

それではターン終了の関数を見ていきます。

CL-USER> (defun add-passing-move (board player spare-dice first-move moves)
           (if first-move               ;もしターンの最初なら
               moves                    ;攻撃に入る
               (cons (list nil          ;手をゲームツリーに加える。ターン終了はnil
                           (game-tree (add-new-dice board player (1- spare-dice))
                                      (mod (1+ player) *num-players*)
                                      0
                                      t))
                     moves)))
; in: DEFUN ADD-PASSING-MOVE
;     (ADD-NEW-DICE BOARD PLAYER (1- SPARE-DICE))
; 
; caught STYLE-WARNING:
;   undefined function: ADD-NEW-DICE
; 
; compilation unit finished
;   Undefined function:
;     ADD-NEW-DICE
;   caught 1 STYLE-WARNING condition
ADD-PASSING-MOVE
CL-USER>

やっぱりよくわからないぞ。game-tree関数を再帰的に呼び出しているのはいいんですが…。
ああ、最後のmoveは、ターンを終了せずに再度攻撃した場合のゲームツリーを表現するのか。
ターン終了の関数とか言ってるのがよくない気がします。
参考書通り、「相手に手番を渡すという指し手をゲーム木に加える関数」と表現した方が理解できそう。
add-new-dice関数はターン終了時の盤面に更新するための関数ですね。未定義ですが。
その真下では次のプレイヤーに回すための処理ですね。プレイヤーが2人より多くなっても対応できます。

それでは「可能な攻撃の指し手をゲーム木に追加する関数」です。

CL-USER> (defun attacking-moves (board cur-player spare-dice)
           (labels ((player (pos)
                      (car (aref board pos))) ;引数番目のマスの所有プレイヤーを返す
                    (dice (pos)
                      (cadr (aref board pos)))) ;引数番目のマスのサイコロの数を返す
             (mapcan (lambda (src)              
                       (when (eq (player src) cur-player) ;引数のマスがプレイヤーのものなら
                         (mapcan (lambda (dst)
                                   (when (and (not (eq (player dst) cur-player))
                                              (> (dice src) (dice dst))) ;そして攻撃可能なら
                                     (list ;mapcanのためにリストにする
                                      (list (list src dst)
                                            (game-tree (board-attack board cur-player ;攻撃後の盤面の状態を
                                                                     src dst (dice src)) ;渡しているのだと思う
                                                       cur-player
                                                       (+ spare-dice (dice dst))
                                                       nil)))))
                                 (neighbors src)))) ;隣接するマスのリストを作っているのだろう
                     (loop for n below *board-hexnum*
                          collect n)))) ;全マスを走査
; in: DEFUN ATTACKING-MOVES
;     (BOARD-ATTACK BOARD CUR-PLAYER SRC DST (DICE SRC))
; 
; caught STYLE-WARNING:
;   undefined function: BOARD-ATTACK

;     (NEIGHBORS SRC)
; 
; caught STYLE-WARNING:
;   undefined function: NEIGHBORS
; 
; compilation unit finished
;   Undefined functions:
;     BOARD-ATTACK NEIGHBORS
;   caught 2 STYLE-WARNING conditions
ATTACKING-MOVES
CL-USER>

mapcanは確か返ってきたリストたちを一つのリストにまとめるのだったような。
mapcanが入れ子になっていますが、外側のもので全マスを走査して内側で1マス1マスの
隣接するマスを対象に攻撃可能か判定し攻撃可能なら攻撃後のゲームツリーを作るって感じですね。
ちょっととまどいました。複雑そうな関数を見るとひるんでしまう癖を直したいですね。

さ、今でた隣接するマスを見つける関数を書きます。

CL-USER> (defun neighbors (pos)
           (let ((up (- pos *board-size*)) ;対象のマスの上下を定義
                 (down (+ pos *board-size*)))
             (loop for p in (append (list up down)
                                    (unless (zerop (mod pos *board-size*)) ;posが左端でなければ
                                      (list (1- up) (1- pos))) ;左上と左側のマスを追加
                                    (unless (zerop (mod (1+ pos) *board-size*)) ;posが右端でなければ
                                      (list (1+ pos) (1+ down)))) ;右側と右下のマスを追加
                  when (and (>= p 0) (< p *board-hexnum*))
                  collect p)))          ;ゲーム盤に収まるマスを集めてリストにする
NEIGHBORS
CL-USER>

特につけ足すコメントはないですね。

攻撃を行う関数を書くとします。

CL-USER> (defun board-attack (board player src dst dice)
           (board-array (loop for pos from 0
                             for hex across board ;acrossは配列から値を取り出すためのもの
                             collect (cond ((eq pos src) (list player 1)) ;攻撃元ならサイコロ1個に
                                           ((eq pos dst) (list player (1- dice))) ;攻撃先なら攻撃元のサイコロ-1
                                           (t hex))))) ;それ以外ならそのまま
BOARD-ATTACK
CL-USER>

なんとか理解できます。ちょっと動かしてみます。

CL-USER> (draw-board #((0 3) (0 3) (1 3) (1 1)))
  a-3 a-3 
 b-3 b-1 
NIL
CL-USER> (board-attack #((0 3) (0 3) (1 3) (1 1)) 0 1 3 3)
#((0 3) (0 1) (1 3) (0 2))
CL-USER> (draw-board #((0 3) (0 1) (1 3) (0 2)))
  a-3 a-1 
 b-3 a-2 
NIL
CL-USER>

上で描写した状態からプレイヤーaで、右上から右下に攻撃を仕掛けました。
攻撃後の状態を描写したものが下のものなので、合っていますね。よしよし。

さて、あとはターンの終わりにサイコロを補給してくれる処理も必要です。
補給するためには、盤面を走査していき、ターンを終えようとしているプレイヤーのマスをみつけたら、
そのターン中に獲得したサイコロ-1個になるまで補給を続けるという処理が必要です。
つまり、補給している間は残りの補給可能数を記録しなくてはなりません。
手続き型に汚染された頭は、専用の変数を作り、補給をするたびにその数を減らす、
というようなことをまっ先に考えてしまいますが、それは関数型プログラミングスタイルではありえません。
それが封じられるとなると、再帰的に呼び出される関数を定義し、
引数に残り補給数を貰って減らして再帰するというような方法が次に思いつきますが、どうでしょう。

CL-USER> (defun add-new-dice (board player spare-dice)
           (labels ((f (lst n)
                      (cond ((null lst) nil) ;再帰の終了条件
                            ((zerop n) lst)  ;補給可能数が0なら何もしない
                            (t (let ((cur-player (caar lst)) ;走査中のマスを所有するプレイヤー
                                     (cur-dice (cadar lst))) ;走査中のマスのダイス数
                                 (if (and (eq cur-player player) (< cur-dice *max-dice*))
                                     (cons (list cur-player (1+ cur-dice)) ;補給して
                                           (f (cdr lst) (1- n)))           ;再帰を続ける
                                     (cons (car lst) (f (cdr lst) n)))))))) ;今回は変更なし、再帰続行
             (board-array (f (coerce board 'list) spare-dice)))) ;配列で受け取った盤面をリストにし処理を行なう、最終的には配列で返す
ADD-NEW-DICE
CL-USER>

ふう、これでルールエンジンの部分は実装できた気がします。
続きの対戦のための部分はまた明日。