Как создать функцию минимакса в Haskell? - PullRequest
Новая
       81

Как создать функцию минимакса в Haskell?

0 голосов
/ 28 сентября 2018

Я изо всех сил пытался создать минимаксную функцию в Haskell и не смог найти отличных альтернатив для SO, поэтому я спрашиваю:

Я хочу создать следующую функцию: 

minimax :: Player -> Rose Board -> Rose Int

Я хочу получить RoseTree of Integers, они должны быть 1, 0 или -1 (ход может быть хорошим, нейтральным или плохим для игрока, у которого есть ход. 

(root :> leaves)               -- constructor of a Rose
(board :> boards)              -- constructor of a Rose Board
(Int :> Ints)                  -- constructor of a Rose Int

Я написал функцию hasWinner, минимум 'и максимум', чтобы упростить задачу: 

hasWinner :: Board -> Maybe Player

minimum' :: [Int] -> Int
minimum' (x:xs) | x == -1 = -1
                | otherwise = minimum' xs

maximum' :: [Int] -> Int
maximum' (x:xs) | x == 1 = 1
                | otherwise = maximum' xs

Далее я думаю, что мой базовый случай следующий: 

minimax player (board :> []) = (0 :> [])

На данный моментвот где я нахожусь: 

minimax player (board :> boards)| maximum' [(isWinner player b (minimax' player)) | (b :> bs) <- boards] == 1 = _
                                | minimum' [(isWinner player b (minimax' player)) | (b :> bs) <- boards] == -1 = _
                                | otherwise = _
                 where   minimax' player     | player == P1 = P2
                                             | otherwise = P1
                         isWinner p1 board p2    | hasWinner board == Just p1 = 1
                                                 | hasWinner board == Just p2 = -1
                                                 | otherwise = 0

Я просто не могу понять, что должно произойти, когда я нашел доску, которая либо выиграна, проиграна или не имеет последствий. Так как бы я назвалснова минимаксная функция с правильной розовой доской?

Любая помощь очень ценится!

Рамон

1 Ответ

0 голосов
/ 28 сентября 2018

Я действительно нашел другой пост, обсуждающий ту же проблему, что и у меня здесь: Рекурсивное минимаксное дерево Haskell

Ответ был следующий: 

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

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

Я надеюсь нахотя бы это могло бы помочь кому-то еще в будущем.Функции, которые использовались в этом ответе: 

root :: Rose a -> a
root (a :> bs) = a 

nextPlayer :: Player -> Player
nextPlayer P1 = P2
nextPlayer P2 = P1

hasWinner :: Board -> Maybe Player

minimum :: Ord a => [a] -> a
maximum :: Ord a => [a] -> a

ура!

...