#!/usr/bin/python -tt

import sys
import csv
import random
from decimal import *
from texttable import Texttable


'''Usage is

python bcogamesolver.py [csvfile]

Optionally

python bcogamesolver.py [csvfile] -update

to run the updatevals function, which tries to factor in the cost of spending a pair for next beat
'''


############################
### General game solvers ###
############################

#http://code.activestate.com/recipes/496825-game-theory-payoff-matrix-solver/

''' Approximate the strategy oddments for 2 person zero-sum games of perfect information.

Applies the iterative solution method described by J.D. Williams in his classic
book, The Compleat Strategyst, ISBN 0-486-25101-2.   See chapter 5, page 180 for details. '''

from operator import add, neg

def solve(payoff_matrix, iterations=100):
    'Return the oddments (mixed strategy ratios) for a given payoff matrix'
    transpose = zip(*payoff_matrix)
    numrows = len(payoff_matrix)
    numcols = len(transpose)
    row_cum_payoff = [0] * numrows
    col_cum_payoff = [0] * numcols
    colpos = range(numcols)
    rowpos = map(neg, xrange(numrows))
    colcnt = [0] * numcols
    rowcnt = [0] * numrows
    active = 0
    for i in xrange(iterations):
        rowcnt[active] += 1.0/iterations
        col_cum_payoff = map(add, payoff_matrix[active], col_cum_payoff)
        active = min(zip(col_cum_payoff, colpos))[1]
        colcnt[active] += 1.0/iterations
        row_cum_payoff = map(add, transpose[active], row_cum_payoff)
        active = -max(zip(row_cum_payoff, rowpos))[1]
    value_of_game = (max(row_cum_payoff) + min(col_cum_payoff)) / 2.0 / iterations
    return rowcnt, colcnt, value_of_game

def solve_dict(payoff_dict, iterations=100):
    '''
    This takes a dictionary of the form { ((s1,b1),(s2,b2)):val, ...} and returns the EV of the game and dicts astrat and bstrat of the form { (s1,b1):freq, ...} which gives the frequency of each pair at equilibrium.
    This function is reformats from a dictionary to a list of list, and then that list of lists is fed into the solve function, and then the output is reformatted into a dict
    '''
    apairs = []
    bpairs = []
    for pairofpairs in payoff_dict.keys():
        apairs.append(pairofpairs[0])
        bpairs.append(pairofpairs[1])
    apairs = list(set(apairs)) #set removes duplicates
    bpairs = list(set(bpairs))
    apairs.sort() #python sorts tuples lexicographically
    bpairs.sort()

    payoff_matrix = matrixofzeros(len(apairs),len(bpairs))
    for (i,ap) in enumerate(apairs):
        for (j,bp) in enumerate(bpairs):
            payoff_matrix[i][j] = payoff_dict[(ap,bp)]

    (astrat_list, bstrat_list, EV) = solve(payoff_matrix,iterations)

    astrat = {}
    bstrat = {}
    for (i,ap) in enumerate(apairs):
        astrat[ap] = astrat_list[i]
    for (j,bp) in enumerate(bpairs):
        bstrat[bp] = bstrat_list[j]

    return (astrat, bstrat, EV)





####################################
### List and matrix manipulation ###
####################################

def matrixofzeros(numrows,numcolumns):
    #[[0]*numcolumns]*numrows didn't work in the functions I wanted to use this in, and I don't want to think about it. Sorry for ugly.
    mat = []
    for i in range(numrows):
        row = []
        for j in range(numcolumns):
            row.append(0)
        mat.append(row)
    return mat

def deleterow(i,matrix):
    newmat = [row for (index,row) in enumerate(matrix) if index != i]
    return newmat

def deletecolumn(j,matrix):
    newmat = []
    for row in matrix:
        newmat.append( [val for (index,val) in enumerate(row) if index != j] )
    return newmat

def deleteemptystrings(mylist): #removes empty strings from the end of a list, in place
    while len(mylist) > 0 and mylist[-1] == '':
        mylist.pop()

def printmatrix(mat):
    for row in mat:
        print [ float(Decimal('%.2f' % elem)) for elem in row ]

def printdictmatrix(mat,astrat,bstrat,EV):
    apairs = [ap for (ap,bp) in mat.keys()]
    bpairs = [bp for (ap,bp) in mat.keys()]
    apairs = list(set(apairs))
    bpairs = list(set(bpairs))
    apairs.sort(key=lambda pair: -astrat[pair])
    bpairs.sort(key=lambda pair: -bstrat[pair])

    ttrowlist = []
    toprow = ['EV = '+str(EV)]
    for bp in bpairs:
        toprow.append('('+str(bstrat[bp])+') '+bp[0]+' '+bp[1])
    ttrowlist.append(toprow)
    for ap in apairs:
        row = ['('+str(astrat[ap])+') '+ap[0]+' '+ap[1]]
        for bp in bpairs:
            row.append(str(mat[(ap,bp)]))
        ttrowlist.append(row)
    t = Texttable()
    t.add_rows([row for row in ttrowlist])
    t.set_max_width(0)
    print t.draw()

def printstrat(strat):
    toprintlist = []
    for pair in strat.keys():
        toprintlist.append((pair,strat[pair]))
    toprintlist.sort(key=lambda tup: -tup[1])
    for (pair,freq) in toprintlist:
        print pair[0],pair[1]+':', freq


############################
### BCO specific solving ###
############################

def clashval(clashmatrix,abases,bbases,iterations,pentaclashvalue=0):
    '''
    clashmatrix is a dict of the form { (b1,b2):val }, where val can be a number representing the payout, or 'clash'. b1 and b2 range over all 7 posible bases.
    abases and bbases are lists with the bases each player has available.
    This function returns the EV of the clash
    '''
    abases.sort()
    bbases.sort()
    #valmatrix = matrixofzeros(len(abases),len(bbases))
    valmatrix = {}
    '''
    valmatrix is going to store the payouts of each pair of bases available to the players right now.
    It is different from clashmatrix in 2 ways:
      1. It only contains pairs of bases that are available right now
      2. It has numeric values for clashes, instead of 'clash'. It finds these numeric values recursively: when it encounters a clash, it deletes that base from both players, and then runs this function on the smaller matrix.
    These are called step 1 and step 2 below
    '''
    #step 1
    for ab in abases:
        for bb in bbases:
            valmatrix[(ab,bb)] = clashmatrix[(ab,bb)]

    #step 2
    for ab in abases:
        for bb in bbases:
            if valmatrix[(ab,bb)] == 'clash':
                abases_remaining = [abase for abase in abases if abase != ab]
                bbases_remaining = [bbase for bbase in bbases if bbase != bb]
                valmatrix[(ab,bb)] = clashval(valmatrix,abases_remaining,bbases_remaining,iterations)[3]

    if len(valmatrix) == 0: #pentaclash
        return (valmatrix,None,None,pentaclashvalue)
    else:
        (astrat,bstrat,EV) = solve_dict(valmatrix,iterations)
        return (valmatrix,astrat,bstrat,EV)

def gameval(gamematrix,clashmatrixdict,discards,iterations):
    '''
    gamematrix is a dict of the form { ((s1,b1),(s2,b2)):val, ...}, where val is either a payout or 'clash'.
    clashmatrixdict is a dict of clashmatrices, like the ones that get passed to the clashval function, indexed by pairs of styles (astyle,bstyle)
    discards is a pair of list of pairs, ( [(as1,ab1),(as2,ab2),...] ,  [(bs1,bb1),(bs2,bb2),...]) indicating which styles and bases are unavailable for both players right now. The first element of each list is the one that's going to become available to the player next beat

    All bases should be one of 'grasp', 'drive', 'strike', 'dodge', 'shot', 'burst', 'ub_a', or 'ub_b'.

    This function returns (valmatrix,astrat,bstrat,EV)
    '''

    abases = ('grasp','drive','strike','dodge','shot','burst','ub_a')
    bbases = ('grasp','drive','strike','dodge','shot','burst','ub_b')
    astylediscards = [astyle for (astyle,abase) in discards[0]]
    abasediscards = [abase for (astyle,abase) in discards[0]]
    bstylediscards = [bstyle for (bstyle,bbase) in discards[1]]
    bbasediscards = [bbase for (bstyle,bbase) in discards[1]]

    restrictedgamematrix = {}
    for ((astyle,abase),(bstyle,bbase)) in gamematrix.keys():
        if (astyle not in astylediscards) and (abase not in abasediscards) and (bstyle not in bstylediscards) and (bbase not in bbasediscards):
            restrictedgamematrix[((astyle,abase),(bstyle,bbase))] = gamematrix[((astyle,abase),(bstyle,bbase))]

    valmatrix = dict(restrictedgamematrix) #copy
    for ((astyle,abase),(bstyle,bbase)) in restrictedgamematrix.keys():
        if restrictedgamematrix[((astyle,abase),(bstyle,bbase))] == 'clash':
            clashmatrix = clashmatrixdict[(astyle,bstyle)]
            abases = [ab for ab in abases if (ab != abase) and (ab not in abasediscards)]
            bbases = [bb for bb in bbases if (bb != bbase) and (bb not in bbasediscards)]
            if bstyle == 'Special': #THIS IS MIKHAIL SPECIFIC CHANGE IT IF IT'S NOT VS MIKHAIL
                pentaclashvalue = 0
            else:
                pentaclashvalue = 1
            valmatrix[((astyle,abase),(bstyle,bbase))] = clashval(clashmatrix,abases,bbases,iterations,pentaclashvalue)[3]

    (astrat,bstrat,EV) = solve_dict(valmatrix,iterations)
    return (valmatrix,astrat,bstrat,EV)


def updatevals(gamematrix,clashmatrixdict,discards,iterations,cyclecards=False): #cyclecards means remove the 0th element of the discard list
    #This probably takes a long time...
    updatedmatrix = dict(gamematrix) #copy
    (valmatrix,astrat,bstrat,EV) = gameval(gamematrix,clashmatrixdict,discards,iterations)
    asupport = [ap for ap in astrat.keys() if astrat[ap] > 0.001] #the ''support'' of a function is the set of inputs on which it takes nonzero values
    bsupport = [bp for bp in bstrat.keys() if bstrat[bp] > 0.001]
    for (apair,bpair) in gamematrix.keys():
        if apair in asupport and bpair in bsupport:
            if len(discards[0]) == 0:
                newdiscards_a = [apair]
            else:
                if cyclecards:
                    newdiscards_a = discards[0][1:].append(apair)
                else:
                    newdiscards_a = discards[0][:]
                newdiscards_a.append(apair)
            if len(discards[1]) == 0:
                newdiscards_b = [bpair]
            else:
                if cyclecards:
                    newdiscards_b = discards[1][1:]
                else:
                    newdiscards_b = discards[1][:]
                newdiscards_b.append(bpair)
            newdiscards = (newdiscards_a, newdiscards_b)
            modifier = gameval(gamematrix,clashmatrixdict,newdiscards,iterations)[3] #EV of the full game with the new discards.
            updatedmatrix[(apair,bpair)] = valmatrix[(apair,bpair)] + modifier - EV

    return updatedmatrix






###########################
### Reading and writing ###
###########################

def readmatrices(csvfile):
    '''
    This function reads matrices from a csv file and turns them into dicts to use in other functions. The matrices in the csv file should look like

    *full,fusion/flash,chrono/drive,eternal/shot,fusion/shot,fusion/drive,eternal/flash,fusion/dodge
    magical/starlight,-3.8,2.2,-2.2,2.2,2.2,0,-0.8
    aurora/burst,3.2,-3,-1.2,-1.8,-3.8,1.8,-0.8
    galactic/shot,0.2,0.2,-1.2,-1.8,-1.8,0.8,-0.8
    comet/burst,3.2,-3,1.8,-5.8,3.2,-0.8,-0.8

    All matrices are expected to start with an asterix, and this function uses that know where to start building them.
    All matrices should have at least one blank row between them
    The first matrix in the file should be the full game matrix, and the ones after that should be clash matrices
    All pairs should be of the form 'style/base', even in clash matrices.
    Anything that affects clash chains should be given as a different style. For example, if Luc sometimes antes 1 time on a Fusion shot, then you should treat 'fusion' and 'fusion [1 time]' as different styles everywhere.
    '''
    with open(csvfile,'r') as f:
        myreader = csv.reader(f)
        rowlistraw = list(myreader)

    rowlist = []
    for row in rowlistraw:
        rowcopy = row[:]
        deleteemptystrings(rowcopy)
        rowlist.append(rowcopy)

    matrixlist = []
    for (i,row) in enumerate(rowlist):
        #deleteemptystrings(row)
        if len(row) > 0 and row[0][0] == '*':
            newmatrix = {}
            apairs = []
            bpairs = []

            #get bpairs
            splitrow = row#.split(',')
            for bpairstr in splitrow[1:]:
                bpairs.append(tuple(bpairstr.split('/')))

            #get apairs
            count = 1
            while len(rowlist[i+count]) > 1: #len(rowlist[i+count].split(',')) > 1:
                apairstr = rowlist[i+count][0] #.split(',')[0]
                apairs.append(tuple(apairstr.split('/')))
                count = count + 1

            for rowcount in range(len(apairs)):
                for colcount in range(len(bpairs)):
                    val = rowlist[i+1+rowcount][colcount+1] #rowlist[i+1+rowcount].split(',')[colcount+1]
                    if val == 'clash':
                        newmatrix[(apairs[rowcount],bpairs[colcount])] = 'clash'
                    else:
                        newmatrix[(apairs[rowcount],bpairs[colcount])] = float(rowlist[i+1+rowcount][colcount+1]) #float(rowlist[i+1+rowcount].split(',')[colcount+1])

            matrixlist.append(newmatrix)


    fullmatrix = matrixlist.pop(0)
    clashmatrixdict = {}
    for mat in matrixlist:
        clashmatrix = {}
        for ((astyle,abase),(bstyle,bbase)) in mat.keys():
            clashmatrix[(abase,bbase)] = mat[((astyle,abase),(bstyle,bbase))]
        astyle = mat.keys()[0][0][0]
        bstyle = mat.keys()[0][1][0]
        clashmatrixdict[(astyle,bstyle)] = clashmatrix

    return (fullmatrix,clashmatrixdict)


def main():
    csvfile = sys.argv[1]
    (gamematrix,clashmatrixdict) = readmatrices(csvfile)
    iterations = 10000
    #discards = ([],[])
    discards = ([('random','strike'),('random','grasp')],[('random','shot'),('random','grasp')])
    if len(sys.argv) == 2:
        (valmatrix,astrat,bstrat,EV) = gameval(gamematrix,clashmatrixdict,discards,iterations)
        printdictmatrix(valmatrix,astrat,bstrat,EV)
    if len(sys.argv) == 3 and sys.argv[2] == '-update':
        (valmatrix_u,astrat_u,bstrat_u,EV_u) = gameval(updatevals(gamematrix,clashmatrixdict,discards,iterations),clashmatrixdict,discards,iterations)
        printdictmatrix(valmatrix_u,astrat_u,bstrat_u,EV_u)


#This is the standard boilerplate that calls the main() function.
if __name__ == '__main__':
    main()