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嵌套列表上的操作？

回答

相關問題