4

遺伝的アルゴリズムを使用して、三目並べのすべての可能なゲームを再帰的に再生し、（勝ち、負け、引き分け）のタプルを返す関数を作成しようとしています。ただし、以下の関数は、次のように呼び出されると常にスタックをオーバーフローします。

scoreOne :: UnscoredPlayer -> [String] -> ScoredPlayer
scoreOne player boards = ScoredPlayer (token player) (chromosome player) (evaluateG $!             testPlayer player boards)
...
let results = map (\x->scoreOne x boards) players
print (maximum results)

ここplayersで、は染色体のリストです。オーバーフローは、1人のプレーヤーだけでは発生しませんが、2人のプレーヤーでは発生します。

編集：関数が次のように呼び出された場合、スタックはオーバーフローしません。

let results = map (\player -> evaluateG (testPlayer player boards)) players
print (maximum results)

ただし、次の方法ではスタックがオーバーフローします。

let results = map (\player -> ScoredPlayer (token player) (chromosome player) (evaluateG $! testPlayer player boards)) players

参考までに、ScoredPlayerは次のように定義されます（文字列はプレーヤートークン、[Int]は染色体、Floatはスコア）：

data ScoredPlayer = ScoredPlayer String ![Int] !Float deriving (Eq)

Haskellについて私が知っていることから、私が使用している呼び出しは関数の結果に対してさらに処理を実行しているplayAll'ため、関数は末尾再帰ではありません。ただし、可能なすべてのゲームを確実にプレイする必要があるため、呼び出しfoldl'を削除する方法がわかりません。foldl'関数を末尾再帰になるように（または少なくともスタックをオーバーフローさせないように）再構築する方法はありますか？

事前に感謝し、大量のコードリストをお詫びします。

playAll' :: (Num a) => UnscoredPlayer -> Bool -> String -> [String] -> (a,a,a) ->    (a,a,a)
playAll' player playerTurn board boards (w,ls,t)= 
    if won == self then (w+1,ls,t) -- I won this game
    else
        if won == enemy then (w,ls+1,t) -- My enemy won this game
        else
            if '_' `notElem` board then (w,ls,t+1) -- It's a tie
            else
                if playerTurn then --My turn; make a move and try all possible combinations for the enemy
                    playAll' player False (makeMove ...) boards (w,ls,t)
                else --Try each possible move against myself
                    (foldl' (\(x,y,z) (s1,s2,s3) -> (x+s1,y+s2,z+s3)) (w,ls,t)
                        [playAll' player True newBoard boards (w,ls,t)| newBoard <- (permute enemy board)])
    where
        won = winning board --if someone has one, who is it?
        enemy = (opposite.token) player --what player is my enemy?
        self = token player --what player am I?
4

1 に答える 1

6

foldl'関数は末尾再帰ですが、問題はそれが十分に厳密ではないということです。これは、ドン・スチュワートがコメントで言及している問題です。

Haskellのデータ構造を怠惰なボックスと考えてください。新しいコンストラクターごとに新しいボックスが作成されます。あなたがのような折り目を持っているとき

foldl' (\(x,y,z) (s1,s2,s3) -> (x+s1,y+s2,z+s3))

タプルは1つのボックスであり、タプル内の各要素は別のボックスです。からの厳密さfoldl'は、最も外側のボックスのみを削除します。タプル内の各要素は、まだレイジーボックス内にあります。

これを回避するには、余分なボックスを削除するために、より深い厳密さを適用する必要があります。ドンの提案は作ることです

data R = R !Int !Int !Int

foldl' (\(R x y z) (s1,s2,s3) -> R (x+s1) (y+s2) (z+s3))

これで、の厳密さfoldl'は十分です。Rの個々の要素は厳密であるため、最も外側のボックス（Rコンストラクター）を削除すると、内部の3つの値も評価されます。

私が提供できるすべてのコードをこれ以上見ることなく。このリストを実行できなかったので、これで問題が解決するのか、プログラム全体に他の問題があるのか​​わかりません。

スタイルのポイントとして、ネストされたものの代わりにif、次のことをお勧めします。

playAll' player playerTurn board boards (w,ls,t)=
  case () of
    _ | won == self -> (w+1,ls,t) -- I won this game
    _ | won == enemy -> (w,ls+1,t) -- My enemy won this game
    _ | '_' `notElem` board -> (w,ls,t+1) -- It's a tie 
    _ -> ... --code omitted
于 2010-10-06T23:44:44.073 に答える