Haskell Recursive Minimax Tree

Question

私は、minimaxアルゴリズムを使ってHaskellでTic Tac Toeプログラムを書こうとしています。私は次のようにデータ型「ローズ」自分を構築：

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

「プレーヤー」はまた、値P1又はP2のものとすることができる自己構成されたデータ型です。 "hasWinner"関数は、指定された "Board"（Tic Tac Toeボードを保持できるデータ型）が勝者を持っているかどうかをチェックし、P1またはP2、またはNothingを返します。

私が書いたこの「ミニマックス」機能は私にエラーを与えているわけではありませんが、結果は正しくありません。私のminimax実装の欠陥はどこですか？

Answer 1

2人のプレーヤーを正しく切り替えることはできません。 minimax' p b@(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 

Answer 2

を最小化しようとしています

多くのテストと混乱して、ゲームツリーを作った機能にいくつかの欠陥があることが分かりました。デバッグした後、Cirdecが提案したアルゴリズムが正しく動作しました！