# OK to post homework
# Vikrant, Jan 30 2022, Assignment 2

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

Help2:=
    proc()
        print(`GameDB(), Rand2PlayerGame(a,b,K), IsStictDom(v1,v2), FindR(G), FindC(G), ShrinkGame(G), ReducedGame(G) , MyMaxIndex(L), LoadedCoin(p), BR1(G,a2), BR2(G,a1), BR1v(G), BR2v(G)`):
    end:

GameDB:=
    proc():
        [
            [ 
                [ [[-1,-1],[-9,0]], [[0,-9],[-6,-6]] ],
                [`Mum`, `Fink`], 
                [`Mum`, `Fink`]
            ],
            [
                [ [[2,1],[0,0]], [[0,0],[1,2]] ],
                [`Box`, `Opera`],
                [`Box`, `Opera`]
            ],
            [
                [ [[-1,1],[1,-1]], [[1,-1],[-1,1]] ],
                [`Odd`, `Even`],
                [`Odd`, `Even`]
            ],
            [
                [ [[1,0],[1,2],[0,1]], [[0,3],[0,1],[2,0]] ],
                [`Up`, `Down`],
                [`Left`, `Middle`, `Right`]
            ],
            [
                [ [[0,4],[4,0],[5,3]], [[4,0],[0,4],[5,3]], [[3,5],[3,5],[6,6]] ],
                [`T`, `M`, `B`],
                [`L`,`C`,`R`]
            ],
            [
                [ [[0,0],[-1,1],[1,-1]], [[1,-1],[0,0],[-1,1]], [[-1,1],[1,-1],[0,0]] ],
                [`Scissors`, `Rock`, `Paper`],
                [`Scissors`, `Rock`, `Paper`]
            ]
        ]:
    end:

PrintGame:=
    proc(G)
        local i:
        matrix(
            [
                [" ", op(G[3])],
                seq([G[2][i],op(G[1][i])],i=1..nops(G[2]))
            ]
        ):
    end:

Rand2PlayerGame:=
    proc(a,b,K)
        local ra,i,j:
        ra:=rand(0..K):
        [
            [seq([seq([ra(),ra()],j=1..b)],i=1..a)],
            [seq(i,i=1..a)],
            [seq(j,j=1..b)]
        ]:
    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:

FindR:=
    proc(G)
        local G1,RowS,i1,i2,j,v1,v2:
        G1:=G[1]:
        RowS:=G[2]:
        for i1 from 1 to nops(RowS) do
            for i2 from i1+1 to nops(RowS) do
                v1:=[seq(G1[i1][j][1],j=1..nops(G1[i1]))]:
                v2:=[seq(G1[i2][j][1],j=1..nops(G1[i2]))]:
                if IsStrictDom(v1,v2) then
                    RETURN(i1):
                elif IsStrictDom(v2,v1) then
                    RETURN(i2):
                fi:
            od:
        od:
        FAIL:
    end:

FindC:=
    proc(G)
        local G1,ColS,j1,j2,i,v1,v2:
        G1:=G[1]:
        ColS:=G[3]:
        for j1 from 1 to nops(ColS) do
            for j2 from j1+1 to nops(ColS) do
                v1:=[seq(G1[i][j1][2],i=1..nops(G1))]:
                v2:=[seq(G1[i][j2][2],i=1..nops(G1))]:
                if IsStrictDom(v1,v2) then
                    RETURN(j1):
                elif IsStrictDom(v2,v1) then
                    RETURN(j2):
                fi:
            od:
        od:
        FAIL:
    end:

ShrinkGame:=
    proc(G)
        local i,j,G1,RowS,ColS,i1:
        G1:=G[1]:
        RowS:=G[2];
        ColS:=G[3]:
        i:=FindR(G):
        if i<>FAIL then
            RETURN([
                [op(1..i-1,G1),op(i+1..nops(G1),G1)], 
                [op(1..i-1,RowS),op(i+1..nops(RowS),RowS)],ColS
            ]):
        fi:
        j:=FindC(G):
        if j<>FAIL then
            RETURN(
                [
                    [seq( [op(1.. j-1,G1[i1]),op(j+1..nops(G1[i1]),G1[i1])],i1=1..nops(G1))],
                    RowS,
                    [op(1..j-1,ColS),op(j+1..nops(ColS),ColS)]
                ]
            ):
        fi:
        FAIL:
    end:

ReducedGame:=
    proc(G)
        local G1,G2:
        G1:=G:
        G2:=ShrinkGame(G1):
        while G2<>FAIL do
            G1:=G2:
            G2:=ShrinkGame(G1):
        od:
        G1:
    end:

MyMaxIndex:=
    proc(L)
        local i,m,S:
        m:=max(L):
        S:={}:
        for i from 1 to nops(L) do
            if L[i]=m then
                S:=S union {i}:
            fi:
        od:
        S:
    end:

BR1:=
    proc(G,a2)
        local a1:
        MyMaxIndex([seq(G[a1][a2][1],a1=1..nops(G))]):
    end:

BR2:=
    proc(G,a1)
        local a2:
        MyMaxIndex([seq(G[a1][a2][2],a2=1..nops(G[a1]))]):
    end:

BR1v:=
    proc(G)
        local a2:
        [seq(BR1(G,a2),a2=1..nops(G[1]))]:
    end:

BR2v:=
    proc(G)
        local a1:
        [seq(BR2(G,a1),a1=1..nops(G))]:
    end:

LoadedCoin:=
    proc(p)
        local m,n,ra:
        m:=numer(p):
        n:=denom(p):
        ra:=rand(1..n)():
        if ra<=m then
            1:
        else
            2:
        fi:
    end:

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

(*

g:= (x,y) -> x*y/(1 + x^2 + y^2);
g(sin(t),cos(t));
simplify(%);
map(g,[seq(i,i=0..10)],Pi);
map((x->x^2)@g,[seq(i,i=0..10)],Pi);
f:= x -> exp(x^2);
diff(f(x),x);
diff(f(x),x$10);
diff(g(x,y),x);
diff(g(x,y),x,y);
diff(g(x,y),y,x);
D(g(x,y));
int(exp(-x^2),x);
Int(Int(x*y,x),y);
taylor(log(1+x),x=0,4);

*)

# ================================================================================
# 2. Five random games and corresponding best responses.
# ================================================================================

randomize(1203307093):

# [[[[3, 0], [1, 0], [1, 3]], [[1, 0], [1, 3], [1, 0]], [[1, 3], [1, 1], [0, 0]]], [1, 2, 3], [1, 2, 3]].
G1:= Rand2PlayerGame(3,3,3):
# [{1}, {1, 2, 3}, {1, 2}].
G1_BRv_ROW:= BR1v(G1[1]):
# [{3}, {2}, {1}].
G1_BRv_COL:= BR2v(G1[1]):


# Omitted due to length.
G2:= Rand2PlayerGame(4,4,4):
# [{1, 3}, {3}, {2}, {1}].
G2_BRv_ROW:= BR1v(G2[1]):
# [{2, 3}, {2}, {1}, {1, 4}].
G2_BRv_COL:= BR2v(G2[1]):


# Omitted due to length.
G3:= Rand2PlayerGame(5,5,5):
# [{2}, {2, 5}, {5}, {1}, {5}].
G3_BRv_ROW:= BR1v(G3[1]):
# [{2, 4}, {5}, {5}, {1}, {2}].
G3_BRv_COL:= BR2v(G3[1]):


# Omitted due to length.
G4:= Rand2PlayerGame(6,6,6):
# [{1}, {1}, {1}, {1}, {4}, {1, 3}].
G4_BRv_ROW:= BR1v(G4[1]):
# [{1, 3}, {2, 4}, {4, 5}, {1, 3, 5}, {6}, {5}].
G4_BRv_COL:= BR2v(G4[1]):


# Omitted due to length.
G5:= Rand2PlayerGame(7,7,7):
# [{5}, {6}, {2, 3}, {7}, {7}, {5}, {2, 3}].
G5_BRv_ROW:= BR1v(G5[1]):
# [{3}, {6}, {2}, {1, 3}, {1, 6}, {5, 6}, {6}].
G5_BRv_COL:= BR2v(G5[1]):

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

# Read.

# ================================================================================
# 4. Nash Tester.
# ================================================================================

IsNash:=
    proc(G,a1,a2)
        a1 in BR1(G,a2) and a2 in BR2(G,a1):
    end:

# ================================================================================
# 5. Pure Nash Searcher.
# ================================================================================

PureNashEqui:=
    proc(G)
        local i,j:
        {seq(seq(`if`(IsNash(G,i,j),[i,j],NULL),j=1..nops(G[i])),i=1..nops(G))}:
    end:

for i from 1 to 20 do
    G:= Rand2PlayerGame(10,12,2^i):
    print(cat("Payoffs in range 0..", 2^i, ". Pure Nash equilibria: ", PureNashEqui(G[1]), "."));
od: