#!/usr/bin/python
# D. Vrajitoru, C463/B551 Spring 2008
 
# Game from A. Trautman.

# Implementing a program that will play the Nintendo DS game of
# loves-me / loves-me-not.

# The game starts with a number of petals to pluck from a flower. To
# make the game more interesting, each player can remove up to 4
# petals from the flower and at least 1. In the end the player wins if
# either the game ends with a "loves me" for him or a "loves me not"
# for the adversary. The first move is a "loves me".

# This is a small example of implementing the MinMax and Alpha-Beta
# algorithms.

from sys import *

plus_inf = 2
minus_inf = -2

# Defines the score for terminal nodes which are 0 or 1. 
def term_score(state, loves_me, turn):
    if turn == 0:
        score = 1-term_score(state, loves_me, 1)
    elif state == 0:
        # if we are left with one loves_me move, we win
        # Note that we return 2 things:
        score = int(loves_me) 
    elif state == 1:
        # if we are left with one loves_me move, we win
        score = int(loves_me)
    else:
        score = -1
    return score

# The state is a simple number, meaning the number of petals that are
# left on the flower. It must return the best move and the score. Even
# though the score is a 0/1 for lose/win, the function treats it as if
# it had a larger range.
# The MinMax for a Max node (us):
def minmax(state, loves_me, turn):
    # check the terminal conditions:
    if state < 2:
        # Note that we return 2 things:
        return state, term_score(state, loves_me, turn)
    # compute the score of all of its children using 1-what
    scores = []
    for move in range(1,min(5,state+1)):
        child = state-move
        if move % 2 == 0:
            m, score = minmax(child, loves_me, 1-turn)
        else:
            m, score = minmax(child, not loves_me, 1-turn)
        scores.append(score)
    #print "scores for", state, scores, "in turn", turn
    if turn == 1:
        # return the max score of the children
        score = max(scores)
    else:
        # return the min score of the children
        score = min(scores)
    move = scores.index(score) + 1 # moves start from 1
    return move, score

def MAX_AB (state, loves_me, A, B):
    #if N is a leaf:
    #print state, "+", A, B
    if state < 2:
        score = term_score(state, loves_me, 1)
        return state, score
    else: 
        alpha = minus_inf # -infinity
        best_move = 0
        #for each successor S of N:
        for move in range(1,min(5,state+1)):
            child = state - move
            if move % 2 == 0:
                m, val = MIN_AB(child, loves_me, max(A, alpha), B)
            else:
                m, val = MIN_AB(child, not loves_me, max(A, alpha), B)
            if val > alpha:
                alpha = val
                best_move = move
            if alpha >= B: #prune the subtree
                return move, alpha
        return best_move, alpha

def MIN_AB (state, loves_me, A, B):
    #if N is a leaf:
    #print state, "-", A, B
    if state < 2:
        score = term_score(state, loves_me, 0)
        alpha = score
        beta = score
        return state, score
    else: 
        beta = plus_inf # +infinity 
        #for each successor S of N:
        best_move = 0
        for move in range(1,min(5,state+1)):
            child = state - move
            if move % 2 == 0:
                m, val = MAX_AB(child, loves_me, A, min(B, beta))
            else: 
                m, val = MAX_AB(child, not loves_me, A, min(B, beta))
            if val < beta:
                best_move = move
                beta = val
            if A >= beta: #prune the subtree
                return move, beta
        return best_move, beta

if __name__ == '__main__':
    # We are using argv defined in the module sys
    start = 11
    case = 1
    if len(argv) > 1:
        start = int(argv[1])
    if len(argv) > 2:
        case = bool(int(argv[2]))
    move, score = minmax(start, case, 1)
    print "State:", start, "Move:", move, "Score:", score

    # Doing the same thing using alpha-beta:
##     alpha = []
##     beta = []
##     for i in range(start + 1):
##         alpha.append(minus_inf)
##         beta.append(plus_inf)
    move, score = MAX_AB(start, case, minus_inf, plus_inf)
    print "State:", start, "Move:", move, "Score:", score