Minimax在Scheme/Racket/Lisp嵌套列表上的操作？

我正在尝试编写一个函数来分析游戏树。树由嵌套列表表示，其中每个子列表表示一个分支。基本上，我想弄清两件事：Minimax在Scheme/Racket/Lisp嵌套列表上的操作？

什么是嵌套列表的最小值？
该值的指数是什么？

我以为我主要解决了第一个问题，但我的代码不断返回错误的值 - 我检查了一切，看不到我做错了什么。

任何帮助将不胜感激，谢谢！

;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")))))

来源

2011-03-08 CommonTragedian

你可以先做的一件事是简化代码。在Racket中有'argmin'和'argmax'函数可以返回列表的最小和最大元素，所以你不需要自己编写这些函数。还有'min'和'max'作为功能直接使用。如果您正在执行minimax算法而不是alpha-beta修剪，那么您可以使用递归“map”操作编写一个函数，该操作将更加简单。 – 2011-03-08 02:22:50

或采取另一种数据结构，如记录。 – Sebastian 2011-08-03 14:07:05

如果您发布了一些输入和您的预期输出值的示例，这将有所帮助。 – soegaard 2011-10-22 13:07:03

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

对于最小极大值过程，数据是来自树还是列表并不重要。所以，你可以写你自己，你的转换器树成一个列表像这样的

(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。这是一本学习计划和一般编程的好书。

来源

2014-02-12 18:42:31

Minimax在Scheme/Racket/Lisp嵌套列表上的操作？

回答

相关问题