Minimax算法不起作用
问题描述:
我使用Realm of Racket书中给出的存根作为基础,构建了一个tick-tack-toe游戏的AI。到目前为止,一切都进展顺利。但是,当我尝试在树的根上运行我的minimax
函数时,它将返回可以通过运行它获得的最低可能值列表(以任一播放器作为谓词)。
下面是函数的代码转储:Minimax算法不起作用
(define (minimax tree player depth)
(define (generate-score tree player depth)
(define won (winner (ttt-tree-board tree)))
(if (<= depth 0) 0
(+ (cond
[(equal? won player) 1]
[(false? won) 0]
[else -1])
(apply +
(for/list ([t (ttt-tree-moves tree)])
(generate-score (second t) player (sub1 depth)))))))
(for/list ([t (ttt-tree-moves tree)])
(generate-score (second t) player depth)))
这只是我的minimax
功能,因为没有其他人(除了winner
)的需要显示。这是winner
:
(define (winner board)
(or
(ormap (lambda (row) (if (all-equal? row) (first row) #f)) board) ; Horizontal
(ormap (lambda (i) (if ; Vertical
(all-equal? (map (lambda (j) (list-ref (list-ref board j) i)) (stream->list (in-range (length board)))))
(list-ref (first board) i) #f))
(stream->list (in-range (length board))))
(if ; Diagonal
(all-equal? (map (lambda (i) (list-ref (list-ref board i) i)) (stream->list (in-range (length board)))))
(first (first board)) #f)
(if ; Diagonal cont.
(all-equal? (map (lambda (i) (list-ref (reverse (list-ref board i)) i)) (stream->list (in-range (length board)))))
(last (first board)) #f)))
(这是一个有点草率,因此,如果任何人有一个想法,把它缩短,告诉我你的建议)ttt-tree
结构遵循此模式:
(ttt-tree board moves)
在其中board
是与tick-tack-toe板(形式为'((X - O) (O X -) (- X O))
)相对应的2D阵列,并且moves
是可以从该节点制作的可能移动的列表,其中每个移动都是具有两个元素的列表:位置那改变了,并且ttt-tree
形成下一个节点。所以(second t)
指到下一个节点,如果t
是(list-ref (ttt-tree-moves #<ttt-tree>) x)
我最初的想法是,有可能是在cond
一些错误,但我使用equal?
不eq?
,所以我看不出这将是一个问题。另一种可能性是我错误地定义了winner
,但我已经测试了很多次,所以我不知道会出现什么问题。请帮忙!
(我全码:http://paste.ofcode.org/AYez79zTQksys3CU7KJBZV)
答
事实证明,问题是,在我的winner
功能,我从来没有检查,如果冠军是"-"
,空瓦。因此,在大多数情况下会触发else子句并导致-1分。