## 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 N2 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 socalled minimax and alphabeta
pruning strategies.
#### Generating Decision Trees
For some games, say tictactoe 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 memorywithout 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 treessuch as
Santorini'sis 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/20180106/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 MillerMcGlone  Marina Karr  assistant 
 Shane Timmerman  Jack Davis  secretary 