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

你应该稍微改变一下你的方法。您可以实现一些实用程序，而不是编写一个基本过程来完成所有事情。

对于极小极大过程，数据是在树中还是在列表中并不重要。因此，您可以自己编写一个过程，将树转换为像这样的列表。

 (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))))

进一步阅读 计算机程序的结构和解释。这是一本学习方案和一般编程的好书。