【CLドリル】8 リスト処理 (その2)

• 8.2.6 ミニマックス手続き
  
  
  
  • これ、問題文の意味すらわからないのでメモ。。。
    
  • 不完全なゲーム木にて、考えられるすべての次の局面から最良の次の手を決める、というお話。
    
  • 局面の評価関数f(x)というものを用意する。
    
  • その局面の手番のプレイヤーが勝つ確立を見積るための関数。
    
  • 二人の対戦者をAとBと呼ぶ。
    
  • Aの手番である局面xにて、Aが勝つ勝率p(x)は、f(x)。よってBが勝つ勝率は1-f(x)。
    
  • これらを前提としてミニマックス手続き、というのを導入する。
    
    
  • ミニマックス手続き
    
  • 局面xに対して、後続可能な局面をy1,...,ynとする。
    
  • Aの手番である局面xにおいては、勝つように最良の手を選択するので、p(y1),...,p(yn)の最大値をp(x)とする。
    
  • かわって、Bの手番である局面xにおいては、Bは負けないように、p(y1),...,p(yn)の最小値の局面を選択するものとし、それがp(x)となる。
    
    
  • お題は、
    「評価関数と(不完全な)ゲーム木を与えられ、ミニマックス手続きを使ってA(ゲーム・プログラム)の手番で初めた場合とB(対戦者)の手番で初めた場合のAの勝率をそれぞれ求めるestimate-my-turnとestimate-his-turnという関数を定義せよ」
    ということ。
    
    
  • ゲーム木は、( 《局面》《次の局面1》...《次の局面n》)の形のリストによって表現すること。
    
  • 末葉は(《局面》)とする。
    
  • 不完全なゲーム木は、それが先読み深さというか、探索範囲であるのだと理解する。(問題文はちょっと曖昧なので)
    
  • すると、末葉に評価関数を適用して、それが属する枝がAの手番かBの手番かによって、その枝に属する葉の中から選択すべき葉を選び(ミニマックス)、その選んだ評価をその枝の評価とする、ということを再帰的に繰返していくのだろう。
    
    
  • なんとなくわかった。
    
  • ついでなんで、自分なりのプログラムを載せておく。
    

    
    (defun estimate-my-turn (eval-fun tree)
      (if (null (second tree))
          (funcall eval-fun (car tree))
        (apply #'max (mapcar #'(lambda (x)
                                 (estimate-his-turn eval-fun x))
                             (cdr tree)))))
    
    
    (defun estimate-his-turn (eval-fun tree)
      (if (null (second tree))
          (funcall eval-fun (car tree))
        (apply #'min (mapcar #'(lambda (x)
                                 (estimate-my-turn eval-fun x))
                             (cdr tree)))))
    
    (defun nim (n)
      (case n
       (0 '(0))
       (1 '(1 (0)))
       (2 '(2 (1 (0))
            (0)))
       (t (list n
                (nim (- n 1))
                (nim (- n 2))
                (nim (- n 3))))))
    
    (defun estimate-my-turn-for-nim (n)
      (estimate-my-turn #'(lambda (x) 1) (nim n)))
    
    (defun estimate-his-turn-for-nim (n)
      (estimate-his-turn #'(lambda (x) 1) (nim n)))
    

    
    
  • 解答をみると、、、だいたい一緒だった!
    
  
  

ミニマックスの理解に時間がかかった。。。
こつこつ。