"""
$RCSfile: ga.py,v $ $Revision: 1.2 $
Author: Trevor R.H. Clarke <retrev@csh.rit.edu>
Description: play the game
"""

from game import *
from whrandom import *
from common import v,PSIZE

# An individual is a variable length string of moves (NSEW) thus
# the population is a list of strings
#
population = []
fitness = []
hero = -1


def ga_init(minl,maxl):
    """
	this function takes a minimum and maximum length for a
	generation 0 string and initializes the population
    """
    global population

    for i in range(PSIZE):
	population.append("")
	l = randint(minl,maxl)
	for j in range(l):
	    population[i] = population[i] + choice(['N','S','E','W'])


def ga_cross(pa,pb):
    """
	takes two parent strings and returns two child strings
	this function performs crossover on the two parent strings
    """
    if CTYPE == C_ONE:  # one point crossover
	ca,cb = randint(1,len(pa)-1),randint(1,len(pb)-1)
	oa = pa[:ca] + pb[cb:]
	ob = pb[:cb] + pa[ca:]
    elif CTYPE == C_TWO: # two point crossover
	caa,cba = randint(1,len(pa)-2),randint(1,len(pb)-2)
	cab,cbb = randint(caa+1,len(pa)-1),randint(cba+1,len(pb)-1)
	oa = pa[:caa] + pb[cba:cbb] + pa[cab:]
	ob = pb[:cba] + pa[caa:cab] + pb[cbb:]
    return oa,ob  # offspring a and b


def ga_mutate(s):
    """
	this function performs mutation on a string based on mutation chances
    """
    # first type of mutation replaces an allele
    #
    if random() <= MRATE_C:
	# pick an allele to mutate
	#
	tmp = randint(0,len(s) - 1)

	# an allele can mutate to the same value
	#
	if tmp == 0:
	    s = choice(['N','S','E','W']) + s[1:]
	else:
	    s = s[:tmp] + choice(['N','S','E','W']) + s[tmp + 1:]

    # second type of mutation exchanges two adjacent alleles
    #
    if random() < MRATE_F:
	l = randint(0,len(s) - 2)
	s = s[:l] + s[l+1] + s[l] + s[l+2:]

    # third type of mutation adds alleles to the end of the string
    #
    if random() <= MRATE_A:
	l = randint(MADD_MIN,MADD_MAX)
	for j in range(l):
	    s = s + choice(['N','S','E','W'])

    # the fourth type of mutation removes alleles from the end of the string
    #
    if random() <= MRATE_D:
	try:  # in case the string is not long enough to remove alleles from
	    l = randint(1,len(s)-2)
	    s = s[:-l]
	except:
	    pass
    return s


def ga_eval(grid):
    """
	this function plays a game with each member of the
	current population and updates its fitness value

	also, the hero of the population is found and hero is set it its index
    """
    global fitness,population,hero

    fitness = []
    tmp = 0	# local variables are quicker to access because
		# we don't need to make a scope change to global every
		# time through the loop....very small difference but
		# significant when we average 500 000 calls to ga_eval
		# in a run
    for i in range(len(population)):
	fitness.append(play_game(grid,population[i]))
	if fitness[i] > fitness[tmp]:
	    tmp = i
    hero = tmp


def ga_tourn():
    """
	hold a tournament for parenthood
	we choose three random individuals and the one with
	the highest fitness wins the tournament
    """
    global population

    ta=randint(0,len(population)-1)
    tb = ta
    while tb == ta: tb = randint(0,len(population)-1)
    tc = tb
    while tc == ta or tc == tb: tc = randint(0,len(population)-1)

    if fitness[tc] > fitness[tb] and fitness[tc] > fitness[ta]:
	return tc
    elif fitness[tb] > fitness[ta]:
	return tb
    else:
	return ta


def ga_breed():
    """
	breeding function
	we move the hero to the next generation(elitism) and move the
	winner of one random tournament to the next generation(random elitism)
	for the rest (PSIZE-2) slots we perform two tournaments and cross the
	two parents. the two offspring are inserted into the next generation
    """
    global population,hero

    remain = PSIZE
    npop = []
    npop.append(population[hero])     # elitism
    npop.append(population[ga_tourn()]) # random elitism
    remain = remain - 2
    while remain > 0:
	pa = ga_tourn()
	pb = pa
	while pb == pa: pb = ga_tourn()
	oa,ob = ga_cross(population[pa],population[pb])
	oa,ob = ga_mutate(oa),ga_mutate(ob)
	npop.append(oa)
	npop.append(ob)
	remain = remain - 2
    if len(npop) != len(population):
	npop = npop[:-1]
    population = npop  # replace the current population with the new generation


def ga_loop(grid):
    """
	this is the main loop of the ga
	first we initialize the population and evaluate their fitness
	then each generation we breed, evaulate fitness and check
	for stop conditions

	this function takes the problem grid and returns
	a tuple containing the hero's string and fitness (score)
    """
    global population,fitness,hero

    gens = 0
    ga_init(MIN_GEN0,MAX_GEN0)
    ga_eval(grid)
    while 1:
	ga_breed()
	ga_eval(grid)
	gens = gens + 1
	if gens >= MAXGENS:
	    break
    return population[hero],fitness[hero]