Test code for zero move nim

zero-move-nim.py

#Generating zero move nim game outcomes
import copy

def GenGames(piles, passes, turn, stateOptions, stateWins):

	options = []

	nonZeroPiles = []
	for i, p in enumerate(piles):
		if p > 0:
			nonZeroPiles.append(i)

	if len(nonZeroPiles) == 1: #Winning move is possible
		stateWins[(tuple(piles), tuple(passes))] = 0
		stateOptions[(tuple(piles), tuple(passes))] = None
		return

	for i, p in enumerate(piles):
		if p == 0: continue
		if passes[i]: continue
		passes2 = copy.copy(passes)
		passes2[i] = True
		options.append(("P", i))
		state = (tuple(piles), tuple(passes2))
		if state not in stateOptions:
			GenGames(piles, passes2, 1-turn, stateOptions, stateWins)

	for i, p in enumerate(piles):
		if p == 0: continue
		for j in range(1, p+1):
			piles2 = copy.copy(piles)
			piles2[i] -= j
			options.append(("T", i, j))
			state = (tuple(piles2), tuple(passes))
			if state not in stateOptions:
				GenGames(piles2, passes, 1-turn, stateOptions, stateWins)

	stateOptions[(tuple(piles), tuple(passes))] = options

def AnalyseGames(piles):
	passes = [False] * len(piles)
	
	stateOptions, stateWins = {}, {}
	GenGames(piles, passes, 0, stateOptions, stateWins)

	#print stateOptions
	#print stateWins

	while len(stateWins) < len(stateOptions):
		
		for state in stateOptions:
			if state in stateWins: continue
			#print "chk", state

			options = stateOptions[state]
			allFound = True
			winningOpts = 0
			losingOpts = 0
			for opt in options:
				state2 = [list(state[0]), list(state[1])]
				if opt[0] == "P":
					state2[1][opt[1]] = True
				if opt[0] == "T":
					state2[0][opt[1]] -= opt[2]
				state3 = (tuple(state2[0]), tuple(state2[1]))

				if state3 in stateWins:
					ws = stateWins[state3]
					#print opt, ws
					if ws == 0:
						losingOpts += 1
					else:
						winningOpts += 1
				else:
					#print opt, "nf", state3
					allFound = False

			if allFound:
				#print "allfound"
				if winningOpts > 0:
					stateWins[state] = 0 #A winning position
				else:
					stateWins[state] = 1 #A losing position

	return stateWins[(tuple(piles), tuple(passes))]

def ShowPilesAndResult(piles):
	print piles, AnalyseGames(piles)

if __name__=="__main__":
		
	ShowPilesAndResult([2,2])
	ShowPilesAndResult([2,1])
	ShowPilesAndResult([8,4,2])