unit Alpha;

interface

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):move;
function winCheck(m : matrix ; size : coord): boolean;

implementation

function switch(player : integer):integer;
begin
	if player = 1 then switch := 2 else switch := 1;
end;

function winCheck(m : matrix ; size : coord): boolean;
var
	i,j : integer;
	res,vide1,vide2 : boolean;
begin
	res := FALSE;
	vide1 := true;
	vide2 := true;
	i := 0;
	while not res and (i < size.x) do
	begin
		j := 0;
		res := (m[i,0] = 1) or (m[i,size.y-1] = 2);
		if not res then
			while (vide1 or vide2) and (j < size.y) do
			begin
				vide1 := (m[i,j] <> 1) and vide1;
				vide2 := (m[i,j] <> 2) and vide2;
				j := j+1;
			end;
		i := i+1;
	end;
	winCheck := res or vide1 or vide2;
end;

function diagonals(m : matrix ; size : coord ; x,y : integer ; protect : boolean):integer;
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;
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;
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;
begin
	if player = 1 then
		perspective := j
	else
		perspective := sizey-j-1;
end;

function eval(m : matrix ; size : coord ; player : integer):integer;
// 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;
				if tmpy = 0 then
					res[m[i,j]] := res[m[i,j]]+10000
				else if tmpy = size.y-1 then
					res[m[i,j]] := res[m[i,j]]+10;
				res[m[i,j]] := res[m[i,j]] + diagonals(m,size,i,j,true) * 10;
				res[m[i,j]] := res[m[i,j]] - diagonals(m,size,i,j,false) * 10;
				if barrierH(m,size,i,j) then res[m[i,j]] := res[m[i,j]]+10;
				if barrierV(m,size,i,j) then res[m[i,j]] := res[m[i,j]]+10;
				colVide[m[i,j]] := false;
			end;
		if colVide[1] then res[1] := res[1]-10;
		if colVide[2] then res[2] := res[2]-10;
	end;
	eval := (res[2] + count[2] * 400) - (res[1] + count[1] * 400);
end;

function moveTmp(m : matrix ; size : coord ; coup : move ; player : integer):matrix;
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 alphaBeta(m : matrix ; size : coord ; prof : integer ; var alpha, beta : integer ; player : integer):integer;
var
	coup : move;
	tmp : integer;
begin
	if (prof = 0) or winCheck(m,size) then
		alphaBeta := eval(m,size,player)
	else
	begin
		coup.dep.y := 0;
		while coup.dep.y < size.y do
		begin
			coup.dep.x := 0;
			if player = 2 then coup.arr.y := coup.dep.y+1 else coup.arr.y := coup.dep.y-1;
			if (coup.arr.y >= 0) and (coup.arr.y < size.y) then
				while coup.dep.x < size.x do
				begin
					coup.arr.x := coup.dep.x-1;
					if m[coup.dep.x,coup.dep.y] = player then
						while coup.arr.x < coup.dep.x+2 do
						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
								begin
									tmp := alphaBeta(moveTmp(m,size,coup,player),size,prof-1,alpha,beta,switch(player));
									if (player = 2) and (tmp > alpha) then
										alpha := tmp // get maximum
									else if (player = 1) and (tmp < beta) then
										beta := tmp // get minimum
									else // break
									begin
										coup.arr.x := size.x+2;
										coup.dep.x := size.x;
										coup.dep.y := size.y;
									end;
								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;
		alphaBeta := tmp;
	end;
end;
		


function ajoutCoup(coup : move ; val : integer ; lCoup : ptr_coup):ptr_coup;
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 makeMove(m : matrix ; size : coord):move;
var
	lCoup,tmp : ptr_coup;
	coup : move;
	i,j,k,val,alpha,beta : integer;
begin
	lCoup := nil;
	val := -32000;
	for j := 0 to size.y-2 do
		for i := 0 to size.x-1 do
			if m[i,j] = 2 then
			begin
				coup.dep.x := i;
				coup.dep.y := j;
				coup.arr.y := j+1;
				for k := 0 to 2 do
				begin
					alpha := -32000;
					beta := 32000;
					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] <> 2) and (coup.arr.x <> coup.dep.x)) then
							lCoup := ajoutCoup(coup,alphaBeta(moveTmp(m,size,coup,2),size,3(*profondeur*),alpha,beta,1),lCoup);
				end;
			end;
	while lCoup <> nil do
	begin
		writeln(lCoup^.val,', ',lCoup^.coup.dep.x+1,',',lCoup^.coup.dep.y+1,' to ',lCoup^.coup.arr.x+1,',',lCoup^.coup.arr.y+1);
		if lCoup^.val > val then
		begin
			val := lCoup^.val;
			coup := lCoup^.coup;
		end;
		tmp := lCoup;
		lCoup := lCoup^.suiv;
		dispose(tmp);
	end;
	writeln('Valeur max = ',val,' ; Coup joué : ',coup.dep.x+1,',',coup.dep.y+1,' vers ',coup.arr.x+1,',',coup.arr.y+1);
	makeMove := coup;
end;

end.

// EOF