start
move option 1
counter-move 1
counter-move 2
move option 2
counter-move 3
counter-move 4
Episode One: Be infinitely lazy and defer all work
A board game is a series of mutual moves, each resulting in a new board position. Since there are many possible moves and for every move there are a number of possible counter-moves by the opponent, the possible evolutions of the game form a tree of board positions.
Moves and counter-moves form a tree.
Depending on the game rules, such a game tree can become infinitely large.
The natural way of modeling this in a lazy functional language like Frege or Haskell is to not care about the size of the tree at all but only about how to construct it. We stay focused on generation task and defer the limitation work to later.
Here is the construction for an arbitrary payload "a".
Children of each node recursively arise from making Nodes for all the payloads that "a" can unfold to.
The general recursive tree building
buildTree :: (a -> [a]) -> a -> Tree a
buildTree unfold a = Node a children where
children = map (buildTree unfold) (unfold a)We do not care about a base case to stop the recursion or limit the size of the tree
but note that calling buildTree will neither exhaust memory nor computation time.
Laziness in the language cares for constructing children only when needed.
This is now something that we can specialize for a given data type Board and a function moves
that unfolds to all boards that result from applying a valid move.
A game tree unfolds by placing all possible moves on the board
gameTree :: Board -> Tree Board
gameTree board = buildTree moves boardThe specialization needs no subtyping and is yet fully type-safe. We have extended the system non-intrusively and we will do so again for limiting the size of the game tree.
When an evaluation of the tree shall be limited to a depth "n" we simply prune the tree at that depth. That code is independent of our special game use case and can therefore work on nodes of arbitrary trees. Here is the recursive definition.
Pruning any arbitrary tree
prune 0 (Node a children) = Node a []
prune n (Node a children) = Node a (map (prune (n-1)) children)To make a pruned game tree we use function composition (.) for the generation:
Pruning a game tree at depth 5
prunedTree = prune 5 . gameTreeNote that we still haven’t materialized the tree! A user of the pruned tree can never look below level 5. No children below that level are ever evaluated, and thus - thanks to laziness - never get constructed.
Laziness allows us to work incrementally not only from generic tree generation to specialized logic and data types. We even apply pruning conditions non-intrusively "from the outside". We didn’t need to anticipate the need for pruning.
We never had to go back to previous code to change it. We did not even re-compile!
This is it for episode one. Stay tuned for episode two.
References
| John Hughes | |
| Tic Tac Toe |