## Game Trees, Design Reviews ### Algorithms and Data Structures Every major software project comes with one major, complex data structure or mathematical component. The company I worked for needed an operations research person for modeling and running "mathematical optimization programs" (e.g., linear programming). In our project, we will need a game tree aka a decision tree for the AI player to compute strategic decisions. Roughly speaking, such a tree has the following shape: ``` * player 1, state of the game (1) | +----+----+----+----+----+----+----+----+ all possible choices by player 1 | | | | | | | | | * player 2, state of the game (2) | +----+----+----+----+----+----+----+----+ all possible choices by player 2 | | | | | | | | | * player 1, state of the game (3) | +----+----+----+----+----+----+----+----+ all possible choices by player 1 | | | | | | | | | ``` That is, every node describes a complete game state, which consists of the current board and the player whose turn it is. The outgoing edges represents (as in data representation) all possible actions that the player may take in this game state. For Santorini, the target state of these edges represent the next game state, which is the board that results from taking the action and the other player (whose turn it is now). The referee component could use the game tree to decide whether requested actions are legal. For the next assignment, you are to implement a player strategy that computes a "stay alive" decision for a certain number of rounds. For player 1 to stay alive for N rounds means that ``` there exists an action that player 1 can take, so that for all actions that player 2 takes, (1) player 2 can't win (2) player 1 can play N-2 rounds ``` [We consider each level in the tree one round.] In AI (and economic game theory), strategies employ game tree in different ways. Generally speaking, an actor computes the (expected) utility of nodes and then picks actions accoring to so-called minimax and alpha-beta pruning strategies. #### Generating Decision Trees For some games, say tic-tac-toe on a 3 x 3 grid, decision trees are small and fit into memory. For many scenarios, decision trees are too large to fit into plain memory---without looking at virtual distributed memory or other such ideas. In general, many projects come with a component that deals with very large forms of data (e.g. databases, though they are taken care of in modern systems). The key problem of dealing with large decision trees---such as Santorini's---is hence the generation of the tree. Going back to Fundamentals I, you have seen some ideas of representing large and even infinite forms of information as data. See {Representing Data with Lambda}[[https://htdp.org/2018-01-06/Book/part_three.html#%28part._sec~3alambda.I.I%29]] for an example. Your chosen languages also support _generators_, which are useful though in the context of these imperative languages other problems lurk when you deal with game trees. If your language supports neither of these concepts directly, consider the Command pattern to represent these game trees. *Hint* Suspend the computation of nodes, not the generation of actions for your game tree. When you design your test harness, you will need those. ### Design Review 1: Rule Checker Code | Matthias | Jason | Role | | ---------------------- | ---------------------- | ---------------------- | | Derek Schuster | Jon Corbett | presenter | | Shane Timmerman | Alex Zilbersher | | | | | panelists | | David Reed | Colin Riley | head | | Andrew Schoenberger | Melvin Chen | assistant | | Brendan Rejevich | Quincy Els | secretary | ### Design Review 2: Rule Checker Code | Matthias | Jason | Role | | ---------------------- | ---------------------- | ---------------------- | | David Reed | Grigory Zaytsev | presenter | | Brendan Rejevich | Maria Zaytseva | | | | | panelists | | Jacob Gino | Sebastian Ruiz Velasco Aguado | head | | Emily Miller-McGlone | Marina Karr | assistant | | Shane Timmerman | Jack Davis | secretary |