IA MORPION N X N

def score(Jeu,x,y,k,n,car):

	horz=0
	vert=0
	diagHD=0
	diagHG=0
	
	for i in range(max(0,y-k+1),min(n-1,y+k-1)-k+2):
		res=1
		for j in range(i,i+k):
			if Jeu[x][j] == car:
				res=res*0
			if Jeu[x][j] != car and Jeu[x][j] != ' ':
				res=res*n
		if res>horz:
			horz=res
	
	for i in range(max(0,x-k+1),min(n-1,x+k-1)-k+2):
		res=1
		for j in range(i,i+k):
			if Jeu[j][y] == car:
				res = res*0
			if Jeu[j][y] != ' ' and Jeu[j][y] != car:
				res=res*n
		if res>vert:
			vert=res
	
	
	if (min(min(n-1,y+k-1),y+min(n-1,x+k-1)-x)-max(max(0,y-k+1),y-(x-max(0,x-k+1)))>=(k-1)):
	
		for i in range(max(max(0,y-k+1),y-(x-max(0,x-k+1))),min(min(n-1,y+k-1),y+min(n-1,x+k-1)-x)-k+2):
			res=1
			for j in range(i,i+k):
				if Jeu[x-(y-j)][j] == car:
					res = res*0
				if Jeu[x-(y-j)][j] != car and Jeu[x-(y-j)][j] != ' ':
					res = res*n
			if res>diagHG:
				diagHG=res
		
	if (min(min(n-1,y+k-1),y+(x-max(0,x-k+1)))-max(max(0,y-k+1),y-(min(n-1,x+k-1)-x))>=(k-1)):
	
		for i in range(max(max(0,y-k+1),y-(min(n-1,x+k-1)-x)),min(min(n-1,y+k-1),y+(x-max(0,x-k+1)))-k+2):
			res=1
			for j in range(i,i+k):
				if Jeu[x+(y-j)][j] == car:
					res = res*0
				if Jeu[x+(y-j)][j] != car and Jeu[x+(y-j)][j] != ' ':
					res = res*n
			if res>diagHD:
				diagHD = res
			
	return max(vert,horz,diagHD,diagHG)
	
#  la variable car indique ici le joueur qui joue !! (rappel : 'x' pour l'ordi et 'o' pour le joueur humain)
def choixCoup(Jeu,pro,car,k,n,val=0,deb=0,ref=0):
	if car == 'x':
		resultat=-100000
	else:
		resultat = 100000
	if deb == 0:
		Mligne=0
		Mcolonne=0
	res = 0
	pouet=0
	if pro>0:
		liste = []
		for q,i in enumerate(Jeu):
			for s,j in enumerate(i):
				if j == ' ':
					Jeu[q][s] = car
					if car=='x':
						sc=score(Jeu,q,s,k,n,'o')
					else:
						sc=score(Jeu,q,s,k,n,'x')
					liste.append([sc,q,s])
					Jeu[q][s] = ' '
		liste.sort()
		liste.reverse()
		for pouik in liste:
			q=pouik[1]
			s=pouik[2]
			pouet=1
			Jeu[q][s] = car
			if car=='x':
				sc=pro*pouik[0]
				val = val+sc
				res = choixCoup(Jeu,pro-1,'o',k,n,val,1,resultat)
				val = val-sc
			else :
				sc=pro*pouik[0]
				val = val-sc
				res = choixCoup(Jeu,pro-1,'x',k,n,val,1,resultat)
				val = val+sc
			
			if deb==0:
				print "x,y",q,s,res
			
			if car == 'x':			
				if res>resultat:
					resultat = res
					if deb == 0:
						Mligne = q
						Mcolonne = s
					else:
						if (resultat>ref) :
							Jeu[q][s] = ' '
							return ref
							
			else:
				if res<resultat:
					resultat=res
					if (resultat<ref):
						Jeu[q][s] = ' '
						return ref
			Jeu[q][s] = ' '		
	else:
		resultat = val
	
	if pouet ==0:
		resultat = val
	if deb == 0:
		return resultat,Mligne,Mcolonne
	else:	
		return resultat	
					
				
def JeuFini(Jeu):
	resultat=True
	for i in Jeu:
		if ' ' in i:
			resultat =False
			#print "pouet !!!!!"
	return resultat			
def pouik(Jeu):
	resultat=0
	for i in Jeu:
		for j in i:
			if j == ' ':
				resultat +=1
	return resultat	
k=3
n=3
dif=3
deb=0
#Jeu=[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']]
#pouet = choixCoup(Jeu,2,'x',k,n)
#pouet = score(Jeu,2,2,k,n,'o')

Jeu=[]
n=input("taille du jeu n:")
k=input("nbr de pion a aligner:")
dif= input("niveau du jeu (1 à 10):")
for i in range(0,n):
	Jeu.append([])
for i in range(0,n):
		for j in range(0,n):
			Jeu[i].append(' ')


deb=0
print pouik(Jeu)
while (not(JeuFini(Jeu))):
	print "le jeu:"
	for i in Jeu:
		print i

	if deb!=0:	
		l=input("ligne:")
		c=input("colonne:")
		Jeu[l][c] = 'o'
	deb=1	
	pouet = choixCoup(Jeu,min(pouik(Jeu),dif),'x',k,n)
	Jeu[pouet[1]][pouet[2]]='x'