Recursion is about to become trickier. Previously, we've used to search through nested lists and trees to find the longest branch, to sum all of the values, and to return the values of the leaves. So far our assignments have dealt with relatively small trees, only 3 or 4 nodes deep. Assignment 2 won't be so easy. Why? Because tippy can take 9 moves to end and has 138 different terminal positions. That means that the algorithm we make to search through these game states and evaluate the best ones will take a while to search through. Furthermore, we'll have to use come up with a base case that checks if a player has won the game, and then quits searching down that tree. If we don't make sure to stop recursively searching after a player has won, there would be a total of 326,800 different games that could occur (according to wikipedia). It will be crucial to write a tight recursive algorithm.
No comments:
Post a Comment