All Assignment Problems for Cohort 1 (Summer after 10th Grade)

Problem 32-1

(ML; 60 min)

Store your answers in machine-learning/analysis/logistic_regression.py

Suppose that you have a dataset of points $(x,y)$ where $x$ is the number of hours that a player has practiced Space Empires and $y$ is their probability of winning against an average player.

data = [(10, 0.05), (100, 0.35), (1000, 0.95)]

Fit a function $y=\dfrac{1}{1+e^{\beta_0 + \beta_1 x}}$ to the following data, using matrix methods involving the pseudoinverse.

a) Write the system of equations:

__ = 1/(1 + e^(beta_0 + beta_1 * ___) )
__ = 1/(1 + e^(beta_0 + beta_1 * ___) )
__ = 1/(1 + e^(beta_0 + beta_1 * ___) )

b) Convert the system to a system of linear equations:

beta_0 + beta_1 * ___ = ___
beta_0 + beta_1 * ___ = ___
beta_0 + beta_1 * ___ = ___

c) Solve for beta_0 and beta_1 using the pseudoinverse.

d) For a player who has practiced 500 hours, compute the probability of winning against an average player.

e) How many hours does an average player practice? Tip: an average player will have 0.5 probability of winning against an average player, so you just need to solve the equation 0.5 = 1/(1 + e^(beta_0 + beta_1 * x) ) for x.

Problem 32-2

(Algo; 45 min)

Implement breadth-first search in your Graph class. This will be very similar to the breadth-first search in your Tree class, but now you will have to make sure that you do not revisit any nodes (because now there are multiple paths from one node to another).

  • Luckily, this is a simple adjustment: keep a list of the nodes you've visited, and only make the recursive call on unvisited nodes.

Example:

>>> edges = [(0,1),(1,2),(1,3),(3,4),(1,4),(4,5)]
>>> vertices = ['a','b','c','d','e','f']
>>> graph = Graph(edges, vertices)
>>> graph.breadth_first_search(2)  (note: 2 is the index of the starting node)

[2, 1, 0, 3, 4, 5] (note: in class, we printed out the values, but let's instead return a list of the indices)

other answers are valid, e.g. [2, 1, 4, 3, 0, 5]

Problem 32-3

(Space Empires; 90 min)

Note: this is the same problem as the previous assignment -- that means you've got an extra class to catch up on it, and it also means that you should indeed fully catch up on it.

Implement the following additional tests in tests/test_combat_test_player.py:

  • At the end of Turn 1 Economic Phase:

    • Player 1 has 1 CP, 3 scouts at (2,2), 1 destroyer at (2,0)
    • Player 2 has 4 CP, 1 destroyer at (2,4).

  • At the end of Turn 2 Movement Phase:

    • Player 1 has 3 scouts and 1 destroyer at (2,2)
    • Player 2 has 1 destroyer at (2,2)

  • At the end of Turn 2 Combat Phase:

    • Player 1 has 3 scouts and 1 destroyer at (2,2)
    • Player 2 has no ships other than its home colony/shipyards

  • At the end of Turn 2 Economic Phase:

    • Player 1 has 0 CP, 3 scouts at (2,2), 1 destroyer at (2,2).
    • Player 2 has 1 CP, 1 scout at (2,4).

  • At the end of Turn 3 Movement Phase:

    • Player 1 has 3 scouts and 1 destroyer at (2,2)
    • Player 2 has 1 scout at (2,2)

  • At the end of Turn 3 Combat Phase:

    • Player 1 has 3 scouts and 1 destroyer at (2,2)
    • Player 2 has no ships other than its home colony/shipyards

  • At the end of Turn 3 Economic Phase:

    • Player 1 has 0 CP, 2 scouts and 1 destroyer at (2,0).
    • Player 2 has 4 CP, no ships other than its home colony/shipyards

Note: These tests are based on the following game events file. I've done my best to ensure this is accurate, but if your game doesn't match up and you think there might be an error in the events, please post about it.

STARTING CONDITIONS

Players 1 and 2
    are CombatTestingPlayers
    start with 20 CPs
    have an initial fleet of 3 scouts, 3 colony ships, 4 ship yards

---

TURN 1 - MOVEMENT PHASE

Player 1:
    Scouts 1,2,3: (2,0) --> (2,2)
    Colony Ships 4,5,6: (2,0) --> (2,2)

Player 2:
    Scouts 1,2,3: (2,4) --> (2,2)
    Colony Ships 4,5,6: (2,4) --> (2,2)

COMBAT PHASE

Colony Ships are removed

| PLAYER |        SHIP        | HEALTH  |
----------------------------------------
|    1   |         Scout 1    |    1    |
|    1   |         Scout 2    |    1    |
|    1   |         Scout 3    |    1    |
|    2   |         Scout 1    |    1    |
|    2   |         Scout 2    |    1    |
|    2   |         Scout 3    |    1    |

Attack 1
    Attacker: Player 1 Scout 1
    Defender: Player 2 Scout 1
    Largest Roll to Hit: 3
    Die Roll: 1
    Hit or Miss: Hit

| PLAYER |          SHIP          | HEALTH  |
---------------------------------------------
|    1   |         Scout 1        |    1    |
|    1   |         Scout 2        |    1    |
|    1   |         Scout 3        |    1    |
|    2   |         Scout 2        |    1    |
|    2   |         Scout 3        |    1    |

Attack 2
    Attacker: Player 1 Scout 2
    Defender: Player 2 Scout 2
    Largest Roll to Hit: 3
    Die Roll: 2
    Hit or Miss: Hit

| PLAYER |          SHIP          | HEALTH  |
---------------------------------------------
|    1   |         Scout 1        |    1    |
|    1   |         Scout 2        |    1    |
|    1   |         Scout 3        |    1    |
|    2   |         Scout 3        |    1    |

Attack 3
    Attacker: Player 1 Scout 3
    Defender: Player 2 Scout 3
    Largest Roll to Hit: 3
    Dice Roll: 3
    Hit or Miss: Hit

| PLAYER |          SHIP          | HEALTH  |
---------------------------------------------
|    1   |         Scout 1        |    1    |
|    1   |         Scout 2        |    1    |
|    1   |         Scout 3        |    1    |

Combat phase complete

------------------------

TURN 1 - ECONOMIC PHASE

Player 1

    INCOME/MAINTENANCE (starting CP: 20)
        colony income: +3 CP/Colony x 1 Colony = +3 CP
        maintenance costs: -1 CP/Scout x 3 Scouts = -3 CP

    PURCHASES (starting CP: 20)
        ship size technology 2: -10 CP
        destroyer: -9 CP

    REMAINING CP: 1

Player 2

    INCOME/MAINTENANCE (starting CP: 20)
        colony income: +3 CP/Colony x 1 Colony = +3 CP
        maintenance costs: 0

    PURCHASES (starting CP: 23)
        ship size technology 2: -10 CP
        destroyer: -9 CP

    REMAINING CP: 4

------------------------

TURN 2 - MOVEMENT PHASE

Player 1:
    Scouts 1,2,3: stay at (2,2)
    Destroyer 1 : (2,0) --> (2,2)

Player 2:
    Destroyer 1: (2,4) --> (2,2)

------------------------

TURN 2 - COMBAT PHASE

| PLAYER |          SHIP          | HEALTH  |
---------------------------------------------
|    1   |         Destroyer 1    |    1    |
|    2   |         Destroyer 1    |    1    |
|    1   |         Scout 1        |    1    |
|    1   |         Scout 2        |    1    |
|    1   |         Scout 3        |    1    |

Attack 1
    Attacker: Player 1 Destroyer 1
    Defender: Player 2 Destroyer 1
    Largest Roll to Hit: 4
    Dice Roll: 4
    Hit or Miss: Hit

| PLAYER |          SHIP          | HEALTH  |
---------------------------------------------
|    1   |         Destroyer 1    |    1    |
|    1   |         Scout 1        |    1    |
|    1   |         Scout 2        |    1    |
|    1   |         Scout 3        |    1    |

------------------------

TURN 2 - ECONOMIC PHASE

Player 1

    INCOME/MAINTENANCE (starting CP: 1)
        colony income: +3 CP/Colony x 1 Colony = +3 CP
        maintenance costs: -1 CP/Scout x 3 Scouts -1 CP/Destroyer x 1 Destroyer = -4 CP

    REMAINING CP: 0

Player 2

    INCOME/MAINTENANCE (starting CP: 4)
        colony income: +3 CP/Colony x 1 Colony = +3 CP
        maintenance costs: 0

    PURCHASES (starting CP: 7)
        scout: -6 CP

    REMAINING CP: 1

------------------------

TURN 3 - MOVEMENT PHASE

Player 1:
    Scouts 1,2,3: stay at (2,2)
    Destroyer 1 : stay at (2,2)

Player 2:
    Scout 1: (2,4) --> (2,2)

------------------------

TURN 3 - COMBAT PHASE

| PLAYER |          SHIP          | HEALTH  |
---------------------------------------------
|    1   |         Destroyer 1    |    1    |
|    1   |         Scout 1        |    1    |
|    1   |         Scout 2        |    1    |
|    1   |         Scout 3        |    1    |
|    2   |         Scout 1        |    1    |

Attack 1
    Attacker: Player 1 Destroyer 1
    Defender: Player 2 Scout 1
    Largest Roll to Hit: 4
    Dice Roll: 5
    Hit or Miss: Miss

Attack 2
    Attacker: Player 1 Scout 1
    Defender: Player 2 Scout 1
    Largest Roll to Hit: 3
    Dice Roll: 6
    Hit or Miss: Miss

Attack 3
    Attacker: Player 1 Scout 2
    Defender: Player 2 Scout 1
    Largest Roll to Hit: 3
    Dice Roll: 1
    Hit or Miss: Hit

| PLAYER |          SHIP          | HEALTH  |
---------------------------------------------
|    1   |         Destroyer 1    |    1    |
|    1   |         Scout 1        |    1    |
|    1   |         Scout 2        |    1    |
|    1   |         Scout 3        |    1    |

------------------------

TURN 3 - ECONOMIC PHASE

Player 1

    INCOME/MAINTENANCE (starting CP: 0)
        colony income: +3 CP/Colony x 1 Colony = +3 CP
        maintenance costs: -1 CP/Scout x 3 Scouts -1 CP/Destroyer x 1 Destroyer = -4 CP

    REMOVALS
        remove scout 3 due to inability to pay maintenance costs

    REMAINING CP: 0

Player 2

    INCOME/MAINTENANCE (starting CP: 1)
        colony income: +3 CP/Colony x 1 Colony = +3 CP
        maintenance costs: 0

    REMAINING CP: 4

Problem 31-1

(Stats; 45 min)

For this problem, put your code in assignment-problems/src/conditional_probability.py

During class, each person created a distribution of coin flips.

flips = {
    'George': 'THTH HTHT THTH HHTH THTH TTHT THTH TTTH THTH TTHT THHT HTTH THTH THHT THHT THTH THTH THHT THTH THTH',
    'David': 'TTHH HHTT HHTT TTHH HTHT THTH THTH THTH HTHT HTHT THTH HTHT THHH THTH HHTT HHTT TTTH HHTH HTHH TTTH',
    'Elijah': 'THTT HTHT HTHH HHHT TTHH THHH TTTT HHTT TTTH TTHH HTHT HTHT TTTT HTTT TTTH HTTT TTHH THTH THHH HTHH',
    'Colby': 'HTTH HTHH THTT HHTH TTHT HTTT THHH TTHH HHTT THTH HHTT THTH THHH TTHH THTT HHTH HTTH HTHH TTHT HTTT',
    'Justin': 'THTT HTHT TTTH THHT HTHH TTTH THTH HHTH TTTT HTTH HHTT THHH HHHH THTH HTTH TTHH HTHT HHHT THHT TTTH'
}

For each person, print out the following probabilities:

  • $P(\text{ next flip was heads | previous flip was heads })$

  • $P(\text{ next flip was tails | previous flip was heads })$

  • $P(\text{ next flip was heads | previous flip was tails })$

  • $P(\text{ next flip was tails | previous flip was tails })$

Also, print out the probabilities on the simple dataset HHTTHT to double check that your code is correct.

  • For the dataset HHTTHT, the pairs are HH, HT, TT, TH, HT. So,

    • $P(\text{ next flip was heads | previous flip was heads }) = 1/3$

    • $P(\text{ next flip was tails | previous flip was heads }) = 2/3$

    • $P(\text{ next flip was heads | previous flip was tails }) = 1/2$

    • $P(\text{ next flip was tails | previous flip was tails }) = 1/2$

Note: Using Bayes' Rule,

$$P(X \, | \, Y) = \dfrac{P(X \wedge Y)}{P(Y)} = \dfrac{\text{count}(X \wedge Y)}{\text{count}(Y)},$$

we have that

$$\begin{align*} P(\text{ next flip was heads | previous flip was tails }) &= \dfrac{\text{count}(\text{ next flip was heads AND previous flip was tails })}{\text{count}(\text{ previous flip was tails })} \\ &= \dfrac{\text{count}(\text{ consecutive pairs in which tails was followed IMMEDIATELY by heads })}{\text{count}(\text{ consecutive pairs in which previous flip was tails })}. \end{align*}$$

Problem 31-2

(Algo; 45 min)

Implement depth-first search in your Graph class. This will be very similar to the depth-first search in your Tree class, but now you will have to make sure that you do not revisit any nodes (because now there are multiple paths from one node to another).

  • Luckily, this is a simple adjustment: keep a list of the nodes you've visited, and only make the recursive call on unvisited nodes.

Example:

>>> edges = [(0,1),(1,2),(1,3),(3,4),(1,4)]
>>> vertices = ['a','b','c','d','e']
>>> graph = Graph(edges, vertices)
>>> graph.depth_first_search(2)  (note: 2 is the index of the starting node)

[2, 1, 3, 4, 0] (note: in class, we printed out the values, but let's instead return a list of the indices)

other answers are valid, e.g. [2, 1, 0, 4, 3]

Problem 31-3

(Space Empires; 90 min)

Implement the following additional tests in tests/test_combat_test_player.py:

  • At the end of Turn 1 Economic Phase:

    • Player 1 has 1 CP, 3 scouts at (2,2), 1 destroyer at (2,0)
    • Player 2 has 4 CP, 1 destroyer at (2,4).

  • At the end of Turn 2 Movement Phase:

    • Player 1 has 3 scouts and 1 destroyer at (2,2)
    • Player 2 has 1 destroyer at (2,2)

  • At the end of Turn 2 Combat Phase:

    • Player 1 has 3 scouts and 1 destroyer at (2,2)
    • Player 2 has no ships other than its home colony/shipyards

  • At the end of Turn 2 Economic Phase:

    • Player 1 has 0 CP, 3 scouts at (2,2), 1 destroyer at (2,2).
    • Player 2 has 1 CP, 1 scout at (2,4).

  • At the end of Turn 3 Movement Phase:

    • Player 1 has 3 scouts and 1 destroyer at (2,2)
    • Player 2 has 1 scout at (2,2)

  • At the end of Turn 3 Combat Phase:

    • Player 1 has 3 scouts and 1 destroyer at (2,2)
    • Player 2 has no ships other than its home colony/shipyards

  • At the end of Turn 3 Economic Phase:

    • Player 1 has 0 CP, 2 scouts and 1 destroyer at (2,0).
    • Player 2 has 4 CP, no ships other than its home colony/shipyards

Note: These tests are based on the following game events file. I've done my best to ensure this is accurate, but if your game doesn't match up and you think there might be an error in the events, please post about it.

STARTING CONDITIONS

Players 1 and 2
    are CombatTestingPlayers
    start with 20 CPs
    have an initial fleet of 3 scouts, 3 colony ships, 4 ship yards

---

TURN 1 - MOVEMENT PHASE

Player 1:
    Scouts 1,2,3: (2,0) --> (2,2)
    Colony Ships 4,5,6: (2,0) --> (2,2)

Player 2:
    Scouts 1,2,3: (2,4) --> (2,2)
    Colony Ships 4,5,6: (2,4) --> (2,2)

COMBAT PHASE

Colony Ships are removed

| PLAYER |        SHIP        | HEALTH  |
----------------------------------------
|    1   |         Scout 1    |    1    |
|    1   |         Scout 2    |    1    |
|    1   |         Scout 3    |    1    |
|    2   |         Scout 1    |    1    |
|    2   |         Scout 2    |    1    |
|    2   |         Scout 3    |    1    |

Attack 1
    Attacker: Player 1 Scout 1
    Defender: Player 2 Scout 1
    Largest Roll to Hit: 3
    Die Roll: 1
    Hit or Miss: Hit

| PLAYER |          SHIP          | HEALTH  |
---------------------------------------------
|    1   |         Scout 1        |    1    |
|    1   |         Scout 2        |    1    |
|    1   |         Scout 3        |    1    |
|    2   |         Scout 2        |    1    |
|    2   |         Scout 3        |    1    |

Attack 2
    Attacker: Player 1 Scout 2
    Defender: Player 2 Scout 2
    Largest Roll to Hit: 3
    Die Roll: 2
    Hit or Miss: Hit

| PLAYER |          SHIP          | HEALTH  |
---------------------------------------------
|    1   |         Scout 1        |    1    |
|    1   |         Scout 2        |    1    |
|    1   |         Scout 3        |    1    |
|    2   |         Scout 3        |    1    |

Attack 3
    Attacker: Player 1 Scout 3
    Defender: Player 2 Scout 3
    Largest Roll to Hit: 3
    Dice Roll: 3
    Hit or Miss: Hit

| PLAYER |          SHIP          | HEALTH  |
---------------------------------------------
|    1   |         Scout 1        |    1    |
|    1   |         Scout 2        |    1    |
|    1   |         Scout 3        |    1    |

Combat phase complete

------------------------

TURN 1 - ECONOMIC PHASE

Player 1

    INCOME/MAINTENANCE (starting CP: 20)
        colony income: +3 CP/Colony x 1 Colony = +3 CP
        maintenance costs: -1 CP/Scout x 3 Scouts = -3 CP

    PURCHASES (starting CP: 20)
        ship size technology 2: -10 CP
        destroyer: -9 CP

    REMAINING CP: 1

Player 2

    INCOME/MAINTENANCE (starting CP: 20)
        colony income: +3 CP/Colony x 1 Colony = +3 CP
        maintenance costs: 0

    PURCHASES (starting CP: 23)
        ship size technology 2: -10 CP
        destroyer: -9 CP

    REMAINING CP: 4

------------------------

TURN 2 - MOVEMENT PHASE

Player 1:
    Scouts 1,2,3: stay at (2,2)
    Destroyer 1 : (2,0) --> (2,2)

Player 2:
    Destroyer 1: (2,4) --> (2,2)

------------------------

TURN 2 - COMBAT PHASE

| PLAYER |          SHIP          | HEALTH  |
---------------------------------------------
|    1   |         Destroyer 1    |    1    |
|    2   |         Destroyer 1    |    1    |
|    1   |         Scout 1        |    1    |
|    1   |         Scout 2        |    1    |
|    1   |         Scout 3        |    1    |

Attack 1
    Attacker: Player 1 Destroyer 1
    Defender: Player 2 Destroyer 1
    Largest Roll to Hit: 4
    Dice Roll: 4
    Hit or Miss: Hit

| PLAYER |          SHIP          | HEALTH  |
---------------------------------------------
|    1   |         Destroyer 1    |    1    |
|    1   |         Scout 1        |    1    |
|    1   |         Scout 2        |    1    |
|    1   |         Scout 3        |    1    |

------------------------

TURN 2 - ECONOMIC PHASE

Player 1

    INCOME/MAINTENANCE (starting CP: 1)
        colony income: +3 CP/Colony x 1 Colony = +3 CP
        maintenance costs: -1 CP/Scout x 3 Scouts -1 CP/Destroyer x 1 Destroyer = -4 CP

    REMAINING CP: 0

Player 2

    INCOME/MAINTENANCE (starting CP: 4)
        colony income: +3 CP/Colony x 1 Colony = +3 CP
        maintenance costs: 0

    PURCHASES (starting CP: 7)
        scout: -6 CP

    REMAINING CP: 1

------------------------

TURN 3 - MOVEMENT PHASE

Player 1:
    Scouts 1,2,3: stay at (2,2)
    Destroyer 1 : stay at (2,2)

Player 2:
    Scout 1: (2,4) --> (2,2)

------------------------

TURN 3 - COMBAT PHASE

| PLAYER |          SHIP          | HEALTH  |
---------------------------------------------
|    1   |         Destroyer 1    |    1    |
|    1   |         Scout 1        |    1    |
|    1   |         Scout 2        |    1    |
|    1   |         Scout 3        |    1    |
|    2   |         Scout 1        |    1    |

Attack 1
    Attacker: Player 1 Destroyer 1
    Defender: Player 2 Scout 1
    Largest Roll to Hit: 4
    Dice Roll: 5
    Hit or Miss: Miss

Attack 2
    Attacker: Player 1 Scout 1
    Defender: Player 2 Scout 1
    Largest Roll to Hit: 3
    Dice Roll: 6
    Hit or Miss: Miss

Attack 3
    Attacker: Player 1 Scout 2
    Defender: Player 2 Scout 1
    Largest Roll to Hit: 3
    Dice Roll: 1
    Hit or Miss: Hit

| PLAYER |          SHIP          | HEALTH  |
---------------------------------------------
|    1   |         Destroyer 1    |    1    |
|    1   |         Scout 1        |    1    |
|    1   |         Scout 2        |    1    |
|    1   |         Scout 3        |    1    |

------------------------

TURN 3 - ECONOMIC PHASE

Player 1

    INCOME/MAINTENANCE (starting CP: 0)
        colony income: +3 CP/Colony x 1 Colony = +3 CP
        maintenance costs: -1 CP/Scout x 3 Scouts -1 CP/Destroyer x 1 Destroyer = -4 CP

    REMOVALS
        remove scout 3 due to inability to pay maintenance costs

    REMAINING CP: 0

Player 2

    INCOME/MAINTENANCE (starting CP: 1)
        colony income: +3 CP/Colony x 1 Colony = +3 CP
        maintenance costs: 0

    REMAINING CP: 4

Problem 30-1

(Stats; 45 min)

For this problem, put your code in assignment-problems/src/approximations_of_randomness.py

During class, each person created a distribution of coin flips.

flips = {
    'George': 'THTH HTHT THTH HHTH THTH TTHT THTH TTTH THTH TTHT THHT HTTH THTH THHT THHT THTH THTH THHT THTH THTH',
    'David': 'TTHH HHTT HHTT TTHH HTHT THTH THTH THTH HTHT HTHT THTH HTHT THHH THTH HHTT HHTT TTTH HHTH HTHH TTTH',
    'Elijah': 'THTT HTHT HTHH HHHT TTHH THHH TTTT HHTT TTTH TTHH HTHT HTHT TTTT HTTT TTTH HTTT TTHH THTH THHH HTHH',
    'Colby': 'HTTH HTHH THTT HHTH TTHT HTTT THHH TTHH HHTT THTH HHTT THTH THHH TTHH THTT HHTH HTTH HTHH TTHT HTTT',
    'Justin': 'THTT HTHT TTTH THHT HTHH TTTH THTH HHTH TTTT HTTH HHTT THHH HHHH THTH HTTH TTHH HTHT HHHT THHT TTTH'
}

a) Treating these coin flips as simulations of 20 samples of 4 flips, compute the KL divergence between each simulation and the true distribution. Print out your results.

b) Print out the answer to the following question: whose simulation was the best approximation of true random coin flipping?

Problem 30-2

(Algo; 90 min)

a) In the file graph/src/node.py, create a class Node that

  • is initialized with an index, and

  • has the attributes index, value, and neighbors.

b) In the file graph/tests/test_node.py, assert that your Node class passes the following tests. (If you want to remove the >>> at the beginning, use this text replacement tool.)

>>> string_node = Node(0)
>>> string_node.index
0
>>> string_node.set_value('asdf')
>>> string_node.value
'asdf'
>>> string_node.neighbors
[]

>>> numeric_node = Node(1)
>>> numeric_node.set_value(765)
>>> numeric_node.set_neighbor(string_node)
>>> numeric_node.neighbors[0].value
'asdf'
>>> string_node.neighbors[0].value
765

>>> array_node = Node(2)
>>> array_node.set_value([[1,2],[3,4]])
>>> array_node.set_neighbor(numeric_node)
>>> array_node.neighbors[0].value
765
>>> numeric_node.neighbors[1].value
[[1,2],[3,4]]

c) In the file graph/src/graph.py, create a class Graph that

  • is initialized with list of edges (an edge is a tuple of indices) and vertices (a vertex is a node value), and

  • has the attribute nodes.

d) In the file graph/tests/test_graph.py, assert that your class passes the following tests.

>>> edges = [(0,1),(1,2),(1,3),(3,4),(1,4)]
>>> vertices = ['a','b','c','d','e']
>>> graph = Graph(edges, vertices)
>>> [node.index for node in graph.nodes]
[0, 1, 2, 3, 4]
>>> [node.value for node in graph.nodes]
['a','b','c','d','e']
>>> [len(node.neighbors) for node in graph.nodes]
[1, 4, 1, 2, 2]

Problem 30-3

(Space Empires; 60 min)

Continue writing the game events log, up until a combat round occurs in which some player has a destroyer. (You can stop writing the log once you finish that combat round.)

With regards to the die rolls, each combat round should pick up where the previous round left off. So since the first combat ended with a die roll of 3, the second combat will begin with a die roll of 4.

STARTING CONDITIONS

Players 1 and 2
    are CombatTestingPlayers
    start with 20 CPs
    have an initial fleet of 3 scouts and 3 colony ships

---

TURN 1

MOVEMENT PHASE

Player 1, Movement 1
    Scouts 1,2,3: (2,0) --> (2, 1)
    Colony Ships 4,5,6: (2,0) --> (2,1)

Player 2, Movement 1
    Scouts 1,2,3: (2,4) --> (2, 3)
    Colony Ships 4,5,6: (2,4) --> (2,3)

Player 1, Movement 2
    Scout 1,2,3: (2, 1) --> (2, 2)

Player 2, Movement 2
    Scouts 1,2,3: (2, 3) --> (2, 2)
    Colony Ships 4,5,6: (2,1) --> (2,2)

Players 1/2, Movement 3
    No player moved!

Player 1, Final Locations:
    Scout 1: (2, 2)
    Scout 2: (2, 2)
    Scout 3: (2, 2)
    Colony Ship 4: (2,2)
    Colony Ship 5: (2,2)
    Colony Ship 6: (2,2)

Player 2, Final Locations:
    Scout 1: (2, 2)
    Scout 2: (2, 2)
    Scout 3: (2, 2)
    Colony Ship 4: (2,2)
    Colony Ship 5: (2,2)
    Colony Ship 6: (2,2)

COMBAT PHASE

Remaining ships: (list in the table below)

ATTACKING ORDER | PLAYER |        SHIP        | HEALTH  |
---------------------------------------------------------
       1        |    1   |         Scout 1    |    1    |
       2        |    1   |         Scout 2    |    1    |
       3        |    1   |         Scout 3    |    1    |
       4        |    2   |         Scout 1    |    1    |
       5        |    2   |         Scout 2    |    1    |
       6        |    2   |         Scout 3    |    1    |




Attack 1
Attacker: Player 1 Scout 1
Defender: Player 2 Scout 1
Miss Threshold: 3
Die Roll: 1
Hit or Miss: Hit (since Die Roll <= Miss Threshold)

ATTACKING ORDER | PLAYER |          SHIP          | HEALTH  |
-------------------------------------------------------------
       1        |    1   |         Scout 1        |    1    |
       2        |    1   |         Scout 2        |    1    |
       3        |    1   |         Scout 3        |    1    |
       4        |    2   |         Scout 2        |    1    |
       5        |    2   |         Scout 3        |    1    |

Attack 2
Attacker: Player 1 Scout 2
Defender: Player 2 Scout 2
Hit Threshold: 3
Die Roll: 2
Hit or Miss: Hit (since Die Roll <= Miss Threshold)

ATTACKING ORDER | PLAYER |          SHIP          | HEALTH  |
-------------------------------------------------------------
       1        |    1   |         Scout 1        |    1    |
       2        |    1   |         Scout 2        |    1    |
       3        |    1   |         Scout 3        |    1    |
       5        |    2   |         Scout 3        |    1    |

Attack 3
Attacker: Player 1 Scout 3
Defender: Player 2 Scout 3
Hit Threshold: 3
Dice Roll: 3
Hit or Miss: Hit (since Die Roll <= Miss Threshold)

ATTACKING ORDER | PLAYER |          SHIP          | HEALTH  |
-------------------------------------------------------------
       1        |    1   |         Scout 1        |    1    |
       2        |    1   |         Scout 2        |    1    |
       3        |    1   |         Scout 3        |    1    |

Combat phase complete

ECONOMIC PHASE

... (continue here)

Problem 29-1

(ML; 60 min)

Create a file machine-learning/analysis/sandwich_ratings_dummy_variables.py to store your code/answers for this problem.

Slices Beef | Tbsp Peanut Butter | Condiments  | Rating |
--------------------------------------------------------------
 0          | 0                  | -           |    1   |
 0          | 0                  | mayo        |    1   |
 0          | 0                  | jelly       |    4   |
 0          | 0                  | mayo, jelly |    0   |
 5          | 0                  | -           |    4   |
 5          | 0                  | mayo        |    8   |
 5          | 0                  | jelly       |    1   |
 5          | 0                  | mayo, jelly |    0   |
 0          | 5                  | -           |    5   |
 0          | 5                  | mayo        |    0   |
 0          | 5                  | jelly       |    9   |
 0          | 5                  | mayo, jelly |    0   |
 5          | 5                  | -           |    0   |
 5          | 5                  | mayo        |    0   |
 5          | 5                  | jelly       |    0   |
 5          | 5                  | mayo, jelly |    0   |

a) Replace the Condiments feature with the dummy variables Mayo (M) and Jelly (J). Print out the resulting array.

B = slices roast beef
P = tbsp peanut butter
M = mayo
J = jelly
R = rating

   B  P  M  J  R
[[ 0, 0, 0, 0, 1 ],
 [ 0, 0, 1, 0, 1 ],
 [ 0, 0, 0, 1, 4 ],
 [ 0, 0, 1, 1, 0 ],
 [ 5, 0, _, _, 4 ],
 [ 5, 0, _, _, 8 ],
 [ 5, 0, _, _, 1 ],
 [ 5, 0, _, _, 0 ],
 [ 0, 5, _, _, 5 ],
 [ 0, 5, _, _, 0 ],
 [ 0, 5, _, _, 9 ],
 [ 0, 5, _, _, 0 ],
 [ 5, 5, _, _, 0 ],
 [ 5, 5, _, _, 0 ],
 [ 5, 5, _, _, 0 ],
 [ 5, 5, _, _, 0 ]]

b) Include interaction features. Print out the resulting array.

   B  P  M  J  BP  BM  BJ  PM  PJ  MJ  R
[[ 0, 0, 0, 0, __, __, __, __, __, __, 1 ],
 [ 0, 0, 1, 0, __, __, __, __, __, __, 1 ],
 [ 0, 0, 0, 1, __, __, __, __, __, __, 4 ],
 [ 0, 0, 1, 1, __, __, __, __, __, __, 0 ],
 [ 5, 0, _, _, __, __, __, __, __, __, 4 ],
 [ 5, 0, _, _, __, __, __, __, __, __, 8 ],
 [ 5, 0, _, _, __, __, __, __, __, __, 1 ],
 [ 5, 0, _, _, __, __, __, __, __, __, 0 ],
 [ 0, 5, _, _, __, __, __, __, __, __, 5 ],
 [ 0, 5, _, _, __, __, __, __, __, __, 0 ],
 [ 0, 5, _, _, __, __, __, __, __, __, 9 ],
 [ 0, 5, _, _, __, __, __, __, __, __, 0 ],
 [ 5, 5, _, _, __, __, __, __, __, __, 0 ],
 [ 5, 5, _, _, __, __, __, __, __, __, 0 ],
 [ 5, 5, _, _, __, __, __, __, __, __, 0 ],
 [ 5, 5, _, _, __, __, __, __, __, __, 0 ]]

c) To help you ensure that your transformed dataset is correct, I'll tell you that the sum of all the numbers in your matrix, INCLUDING the ratings, should be equal to 313.

assert that the above statement is true.

d) Fit a linear model to the data

rating = beta_0
         + beta_1 ( slices beef ) + beta_2 ( tbsp pb ) + beta_3 ( mayo ) + beta_4 ( jelly ) 
         + beta_5 ( slices beef ) ( tbsp pb ) + beta_6 ( slices beef ) ( jelly ) + beta_7 ( slices beef ) ( jelly )
         + beta_8 ( tbsp pb ) ( mayo ) + beta_9 ( tbsp pb ) ( jelly )
         + beta_10 ( mayo ) ( jelly )

print out your coefficients, labeled with the corresponding variables:

COEFFICIENTS

bias term: ___

beef: ___
peanut butter: ___
mayo: ___
jelly: ___

beef & peanut butter: ___
beef & mayo: ___
beef & jelly: ___
peanut butter & mayo: ___
peanut butter & jelly: ___
mayo & jelly: ___
...

e) Print out the following predictions:

PREDICTED RATINGS

2 slices beef + mayo: __
2 slices beef + jelly: __
3 tbsp peanut butter + jelly: __
3 tbsp peanut butter + jelly + mayo: ___
2 slices beef + 3 tbsp peanut butter + jelly + mayo: ___

Problem 29-2

(Stats; 30 min)

Create a file assignment-problems/detecting_biased_coins.py to store your code/answers for this problem.

Suppose that you run an experiment where you flip a coin 3 times, and repeat that trial 25 times. You run this experiment on 3 different coins, and get the following results:

coin_1 = ['TTH', 'HHT', 'HTH', 'TTH', 'HTH', 'TTH', 'TTH', 'TTH', 'THT', 'TTH', 'HTH', 'HTH', 'TTT', 'HTH', 'HTH', 'TTH', 'HTH', 'TTT', 'TTT', 'TTT', 'HTT', 'THT', 'HHT', 'HTH', 'TTH']
coin_2 = ['HTH', 'HTH', 'HTT', 'THH', 'HHH', 'THH', 'HHH', 'HHH', 'HTT', 'TTH', 'TTH', 'HHT', 'TTH', 'HTH', 'HHT', 'THT', 'THH', 'THT', 'TTH', 'TTT', 'HHT', 'THH', 'THT', 'THT', 'TTT']
coin_3 = ['HHH', 'THT', 'HHT', 'HHT', 'HTH', 'HHT', 'HHT', 'HHH', 'TTT', 'THH', 'HHH', 'HHH', 'TTH', 'THH', 'THH', 'TTH', 'HTT', 'TTH', 'HTT', 'HHT', 'TTH', 'HTH', 'THT', 'THT', 'HTH']

Let $P_i(x)$ be the probability of getting $x$ heads in a trial of 3 tosses, using the $i$th coin. Plot the distributions $P_1(x),$ $P_2(x),$ and $P_3(x)$ on the same graph. Be sure to label them.

  • (This is similar to when you plotted the Monte Carlo distributions, but this time you're given the simulation results.)

Based on the plot of the distributions, what conclusions can you make about the coins? For each coin, does it appear to be fair, biased towards heads, or biased towards tails? Write your answer as a comment.

Problem 29-3

(Space Empires; 90 min)

Write a testing file tests/test_combat_testing_player.py to ensure that a game on a $5 \times 5$ grid with two CombatTestingPlayers proceeds correctly.

  1. At the end of Turn 1 Movement Phase:

    • Player 1 has 3 scouts and 3 colony ships at (2,2)
    • Player 2 has 3 scouts and 3 colony ships at (2,2)

  2. At the end of Turn 1 Combat Phase:

    • Player 1 has 3 scouts at (2,2) and no colony ships (though it does have its home colony)
    • Player has no scouts and no colony ships (though it does have its home colony)

Note: These tests are based on Elijah's game events file, which we verified during class.

STARTING CONDITIONS

Players 1 and 2
    are CombatTestingPlayers
    start with 20 CPs
    have an initial fleet of 3 scouts and 3 colony ships

---

TURN 1

MOVEMENT PHASE

Player 1, Movement 1
    Scouts 1,2,3: (2,0) --> (2, 1)
    Colony Ships 4,5,6: (2,0) --> (2,1)

Player 2, Movement 1
    Scouts 1,2,3: (2,4) --> (2, 3)
    Colony Ships 4,5,6: (2,4) --> (2,3)

Player 1, Movement 2
    Scout 1,2,3: (2, 1) --> (2, 2)
    Colony Ships 4,5,6: (2,1) --> (2,2)

Player 2, Movement 2
    Scouts 1,2,3: (2, 3) --> (2, 2)
    Colony Ships 4,5,6: (2,1) --> (2,2)

Players 1/2, Movement 3
    No player moved!

Player 1, Final Locations:
    Scout 1: (2, 2)
    Scout 2: (2, 2)
    Scout 3: (2, 2)
    Colony Ship 4: (2,2)
    Colony Ship 5: (2,2)
    Colony Ship 6: (2,2)

Player 2, Final Locations:
    Scout 1: (2, 2)
    Scout 2: (2, 2)
    Scout 3: (2, 2)
    Colony Ship 4: (2,2)
    Colony Ship 5: (2,2)
    Colony Ship 6: (2,2)

COMBAT PHASE

Remaining ships: (list in the table below)

ATTACKING ORDER | PLAYER |        SHIP        | HEALTH  |
---------------------------------------------------------
       1        |    1   |         Scout 1    |    1    |
       2        |    1   |         Scout 2    |    1    |
       3        |    1   |         Scout 3    |    1    |
       4        |    2   |         Scout 1    |    1    |
       5        |    2   |         Scout 2    |    1    |
       6        |    2   |         Scout 3    |    1    |




Attack 1
Attacker: Player 1 Scout 1
Defender: Player 2 Scout 1
Miss Threshold: 3
Die Roll: 1
Hit or Miss: Hit (since Die Roll <= Miss Threshold)

ATTACKING ORDER | PLAYER |          SHIP          | HEALTH  |
-------------------------------------------------------------
       1        |    1   |         Scout 1        |    1    |
       2        |    1   |         Scout 2        |    1    |
       3        |    1   |         Scout 3        |    1    |
       4        |    2   |         Scout 2        |    1    |
       5        |    2   |         Scout 3        |    1    |

Attack 2
Attacker: Player 1 Scout 2
Defender: Player 2 Scout 2
Hit Threshold: 3
Die Roll: 2
Hit or Miss: Hit (since Die Roll <= Miss Threshold)

ATTACKING ORDER | PLAYER |          SHIP          | HEALTH  |
-------------------------------------------------------------
       1        |    1   |         Scout 1        |    1    |
       2        |    1   |         Scout 2        |    1    |
       3        |    1   |         Scout 3        |    1    |
       5        |    2   |         Scout 3        |    1    |

Attack 3
Attacker: Player 1 Scout 3
Defender: Player 2 Scout 3
Hit Threshold: 3
Dice Roll: 3
Hit or Miss: Hit (since Die Roll <= Miss Threshold)

ATTACKING ORDER | PLAYER |          SHIP          | HEALTH  |
-------------------------------------------------------------
       1        |    1   |         Scout 1        |    1    |
       2        |    1   |         Scout 2        |    1    |
       3        |    1   |         Scout 3        |    1    |

Combat phase complete

ECONOMIC PHASE

...

Problem 28-1

(ML; 60 min)

Create a file machine-learning/analysis/sandwich_ratings_interaction_terms.py to store your code/answers for this problem.

The food manufacturing company (from the previous assignment) decided to gather some more data on roast beef and peanut butter sandwiches. (The new dataset has two additional rows at the bottom.)

Slices of Roast Beef | Tablespoons of Peanut Butter | Rating |
--------------------------------------------------------------
         0           |               0              |    1   |
         1           |               0              |    2   |
         2           |               0              |    4   |
         4           |               0              |    8   |
         6           |               0              |    9   |
         0           |               2              |    2   |
         0           |               4              |    5   |
         0           |               6              |    7   |
         0           |               8              |    6   |
         2           |               2              |    0   | (new data)
         3           |               4              |    0   | (new data)

a) Using the pseudoinverse, fit another model

$$ \text{rating} = \beta_0 + \beta_1 (\text{slices beef}) + \beta_2 (\text{tbsp peanut butter}).$$

Include your answers to the following questions as comments in your code.

# QUESTION 1
# What is the model?

#    rating = ___ + ___ * (slices beef) + ___ * (tbsp peanut butter)

# QUESTION 2
# What is the predicted rating of a sandwich with 5 slices of roast beef AND 
# 5 tablespoons of peanut butter (on the same sandwich)?

#    ___

# QUESTION 3
# How does this prediction compare to that from the previous assignment? Did 
# including the additional data make the prediction trustworthy? Why or why not?

#    ___

b) Again using the pseudoinverse, fit a model that has an "interaction term" corresponding to $\beta_3.$

$$ \text{rating} = \beta_0 + \beta_1 (\text{slices beef}) + \beta_2 (\text{tbsp peanut butter}) + \beta_3 (\text{slices beef})(\text{tbsp peanut butter}), $$

Include your answers to the following questions as comments in your code.

# QUESTION 4
# Fill out the table with the additional interaction term:

# (slices beef) | (tbsp peanut butter) | (slices beef)(tbsp peanut butter) | Rating |
# -----------------------------------------------------------------------------------
#       0       |           0          |                 _                 |    1   |
#       1       |           0          |                 _                 |    2   |
#       2       |           0          |                 _                 |    4   |
#       4       |           0          |                 _                 |    8   |
#       6       |           0          |                 _                 |    9   |
#       0       |           2          |                 _                 |    2   |
#       0       |           4          |                 _                 |    5   |
#       0       |           6          |                 _                 |    7   |
#       0       |           8          |                 _                 |    6   |
#       2       |           2          |                 _                 |    0   | (new data)
#       3       |           4          |                 _                 |    0   | (new data)

# QUESTION 5
# What is the system of equations?

#   _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
#   _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
#   _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
#   _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
#   _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
#   _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
#   _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
#   _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
#   _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
#   _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
#   _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _

# QUESTION 6
# What is the matrix equation?

#   [[_, _, _, _],                   [[_],
#    [_, _, _, _],                    [_],
#    [_, _, _, _],                    [_],
#    [_, _, _, _],    [[beta_0],      [_],
#    [_, _, _, _],     [beta_1],  =   [_],     
#    [_, _, _, _],     [beta_2],      [_],
#    [_, _, _, _],     [beta_3]]      [_],
#    [_, _, _, _],                    [_],
#    [_, _, _, _],                    [_],
#    [_, _, _, _],                    [_],
#    [_, _, _, _],                    [_],
#    [_, _, _, _]]                    [_]]

# QUESTION 7
# What is the model?

#    rating = ___ + ___ * (slices beef) + ___ * (tbsp peanut butter) + ___ * (slices beef)(tbsp peanut butter)

# QUESTION 8
# What is the predicted rating of a sandwich with 5 slices of roast beef AND 
# 5 tablespoons of peanut butter (on the same sandwich)?

#    ___

# QUESTION 9
# How does this prediction compare to that from the previous assignment? Did 
# including interaction term make the prediction trustworthy? Why or why not?

#    ___

Problem 28-2

(Stats; 60 min)

Create a file assignment-problems/kl_divergence_for_monte_carlo_simulations.py to store your code/answers for this problem.

The Kullback–Leibler divergence (or relative entropy) between two probability distributions $P(X)$ and $Q(X)$ is defined as

\begin{align*} \mathcal{D}(P \, || \, Q) = \sum\limits_{X} P(X) \ln \left( \dfrac{P(X)}{Q(X)} \right) \end{align*}

Intuitively, the divergence measures how "different" the two distributions are.

a) Write a function kl_divergence(p, q) that computes the KL divergence between two probability distributions p and q, represented as arrays. Test your function by asserting that it passes the following test:

>>> p = [0.2, 0.7, 0.1]
>>> q = [0.1, 0.8, 0.1]
>>> kl_divergence(p,q)
0.04515746127
[ ^ computation for the above is 0.2*ln(0.2/0.1) + 0.7*ln(0.7/0.8) + 0.1*ln(0.1/0.1) ]

b) Compute the KL divergence where p is the Monte Carlo distribution and q is the true distribution for the number of heads in 5 coin tosses, using 1,000 samples in your Monte Carlo simulation (that's the default number from the previous assignment).

Then do the same computation with 100 samples, and then with 10,000 samples. Print out the results for all 3 computations:

>>> python assignment-problems/kl_divergence_for_monte_carlo_simulations.py

Testing KL Divergence... Passed!

Computing KL Divergence for MC Simulations...
100 samples --> KL Divergence = ___
1,000 samples --> KL Divergence = ___
10,000 samples --> KL Divergence = ___

In a comment in your code, write down what the general trend is and why:

# As the number of samples increases, the KL divergence __________ because _______________________________.

Problem 28-3

(Space Empires; 60 min)

Create a file notes/game_events_using_combat_testing_players.txt and fill out the following template for what will happen during the movement and combat phases in the first turn when two CombatTestingPlayers play each other on a 5-by-5 grid.

Assume the dice rolls come out in perfect order: 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, 3...

Note the following rules regarding attack order:

Fire combat is never simultaneous. Ships with an A Class fire before ships with a B Class, ships with a B Class fire before ships with a C, etc. If both players have groups with the same Class (for example, if both are B’s), the group belonging to the player with the higher Tactics Technology fires first. If the Class and the Tactics Technology of both groups are the same, then the defender's group fires first.

(The defender is the group that was the first to occupy the space.)

Note: You don't have to implement your tests yet. We should first make sure we're all in agreement on what the outcome of the situation should be.

STARTING CONDITIONS

Players 1 and 2
    are CombatTestingPlayers
    start with 20 CPs
    have an initial fleet of 3 scouts and 3 colony ships

---

TURN 1

MOVEMENT PHASE

Player 1, Movement 1
    Scouts 1,2,3: (2,0) --> ___

Player 2, Movement 1
    Scouts 1,2,3: (2,4) --> ___

Player 1, Movement 2
    Scout 1,2,3: ___ --> ___

Player 2, Movement 2
    Scouts 1,2,3: ___ --> ___

Players 1/2, Movement 3
    ___

Player 1, Final Locations:
    Scout 1: ___
    Scout 2: ___
    Scout 3: ___

Player 2, Final Locations:
    Scout 1: ___
    Scout 2: ___
    Scout 3: ___

COMBAT PHASE

Remaining ships: (list in the table below)

ATTACKING ORDER | PLAYER |        SHIP        | HEALTH  |
---------------------------------------------------------
       1        |    _   |         _          |    _    |
       2        |    _   |         _          |    _    |
       3        |    _   |         _          |    _    |
...

Attack 1

Attacker: ___
Defender: ___
Hit Threshold: ___
Dice Roll: ___
Hit or Miss: ___ <-- label as "Hit" or "Miss"

Remaining ships: (in the table, only list the ships which remain alive)

ATTACKING ORDER | PLAYER |        SHIP        | HEALTH  |
---------------------------------------------------------
       1        |    _   |         _          |    _    |
       2        |    _   |         _          |    _    |
       3        |    _   |         _          |    _    |
...

Attack 2

Attacker: ___
Defender: ___
Hit Threshold: ___
Dice Roll: ___
Hit or Miss: ___ <-- label as "Hit" or "Miss"

Remaining ships: (in the table, only list the ships which remain alive)

ATTACKING ORDER | PLAYER |        SHIP        | HEALTH  |
---------------------------------------------------------
       1        |    _   |         _          |    _    |
       2        |    _   |         _          |    _    |
       3        |    _   |         _          |    _    |
...

... (continue until combat is complete)

Problem 27-1

(ML; 75 min)

Create a file machine-learning/analysis/sandwich_ratings.py to store your code/answers for this problem.

A food manufacturing company is testing out some recipes for roast beef sandwiches and peanut butter sandwiches. They fed sandwiches to several subjects, and the subjects rated the sandwiches.

Slices of Roast Beef | Tablespoons of Peanut Butter | Rating |
--------------------------------------------------------------
         0           |               0              |    1   |
         1           |               0              |    2   |
         2           |               0              |    4   |
         4           |               0              |    8   |
         6           |               0              |    9   |
         0           |               2              |    2   |
         0           |               4              |    5   |
         0           |               6              |    7   |
         0           |               8              |    6   |

In this question, you will fit a plane (i.e. a linear model on 2 input variables) to the data using the following model:

$$ \text{rating} = \beta_0 + \beta_1 \times (\text{slices beef}) + \beta_2 \times (\text{tbsp peanut butter})$$

a) As a comment in your code, fill in the system of $9$ linear equations that we seek to satisfy. (Each data point corresponds to a linear equation.)

#   ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
#   ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
#   ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
#   ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
#   ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
#   ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
#   ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
#   ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
#   ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___

b) As a comment in your code, fill in the corresponding matrix equation:

#   [[___, ___, ___],                   [[___],
#    [___, ___, ___],                    [___],
#    [___, ___, ___],                    [___],
#    [___, ___, ___],    [[beta_0],      [___],
#    [___, ___, ___],     [beta_1],  =   [___],     
#    [___, ___, ___],     [beta_2]]      [___],
#    [___, ___, ___],                    [___],
#    [___, ___, ___],                    [___],
#    [___, ___, ___]]                    [___]]

Note: the comment above is meant to illustrate the following format:

\begin{align} \underbrace{\begin{bmatrix} \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \end{bmatrix}}_{X} \underbrace{\begin{bmatrix} \_\_ \\ \_\_ \\ \_\_ \end{bmatrix}}_{\vec{\beta}} &= \underbrace{\begin{bmatrix} \_\_ \\ \_\_ \\ \_\_ \\ \_\_ \\ \_\_ \\ \_\_ \\ \_\_ \\ \_\_ \\ \_\_ \end{bmatrix}}_{\vec{y}} \end{align}

c) Use your Matrix class to compute the least-squares approximation. Do this computation in the file machine-learning/analysis/sandwich-ratings.py.

$$\vec{\beta} \approx \left( X^T X \right)^{-1} X^T \vec{y}$$

As a comment in your code, fill in the blanks in the resulting model:

#   rating = ___ + ___ * (slices of beef) + ___ * (tbsp peanut butter)

d) Use your model to predict the rating of a sandwich with $5$ slices of roast beef and no peanut butter. Your code should print out this value, and label that it corresponds to $5$ slices of roast beef and no peanut butter.

e) Predict the rating of a sandwich with $5$ slices of roast beef AND $5$ tablespoons of peanut butter (both ingredients on the same sandwich). Your code should print out this value, and label that it corresponds to $5$ slices of roast beef and $5$ tbsp peanut butter.

Should the company trust this prediction? Why or why not? Write your answer as a comment in your code.

# ____, because __________________________________________________________

Problem 27-2

(Space Empires; 90 min)

Create the following classes:

  • Create a class CombatTestingPlayer that uses the following strategy:

    • before buying any ships, buy ship size technology 2
    • alternate between buying Destroyers and Scouts, starting off buying a Destroyer. If it can't pay for the next ship, then just wait until the next turn to buy it.
    • always move ships towards the center of the board, and have the ships stop there
    • during combat, don't screen any ships, and always attack the opposing ship that is highest in the attacking order.

  • Create a class CombatEngine that handles all of the combat functionality, and refactor your Game so that whenever it enters combat phase, it gathers the units that occupy the same grid space and passes them into CombatEngine for processing:

Game asks Board what ships are on the same grid space
Game passes ships into CombatEngine
CombatEngine asks Players what ships they want to screen
CombatEngine figures out the attacking order
while combat is occurring:
    for each Unit in the attacking order:
            CombatEngine asks the unit's Player what other unit they want to attack
            CombatEngine executes the attack by rolling the dice and logging any hit as appropriate
Game proceeds onwards to economic phase

Make sure that when two CombatPlayers play against each other, there are many battles taking place at the center of the board.

Also, make sure that your CombatEngine is implemented well. I DON'T want to see anything ridiculous like CombatEngine inheriting from Game or Board, or implementing any sort of strategy on its own. The Player is the only thing that should be implementing strategy.

Next time, we'll figure out how to test CombatEngine to ensure that the combat is progressing correctly. But this time, just focus on pulling out the Game's combat methods and moving it into CombatEngine.

Problem 26-1

(Stats; 30 min)

a) Using your function probability(num_heads, num_flips), plot the distribution for the number of heads in 10 coin flips. In other words, plot the curve $y=p(x),$ where $p(x)$ is the probability of getting $x$ heads in $10$ coin flips.

b) Make 5 more plots, each using your function monte_carlo_probability(num_heads, num_flips).

c) Put all your plots on the same graph, label them with a legend to indicate whether each plot is the true distribution or a monte carlo simulation, and save the figure as plot.png.

Legend: True, MC 1, MC 2, MC 3, MC 4, MC 5.

Make the true distribution thick (linewidth=2.5) and the monte carlo distributions thin (linewidth=0.75). A plotting example is shown below to assist you.

In [ ]:
import matplotlib.pyplot as plt
plt.style.use('bmh')
plt.plot([0,1,2,3,4],[0.1, 0.3, 0.5, 0.1, 0.1],linewidth=2.5)
plt.plot([0,1,2,3,4],[0.3, 0.1, 0.4, 0.2, 0.1],linewidth=0.75)
plt.plot([0,1,2,3,4],[0.2, 0.2, 0.3, 0.3, 0.2],linewidth=0.75)
plt.legend(['True','MC 1','MC 2'])
plt.xlabel('Number of Heads')
plt.ylabel('Probability')
plt.title('True Distribution vs Monte Carlo Simulations for 10 Coin Flips')
plt.savefig('plot.png')

Problem 26-2

(Algo; 90 min)

Problem Context

Suppose that a railroad network has a list of all of its segments between two towns. For example, if

railroad_segments = [('B','C'), ('B','A'), ('A','D'), ('E','D'), ('C','F'), ('G','C')]

then the towns could be arranged as

A -- B -- C -- F
 \         \
  D -- E    G

Assume that

  • segments can be traveled either way, i.e. ('B','C') means you can go from 'B' to 'C' or you can go from 'C' to 'B',
  • each railroad segment corresponds to the same travel time, and that
  • the railroad segments never form a loop (in other words, to get from any town to another, there is only one possible path that does not backtrack on itself).

Problem Statement

Write a function order_towns_by_travel_time(starting_town, railroad_segments) that lists the towns in order of travel time from the starting_town. Implement this function using two different techniques, both of which we went over during class:

  1. order_towns_by_travel_time_using_tree_class(starting_town, railroad_segments): modify the railroad_segments edge list so that you can pass it into your Tree class and call the breadth_first_traversal() method.

  2. order_towns_by_travel_time_from_scratch(starting_town, railroad_segments): implement breadth first search from scratch, so that it uses the railroad_segments edge list as-is.

Where to Store / Test the Code

  1. Create a repository graph.

  2. Put your Tree class in graph/src/tree.py.

  3. Implement the functions order_towns_by_travel_time_using_tree_class and order_towns_by_travel_time_from_scratch in a file graph/analysis/railroad_travel_time.py.

  4. Create a testing file graph/analysis/test_railroad_travel_time.py, and ASSERT THAT BOTH OF YOUR FUNCTIONS PASS THE FOLLOWING TESTS:

>>> railroad_segments = [('B','C'), ('B','A'), ('A','D'), ('E','D'), ('C','F'), ('G','C')]
>>> order_towns_by_travel_time('D', railroad_segments)
can return either of two possible answers:
[D, E, A, B, C, F, G]
[D, A, E, B, C, F, G]
[D, E, A, B, C, G, F]
[D, A, E, B, C, G, F]

>>> order_towns_by_travel_time('A', railroad_segments)
can return either of eight possible answers:
[A, D, B, C, E, F, G]
[A, B, D, C, E, F, G]
[A, D, B, E, C, F, G]
[A, B, D, E, C, F, G]
[A, D, B, C, E, G, F]
[A, B, D, C, E, G, F]
[A, D, B, E, C, G, F]
[A, B, D, E, C, G, F]

Problem 26-3

(SWE; 0-90 min)

Resolve ALL the remaning issues on your refactoring list. This is the third assignment on which significant time was devoted to refactoring, so I'm expecting you to have 100% of the issues resolved before the next class. Next to your name, it should say "0 issues remaining".

Problem 25-1

(Stats; 60 min)

In this problem, you will compute the probability of getting num_heads heads in num_flips flips of a fair coin. You will do this using two different methods. You should write your functions in a file assignment-problems/coin_flipping.py

a) Write a function probability(num_heads, num_flips) that uses mathematics to compute the probability.

  • First, compute the total number of possible outcomes for num_flips flips. (Hint: it's an exponent.)

  • Then, compute the number of outcomes in which num_heads heads arise in num_flips flips. (Hint: it's a combination.)

  • Then, divide the results.

b) Write a function monte_carlo_probability(num_heads, num_flips) that uses simulation to compute the probability.

  • First, simulate 1000 trials of num_flips coin flips, keeping track of how many heads there were.

  • Then, divide the number of outcomes in which there were num_heads heads, by the total number of trials (1000).

c) When you run assignment-problems/coin_flipping.py, you should print out the result of probability(5,8). Also, print out 3 instances of monte_carlo_probability(5,8).

  • The 3 instances will be slightly different because it's a random simulation, but they should be fairly close to each other and to the true result.

Problem 25-2

(SWE; 120 min)

a) Resolve the remaining issues on your refactoring list.

b) In tests/test_matrix.py, test that the inverse is correctly computed for the following matrices. To do this, you should compute the inverse, multiply the matrix by its inverse, and then check that the result (when rounded to 6 decimal places) is equal to the identity matrix.

A = [[1, 2, 3, 4],
     [5, 0, 6, 0],
     [0, 7, 0, 8],
     [9, 0, 0, 10]]

assert round_down(A @ A.inverse()) == identity_matrix

B = [[1.2, 5.3, 8.9, -10.3, -15],
     [3.14, 0, -6.28, 0, 2.71],
     [0, 1, 1, 2, 3],
     [5, 8, 13, 21, 34],
     [1, 0, 0.5, 0, 0.1]]

assert round_down(B @ B.inverse()) == identity_matrix

Problem 24-1

(ML; 30 min)

For this problem, make a file machine-learning/analysis/rocket_takeoff_regression.py and put your code there.

Recall the following dataset, which represents the distance between a rocket and Earth's surface, as the rocket takes off. The data points are given in the form (time, distance).

data = [(1, 3.1), (2, 10.17), (3, 20.93), (4, 38.71), (5, 60.91), (6, 98.87), (7, 113.92), (8, 146.95), (9, 190.09), (10, 232.65)]

a) Using your PolynomialRegression class, fit a quadratic to the data:

$$y = \beta_0 + \beta_1 t + \beta_2 t^2$$

According to the quadratic, what is the predicted position of the rocket after 200 seconds? Make rocket_takeoff_regression.py print out your answer.

b) Your friend claims that a cubic model will better fit the data. So, using your PolynomialRegression class, fit a cubic to the data:

$$y = \beta_0 + \beta_1 x + \beta_2 x^2 + \beta_3 x^3$$

According to the cubic, what is the predicted position of the rocket after 200 seconds? Make rocket_takeoff_regression.py print out your answer.

c) Which model is better, the quadratic or the cubic? Justify your answer. Write your answer as a comment in rocket_takeoff_regression.py

Problem 24-2

(SWE; 180 min)

Catch up: Make sure your tests for machine-learning/test/test_matrix.py and space-empires/src/test_dumb_player.py are working and complete.

  • Make sure that your DumbPlayer test is using assert statements to check the relevant aspects of the game. You should NOT just print out the logging data and compare it visually. Rather, for each test, you should print out what you're testing for and whether the test passed.

Naming conventions:

  • Make sure all your files are named properly, using snake_case and correct grammar.

  • Make sure all your classes are named as nouns and all your methods/functions are named as verbs. This includes past files as well.

Refactoring: Resolve all the high-priority issues on your refactoring list.

NOTE: There's really not much else on this assignment, so I'm expecting you to get all of the above done over the weekend. If you run into any prolonged trouble, please make a post on Discord! If you find yourself not making progress on an issue for 30 min or more, just make a post for help and move onto another thing.

Problem 23-1

(DS/Algo; 60 min)

Create a testing file tests/test_matrix.py that tests your matrix methods

  • 1 test for each arithmetic operation: addition, subtraction, scalar multiplication, matrix multiplication, transpose.

  • 6 tests for reduced row echelon form. You should test all combinations of the following cases:

    1. a a square matrix, a tall rectangular matrix, and a wide rectangular matrix;
    2. has the maximum number of possible pivots (i.e. no pivot disappears); has fewer than the maximum number of pivots (i.e. some pivot disappears)

  • 3 tests for each of inverse, inverse by minors, determinant, and recursive determinant (so, 12 tests in all).

    1. the case when the matrix is invertible
    2. the case when the matrix is not invertible due to having dependent rows
    3. the case when the matrix is not invertible due to not being square

Problem 23-2

(DS/Algo; 45 min)

Write a recursive function divide_and_conquer_sort(x) that sorts an input list x according to the following technique:

If the input list consist of more than one element, then split the list into the first half and the second half, recursively use divide_and_conquer_sort to sort each half, combine the two sorted halves, and return the result. Otherwise, if the input list consists of only one element, then the input list is already sorted and you can return it.

Put your function in assignment-problems and create a testing file that implements 4 tests, each of which are significantly different in some way.

HERE IS SOME PSEUDOCODE TO HELP YOU STRUCTURE YOUR FUNCTION:

divide_and_conquer_sort(input list):
    if the input list consists of more than one element:
        break up the input list into its left and right halves
        sort the left and right halves by recursively calling divide_and_conquer_sort
        combine the two sorted halves
        return the result
    otherwise, if the input list consists of only one element, then it is already sorted,
        and you can just return it.

And here is an example of what's going on under the hood:

input list:[6,9,7,4,2,1,8,5]
break it in half: [6,9,7,4] [2,1,8,5]
use divide_and_conquer_sort recursively to sort the two halves

    input list: [6,9,7,4]
    break it in half: [6,9] [7,4]
    use divide_and_conquer_sort recursively to sort the two halves

        input list: [6,9]
        break it in half: [6] [9]
        the two halves have only one element each, so they are already sorted
        so we can combine them to get [6,9]

        input list: [7,4]
        break it in half: [7] [4]
        the two halves have only one element each, so they are already sorted
        so we can combine them to get [4,7]

    now we have two sorted lists [6,9] and [4,7]
    so we can combine them to get [4,6,7,9]

    input list: [2,1,8,5]
    break it in half: [2,1] [8,5]
    use divide_and_conquer_sort recursively to sort the two halves

        input list: [2,1]
        break it in half: [2] [1]
        the two halves have only one element each, so they are already sorted
        so we can combine them to get [1,2]

        input list: [8,5]
        break it in half: [8] [5]
        the two halves have only one element each, so they are already sorted
        so we can combine them to get [5,8]

    now we have two sorted lists [1,2] and [5,8]
    so we can combine them to get [1,2,5,8]

now we have two sorted lists [4,6,7,9] and [1,2,5,8]
so we can combine them to get [1,2,4,5,6,7,8,9]

Problem 23-3

(SWE; 90 min)

Write a testing file tests/test_dumb_player.py to ensure that a game on a $5 \times 5$ grid with two DumbPlayers proceeds correctly.

Over the course of 4 turns, you should check the board for the following 8 tests:

  1. At the end of Turn 1 Movement Phase:

    • Player 1 has 3 scouts at (4,0)
    • Player 2 has 3 scouts at (4,4)

  2. At the end of Turn 1 Economic Phase:

    • Player 1 has 3 scouts at (4,0) and 3 scouts at (2,0)
    • Player 2 has 3 scouts at (4,4) and 3 scouts at (2,4)
    • Players 1/2 have 2 CPs each

  3. At the end of Turn 2 Movement Phase:

    • Player 1 has 6 scouts at (4,0)
    • Player 2 has 6 scouts at (4,4)

  4. At the end of Turn 2 Economic Phase:

    • Player 1 has 5 scouts at (4,0)
    • Player 2 has 5 scouts at (4,4)
    • Players 1/2 have 0 CPs each

  5. At the end of Turn 3 Movement Phase:

    • Player 1 has 5 scouts at (4,0)
    • Player 2 has 5 scouts at (4,4)

  6. At the end of Turn 3 Economic Phase:

    • Player 1 has 3 scouts at (4,0)
    • Player 2 has 3 scouts at (4,4)
    • Players 1/2 have 0 CPs each

  7. At the end of Turn 4 Movement Phase:

    • Player 1 has 3 scouts at (4,0)
    • Player 2 has 3 scouts at (4,4)

  8. At the end of Turn 4 Economic Phase:

    • Player 1 has 3 scouts at (4,0)
    • Player 2 has 3 scouts at (4,4)
    • Players 1/2 have 0 CPs each

For your reference, here's my scratch work when figuring out the conditions above.

STARTING CONDITIONS

Players 1 and 2
    are DumbPlayers
    start with 20 CPs
    have an initial fleet of 3 scouts and 3 colony ships

---

TURN 1

MOVEMENT PHASE

Player 1, Movement 1
    Scouts 1,2,3: (2,0) --> (3,0)

Player 2, Movement 1
    Scouts 1,2,3: (2,4) --> (3,4)

Player 1, Movement 2
    Scout 1,2,3: (3,0) --> (4,0)

Player 2, Movement 2
    Scouts 1,2,3: (3,4) --> (4,4)

Players 1/2, Movement 3
    no movements occur

Player 1, Final Locations:
    Scout 1: (4,0)
    Scout 2: (4,0)
    Scout 3: (4,0)

Player 2, Final Locations:
    Scout 1: (4,4)
    Scout 2: (4,4)
    Scout 3: (4,4)

COMBAT PHASE

no combats occur

ECONOMIC PHASE

Players 1/2
    starting CP: 20
    colony income: 3 CP/Colony x 1 Colony = 3 CP
    maintenance costs: 1 CP/Scout x 3 Scouts = 3 CP
    remaining CP: 20
    buy scouts: 6 CP/Scout x 3 Scouts = 18 CP
    remaining CP: 2

---

TURN 2

MOVEMENT PHASE

Player 1, Movement 1
    Scouts 4,5,6: (2,0) --> (3,0)

Player 2, Movement 1
    Scouts 4,5,6: (2,4) --> (3,4)

Player 1, Movement 2
    Scout 4,5,6: (3,0) --> (4,0)

Player 2, Movement 2
    Scouts 4,5,6: (3,4) --> (4,4)

Players 1/2, Movement 3
    no movements occur

Player 1, Final Locations:
    Scout 1: (4,0)
    Scout 2: (4,0)
    Scout 3: (4,0)
    Scout 4: (4,0)
    Scout 5: (4,0)
    Scout 6: (4,0)

Player 2, Final Locations:
    Scout 1: (4,4)
    Scout 2: (4,4)
    Scout 3: (4,4)
    Scout 4: (4,4)
    Scout 5: (4,4)
    Scout 6: (4,4)

COMBAT PHASE

no combats occur

ECONOMIC PHASE

Players 1/2
    starting CP: 2
    colony income: 3 CP/Colony x 1 Colony = 3 CP
    maintenance costs: 1 CP/Scout x 6 Scouts = 6 CP
    unable to maintain Scout 6; Scout 6 is removed
    remaining CP: 0

---

TURN 3

MOVEMENT PHASE

Players 1/2, Movements 1/2/3
    no movements occur

Player 1, Final Locations:
    Scout 1: (4,0)
    Scout 2: (4,0)
    Scout 3: (4,0)
    Scout 4: (4,0)
    Scout 5: (4,0)

Player 2, Final Locations:
    Scout 1: (4,4)
    Scout 2: (4,4)
    Scout 3: (4,4)
    Scout 4: (4,4)
    Scout 5: (4,4)

COMBAT PHASE

no combats occur

ECONOMIC PHASE

Players 1/2
    starting CP: 0
    colony income: 3 CP/Colony x 1 Colony = 3 CP
    maintenance costs: 1 CP/Scout x 5 Scouts = 5 CP
    unable to maintain Scouts 4/5; Scouts 4/5 are removed
    remaining CP: 0

---

TURN 3

MOVEMENT PHASE

Players 1/2, Movements 1/2/3
    no movements occur

Player 1, Final Locations:
    Scout 1: (4,0)
    Scout 2: (4,0)
    Scout 3: (4,0)

Player 2, Final Locations:
    Scout 1: (4,4)
    Scout 2: (4,4)
    Scout 3: (4,4)

COMBAT PHASE

no combats occur

ECONOMIC PHASE

Players 1/2
    starting CP: 0
    colony income: 3 CP/Colony x 1 Colony = 3 CP
    maintenance costs: 3 CP/Scout x 3 Scouts = 3 CP
    remaining CP: 0

---

all future turns continue the same way as TURN 3

Problem 22-1

(ML; 30 min)

Create a file tests/test_polynomial_regressor.py to test your PolynomialRegressor on the following tests. (Round the comparisons to 6 decimal places.)

from polynomial_regressor import PolynomialRegressor
data = [(0,1), (1,2), (2,5), (3,10), (4,20), (5,30)]

constant_regressor = PolynomialRegressor(degree=0)
constant_regressor.ingest_data(data)
constant_regressor.solve_coefficients()
constant_regressor.coefficients
[11.333333333333332]
constant_regressor.evaluate(2)
11.333333333333332

linear_regressor = PolynomialRegressor(degree=1)
linear_regressor.ingest_data(data)
linear_regressor.solve_coefficients()
linear_regressor.coefficients
[-3.2380952380952412, 5.828571428571428]
linear_regressor.evaluate(2)
8.419047619047616

quadratic_regressor = PolynomialRegressor(degree=2)
quadratic_regressor.ingest_data(data)
quadratic_regressor.solve_coefficients()
quadratic_regressor.coefficients
[1.107142857142763, -0.6892857142856474, 1.3035714285714226]
quadratic_regressor.evaluate(2)
4.942857142857159

cubic_regressor = PolynomialRegressor(degree=3)
cubic_regressor.ingest_data(data)
cubic_regressor.solve_coefficients()
cubic_regressor.coefficients
[1.1349206349217873, -0.8161375661377197, 1.3730158730155861, -0.009259259259233155]
cubic_regressor.evaluate(2)
4.920634920634827

fifth_degree_regressor = PolynomialRegressor(degree=5)
fifth_degree_regressor.ingest_data(data)
fifth_degree_regressor.solve_coefficients()
fifth_degree_regressor.coefficients
[0.9999999917480108, -2.950000002085698, 6.9583333345161265, -3.9583333337779045, 1.0416666667658463, -0.09166666667401097]
fifth_degree_regressor.evaluate(2)
4.999999990103076

Problem 22-2

(DS/Algo; 30 min)

a) Make a new repository assignment-problems. Going forward, this repository will hold any miscellaneous functions you write in assignments.

b) Write a function combine_sorted_lists(x,y) that combines two sorted lists x and y so that the result itself is also sorted. You should build up the output list by going through x and y in parallel, and repeatedly taking the smallest value.

  • IMPORTANT CLARIFICATION: You should not be mutating the underlying lists. During the example in class, we removed items from x and y and put them in a new list, but you shouldn't actually remove anything from x and y. Rather, you should just loop through each list in parallel, keeping track of your indices in x and y, and repeatedly bring a copy of the smallest element into the output list.
>>> combine_sorted_lists([1,3,4,5,7],[2,6])
[1,2,3,4,5,6,7]

c) Put your function in a file combine_sorted_lists.py. Then, create a file test_combine_sorted_lists.py that runs $4$ tests on the function you wrote.

  • Be sure to consider a variety of test cases. In particular, make sure your code works on edge-cases, such as when list items are repeated.

Problem 22-3

(SWE; 90 min)

a) Create a new class RandomPlayer that inherits from Player. Then, take any methods in Player for which random strategy is currently used, and move them to RandomPlayer.

  • Such methods include move, build_fleet, etc.

b) Create another class DumbPlayer that has the same format as RandomPlayer, but that uses the following strategy:

  • Only spend money on scouts. Always build as many scouts as possible, and don't ever buy anything else (not even technology).

  • Always move ships to the right.

c) Put the player class files in a folder player/ that is analogous to the unit/ folder. So, you should have

src/
|- player/
.  |- player.py
.  |- random_player.py
.  |- dumb_player.py

d) Check to see what happens when two DumbPlayers play the game. You should have a bunch of scouts collect on the right.

e) Check to see what happens when a RandomPlayer plays against a DumbPlayer.

Problem 22-4

(Journal Club; 30 min)

Watch this video on AlphaStar, and think about the following questions. We'll discuss them in class next time, and I'm going to expect everyone to have a thought-out response to each of these questions! (Feel free to watch at higher speed, if you're able to process the information to answer the questions below.)

  • What is deep learning, what is reinforcement learning, and how does AlphaStar integrate them?

  • What are main agents and exploiter agents? How are they different, and why are exploiter agents used?

  • How did AlphaStar perform? Was it better than half of the human players? Better than 9 out of 10 human players? Better than that?

Problem 21-0

Update your file names to be snake case (here's an explanation of why). Also, don't use abbreviations. Write the whole name.

So, you should have:

machine-learning/
|- src/
.  |- matrix.py
.  |- polynomial_regressor.py
.  |- gradient_descent.py
|- tests/
.  |- test_gradient_descent.py
space-empires/
|- src/
.  |- game.py
.  |- player.py
.  |- unit/
.     |- unit.py
.     |- scout.py
.     |- battleship.py
.     |- and so on...

Problem 21-1

(DS/Algo; 60 min)

Write a function cartesian_product(arrays) that computes the Cartesian product of all the lists in arrays.

>>> cartesian_product([['a'], [1,2,3], ['Y','Z']])
[['a',1,'Y'], ['a',1,'Z'], ['a',2,'Y'], ['a',2,'Z'], ['a',3,'Y'], ['a',3,'Z']]

NOTE: This is a reasonably short function if you use the following procedure. You'll probably have to think a bit in order to get the implementation correct, though.

  1. Create a variable points that will be a list of all the points in the cartesian product. Initially, set points to consist of a single empty point: points = [[]].

  2. For each array in the input, create a new list of points.

    • The new set of points can be constructed by looping through each existing point and, for each existing point, adding several new points.

      • For a given point, the new points can be constructed by appending each element of the array onto a copy of the given point.

  3. Return the list of points.

Worked Example:

arrays = [['a'], [1,2,3], ['Y','Z']]

points: [[]]
considering array ['a']
considering element 'a'
new point ['a']

points: [['a']]
considering array [1,2,3]
considering element 1
new point ['a',1]
considering element 2
new point ['a',2]
considering element 3
new point ['a',3]

points: [['a',1], ['a',2], ['a',3]]
considering array ['Y','Z']
considering element 'Y'
new points ['a',1,'Y'], ['a',2,'Y'], ['a',3,'Y']
considering element 'Z'
new points ['a',1,'Z'], ['a',2,'Z'], ['a',3,'Z']

points: [[1,'a','Y'], [1,'a','Z'], [1,'b','Y'], [1,'b','Z'], [1,'c','Y'], [1,'c','Z']]

Problem 21-2

(ML; 60 min)

a) In GradientDescent, clean up tests/test_gradient_descent.py.

  • For each comparison of floating-point decimals, round to 10 decimal places before you check for equality.

  • The only things you should print are the name of each test, and if the test fails, then your custom error message. You can use the format below, or come up with your own format provided that it meets the specifications in the previous sentence.

>>> python tests/test_gradient_descent.py

Testing...

compute_gradient
    single_variable_function
    two_variable_function
    three_variable_function
    six_variable_function

descend
    single_variable_function
    two_variable_function

AssertionError: incorrect output for descend on three_variable_function
OUTPUT: [3.0020000000000000018, 2.0030001000000000055, 1.004000400000000004]
DESIRED: [0.0020000000000000018, -0.0030001000000000055, 0.004000400000000004]

b) In GradientDescent, generalize your grid_search to work on objective functions of any number of variables.

  • HINT: You wrote a cartesian_product function in Problem 1, so use it here as a helper function! Just loop over the cartesian product of the input arrays.

  • Note: For now, don't worry about applying gradient descent within the grid search. Just find the grid point with the lowest value of the function.

Lastly, use assert statements to write the following additional tests for your GradientDescent class, and make sure all your tests pass. Put these additional tests in tests/test_gradient_descent.py.

>>> def single_variable_function(x):
        return (x-1)**2
>>> def two_variable_function(x, y):
        return (x-1)**2 + (y-1)**3
>>> def three_variable_function(x, y, z):
        return (x-1)**2 + (y-1)**3 + (z-1)**4
>>> def six_variable_function(x1, x2, x3, x4, x5, x6):
        return (x1-1)**2 + (x2-1)**3 + (x3-1)**4 + x4 + 2*x5 + 3*x6

>>> minimizer = GradientDescent(single_variable_function)
>>> minimizer.grid_search([[0, 0.25, 0.75]])
>>> minimizer.minimum
[0.75]

>>> minimizer = GradientDescent(two_variable_function)
>>> minimizer.grid_search([[0, 0.25, 0.75], [0.9, 1, 1.1]])
>>> minimizer.minimum
[0.75, 0.9]

>>> minimizer = GradientDescent(three_variable_function)
>>> minimizer.grid_search([[0, 0.25, 0.75], [0.9, 1, 1.1], [0, 1, 2, 3]])
>>> minimizer.minimum
[0.75, 0.9, 1]

>>> minimizer = GradientDescent(six_variable_function)
>>> minimizer.grid_search([[0, 0.25, 0.75], [0.9, 1, 1.1], [0, 1, 2, 3],
                          [-2, -1, 0, 1, 2], [-2, -1, 0, 1, 2], [-2, -1, 0, 1, 2]])
>>> minimizer.minimum
[0.75, 0.9, 1, -2, -2, -2]

Problem 21-3

(SWE; 30 min)

If you haven't already, create a class Board that stores the coordinates of all the units.

  • During combat, the Game should check the Board to identify which units occupy the same spot.

  • The Game should not store its dimensions as an attribute. Rather, it should store a reference to the Board, and the Board should store its dimensions as an attribute.

    • For example, you should never have Game.dimensions. Rather, you would have Game.board.dimensions.

Problem 20-1

(ML; 30-90 min)

Notice that we can test code and print out custom error messages using assert statements:

In [ ]:
should_be_zero = 42
assert should_be_zero == 0, 'should_be_zero is NOT zero'
In [ ]:
should_be_one = 1
assert should_be_one == 1, 'should_be_one is NOT one'
In [ ]:
def add_numbers(x,y):
    return x - y

# let's test the function above to see if it works right
test_function = add_numbers
tests = [
    {'args':(0, 0), 'output': 0}, # will pass
    {'args':(1, 0), 'output': 1}, # will pass
    {'args':(0, 1), 'output': 1}, # will not pass; output will be -1
    {'args':(1, 1), 'output': 2}
]

for test in tests:
    actual_output = test_function(*test['args'])
    desired_output = test['output']
    error_message = 'incorrect output for {}'.format(
        test_function.__name__
    )
    details = '\nINPUT: {}\nOUTPUT: {}\nDESIRED: {}'.format(
        test['args'], actual_output, desired_output
    )
    assert actual_output == desired_output, error_message + details

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-5-9bacb3318584> in <module>()
     20         test['args'], actual_output, desired_output
     21     )
---> 22     assert actual_output == desired_output, error_message + details

AssertionError: incorrect output for add_numbers
INPUT: (0, 1)
OUTPUT: -1
DESIRED: 1

Extend your machine-learning library to include the following 8 tests for GradientDescent.py. For each function, test that GradientDescent computes the correct gradient, and that the minimum is correct after descending once along the gradient.

>>> def single_variable_function(x):
        return (x-1)**2
>>> def two_variable_function(x, y):
        return (x-1)**2 + (y-1)**3
>>> def three_variable_function(x, y, z):
        return (x-1)**2 + (y-1)**3 + (z-1)**4
>>> def six_variable_function(x1, x2, x3, x4, x5, x6):
        return (x1-1)**2 + (x2-1)**3 + (x3-1)**4 + x4 + 2*x5 + 3*x6

>>> minimizer = GradientDescent(single_variable_function)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1)
>>> minimizer.minimum
[0.0020000000000000018]

>>> minimizer = GradientDescent(two_variable_function)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018, 3.0001000000000055]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1)
>>> minimizer.minimum
[0.0020000000000000018, -0.0030001000000000055]

>>> minimizer = GradientDescent(three_variable_function)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018, 3.0001000000000055, -4.0004000000000035]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1)
>>> minimizer.minimum
[0.0020000000000000018, -0.0030001000000000055, 0.004000400000000004]

>>> minimizer = GradientDescent(six_variable_function)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018, 3.0001000000000055, -4.0004000000000035, 1.0000000000000009, 2.0000000000000018, 3.0000000000000027]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1)
>>> minimizer.minimum
(0.0020000000000000018, -0.0030001000000000055, 0.004000400000000004, -0.0010000000000000009, -0.0020000000000000018, -0.0030000000000000027)

You should be able to execute the tests by running tests/test_GradientDescent.py. MAKE SURE THAT ALL YOUR TESTS PASS, and make sure to push your finished code to Github for safekeeping.

machine-learning/
|- src/
.  |- Matrix.py
.  |- PolynomialRegressor.py
.  |- GradientDescent.py
|- tests/
.  |- test_GradientDescent.py

Problem 20-2

(SWE; 60 min)

Refactor your space-empires library so that each movement phase consists of three movements. (No combat occurs during movement phase.)

  • Replace Speed Technology with Movement Technology, under the following settings:
Movement Technology Level | Additional CP Cost | Benefit
---------------------------------------------------------
            1             |       at start     | Can move one space per movement
            2             |         20         | Can move 1 space in each of the first 2 movements and 2 spaces in the third movement
            3             |         30         | Can move 1 space in the first movement and 2 spaces in each of the second and third movements
            4             |         40         | Can move 2 spaces per movement
            5             |         40         | Can move 2 spaces in each of the first 2 movements and 3 spaces in the third movement
            6             |         40         | Can move 2 spaces in the first movement and 3 spaces in each of the second and third movements
  • Note: if you had previously "normalized" the maintenance costs by dividing by 3, then remove that.

Note the following answers to some Space Empires questions that were asked recently:

  • There are no maintenance costs for Colony Ships, Bases

  • If the colony is destroyed are the shipyards on it destroyed too? Yes.

  • You cannot place multiple colonies on the same planet.

If you haven't already, put indents and blank lines in your game logging so that it's easier to read. Example:

-------------------------------------------------
TURN 12 - MOVEMENT PHASE

Player 1 - Move 1
    Unit 1 (Scout) moves from (1,2) to (2,2)
    Unit 1 (Battleship) moves from (3,2) to (4,2)

Player 2 - Move 1
    Unit 1 (Scout) moves from (3,4) to (2,4)

Player 1 - Move 2
    Unit 1 (Scout) moves from (2,2) to (3,2)
    Unit 1 (Battleship) moves from (4,2) to (4,1)

Player 2 - Move 2
    Unit 1 (Scout) moves from (2,4) to (1,4)

...
-------------------------------------------------

Make sure to push your finished code to Github for safekeeping.

Problem 19-1

(30 min)

  1. Create a Github account and create a repository machine-learning.
  2. Create a repl.it account and import the repository into a new repl.
  3. Create a folder src and paste your classes into files:
    • Matrix into Matrix.py
    • PolynomialRegressor into PolynomialRegressor.py
    • GradientDescent into GradientDescent.py

  4. Commit and push the repository to your Github. The repository should have the following structure:

    machine-learning/
|- src/
.  |- Matrix.py
.  |- PolynomialRegressor.py
.  |- GradientDescent.py

  5. Create another Github repository space-empires and paste each class into its own file within a folder src. This repository should have the following structure:

    space-empires/
|- src/
.  |- Game.py
.  |- Player.py
.  |- Unit/
.     |- Unit.py
.     |- Scout.py
.     |- Battleship.py
.     |- and so on...

Problem 19-2

(ML; 60 min)

Make sure that your GradientDescent class works with functions of any number of arguments.

Tip: if you have a function f(x,y,z) and a list args = [0,5,3], then you can pass f(*args) to evaluate f(0,5,3).

Here's Riley's method for detecting the number of arguments to a function f:

self.num_vars = len(inspect.getfullargspec(f).args)

Likewise, here's Elijah's method:

self.num_vars = f.__code__.co_argcount

Here is how to clone your machine-learning repository and import your GradientDescent:

 >>> !git clone https://github.com/yourUserName/machine-learning.git

 >>> import sys
 >>> sys.path.append("/content/machine-learning/src/")
 >>> from GradientDescent import GradientDescent

Here are some tests:

>>> def single_variable_function(x):
        return (x-1)**2
>>> def two_variable_function(x, y):
        return (x-1)**2 + (y-1)**3
>>> def three_variable_function(x, y, z):
        return (x-1)**2 + (y-1)**3 + (z-1)**4
>>> def six_variable_function(x1, x2, x3, x4, x5, x6):
        return (x1-1)**2 + (x2-1)**3 + (x3-1)**4 + x4 + 2*x5 + 3*x6

>>> minimizer = GradientDescent(single_variable_function)
>>> minimizer.minimum
(0)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1, logging=True)
(0.0020000000000000018)

>>> minimizer = GradientDescent(two_variable_function)
>>> minimizer.minimum
(0, 0)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018, 3.0001000000000055]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1, logging=True)
(0.0020000000000000018, -0.0030001000000000055)

>>> minimizer = GradientDescent(three_variable_function)
>>> minimizer.minimum
(0, 0, 0)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018, 3.0001000000000055, -4.0004000000000035]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1, logging=True)
(0.0020000000000000018, -0.0030001000000000055, 0.004000400000000004)

>>> minimizer = GradientDescent(six_variable_function)
>>> minimizer.minimum
(0, 0, 0, 0, 0, 0)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018, 3.0001000000000055, -4.0004000000000035, 1.0000000000000009, 2.0000000000000018, 3.0000000000000027]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1, logging=True)
(0.0020000000000000018, -0.0030001000000000055, 0.004000400000000004, -0.0010000000000000009, -0.0020000000000000018, -0.0030000000000000027)

Problem 19-3

(SWE; 60 min)

On repl.it, refactor your game so that each turn consists of three phases: movement, combat, economic.

  • During the "movement" phase, all players move their ships.
  • During the "combat" phase, all ships that occupy the same grid space engage in combat.
  • During the "economic" phase, all players receive income and buy ships / technologies.

You should have a separate method for each of these phases:

  • Game.complete_movement_phase
  • Game.complete_combat_phase
  • Game.complete_economic_phase

Then, push your new changes to your space-empires repository, clone it here, and run your game to show the output below.

Problem 18-1

(ML; 90 min)

a) Write a class GradientDescent which organizes your gradient descent and grid search functionality. Your output should match the tests below exactly.

>>> def f(x,y):
        return 1 + (x-1)**2 + (y+5)**2
>>> minimizer = GradientDescent(f)
>>> minimizer.minimum
(0, 0) # this is the default guess

>>> minimizer.grid_search([-4,-2,0,-2,4],[-4,-2,0,-2,4])
# evaluates the function on all parameter combinations and updates the minimum accordingly

>>> minimizer.minimum
(0, -4)

>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018, 1.9999999999999574]

>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=4, logging=True)
(0.0020000000000000018, -4.002)
(0.0039959999999999996, -4.003996)
(0.005988007999999989, -4.005988008)
(0.007976031983999987, -4.007976031984)

>>> minimizer.minimum
(0.007976031983999987, -4.007976031984)

b) Make sure the test below works, using your GradientDescent class above. Your output should match the tests below exactly.

>>> data = [(0,1), (1,2), (2,4), (3,10)]
>>> def sum_squared_error(beta_0, beta_1, beta_2):
        squared_errors = []
        for (x,y) in data:
            estimation = beta_0 + beta_1*x + beta_2*(x**2)
            error = estimation - y
            squared_errors.append(error**2)
        return sum(squared_errors)

>>> minimizer = GradientDescent(sum_squared_error)
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=100, logging=True)
(0.03399999999999892, 0.0799999999999983, 0.21599999999999966)
(0.06071999999999847, 0.1417999999999985, 0.3829519999999995)
(0.08180998399999845, 0.18952841599999815, 0.5119836479999996)
(0.09854562099199829, 0.22637707788799802, 0.6116981274880002)
(0.11191318351974236, 0.2548137070760939, 0.6887468675046403)
...
(0.3047314235908722, 0.32259730399636893, 0.9402940523204946)

>>> mimimizer.minimum
(0.3047314235908722, 0.32259730399636893, 0.9402940523204946)
>>> sum_squared_error(minimizer.minimum)
1.246149882168838

c) Write a class PolynomialRegressor which organizes your polynomial regression functionality. Your output should match the tests below exactly.

>>> quadratic_regressor = PolynomialRegressor(degree=2)
>>> quadratic_regressor.coefficients
[0, 0, 0]   # default coefficients --> model is 0 + 0x + 0x^2

>>> quadratic_regressor.evaluate(5)
0   # because it's 0 + 0*5 + 0*5^2

>>> data = [(0,1), (1,2), (2,4), (3,10)]
>>> quadratic_regressor.ingest_data(data)
>>> quadratic_regressor.data
[(0,1), (1,2), (2,4), (3,10)]

>>> quadratic_regressor.sum_squared_error()
121   # the predictions are all 0, so the error is 1^2 + 2^2 + 4^2 + 10^2

>>> quadratic_regressor.solve_coefficients()
>>> quadratic_regressor.coefficients
[1.1499999999999986, -0.8499999999999943, 1.249999999999993] # the coefficients calculated USING THE PSEUDOINVERSE

>>> quadratic_regressor.sum_squared_error()
0.45

>>> quadratic_regressor.plot()

(should show a plot of the regression
function along with the data)

Problem 18-2

(DS/Algo; 30 min)

Write a function heap_sort(arr) that sorts the array by first heapifying the array, and then repeatedly popping off the root and then efficiently restoring the heap.

To efficiently restore the heap, you should NOT make another call to heapify, because at least half of the heap is perfectly intact. Rather, you should create a helper function that implements the procedure below. (read more here)

  1. Replace the root of the heap with last element of the heap.

  2. Compare the element with its new children. If the element is indeed greater than or equal to its children, stop.

  3. If not, swap the element with the appropriate child and repeat step 2.

Problem 18-3

(SWE; 60 min)

Extend your game.

Hull Size. Ships have the following hull sizes:

  • Scouts, Destroyers, and Ship Yards each have hull_size = 1
  • Cruisers and Battlecruisers each have hull_size = 2
  • Battleships and Dreadnaughts each have hull_size = 3

Change your "maintenance cost" logic so that maintenance cost is equal to hull size. Also, change your ship yard technology logic to refer to hull size, rather than armor.

Level | CP Cost | Hull Size Building Capacity of Each Ship Yard
------------------------------------------------------------
   1  |    -    |     1
   2  |   20    |     1.5
   3  |   30    |     2

Ship Size Technology. In order to build particular ships, a player must have particular ship size technology.

Technology  | Cost          | Benefit
----------------------------------------------------------------------------
Ship Size 1 | at start      | Can build Scout, Colony Ship, Ship Yard, Decoy
Ship Size 2 | 10 CPs        | Can build Destroyer, Base
Ship Size 3 | 15 more CPs   | Can build Cruiser
Ship Size 4 | 20 more CPs   | Can build Battlecruiser
Ship Size 5 | 25 more CPs   | Can build Battleship
Ship Size 6 | 30 more CPs   | Can build Dreadnaught

Bases. Bases are a type of unit that can only be built on colonies (and cannot move). Bases have

  • attack class A,
  • attack strength 7,
  • defense strength 2,
  • armor 3.

Bases do not incur maintenance costs. Players must have ship size technology of 2 or more to build a base, and bases are automatically upgraded to the highest technology for free.

Decoys. Decoys are units that are inexpensive and can be used to "trick" the opponent into thinking there is an enemy ship. Decoys cost 1 CP, have zero armor, and do not incur maintenance costs. However, they are removed immediately whenever they are involved in combat (i.e. they are immediately destroyed without even being considered in the attacking order).

Combat screening. During combat, the player with the greater number of ships has the option to "screen" some of those ships, i.e. leave them out of combat. Screened ships do not participate during combat (they cannot attack or be attacked) but they remain alive after combat.

During combat a player has N ships and another player has K ships, where N > K, then the player with N ships can screen up to N-K of their ships. In other words, the player with more ships in combat can screen as many ships as they want, provided that they still have at least as many ships as their opponent participating in combat.

Problem 17-1

(ML; 90 min)

a) The following dataset represents the distance between a rocket and Earth's surface, as the rocket takes off. The data points are given in the form (time, distance).

[(1, 3.1), (2, 10.17), (3, 20.93), (4, 38.71), (5, 60.91), (6, 98.87), (7, 113.92), (8, 146.95), (9, 190.09), (10, 232.65)]

Use gradient descent and grid search to find the best parameters $\beta_0,$ $\beta_1,$ and $\beta_2$ that fit a quadratic function $d=\beta_0 + \beta_1 t + \beta_2 t^2$ to the data.

  • For the grid search, search over all odd integer combinations $(\beta_0, \beta_1, \beta_2)$ in the space $[-5,5] \times [-5,5] \times [-5,5],$ cutting off the gradient descent after a set number of iterations (max_num_iterations=50) and returning the initial guess that had the lowest error.

  • If you find that the grid search is taking too long to run, you can lower max_num_iterations.

  • Once you finish the grid search, continue running gradient descent on the best initial guess, to a precision of precision=0.0001

b) Using the initial guess that yielded the best-fit parameters, plot the quadratic approximation at each iteration. You can use the following function to assist with plotting.

In [ ]:
import matplotlib.pyplot as plt
plt.style.use('bmh')

def plot_approximation(approximation_function, data, title=None, padding=5, num_subintervals=20):
    x_coords_data = [point[0] for point in data]
    y_coords_data = [point[1] for point in data]
    x_min_data, x_max_data = min(x_coords_data), max(x_coords_data)
    y_min_data, y_max_data = min(y_coords_data), max(y_coords_data)

    a, b = x_min_data-padding, x_max_data+padding
    approximation_x_coords = [a + (b-a)*(i/num_subintervals) for i in range(num_subintervals+1)]
    approximation_y_coords = [approximation_function(x) for x in approximation_x_coords]

    plt.scatter(x_coords_data, y_coords_data, color='black')
    plt.plot(approximation_x_coords, approximation_y_coords, color='blue')
    plt.xlim(x_min_data-padding, x_max_data+padding)
    plt.ylim(y_min_data-padding, y_max_data+padding)
    plt.title(title)
    plt.show()

data = [(1,4), (2,5), (3,7)]
beta_0_sequence = [4 * (1-1/n+1/20)**5 for n in range(1,21)]
beta_1_sequence = [-0.5 * (1-1/n+1/20)**5 for n in range(1,21)]
beta_2_sequence = [0.5 * (1-1/n+1/20)**5 for n in range(1,21)]

for beta_0, beta_1, beta_2 in zip(beta_0_sequence, beta_1_sequence, beta_2_sequence):
    title = 'y = {} + {}x + {}x^2'.format(round(beta_0,2), round(beta_1,2), round(beta_2,2))
    def f(x):
        return beta_0 + beta_1 * x + beta_2 * x**2
    plot_approximation(f, data, title=title)

c) Verify your best-fit quadratic coefficients using the linear approximation solver you implemented with your matrix class.

  • To jog your memory: $$\vec{\beta} \approx (\mathbf{X}^T \mathbf{X})^{-1} \mathbf{X}^T \vec{y},$$ where, for the cubic approximation, $$\mathbf{X} = \begin{pmatrix} 1 & t_1 & t_1^2 \\ 1 & t_2 & t_2^2 \\ \vdots & \vdots & \vdots \\ 1 & t_n & t_n^2 \end{pmatrix} \qquad \text{and} \qquad \vec{y} = \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix}$$

d) After 200 seconds, what will be the position of the rocket according to the quadratic approximation?

Problem 17-2

(DS/Algo; 30 min)

a) Write the following functions:

  • get_parent_index(i) - given the index of a node in a binary tree, returns the index of the parent of the node.

  • get_child_indices(i) - given the index of a node in a binary tree, returns the indices of the children of the node.

A binary tree is indexed as follows:

         0
      /     \     
     1       2
   /   \   /   \
  3    4  5     6
 /|   /| 
7 8  9 10

i | get_parent_index(i) | get_child_indices(i) |
------------------------------------------------
0 |         -           |         1, 2         |
1 |         0           |         3, 4         |
2 |         0           |         5, 6         |
3 |         1           |         7, 8         |
4 |         1           |         9, 10        |
5 |         2           |          -           |
6 |         2           |          -           |
7 |         3           |          -           |
8 |         3           |          -           |
9 |         4           |          -           |
10|         4           |          -           |

b) Write a function heapify(arr) that rearranges an input list so that the list satisfies the following condition:

  • When a binary tree is built from the list, every parent node has value greater than or equal to each of its children.

(A binary tree satisfying the above criterion is called a max-heap.)

HINT: loop through the list, starting at the end. For each value, if the value is greater then the value of its parent in the corresponding binary tree, then swap the two values.

>>> arr = [2, 3, 7, 1, 8, 5, 6]
>>> heapified_arr = heapify(arr)
>>> print(heapified_arr)
[8, 3, 7, 1, 2, 5, 6]

The above array can be interpreted as the following tree:
    8
   / \
  3   7
 /|   |\
1 2   5 6

Problem 17-3

(SWE; 60 min)

Implement a unit ShipYard which has

  • attack class C,
  • attack strength 3,
  • defense strength 0,
  • armor 1,
  • CP cost 6, and
  • zero maintenance cost.

Players can only build ships at ship yards that have landed on planets that they have colonized. Initially, a player starts with 4 ship yards on their home planet.

There are some constraints on the types of ships that players can build at a shipyard. A ship with a particular level of armor can only be built at a shipyard if the number of shipyards on the planet is greater than or equal to that armor level.

A player starts with Ship Yard Technology 1 and may purchase additional ship yard technology to increase the armor building capacity of each ship yard:

Level | CP Cost | Armor Building Capacity of Each Ship Yard
------------------------------------------------------------
   1  |    -    |     1
   2  |   20    |     1.5
   3  |   30    |     2

For example, if a player has a single ship yard on a planet (with ship yard technology 1), then then can only build a scout or destroyer there (both armor=1). To build a cruiser (armor=2), the player would have to either put another ship yard on the planet, or upgrade the ship yard technology to level 3.

Problem 16-1

(ML; 60 min)

a) In your function calc_linear_approximation_coefficients(data, initial_guess), include an optional argument plotting=False. If set to True, then show a plot of the data along with the linear approximation at each iteration of the gradient descent. A plotting function is provided for you, below.

Try it on each of the following datasets:

data1 = [(0, -2.7), (1, -0.01), (2, 3.28), (3, 7.07), (4, 10.99), (5, 13.51), (6, 14.75), (7, 17.93), (8, 21.65), (9, 25.48)]
data2 = [(0, 0.41), (1, 1.37), (2, 6.41), (3, 14.49), (4, 18.24), (5, 35.24), (6, 38.84), (7, 63.0), (8, 73.97), (9, 96.11)]
data3 = [(0, 0.12), (1, 4.32), (2, 5.41), (3, 0.74), (4, -3.29), (5, -4.16), (6, -1.38), (7, 3.77), (8, 5.65), (9, 2.7)]
In [ ]:
import matplotlib.pyplot as plt
plt.style.use('bmh')

def plot_linear_approximation(beta_0, beta_1, data, title=None, padding=5):
    x_coords_data = [point[0] for point in data]
    y_coords_data = [point[1] for point in data]
    x_min_data, x_max_data = min(x_coords_data), max(x_coords_data)
    y_min_data, y_max_data = min(y_coords_data), max(y_coords_data)

    line_endpoints_x_coords = [x_min_data-padding, x_max_data+padding]
    line_endpoints_y_coords = [beta_0 + beta_1 * x for x in line_endpoints_x_coords]

    plt.scatter(x_coords_data, y_coords_data, color='black')
    plt.plot(line_endpoints_x_coords, line_endpoints_y_coords, color='blue')
    plt.xlim(x_min_data-padding, x_max_data+padding)
    plt.ylim(y_min_data-padding, y_max_data+padding)
    plt.title(title)
    plt.show()

data = [(1,4), (2,5), (3,7)]
beta_0_sequence = [2.33 * (1-1/n+1/20)**5 for n in range(1,21)]
beta_1_sequence = [1.5 * (1-1/n+1/20)**5 for n in range(1,21)]

for beta_0, beta_1 in zip(beta_0_sequence, beta_1_sequence):
    title = 'y = {} + {}x'.format(round(beta_0,2), round(beta_1,2))
    plot_linear_approximation(beta_0, beta_1, data, title=title)