So I was reading the book Programming in Haskell by Graham Hutton. In chapter 11, the game tic-tac-toe is implemented. My question is about the AI part of the game, where minimax is used. I was a little bit confused about the prune function:
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]
Why do we need such a prune function in Haskell (which has lazy evaluation). Why can't we just create a single infinite game tree, and run the fitness function on it to a certain depth, without creating a new finite tree via pruning? We can then reuse the same tree, by cutting it from the top after each move, and sort of expanding the (same) tree downwards. Shouldn't this also work?
I then saw that one of the exercises of that chapter was: generate the game tree once, rather than for each move
A solution for that exercise is provided here by someone on Github. However, it seems to me that here a new tree is generated after each move, and thus the tree is not shared during the whole game.
Why do we need such a prune function in Haskell (which has lazy evaluation).
Essentially this is a helper function that can be used to search only a limited number of levels, it can take a lazy generated tree, and will prune it in a lazy manner. So if you have a function that for example determines the maximum evaluation of all nodes of a game tree, then that can go into an infinite loop because the tree has an infinite depth. We can specialize the function that determines the score to only check up to a given depth, but the prune function can thus be used as a pre-processor to ensure this.
A solution for that exercise is provided here by someone on Github. However, it seems to me that here a new tree is generated after each move, and thus the tree is not shared during the whole game.
In the solution, it indeed seems to generate each time a new tree, you can use the subnode of the tree if you make a move and thus reuse the game tree that you already have built.