unit AI;

interface

uses crt, gLib2D, sdl_addon, sdl, sdl_ttf, sysutils;

type
	matrix = array of array of integer;
	coord = record
		x,y : integer;
	end;
	move = record
		dep,arr : coord;
	end;
	ptr_coup = ^_ptr_coup;
	_ptr_coup = record
		coup : move;
		val : integer;
		suiv : ptr_coup;
	end;

function switch(player : integer):integer;
function makeMove(m : matrix ; size : coord ; player,multi : integer):move;
function winCheck(m : matrix ; size : coord): boolean;

implementation

function switch(player : integer):integer;
// INGOUFF Christian
// Fonction changeant le tour de jeu
begin
	if player = 1 then switch := 2 else switch := 1;
end;

function winCheck(m : matrix ; size : coord): boolean;
// INGOUFF Christian
// Fonction vérifiant si les conditions de victoires ont été remplies, ie un des joueurs est arrivé de l'autre côté ou un joueur est à court de pions (retournant ainsi TRUE)
var
	i,j : integer;
	res, any1, any2 : boolean;
begin
	res := false;
	any1 := false;
	any2 := false;
	i := 0;
	while not res and (i < size.x) do
	begin
		res := (m[i,0] = 1) or (m[i,size.y-1] = 2);
		j := 0;
		while (not any1 or not any2) and (j < size.y) do
		begin
			any1 := (m[i,j] = 1) or (m[i,j] = 3) or any1;
			any2 := (m[i,j] = 2) or (m[i,j] = 3) or any2;
			j := j+1;
		end;
		i := i+1;
	end;
	winCheck := res or not any1 or not any2;
end;

function diagonals(m : matrix ; size : coord ; x,y : integer ; protect : boolean):integer;
// INGOUFF Christian
// Cadre de l'évaluation de la grille : Vérifie si un pion est protégé (protect = true) ou si un pion peut en manger un autre (protect = false)
var
	i,j,res,tmp : integer;
begin
	res := 0;
	if protect then tmp := switch(m[x,y]) else tmp := m[x,y];
	if tmp = 1 then j := y+1 else j := y-1;
	if (j >= 0) and (j < size.y) then
	begin
		i := x-1;
		while i < x+2 do
		begin
			if (i >= 0) and (i < size.x) and (m[i,j] = tmp) then res := res+1;
			i := i+2;
		end;
	end;
	diagonals := res;
end;

function barrierH(m : matrix ; size : coord ; x,y : integer):boolean;
// INGOUFF Christian
// Cadre de l'évaluation de la grille : Vérifie si un pion est adjacent à un autre pion horizontalement (TRUE = oui, FALSE = non)
begin
	if (x > 0) and (x < size.x-1) then
		barrierH := (m[x-1,y] = m[x,y]) or (m[x+1,y] = m[x,y])
	else
		barrierH := FALSE;
end;

function barrierV(m : matrix ; size : coord ; x,y : integer):boolean;
// INGOUFF Christian
// Cadre de l'évaluation de la grille : Vérifie si un pion est adjacent à un autre pion verticalement (TRUE = oui, FALSE = non)
var
	res : boolean;
begin
	res := false;
	if y > 0 then
		res := m[x,y-1] = m[x,y];
	if not res and (y < size.x-1) then
		res := m[x,y+1] = m[x,y];
	barrierV := res;
end;

function perspective(j,sizey,player : integer):integer;
// INGOUFF Christian
// Détermine la perspective de vue selon la valeur du pion : si le joueur commence en bas, perspective inchangée, elle est inversée sinon.
begin
	if player = 1 then
		perspective := j
	else
		perspective := sizey-j-1;
end;

function caseTmpy(tmpy, sizey : integer):integer;
// INGOUFF Christian
// Cadre de l'évaluation de la grille : attribue une valeur à un pion selon sa situation verticale (plus ou moins proche de son but ou protégeant sa 1ère case)
begin
	if tmpy = sizey-1 then
		caseTmpy := 20
	else case tmpy of
		0 : caseTmpy := 8000;
		1 : caseTmpy := 1000;
		2 : caseTmpy := 400;
	else caseTmpy := sizey - tmpy;
	end;
end;

function eval(m : matrix ; size : coord ; player,prof : integer):integer;
// INGOUFF Christian
// Evaluation de la grille, retournant une valeur d'autant plus grande que la situation du bot est bonne
// Evalue juste la situation pour le "joueur" 2
var
	i,j,tmpy : integer;
	res,count : array[1..2] of integer;
	colVide : array[1..2] of boolean;
begin
	count[1] := 0;
	count[2] := 0;
	res[1] := 0;
	res[2] := 0;
	for i := 0 to size.y-1 do
	begin
		colVide[1] := true;
		colVide[2] := true;
		for j := 0 to size.x-1 do
			if m[i,j] > 0 then
			begin
				tmpy := perspective(j,size.y,m[i,j]);
				count[m[i,j]] := count[m[i,j]]+1;
				res[m[i,j]] := res[m[i,j]] + caseTmpy(tmpy,size.y);
				res[m[i,j]] := res[m[i,j]] + diagonals(m,size,i,j,true) * 25 + diagonals(m,size,i,j,false) * 20;
				if barrierH(m,size,i,j) then res[m[i,j]] := res[m[i,j]]+15;
				if barrierV(m,size,i,j) then res[m[i,j]] := res[m[i,j]]+15;
				colVide[m[i,j]] := false;
			end;
		if colVide[1] then res[1] := res[1]-15;
		if colVide[2] then res[2] := res[2]-15;
	end;
	eval := (res[2] + count[2] * 400) - (res[1] + count[1] * 400);
end;

function moveTmp(m : matrix ; size : coord ; coup : move ; player : integer):matrix;
// INGOUFF Christian
// Fonction de simulation de coup : retourne la grille de départ (m) avec le coup testé (coup)
var
	res : matrix;
	i,j : integer;
begin
	setLength(res,size.x,size.y);
	for j := 0 to size.y-1 do
		for i := 0 to size.x-1 do
			if (i = coup.dep.x) and (j = coup.dep.y) then
				res[i,j] := 0
			else if (i = coup.arr.x) and (j = coup.arr.y) then
				res[i,j] := player
			else
				res[i,j] := m[i,j];
	moveTmp := res;
end;

function comparMinmax(fils, frere, player : integer):boolean;
// INGOUFF Christian
// Fonction permettant la comparaison selon le joueur actuel entre 2 valeurs
begin
	if player = 2 then // maximisation
		comparMinmax := fils <= frere
	else // minimisation
		comparMinmax := fils >= frere;
end;

function minMax(m : matrix ; size : coord ; prof, player, minmaxFrere : integer):integer;
// INGOUFF Christian
// Fonction Minmax utilisant une coupure (par minmaxFrere).
var
	coup : move;
	fils,minmaxFils : integer;
begin
	if (prof = 0) or winCheck(m,size) then // Conditions d'arrêt : quelqu'un a gagné ou profondeur = 0
		minMax := eval(m,size,player,prof)
	else
	begin
		if player = 2 then minmaxFils := -32000 // maximisation
		else minmaxFils := 32000; // minimisation
		coup.dep.y := 0;
		while (coup.dep.y < size.y) and comparMinmax(minmaxFils,minmaxFrere,player) do // Parcours de la grille pour tous les coups possibles
		// La boucle sera stoppée quand tous les coups possibles auront été testés ou quand minmaxFils sera plus grand que minmaxFrere lors d'une maximisation (contraire lors d'une minimisation)
		begin
			coup.dep.x := 0;
			if player = 2 then coup.arr.y := coup.dep.y+1 else coup.arr.y := coup.dep.y-1; // Définition de l'ordonnée de la destination du pion
			if (coup.arr.y >= 0) and comparMinmax(minmaxFils,minmaxFrere,player) then
				while (coup.dep.x < size.x) and comparMinmax(minmaxFils,minmaxFrere,player) do // Parcours du tableau
				begin
					coup.arr.x := coup.dep.x-1;
					if m[coup.dep.x,coup.dep.y] = player then // Si la case de départ correspond à un pion du joueur jouant
						while (coup.arr.x < coup.dep.x+2) and comparMinmax(minmaxFils,minmaxFrere,player) do // Test des 3 cases de devant
						begin
							if (coup.arr.x >= 0) and (coup.arr.x <= size.x-1) then
								if (m[coup.arr.x,coup.arr.y] = 0) or ((m[coup.arr.x,coup.arr.y] <> player) and (coup.arr.x <> coup.dep.x)) then // Si le coup est possible
								begin
									fils := minMax(moveTmp(m,size,coup,player),size,prof-1,switch(player),minmaxFils);
									if not comparMinmax(fils,minmaxFils,player) then // Modification de minmaxFils (manière analogue à l'alpha-beta)
										minmaxFils := fils;
								end;
							coup.arr.x := coup.arr.x+1;
						end;
					coup.dep.x := coup.dep.x+1;
				end;
			coup.dep.y := coup.dep.y+1;
		end;
		minMax := minmaxFils;
	end;
end;

function ajoutCoup(coup : move ; val : integer ; lCoup : ptr_coup):ptr_coup;
// INGOUFF Christian
// Fonction ajoutant un pointeur en tête d'une liste
var
	tmp : ptr_coup;
begin
	new(tmp);
	tmp^.coup := coup;
	tmp^.val := val;
	tmp^.suiv := nil;
	if lCoup = nil then
		ajoutCoup := tmp
	else
	begin
		tmp^.suiv := lCoup;
		ajoutCoup := tmp;
	end;
end;

function maxPtr(lCoup : ptr_coup ; max : integer ; coup : move ; player : integer):move;
// INGOUFF Christian
// Fonction retournant le maximum (ou le minimum, selon le joueur dont le bot prend le rôle) d'une liste
begin
	if lCoup = nil then
		maxPtr := coup
	else if (lCoup^.val > max) and (player = 2) then // maximisation
		maxPtr := maxPtr(lCoup^.suiv, lCoup^.val, lCoup^.coup,player)
	else if (lCoup^.val < max) and (player = 1) then // minimisation
		maxPtr := maxPtr(lCoup^.suiv, lCoup^.val, lCoup^.coup,player)
	else
		maxPtr := maxPtr(lCoup^.suiv,max,coup,player);
end;

procedure disposeAll(l : ptr_coup);
// INGOUFF Christian
// Procédure libérant l'ensemble d'une liste
var
	tmp : ptr_coup;
begin
	if l <> nil then
	begin
		tmp := l^.suiv;
		dispose(l);
		disposeAll(tmp);
	end;
end;

function makeMove(m : matrix ; size : coord ; player, multi : integer):move;
// INGOUFF Christian
// Fonction déterminant le coup le plus optimal, selon l'ordinateur, à jouer. Le coup à jouer est retourné.
var
	lCoup : ptr_coup;
	coup : move;
	i,j,k,val : integer;
begin
	lCoup := nil;
	if player = 2 then val := -32000 else val := 32000;
	for j := 0 to size.y-2 do
		for i := 0 to size.x-1 do
			if m[i,j] = player then
			begin
				coup.dep.x := i;
				coup.dep.y := j;
				if player = 2 then coup.arr.y := j+1 else coup.arr.y := j-1;
				if (coup.arr.y > 0) and (coup.arr.y < size.y) then
					for k := 0 to 2 do
					begin
						coup.arr.x := i+k-1;
						if (coup.arr.x >= 0) and (coup.arr.x <= size.x-1) then
							if (m[coup.arr.x,coup.arr.y] = 0) or ((m[coup.arr.x,coup.arr.y] <> player) and (coup.arr.x <> coup.dep.x)) then
								lCoup := ajoutCoup(coup,minMax(moveTmp(m,size,coup,player),size,multi-1,switch(player),val),lCoup);
					end;
			end;
	if lCoup <> nil then coup := maxPtr(lCoup,lCoup^.val,lCoup^.coup,player);
	disposeAll(lCoup);
	makeMove := coup;
end;

end.

// EOF
