Haskell Recursive Minimax Tree

Я пытаюсь написать программу Tic Tac Toe в Haskell, используя алгоритм минимакса. Я построил мой собственный «Роза» в тип данных следующим образом:Haskell Recursive Minimax Tree

data Rose a = a :> [Rose a]

Это тип данных, в котором я хочу «магазин» мой минимаксное дерево. Я понимаю, как работает алгоритм минимакса, но не может реализовать его в рекурсивной функции.

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 [email protected](r :> []) = minimax p b 
minimax' p (r :> rs) = minimum(map root xs) :> xs 
    where xs = map (minimax p) rs

«Игрок» также тип данных, возведенных, который может иметь значение P1 или P2. Функция hasWinner проверяет, имеет ли данный «Совет» (тип данных, который может содержать плату Tic Tac Toe), и возвращает либо «Может быть, P1», либо «P2» или «Nothing».

Эта функция «минимакс», которую я написал, не дает мне ошибок, но результат неверен. Где ошибка в моей минимаксной реализации?

источник

2016-09-30 Felix

Вы не переключаетесь между двумя игроками правильно. minimax' p [email protected](r :> []) = minimax p b неправ. map (minimax p) rs в minimax' не переключается на другого игрока для максимизирующей половины.

Я бы рекомендовал написать это явно для P1 (пытаясь максимизировать) и P2 (пытаясь свести к минимуму).

Эндшпиль может назначить победителя, не заботясь о том, какой игрок в настоящее время играет

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

источник

2016-09-30 19:30:25 Cirdec

Привет, Cirdec, большое спасибо за ваш ответ. Ваш код кажется логичным, однако, когда я тестирую минимаксную функцию, предоставляющую P1 и примерную плату для ввода, мое минимаксное дерево заполняется «1». Но в примере у Совета действительно есть сценарии, в которых выигрывает P2, а это значит, что в дереве также должно быть «-1» ... Я дважды проверял, работает ли функция hasWinner, и после некоторых тестов кажется, что она работает правильно. – Felix

Если 'r' - это перемещение, выбранное' P1', 'rs' - это перемещение, доступное для' P2', 'P2' пытается« свести к минимуму ». Возможно, «P1» должен подумать о том, как другой игрок выбрал бы ход вместо того, чтобы выбрать один «P1», который лучше всего подходит для «P2». – Cirdec

Разве это не то же самое, что минимизировать движение P2? Как мне реализовать свою теорию в моем коде? – Felix

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

источник

2016-10-01 14:45:08 Felix

Haskell Recursive Minimax Tree

ответ

Смежные вопросы