```python
import sympy as sp
from sympy import symbols
import networkx as nx
from math import inf

sp.init_printing()

%matplotlib inline
```

# Problem 1

**Use the $\alpha-\beta$ algorithm to show the minimax value to `MAX` in the following game tree. Show the branches that are pruned during the search, and the values for `MAX` and `MIN` at each level in the tree.**


```python
from IPython.display import display, Image
Image('./tree.png')
```


```python
names = ['A']

class Node(object):
    def __init__(self, state, value=None):
        self.state = state
        self.value = value
        self.alpha = -inf
        self.beta = inf
        self.left = None
        self.right = None
        self.pruned = False
        self._name = None
        
    @property
    def is_empty(self):
        return self.left is None and self.right is None
    
    @property
    def children(self):
        return [x for x in [self.left, self.right] if x is not None]
    
    @property
    def name(self):
        global names
        if self._name is None:
            n = chr(ord(names[-1]) + 1)
            self._name = n
            names.append(n)
        return self._name
        
    def __str__(self):
        if not self.pruned:
            return (('({} , {})' if self.state == 'MIN' else '[{} , {}]').format(
                    -sp.oo if self.alpha == -inf else self.alpha,
                    sp.oo if self.beta == inf else self.beta) +
                ('' if self.is_empty else ' , <{}>'.format(', '.join([str(x) for x in self.children]))))
        else:
            return ''
        
    def nx(self):
        g = nx.DiGraph()
        nodes = []
        edges = []
        def add(cnode):
            if cnode.left and not cnode.left.pruned:
                nodes.append((cnode.left.name, cnode.left.alpha, cnode.left.beta))
                edges.append(((cnode.name, cnode.alpha, cnode.beta),
                              (cnode.left.name, cnode.left.alpha, cnode.left.beta)))
                add(cnode.left)
            if cnode.right and not cnode.right.pruned:
                nodes.append((cnode.right.name, cnode.right.alpha, cnode.right.beta))
                edges.append(((cnode.name, cnode.alpha, cnode.beta),
                              (cnode.right.name, cnode.right.alpha, cnode.right.beta)))
                add(cnode.right)
        g.add_node((self.name, self.alpha, self.beta))
        add(self)
        g.add_nodes_from(nodes)
        g.add_edges_from(edges)
        return g
    
    def show(self, title=''):
        g = self.nx()
        plt.figure()
        pos = nx.drawing.nx_agraph.graphviz_layout(g,prog='dot')
        nodes = nx.draw_networkx_nodes(g, pos=pos, node_size=100, alpha=0.2)
        edges = nx.draw_networkx_edges(g, pos=pos)
        labels = nx.draw_networkx_labels(g, pos=pos, font_size=6)
        plt.axis('off')
        if title:
            plt.title(title)
        plt.show()
        
root = Node('MAX')

root.left = Node('MIN')
root.right = Node('MIN')

root.left.left = Node('MAX')
root.left.right = Node('MAX')
root.right.left = Node('MAX')
root.right.right = Node('MAX')

root.left.left.left = Node('MIN')
root.left.left.right = Node('MIN')
root.left.right.left = Node('MIN')
root.left.right.right = Node('MIN')
root.right.left.left = Node('MIN')
root.right.left.right = Node('MIN')
root.right.right.left = Node('MIN')

root.left.left.left.left = Node('MAX', value=5)
root.left.left.left.right = Node('MAX', value=10)
root.left.left.right.left = Node('MAX', value=6)
root.left.left.right.right = Node('MAX', value=5)
root.left.right.left.left = Node('MAX', value=4)
root.left.right.right.left = Node('MAX', value=0)
root.left.right.right.right = Node('MAX', value=5)
root.right.left.left.left = Node('MAX', value=5)
root.right.left.left.right = Node('MAX', value=10)
root.right.left.right.left = Node('MAX', value=3)
root.right.right.left.left = Node('MAX', value=2)
root.right.right.left.right = Node('MAX', value=14)

root.show(title='Initial')

i = 0

def alpha_beta_pruning(root, depth, player, alpha, beta):
    global i
    if depth == 0 or root.is_empty:
        return root.value
    if player == 'MAX':
        best = -inf
        pruned = False
        for child in root.children:
            if pruned:
                child.pruned = True
            else:
                best = max(best,
                           alpha_beta_pruning(child, depth - 1, 'MIN',
                                              alpha, beta))
                alpha = max(alpha, best)
                root.alpha = alpha
                if beta <= alpha:
                    pruned = True
        i += 1
        root.show(title='Step {}'.format(i))
        return best
    else:
        best = inf
        pruned = False
        for child in root.children:
            if pruned:
                child.pruned = True
            else:
                best = min(best,
                           alpha_beta_pruning(child, depth - 1, 'MAX',
                                              alpha, beta))
                beta = min(beta, best)
                root.beta = beta
                if beta <= alpha:
                    pruned = True
        i += 1
        root.show(title='Step {}'.format(i))
        return best
alpha_beta_pruning(root, 4, 'MAX', -inf, inf)
```

# Problem 2

**Show that the following assertion is true using an example: For every game tree, the utility obtained by `MAX` using minimax decisions against a suboptimal `MIN` will never be lower than the utility obtained playing against an optimal `MIN`. Your example should also include an explanation of what an optimal utility is for `MAX` and `MIN` and what it would mean for either `MAX` or `MIN` to play a sub-optimal game.**

This is evidently true, as the `MAX` value is the theoretical upper bound, and should never be lower than `MIN`.

We can use induction to prove this.

Let $T$ be some theoretical tree, with $T_i$ any given node from this tree.

$$
\max(T_0) \ge \min(T_0)
$$

For some tree with depth 1.

$$
\max(T_i) \ge \min(T_{j})
$$

For any two nodes $i$ and $j$.

# Problem 3

**The following pseudo-code for the minimax algorithm is similar to the code included in the lecture notes. This code shows additional print commands that are not in the lecture notes code.**

```
minimax(node, depth, mexPlayer)
    if depth == 0 or terminal(node) //terminal test is true
        return f(node)
    if maxPlayer // Player(s) = MAX
        bestValue = -MAX_INT  // system property, max negative integer
        for each child in node.adjacent
            eval = minimax(child, depth - 1, FALSE)
            print eval
            bestValue = max(bestValue, eval)
        return bestValue
    else // Player(s) = MIN
        bestValue = MAX_INT
        for each child in node.adjacent
            eval = minimax(child, depth - 1, TRUE)
            print eval
            bestValue = min(bestValue, eval)
        return bestValue
    
    minimax(origin, depth, TRUE) // call from root for MAX player
```

**For the following tre, what numbers are displayed when the algorithm executes with an initial depth $=4$. You can assume that the root of the tree only has one child.**


```python
Image('./tree1.png')
```


```python
names = ['A']

root = Node('MAX')

root.left = Node('MIN')

root.left.left = Node('MAX')
root.left.right = Node('MAX')

root.left.left.left = Node('MIN')
root.left.left.right = Node('MIN')
root.left.right.left = Node('MIN')
root.left.right.right = Node('MIN')

root.left.left.left.left = Node('MAX', value=5)
root.left.left.left.right = Node('MAX', value=10)
root.left.left.right.left = Node('MAX', value=6)
root.left.left.right.right = Node('MAX', value=5)
root.left.right.left.left = Node('MAX', value=4)
root.left.right.right.left = Node('MAX', value=0)
root.left.right.right.right = Node('MAX', value=5)

root.show(title='initial')

step = 1

def alpha_beta_pruning(root, depth, player):
    global step
    if depth == 0 or root.is_empty:
        return root.value
    if player == 'MAX':
        best = -inf
        for child in root.children:
            x = alpha_beta_pruning(child, depth - 1, 'MIN')
            print(x)
            best = max(x, best)
        return best
    else:
        best = inf
        for child in root.children:
            x = alpha_beta_pruning(child, depth - 1, 'MAX')
            print(x)
            beta = min(x, best)
        return best
alpha_beta_pruning(root, 4, 'MAX')
```


```python

```

bc2471e8307b5499252a04762215d741afd0b657
ipynb
Jupyter Notebook
hw4/Will Farmer - Homework 4.ipynb
willzfarmer/CSCI3202
37653da1638536b1f664234129b0e13a269c8a3d
Apache-2.0
hw4/Will Farmer - Homework 4.ipynb
willzfarmer/CSCI3202
37653da1638536b1f664234129b0e13a269c8a3d
Apache-2.0
hw4/Will Farmer - Homework 4.ipynb
willzfarmer/CSCI3202
37653da1638536b1f664234129b0e13a269c8a3d
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES