list - Scheme/Racket/Lisp 中嵌套列表的 Minimax 操作？

Question

我正在尝试编写一个函数来分析博弈树。树由嵌套列表表示，其中每个子列表代表一个分支。基本上，我想弄清楚两件事:

1. 嵌套列表的最小最大值是多少？
2. 该值的索引是什么？

我以为我已经基本解决了第一个问题，但我的代码一直返回错误的值——我检查了所有内容，看不出我做错了什么。

非常感谢任何帮助，谢谢!

;MINIMAX*
(define minimax*
  (lambda (l operation hilo)
    (cond
      ((null? l) hilo)
      ((equal? operation 'max)
       (cond
         ((null? (cdr l)) (if
                           (list? (car l))
                           (minimax* (car l) 'min hilo)
                           (if
                            (> (car l) hilo)
                            (car l)
                            hilo)))
         (else (if
                (list? (car l))
                (if
                 (> (minimax* (car l) 'min hilo) hilo)
                 (minimax* (cdr l) 'max (minimax* (car l) 'min hilo))
                 (minimax* (cdr l) 'max hilo))
                (if
                 (> (car l) hilo)
                 (minimax* (cdr l) 'max (car l))
                 (minimax* (cdr l) 'max hilo))))))
      ((equal? operation 'min)
       (cond
         ((null? (cdr l)) (if
                           (list? (car l))
                           (minimax* (car l) 'max hilo)
                           (if
                            (< (car l) hilo)
                            (car l)
                            hilo)))
         (else (if
                (list? (car l))
                (if
                 (< (minimax* (car l) 'max hilo) hilo)
                 (minimax* (cdr l) 'min (minimax* (car l) 'max hilo))
                 (minimax* (cdr l) 'min hilo))
                (if
                 (< (car l) hilo)
                 (minimax* (cdr l) 'min (car l))
                 (minimax* (cdr l) 'min hilo))))))
      (else (error "Invalid operation type, must be 'max or 'min")))))

Answer 1

你应该稍微改变一下你的方法。您可以实现一些实用程序，而不是编写一个构成一切的基本程序。

对于 minimax 过程，数据是在树中还是列表中并不重要。所以你可以自己编写一个程序，将你的树转换成这样的列表

 (define (fringe t)
   (cond ((null? t) t)
     ((pair? (car t)) (append (fringe (car t)) 
                      (fringe (cdr t))))
     (else (cons (car t) (fringe (cdr t))))))

检查最小值或最大值基本上是对列表或树的迭代。所以你可以用 fold 来做到这一点。参见 http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Reduction-of-Lists.html

所以你可以这样写你的程序:

(define (minimax op t)
  (let ((flat-list (fringe t)))
    (fold op (car t) (cdr t))))

进一步阅读 Structure and Interpretation of Computer Programs .这是一本学习 Scheme 和一般编程的好书。