Então eu estava lendo o livro Programming in Haskell de Graham Hutton. No capítulo 11, o jogo da velha é implementado. Minha pergunta é sobre a parte de IA do jogo, onde o minimax é usado. Fiquei um pouco confuso sobre a função prune:
prune :: Int -> Tree a -> Tree a
prune 0 (Node x _) = Node x []
prune n (Node x ts) = Node x [prune (n-1) t | t <- ts]
Por que precisamos de uma função de poda em Haskell (que tem avaliação preguiçosa). Por que não podemos simplesmente criar uma única árvore de jogo infinita e executar a função de fitness nela até uma certa profundidade, sem criar uma nova árvore finita por meio de poda? Podemos então reutilizar a mesma árvore, cortando-a do topo após cada movimento, e expandindo a (mesma) árvore para baixo. Isso também não deveria funcionar?
Vi então que um dos exercícios daquele capítulo era: gerar a árvore do jogo uma vez, e não para cada movimento
Uma solução para esse exercício é fornecida aqui por alguém no Github . Porém, parece-me que aqui uma nova árvore é gerada após cada movimento e, portanto, a árvore não é compartilhada durante todo o jogo.
Essencialmente, esta é uma função auxiliar que pode ser usada para pesquisar apenas um número limitado de níveis, pode pegar uma árvore gerada lentamente e podá-la de maneira preguiçosa. Portanto, se você tiver uma função que, por exemplo, determine a avaliação máxima de todos os nós de uma árvore de jogo, ela poderá entrar em um loop infinito porque a árvore tem uma profundidade infinita. Podemos especializar a função que determina a pontuação para verificar apenas até uma determinada profundidade, mas a
prune
função pode, portanto, ser usada como um pré-processador para garantir isso.Na solução, de fato parece gerar uma nova árvore a cada vez, você pode usar o subnó da árvore se fizer um movimento e assim reaproveitar a árvore do jogo que você já construiu.