#!/usr/local/bin/maple
# -*- maplev -*-

# Nathaniel Shar
# HW 26
# Experimental Mathematics

# It is okay to link to this assignment on the course webpage.

# Stuff from my c26.txt:

GetMax := proc(S, f) local champion, record, new, newval, i:
    if S = {} then:
        return FAIL:
    fi:
    champion := S[1]:
    record := f(champion):
    for i from 2 to nops(S) do:
        new := S[i]:
        newval := f(new):
        if newval > record then:
            champion := new:
            record := newval:
        fi:
    od:
    return [champion, record]:
end:

ElsterCentipede :=
[
          {2,3},
    [2,-1],
               {4,5},
          [1,2],
                    {6,7},
               [4,1],
                         {8,9},
                    [6,3],
                              [3,4]
]:

BestMove := proc(G, i, player) local best: option remember:
    if not type(i, integer) then:
        return false, [-infinity, -infinity]:
    fi:
    if type(G[i], list) then:
        return false, G[i]:
    else:
        best := GetMax(G[i], x->BestMove(G, x, 3-player)[2][player])[1]:
        return best, BestMove(G, best, 3-player)[2]
    fi:
end:

#############
# Problem 1 #
#############


with(combinat):

AllBetterDeals := proc(G, i, player := 1) local payoff, S:
    payoff := BestMove(G, i, player)[2]:
    S := select(x->evalb(BestMove(x, i, player)[2][1] > payoff[1] and BestMove(x, i, player)[2][2] > payoff[2]), AllSubgames(G)):
    return map(x->[x, BestMove(x, i, player)[2]], S):
end:

AllSubgames := proc(G, omit:= {}) local choices, i, k, m, S, T, t, L, Linv: option remember:
    S := {}:
    choices := select(x->type(G[x], set), {seq(i, i=1..nops(G))}) minus omit:
    if choices = {} then:
        return {G}:
    else:
        k := choices[1]:
        for m in powerset(G[k]) do:
            S := S union AllSubgames([seq(`if`(i=k, G[i] minus m, G[i]), i=1..nops(G))],
                                     omit union {k}):
        od:
        return S:
    fi:
end:

#############
# Problem 3 #
#############

OneBetterDeal := proc(G, i, K, player := 1) local payoff, j, S, nG:
    payoff := BestMove(G, i, player)[2]:
    for j from 1 to K do:
        nG := RandomSubgame(G):
        if BestMove(nG, i, player)[2][1] > payoff[1] and BestMove(nG, i, player)[2][2] > payoff[2] then:
            return nG, BestMove(nG, i, player)[2]:
        fi:
    od:
    return FAIL:
end:

RandomSubgame := proc(G):
    return [seq(`if`(type(i, list), i, randsubset(i)), i=G)]:
end:

randsubset := proc(S) local T,i:
    T := {}:
    for i from 1 to nops(S) do:
        if rand(1..2)() = 2 then:
            T := T union {S[i]}:
        fi:
    od:
    return T:
end: