Haskell遞歸極大極小樹

我想在Haskell中使用極小極大算法編寫井字節程序。我建立我自己的「玫瑰」數據類型，如下所示：Haskell遞歸極大極小樹

data Rose a = a :> [Rose a]

這是我想「商店」我最小最大樹中的數據類型。我理解minimax算法是如何工作的，但似乎無法在遞歸函數中實現它。

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」函數檢查給定的「Board」（可以容納井字棋牌的數據類型）是否具有贏家，並且返回Maybe P1或Maybe P2或Nothing。

我寫的這個「minimax」函數並沒有給我錯誤，但結果是不正確的。我的minimax實施中的缺陷在哪裏？

來源

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和示例Board輸入的極小極大函數時，你的代碼似乎是合乎邏輯的，我的極大極小樹填充了'1'。但是示例Board實際上有P2獲勝的場景，這意味着樹中應該有'-1'......我仔細檢查了「hasWinner」函數是否工作，並且經過一些測試，似乎工作正常。 – Felix

如果'r'是由'P1'選擇的移動，'rs'是可用於'P2'的移動，'P2'正嘗試'最小化'。也許'P1'需要考慮另一個玩家如何選擇一個移動，而不是選擇一個最適合'P2'的P1。 – Cirdec

這與P2的移動最小化並不相同嗎？我如何在你的代碼中實現你的理論？ – Felix

經過大量的測試和存在困惑，我發現創建遊戲樹的函數有一些缺陷。調試完成後，Cirdec建議的算法正常工作！

來源

2016-10-01 14:45:08 Felix

Haskell遞歸極大極小樹

回答

相關問題