Cs440Wa4

1

1.1

function OracleMinimaxSearch(state, player):
    if TERMINAL(state) then
        return UTILITY(state)
    
    if player == MAX then:
        bestValue ← -∞
        for each action a in ACTIONS(state) do:
            newState ← RESULT(state, a)
            value_a ← OracleMaxSearch(newState)
            if value_a > bestValue then:
                bestValue ← value_a
        return bestValue

    else if player == MIN then:
        // Use the oracle to get the opponent’s optimal move.
        opponent_action ← O(state)
        newState ← RESULT(state, opponent_action)
        return OracleMaxSearch(newState)

// helper
function BestMove(s0):
    bestValue ← -∞
    bestAction ← null
    for each action a in ACTIONS(s0) do:
        value_a ← OracleMaxSearch(RESULT(s0, a))
        if value_a > bestValue then:
            bestValue ← value_a
            bestAction ← a
    return bestAction

1.2

function OracleMaxSearchStochastic(state, player):
    if TERMINAL(state) then
        return UTILITY(state)

	if NODE_TYPE(state) == CHANCE then:
        expectedValue ← 0
        for each outcome o in CHANCE_OUTCOMES(state) do:
            //probability p(o) if each outcome
            newState ← RESULT(state, o)
            expectedValue ← expectedValue + p(o) *    
	            OracleMaxSearchStochastic(newState)
	    return expectedValue
            
    else if player == MAX then:
        bestValue ← -∞
        for each action a in ACTIONS(state) do:
            newState ← RESULT(state, a)
            value_a ← OracleMaxSearchStochastic(newState)
            if value_a > bestValue then:
                bestValue ← value_a
        return bestValue

    else if player == MIN then:
        // use the oracle to get the opponent’s optimal action.
        opponent_action ← O(state)
        newState ← RESULT(state, opponent_action)
        return OracleMaxSearchStochastic(newState)

2

2.1

2.2

If you have already observed the first six leaf nodes, do we need to evaluate the seventh and eighth leaves in order to determine the value of the parent CHANCE node?

Yes. take for example say If the seventh node and the eighth nodes are extremely large, then we would go to the right chance node instead.

What if we’ve observed the first seven leaves, do we need to observe the eighth in order to determine the value of the parent CHANCE node? Note: this is not a proof.

Sometimes yes and sometimes no. if we already know that leaf 7 turned out to be very small, and the MIN of {7,8} cannot be larger than that, there's no need to know. However, If leaf 7 is large enough that the right MIN child could still beat (or tie) the left CHANCE node, we do need to look at leaf 8, because the MIN of a large number and an unknown number is unknown.

2.3

if the second two leaves are both the lowest, -2, and -2, we get 0 in the chance node. If they're both largest, 2, and 2, we get 2 in the chance node. so the range is [0,2]

2.4

When we get to the right CHANCE node (the one on the right), we first evaluate its left MIN child (from leaves “0” and “2”) and find its value is 0.

Next we start evaluating its right MIN child. When we see its first leaf, –1, we know that the MIN operator will take the smaller of (–1, L8). But since L8 can be at best +2, the best (i.e. highest) that MIN could ever be is –1 (if L8 ≥ –1).

Thus, the value of the right CHANCE node will be at most -0.5.
which is strictly less than the left CHANCE node’s value (1.5). In other words, no matter what L8 turns out to be, this branch cannot beat the left branch at the root. Thus we can prune L8.

3