Castle assignment algorithm explanation.

Run 1, no rr(round-robin): [ 1  3  8  5 12 22  2 33  6  8]
Run 1, rr: [ 4  0  6 13 13 25  1  3 26  9]
Run 2, no rr: [ 5  1  8 13 12 23  3  2 25  8]
Run 2, rr: [ 0  1  8 14 16  1 22  3 25 10]

These assignments have been generated by a genetic algorithm, described below.

Genotype of individuals
-----------------------

Each genotype is a sorted list of nine integers between 0 and 100 inclusive.

[k(1) k(2) k(3) k(4) k(5) k(6) k(7) k(8) k(9)]

Let k(0) = 0 and k(10) = 100. Each genotype expresses thus expresses their phenotype as follows:

-Castle n(n=1 to 10) attack strength = k(n) - k(n-1)

This implementation has a few advantages:

-You do not have to check the total # of soldiers assigned, and only have to sort genotypes to ensure non-negative attack strengths.
-There is a 1-1 correspondence between genotypes and valid assignments with 100 soldiers.
-Small changes in genotype correspond to small changes in phenotype.


Crossover & mutation
--------------------
Crossover is single point, with sorting afterwards to ensure valid assignments.

Mutation on single list entry k(n) are done by using binomial trials:

new k(n) = ( # of successes in 302 trials with p = ((3*k(n) + 1) / 302) )//3

Repeated iterations to force mutation can be done. This ensures most mutations will be small and that only a sort is needed to ensure a valid genotype.


Selection
---------
Given a ranking of each individual within a population, here is how I prepared the next generation, assuming a pop. size of 200:

-Bottom 20 are replaced by copies of top 20. Entries ranked 11-20 undergo a single forced mutation in this copy.
-Next-to-bottom 20 undergo hypermutation: forced mutations on each entry.
-A few non-forced mutations occur in the middle 120 of the population.
-All of the top 180, (Including the originals, but not the copies of the top 20), undergo randomly paired crossover.

This procedure is rather ad-hoc, but it was effective nevertheless.

Evaluation and general approach
-------------------------------
To take account of the fact that the data from the previous contest was available and likely to be exploited, I adopted a two-stage approach.

In the first stage, I generated an 'optimized' population. For each run, 200 random submitted assignments were used, which remained the same generation over generation. At the the end of each run, the best at the end is chosen. This is repeated several times to obtain an 'optimized' population.

The second stage is largely the same, but in addition to the 200 submitted assignments, 100 'optimized' assignments are used in evaluation. At the end of these runs, the best of each is evaluated under the full submitted and optimized populations, and the best under that criteria is chosed. Alternatively, we can perform a round robin with the best-of-runs, add the scores to the previous, and use that criteria.

'Optimized' pop. code (Python 2.7, Numpy 1.7)
---------------------------------------------
import numpy as np
import csv

#Returns the phenotype of the given genome.
def expPheno(c1):
	temp = np.zeros(11, dtype=np.int)
	temp[-1] = 100
	temp[1:-1] = c1
	pheno = temp[1:] - temp[:-1]
	return pheno

#Emulates the battles, written so no floats are necessary.
def canEval(c1, c2):
	p1 = expPheno(c1)
	p2 = expPheno(c2)
	bwins = np.sign(p1 - p2)
	#print bwins
	cval = (bwins + 1 )*np.array(range(1,11))
	#print cval
	tval = np.sum(cval)
	#print tval
	return np.sign(tval - 55) + 1

def trueEval(c1, c2):
	bwins = np.sign(c1 - c2)
	#print bwins
	cval = (bwins + 1 )*np.array(range(1,11))
	#print cval
	tval = np.sum(cval)
	#print tval
	return np.sign(tval - 55) + 1

#Implements single point crossover on two genotypes
def crossover(c1,c2):
	cut = np.random.randint(1, high = 9)
	out = np.array([c1, c2])
	out[:,cut:] = out[::-1,cut:]
	out = np.sort(out)
	return out

#Implements a point mutation on the genotype using the binomial distribution
def mutate(c1, pos = None, force = False):
	vals = 101
	w = 1
	n = ((2*w +1)*vals) - 1
	if (pos == None):
		pos = np.random.randint(9)
	pn = (2*w + 1)*c1[pos] + w
	p = pn / float(n)

	while True:
		r = np.random.binomial(n, p)
		new = r//(2*w + 1)
		if (not force):
			break
		if (new != c1[pos]):
			break

	c1[pos] = new
	out = np.sort(c1)
	return out

#The submitted strategies in the first round
subPop = np.genfromtxt('castle-solutions_fix.csv', dtype=np.int, delimiter=',',skip_header=1,usecols = (0,1,2,3,4,5,6,7,8,9))
sp = 1387

rSize = 700
gNum = 50

refPop = np.zeros((rSize, 9), dtype=np.int)

for iter in range(rSize):
	pSize = 200
	evoPop = np.random.randint(101, size = (pSize, 9))
	evoPop = np.sort(evoPop)

	sSize = 200
	sPop = np.random.permutation(subPop)
	sPop = sPop[:sSize,:]
	best = np.zeros(9, dtype=np.int)
	bSc = 0

	for gen in range(gNum):
		scores = np.zeros(pSize, dtype=np.int)

		#Evaluating genotypes
		for i in range(pSize):
			pheno = expPheno(evoPop[i,:])
			for j in range(sSize):
				out = trueEval(pheno, sPop[j,:])
				scores[i] += out

		#argsort outputs the original indices of the items a hypothetical sorted list
		#The last entry is the index of the best scoring strategy
		rank = np.argsort(scores)
		best = evoPop[rank[pSize-1],:]
		bSc = scores[ rank[ pSize - 1 ] ]

		#Replace last 20 with first 20 and mutates ranks 11-20
		for i in range(20):
			evoPop[rank[i],:] = evoPop[rank[i + pSize - 20],:]

		for i in range(10):
			evoPop[rank[i],:] = mutate(evoPop[rank[i],:], force = True)

		#Hypermutates next to last 20
		for i in range(20):
			for j in range(9):
				evoPop[rank[i+20],:] = mutate(evoPop[rank[i + pSize - 20],:], pos = j , force = True)

		#Random mutations for middle 120
		rk = np.random.permutation(rank[40:-40])
		for i in range(12):
			evoPop[rk[i],:] = mutate(evoPop[rk[i],:])

		#Crossover with all but last 20
		cross = np.random.permutation(rank[20:])
		for i in range(90):
			out = crossover(evoPop[cross[2*i],:], evoPop[cross[2*i+1],:])
			evoPop[cross[2*i],:] = out[0,:]
			evoPop[cross[2*i + 1],:] = out[1,:]

		#if (gen%5 == 4):
		#	print ""
		#	print gen
		#	print best
		#	print scores[ rank[ pSize - 1 ] ]

	refPop[iter] = best
	print ""
	print iter
	print refPop[iter]
	print bSc

with open('optGen.csv', 'wb') as wtag:
	write = csv.writer(wtag, delimiter=',')
	write.writerows(refPop)


Blended evaluation code (Python 2.7, Numpy 1.7)
-----------------------------------------------
import numpy as np
import csv

#Returns the phenotype of the given genome.
def expPheno(c1):
	temp = np.zeros(11, dtype=np.int)
	temp[-1] = 100
	temp[1:-1] = c1
	pheno = temp[1:] - temp[:-1]
	return pheno

#Emulates the battles, written so no floats are necessary.
def canEval(c1, c2):
	p1 = expPheno(c1)
	p2 = expPheno(c2)
	bwins = np.sign(p1 - p2)
	#print bwins
	cval = (bwins + 1 )*np.array(range(1,11))
	#print cval
	tval = np.sum(cval)
	#print tval
	return np.sign(tval - 55) + 1

def trueEval(c1, c2):
	bwins = np.sign(c1 - c2)
	#print bwins
	cval = (bwins + 1 )*np.array(range(1,11))
	#print cval
	tval = np.sum(cval)
	#print tval
	return np.sign(tval - 55) + 1

#Implements single point crossover on two genotypes
def crossover(c1,c2):
	cut = np.random.randint(1, high = 9)
	out = np.array([c1, c2])
	out[:,cut:] = out[::-1,cut:]
	out = np.sort(out)
	return out

#Implements a point mutation on the genotype using the binomial distribution
def mutate(c1, pos = None, force = False):
	vals = 101
	w = 1
	n = ((2*w +1)*vals) - 1
	if (pos == None):
		pos = np.random.randint(9)
	pn = (2*w + 1)*c1[pos] + w
	p = pn / float(n)

	while True:
		r = np.random.binomial(n, p)
		new = r//(2*w + 1)
		if (not force):
			break
		if (new != c1[pos]):
			break

	c1[pos] = new
	out = np.sort(c1)
	return out

#The submitted strategies in the first round
subPop = np.genfromtxt('castle-solutions_fix.csv', dtype=np.int, delimiter=',',skip_header=1,usecols = (0,1,2,3,4,5,6,7,8,9))
sp = 1387

optPop = np.genfromtxt('optGen.csv', dtype=np.int, delimiter=',')
op = 700

rSize = 400
gNum = 50

pSize = 200
sSize = 200
oSize = 100

refPop = np.zeros((rSize, 9), dtype=np.int)

for iter in range(rSize):
	evoPop = np.random.randint(101, size = (pSize, 9))
	evoPop = np.sort(evoPop)

	sPop = np.random.permutation(subPop)
	sPop = sPop[:sSize,:]

	oPop = np.random.permutation(optPop)
	oPop = oPop[:oSize,:]

	best = np.zeros(9, dtype=np.int)
	bSc = 0

	for gen in range(gNum):

		scores = np.zeros(pSize, dtype=np.int)

		#Evaluating genotypes against submitted phenotypes
		for i in range(pSize):
			pheno = expPheno(evoPop[i,:])
			for j in range(sSize):
				out = trueEval(pheno, sPop[j,:])
				scores[i] += out


		#Evaluating genotypes against optimized phenotypes
		for i in range(pSize):
			for j in range(oSize):
				out = canEval(evoPop[i,:], oPop[j,:])
				scores[i] += out


		#argsort outputs the original indices of the items a hypothetical sorted list
		#The last entry is the index of the best scoring strategy
		rank = np.argsort(scores)
		best = evoPop[rank[pSize-1],:]
		bSc = scores[ rank[ pSize - 1 ] ]

		#Replace last 20 with first 20 and mutates ranks 11-20
		for i in range(20):
			evoPop[rank[i],:] = evoPop[rank[i + pSize - 20],:]

		for i in range(10):
			evoPop[rank[i],:] = mutate(evoPop[rank[i],:], force = True)

		#Hypermutates next to last 20
		for i in range(20):
			for j in range(9):
				evoPop[rank[i+20],:] = mutate(evoPop[rank[i + pSize - 20],:], pos = j , force = True)

		#Random mutations for middle 120
		rk = np.random.permutation(rank[40:-40])
		for i in range(12):
			evoPop[rk[i],:] = mutate(evoPop[rk[i],:])

		#Crossover with all but last 20
		cross = np.random.permutation(rank[20:])
		for i in range(90):
			out = crossover(evoPop[cross[2*i],:], evoPop[cross[2*i+1],:])
			evoPop[cross[2*i],:] = out[0,:]
			evoPop[cross[2*i + 1],:] = out[1,:]

		#if (gen%5 == 4):
		#	print ""
		#	print gen
		#	print best
		#	print scores[ rank[ pSize - 1 ] ]

	refPop[iter] = best

	print ""
	print iter
	print refPop[iter]
	print bSc


#Comparing best of the runs above
hScores = np.zeros(rSize, dtype=np.int)

for iter in range(rSize):

	#Evaluating genotypes against submitted phenotypes
	pheno = expPheno(refPop[iter,:])
	for j in range(sp):
		out = trueEval(pheno, subPop[j,:])
		hScores[iter] += out


	#Evaluating genotypes against optimized phenotypes
	geno = refPop[iter,:]
	for j in range(op):
		out = canEval(geno, optPop[j,:])
		hScores[iter] += out

hRank = np.argsort(hScores)
hBest = refPop[hRank[rSize-1],:]

hPheno = expPheno(hBest)

print ""
print hBest
print hPheno
print hScores[hRank[rSize-1]]
print hScores[hRank[rSize-1]] / float((op + sp)*2)
print ""

#Adding head to head comparisons
tScores = np.copy(hScores)

for i in range(rSize - 1):
	for j in range(i + 1, rSize):
		out = canEval(refPop[i,:], refPop[j,:])
		tScores[i] += out
		tScores[j] += 2 - out

tRank = np.argsort(tScores)
tBest = refPop[tRank[rSize-1],:]

tPheno = expPheno(tBest)

print tBest
print tPheno
print tScores[tRank[rSize-1]]
print tScores[tRank[rSize-1]] / float((op + sp + rSize - 1)*2)

#Saving best for examination
refStat = np.zeros((rSize, 11), dtype=np.int)

refStat[:,:9] = refPop
refStat[:,9] = hScores
refStat[:,10] = tScores

with open('blendEvo.csv', 'wb') as wtag:
	write = csv.writer(wtag, delimiter=',')
	write.writerows(refStat)