Haskell递归极小极大树

问题描述

我正在尝试使用minimax算法在Haskell中编写一个Tic Tac Toe程序.我构造了自己的"Rose a"数据类型，如下所示:

I'm trying to write a Tic Tac Toe program in Haskell, using the minimax algorithm. I constructed my own "Rose a" data type as follows:

data Rose a = a :> [Rose a]

这是我要存储"我的minimax树的数据类型.我了解minimax算法的工作原理，但似乎无法在递归函数中实现它.

This is the data type in which I want to 'store' my minimax tree. I understand how the minimax algorithm works, but can't seem to implement it in a recursive function.

minimax :: Player -> Rose Board -> Rose Int
minimax p (r :> [])   | hasWinner r == Just p              = 1  :> []
                      | hasWinner r == Just (nextPlayer p) = (-1) :> []
                      | otherwise                          = 0  :> []
minimax p (r :> rs)   = maximum(map root xs) :> xs
    where xs = map (minimax' (nextPlayer p)) rs

minimax' :: Player -> Rose Board -> Rose Int
minimax' p b@(r :> []) = minimax p b
minimax' p   (r :> rs) = minimum(map root xs) :> xs
    where xs = map (minimax p) rs

播放器"也是一种自构造的数据类型，其值可以为P1或P2. "hasWinner"功能检查给定的"Board"(可以容纳井字游戏板的数据类型)是否有获胜者，并返回Maybe P1或Maybe P2或Nothing.

The "Player" is also a self-constructed data type, which can be of value P1 or P2. The "hasWinner" function checks if a given "Board" (data type which can hold a Tic Tac Toe board) has a winner, and returns either Maybe P1 or Maybe P2, or Nothing.

我写的这个"minimax"函数没有给我错误，但是结果不正确. minimax实施中的缺陷在哪里?

This "minimax" function I wrote is not giving me errors, but the result is not correct. Where is the flaw in my minimax implementation?

推荐答案

您没有正确在两个播放器之间切换. minimax' p b@(r :> []) = minimax p b是错误的. minimax'中的map (minimax p) rs不会切换到其他播放器以最大化一半.

You aren't switching between the two players correctly. minimax' p b@(r :> []) = minimax p b is wrong. map (minimax p) rs in minimax' doesn't switch to the other player for the maximizing half.

我建议为P1(尝试最大化)和P2(尝试最小化)明确地写出这一点.

I'd recommend writing this out explicitly for P1 (trying to maximize) and P2 (trying to minimize).

最终游戏可以分配获胜者而无需关心当前正在玩的玩家

The endgame can assign the winner without caring about which player is currently playing

minimax :: Player -> Rose Board -> Rose Int
minimax p (r :> [])   | hasWinner r == Just P1 = 1    :> []
                      | hasWinner r == Just P2 = (-1) :> []
                      | otherwise              = 0    :> []

玩家P1试图最大化

minimax P1 (r :> rs) = maximum (map root xs) :> xs
    where xs = map (minimax (nextPlayer p)) rs

玩家P2试图最小化

minimax P2 (r :> rs) = minimum (map root xs) :> xs
    where xs = map (minimax (nextPlayer p)) rs

这篇关于Haskell递归极小极大树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！