## 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 |