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

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

Common Lispを頑張る(58)

それではやっていきます、「Land of Lisp」。
今日の目標は、コンピュータによる対戦相手を実装することです。

AIプレイヤー(?)の実装

AIはどう手を選べばいいのでしょうか、それには次のような戦略が使えるといいます。
・可能な手それぞれについて、その手を指すことで生じる盤面の状態に点数をつけ、最も高い点数の手を選ぶ
盤面の状態の点数化は、そこからゲーム終了までゲームツリーを見て、勝つことのできる手なら点数をつける、
という風にすればよいでしょう。
これは相手の手について考えるときにも同じように考えることができ、相手の手に点数をつけるときも同じようにし、
ただしその中で一番点数の低い手(AIにとって悪い手)を常に選んでくる、という風にしてあげれば
相手の手を読んで手を選択する、みたいな動作ができるはずです。
なるほどなあ、と感心しています。

CL-USER> (defun rate-position (tree player)
           (let ((moves (caddr tree)))
             (if moves                  ;指せる手があるか?
                 (apply (if (eq (car tree) player) ;指し手によって最大を取るか最小を取るか
                            #'max
                            #'min)
                        (get-ratings tree player))
                 (let ((w (winners (cadr tree)))) ;ツリーの最後まで来た
                   (if (member player w)          ;勝者の一覧に自分がいるか?
                       (/ 1 (length w))           ;勝者で1点を分けあう
                       0)))))                     ;勝ってなきゃ0点
; in: DEFUN RATE-POSITION
;     (GET-RATINGS TREE PLAYER)
; 
; caught STYLE-WARNING:
;   undefined function: GET-RATINGS
; 
; compilation unit finished
;   Undefined function:
;     GET-RATINGS
;   caught 1 STYLE-WARNING condition
RATE-POSITION
CL-USER> (defun get-ratings (tree player)
           (mapcar (lambda (move)
                     (rate-position (cadr move) player)) ;受けとったツリーの今の全ての枝に
                   (caddr tree)))                        ;rate-positionを実行
GET-RATINGS
CL-USER>

よし、もうAIの頭脳の部分は出来たといっていいでしょう。
それでは実際に上の関数を利用して手を選択する部分を作成します。

CL-USER> (defun handle-computer (tree)
           (let ((ratings (get-ratings tree (car tree)))) ;可能な指し手の点数のリストをratingsとする
             (cadr (nth (position (apply #'max ratings) ratings) (caddr tree))))) ;一番点数の高い最初のツリーを返す
HANDLE-COMPUTER
CL-USER>

3行目で一瞬悩みましたが、ratingsの最大値の場所を調べて同じ位置にあるツリーを返しているということですね。

じゃあ、残りは対戦を司る部分。

CL-USER> (defun play-vs-computer (tree)
           (print-info tree)
           (cond ((null (caddr tree)) (announce-winner (cadr tree))) ;もう手がなければ決着のアナウンス
                 ((zerop (car tree)) (play-vs-computer (handle-human tree))) ;人間の手番なら人間にターンを渡して再帰
                 (t (play-vs-computer (handle-computer tree))))) ;それ意外ならAIのターンのあと再帰
PLAY-VS-COMPUTER
CL-USER>

完成です! 嬉しい。なんか強そうな気がするんですが遊んでみます。

CL-USER> (play-vs-computer (game-tree (gen-board) 0 0 t))
current player = a
    b-3 b-2 
  a-2 a-3 
choose your move:
1. 3 -> 1
1
current player = a
    b-3 a-2 
  a-2 a-1 
choose your move:
1. end turn
1
current player = b
    b-3 a-3 
  a-2 a-1 
current player = b
    b-1 a-3 
  b-2 a-1 
current player = a
    b-2 a-3 
  b-2 a-1 
choose your move:
1. 1 -> 0
1
current player = a
    a-2 a-1 
  b-2 a-1 
choose your move:
1. end turn
1
current player = b
    a-3 a-1 
  b-2 a-1 
current player = b
    a-3 a-1 
  b-1 b-1 
current player = a
    a-3 a-1 
  b-1 b-1 
choose your move:
1. 0 -> 2
2. 0 -> 3
1
current player = a
    a-1 a-1 
  a-2 b-1 
choose your move:
1. end turn
2. 2 -> 3
2
current player = a
    a-1 a-1 
  a-1 a-1 
choose your move:
1. end turn
1
current player = b
    a-2 a-1 
  a-1 a-1 
The winner is a
NIL
CL-USER>

普通に遊べるクオリティではあります。甘すぎかもしれません。
まあ、面白くてたまらないというレベルではありませんけど、ちゃんと動いているというのが大事です。

なぜ面白くないのか。単純にゲーム盤が小さいというのが大きな理由ですね。
せっかくのAIなのにゲーム性が広がりません。
おっきくしましょう。とりあえず3*3でいいかな。

CL-USER> (defparameter *board-size* 3)
*BOARD-SIZE*
CL-USER> *board-hexnum*
4
CL-USER> (defparameter *board-hexnum* (* *board-size* *board-size*))
*BOARD-HEXNUM*
CL-USER>

よし、ゲーム盤を縦横1マスずつ拡張しました。
遊んでみます。

CL-USER> (play-vs-computer (game-tree (gen-board) 0 0 t))
current player = a
      b-2 b-3 a-1 
    b-2 a-2 a-1 
  a-1 b-1 b-2 
choose your move:
1. 4 -> 7
1
current player = a
      b-2 b-3 a-1 
    b-2 a-1 a-1 
  a-1 a-1 b-2 
choose your move:
1. end turn
1
current player = b
      b-2 b-3 a-1 
    b-2 a-1 a-1 
  a-1 a-1 b-2 
current player = b
      b-1 b-3 a-1 
    b-2 b-1 a-1 
  a-1 a-1 b-2 
current player = a
      b-1 b-3 a-1 
    b-2 b-1 a-1 
  a-1 a-1 b-2 
The winner is b
NIL
CL-USER> (play-vs-computer (game-tree (gen-board) 0 0 t))

返ってこなくなりました。1回目みたいにすぐ終わるゲームでなければ
ゲームツリーの生成に相当時間がかかってしまうようです。

遊べなくなってしまっては、もはやゲームとして成り立ちません。悲しい…。

というわけで次回からは、高速化・効率化をしていきます。