# OK to post homework
# Vikrant, Jan 23 2022, Assignment 1

# ================================================================================
# 0. Code that has been given.
# ================================================================================

Help1:=
    proc()
        print(` GameDB(), Rand2PlayerGame(a,b,K), IsDom(v1,v2)`):
    end:

GameDB:=
    proc()
        [
            [ [[-1,-1],[-9,0]], [[0,-9],[-6,-6]] ],
            [ [[2,1],[0,0]], [[0,0],[1,2]] ],
            [ [[-1,1],[1,-1]], [[1,-1],[-1,1]] ],
            [ [ [1,0],[1,2],[0,1]], [ [0,3],[0,1],[2,0]] ],
            [ [ [0,4],[4,0],[5,3]],[ [4,0],[0,4],[5,3]], [ [3,5],[3,5],[6,6]] ]
        ]:
    end:

Rand2PlayerGame:=
    proc(a,b,K)
        local ra,i,j:
        ra:=rand(0..K):

        [seq([seq([ra(),ra()],j=1..b)],i=1..a)]:
    end:

IsDom:=
    proc(v1,v2)
        local i:

        for i from 1 to nops(v1) do
            if v1[i] > v2[i] then
                RETURN(false):
            fi:
        od:
        true:
    end:

IsStrictDom:=
    proc(v1,v2)
        local i:

        for i from 1 to nops(v1) do
            if v1[i] >= v2[i] then
                RETURN(false):
            fi:
        od:
        true:
    end:

# ================================================================================
# 1. Samples from Garvan's Maple Primer.
# ================================================================================

(*

# Prints differently from book.
tan(Pi/5);
# Prints same as book.
evalf(%);

*)

(*

x:= 'x';

# Prints series.
p:= sum(x^k, k = 0 .. infinity);
# Prints series with substitution.
subs(x=1/2, p);
# Prints 2.
eval(%);
(1-x)*p;
# No simplification.
simplify((1-x)*p);
# Self substitution.
subs(x=p, p);
subs(x=subs(x=p, p),p);
# Warning that solution may have been lost. Prints RootOf(...).
solve(p=2, x);
# Prints 0.5000000000.
fsolve(p=2, x);

# Repeat the above, with the following assumption.
assume(x > -1 and x < 1);

# Prints closed form (but there's a negative sign in front).
p:= sum(x^k, k = 0 .. infinity);
# Prints 2. Skip eval(%) since subs() evals.
subs(x=1/2, p);
(1-x)*p;
# Simplification.
simplify((1-x)*p);
# Self substitution.
subs(x=p, p);
subs(x=subs(x=p, p),p);
# Warning given that solve may ignore assumptions. Prints 1/2.
solve(p=2, x);
# Prints 0.5000000000.
fsolve(p=2, x);

x:= 'x';
p:= 'p';

*)

(*

# ithprime(2^25) takes a long time on my machine.
ithprime(2^24);
ifactor(%+1);
# ifactor(2^(2^33)) takes slightly long on my machine.
ifactor(2^(2^32));

*)

# ================================================================================
# 2. Game 4,5 data.
# ================================================================================

# Game 4.
P2a:=
    proc()
        # ROW has strategies {1,2}, COL has strategies {1,2,3}.
        local U_ROW:= array(1..2,1..3,[]):
        local U_COL:= array(1..2,1..3,[]):
        local G:= GameDB()[4]:
        local i, j:

        # ROW's payoffs.
        U_ROW[1,1]:= 1:
        U_ROW[1,2]:= 1:
        U_ROW[1,3]:= 0:
        U_ROW[2,1]:= 0:
        U_ROW[2,2]:= 0:
        U_ROW[2,3]:= 2:

        # COL's payoffs.
        U_COL[1,1]:= 0:
        U_COL[1,2]:= 2:
        U_COL[1,3]:= 1:
        U_COL[2,1]:= 3:
        U_COL[2,2]:= 1:
        U_COL[2,3]:= 0:
        
        for i from 1 to 2 do
            for j from 1 to 3 do
                if G[i][j][1] <> U_ROW[i,j] or G[i][j][2] <> U_COL[i,j] then
                    print("Error in P2a."):
                    RETURN(FAIL):
                fi:
            od:
        od:

        print(matrix(G)):
    end:

# Game 5.
P2b:=
    proc()
        # ROW has strategies {1,2,3}, COL has strategies {1,2,3}.
        local U_ROW:= array(1..3,1..3,[]):
        local U_COL:= array(1..3,1..3,[]):
        local G:= GameDB()[5]:
        local i, j:

        # ROW's payoffs.
        U_ROW[1,1]:= 0:
        U_ROW[1,2]:= 4:
        U_ROW[1,3]:= 5:
        U_ROW[2,1]:= 4:
        U_ROW[2,2]:= 0:
        U_ROW[2,3]:= 5:
        U_ROW[3,1]:= 3:
        U_ROW[3,2]:= 3:
        U_ROW[3,3]:= 6:


        # COL's payoffs.
        U_COL[1,1]:= 4:
        U_COL[1,2]:= 0:
        U_COL[1,3]:= 3:
        U_COL[2,1]:= 0:
        U_COL[2,2]:= 4:
        U_COL[2,3]:= 3:
        U_COL[3,1]:= 5:
        U_COL[3,2]:= 5:
        U_COL[3,3]:= 6:
        
        for i from 1 to 3 do
            for j from 1 to 3 do
                if G[i][j][1] <> U_ROW[i,j] or G[i][j][2] <> U_COL[i,j]then
                    print("Error in P2b."):
                    RETURN(FAIL):
                fi:
            od:
        od:

        print(matrix(G)):
    end:

# ================================================================================
# 3. Reading.
# ================================================================================

# Read.

# ================================================================================
# 4. Minimize three 2-player games with 3 strats each and random payoffs in 0..3.
# ================================================================================

randomize(1352548505):

# [ [[2,1],[1,1],[0,3]], [[0,3],[2,1],[3,1]], [[1,0],[0,1],[1,3]] ].
G1:= Rand2PlayerGame(3,3,3):

# Order of elimination: .
ReducedG1:= [ [[2,1],[1,1],[0,3]], [[0,3],[2,1],[3,1]], [[1,0],[0,1],[1,3]] ]:

# [ [[1,3], [2,1], [0,2]], [[3,0], [0,3], [2,1]], [[3,0], [3,3], [3,0]] ].
G2:= Rand2PlayerGame(3,3,3):

# Order of elimination: R1, C1, C3, R2.
ReducedG2:= [ [[3,3]] ]:

# [ [[2,0], [1,1], [3,3]], [[0,1], [1,0], [2,2]], [[0,1], [3,1], [2,3]] ].
G3:= Rand2PlayerGame(3,3,3):

# Order of elimination: C1, C2, R2, R3.
ReducedG3:= [ [[3,3]] ]:

# Game 1 does not reduce. Games 2 and 3 reduce to a 1by1 bimatrix.

# ================================================================================
# 5. Find (weakly) dominated strategies.
# ================================================================================

with(ListTools, Transpose):

FindDominatedRowStrategy:=
    proc(G)
        FindDominatedStrategy(G,1)
    end:

FindDominatedColumnStrategy:=
    proc(G)
        FindDominatedStrategy(G,2)
    end:

FindDominatedStrategy:=
    proc(G,p)
        local H:= G:
        local i,j,k:
        if p = 2 then
            H:= Transpose(G)
        fi:
        for i from 1 to nops(H) do
            for j from 1 to nops(H) do
                if i <> j and IsDom([seq(H[i][k][p],k=1..nops(H[i]))],[seq(H[j][k][p],k=1..nops(H[j]))]) then
                    return(i):
                fi:
            od:
        od:
        return(FAIL):
    end:

# ================================================================================
# 6. Find (strictly) dominated strategies.
# ================================================================================

FindStrictDominatedRowStrategy:=
    proc(G)
        FindStrictDominatedStrategy(G,1)
    end:

FindStrictDominatedColumnStrategy:=
    proc(G)
        FindStrictDominatedStrategy(G,2)
    end:

FindStrictDominatedStrategy:=
    proc(G,p)
        local H:= G:
        local i,j,k:
        if p = 2 then
            H:= Transpose(G)
        fi:
        for i from 1 to nops(H) do
            for j from 1 to nops(H) do
                if IsStrictDom([seq(H[i][k][p],k=1..nops(H[i]))],[seq(H[j][k][p],k=1..nops(H[j]))]) then
                    return(i):
                fi:
            od:
        od:
        return(FAIL):
    end:

# ================================================================================
# 7. Reduce game (by eliminating strictly dominated strategies).
# ================================================================================

ShrinkGame:=
    proc(G)
        local x:
        x:= FindStrictDominatedRowStrategy(G):
        if x <> FAIL then
            return(RemoveRow(G,x)):
        fi: 
        x:= FindStrictDominatedColumnStrategy(G):
        if x <> FAIL then
            return(Transpose(RemoveRow(Transpose(G),x))):
        fi:
        return(FAIL):
    end:

RemoveRow:=
    proc(G,x)
        local i:
        return([seq(G[i],i=(seq(1..x-1),seq(x+1..nops(G))))]):
    end:

ReducedGame:=
    proc(G)
        local H:= ShrinkGame(G):
        if H = FAIL then
            return(G):
        fi:
        return(ReducedGame(H)):
    end: