cắt tủa anpha beta

PROGRAM CAT_TIA;
uses crt;
const
        n = 3;
        m = n*n;
type
        item = integer;                 {Kieu du lieu}
        pointer = ^node;
        node = record
                info : item;            {Gia tri cac Nut, 1 X thang, 0 hoa nhau, -1 X thua}
                numChild : integer;     {So con cua Nut}
                lab : char;             {Nhan cua Nut}
                child : array[1..m] of pointer;   {Mang cac con cua Nut}
        end;
        M2C = array[1..n,1..n] of char;
        IJ = record               {Toa do trong bang}
                i, j: integer;
        end;
var
        T : pointer;         {Cay}
        MT : M2C;            {Mang cac o caro}
        lb : integer;        {Nhan cac o}


function setValLa(MT: M2C): integer;    {Kiem tra xem co thang?}
var
        i, j, c, x, y: integer;
        check : boolean;
begin
        c := 0;
        for i:=1 to n do
        begin
                for j:=1 to n do
                begin
                        if ((j<=n-2) and (MT[i][j] = MT[i][j+1]) and (MT[i][j+1] = MT[i][j+2]) and (MT[i][j] <> '_'))
                                or ((i<=n-2) and (MT[i][j] = MT[i+1][j]) and (MT[i+1][j] = MT[i+2][j])  and (MT[i][j] <> '_'))
                                or ((i<=n-2) and (j <= n-2) and (MT[i][j] = MT[i+1][j+1]) and (MT[i+1][j+1] = MT[i+2][j+2])  and (MT[i][j] <> '_'))
                                or ((i<=n-2) and (j >2) and (MT[i][j] = MT[i+1][j-1]) and (MT[i+1][j-1] = MT[i+2][j-2]) and (MT[i][j] <> '_'))
                        then
                        begin
                                c := 1;
                        end;
                        if c=1 then break;
                end;
                if c=1 then break;
        end;
        setValLa := c;
end;


procedure newMT(var MT: M2c);       {Khoi tao cau hinh rong}
var
        i, j: integer;
begin
        for i:=1 to n do
                for j:=1 to n do
                        MT[i][j] := '_';
end;

procedure creatMT(MT: M2c; c : char; var T: pointer);     {Sinh cac TH va tao du lieu cho cay}
var
        i, j, count, check: integer;   {i, j la chi so Ma tran, count - dem cac o con trong, check - kiem tra thang thua}
        A : array[1..n] of IJ;
        p: pointer;
begin
        count := 0;
        check := 0;
        for i:= 1 to n do      {Dem va luu lai cac o rong, in ra cau hinh thu duoc}
        begin
                for j:=1 to n do
                begin
                        if (MT[i][j] <> 'X') and (MT[i][j] <> 'O') then
                        begin
                                inc(count);
                                A[count].i := i;
                                A[count].j := j;
                        end;
                        write(MT[i][j]);
                end;
                writeln();
        end;
        check := setValLa(MT);    {Kiem tra thang thua}


        if (T = nil) then new (T);       {Khoi tao cay}
        T^.numChild := count;            {Tao so Nut con cua Nut = so o rong}

        if (count = 0) then T^.info := 0;   {Neu khong o nao rong thi info = 0 - 2 ben hoa nhau}
        if (c = 'X') and (check = 1) then T^.info := -1   {X thua}
        else
                if (c = 'X') and (check <> 1) and (count <> 0) then T^.info := -2   {chua xac dinh, gia tri tam la -2}
                else
                        if (c = 'O') and (check = 1) then T^.info := 1              {X thang}
                        else if (c = 'O') and (check <> 1) and (count <>0) then T^.info := 2; {chua xac dinh, tam la 2}

        inc(lb);
        T^.lab := chr(lb);  {gan nhan cho Nut}
        writeln('Gai tri Nut cua cau hinh ', T^.lab, ' la: ', T^.info);

        writeln('-----------------So o rong: ', count, ' , luot di cua ', c);
        writeln;

        if (check = 1) or (count = 0) then T^.numChild := 0
        else
        begin                          {De quy tao cay va cau hinh tuong ung}
                for i:= 1 to count do
                begin
                        new (T^.child[i]);
                        MT[A[i].i][A[i].j] := c;
                        if c = 'X' then creatMT(MT, 'O', T^.child[i])
                        else if c = 'O' then creatMT(MT, 'X', T^.child[i]);
                        MT[A[i].i][A[i].j] := '_';
                end;
        end;
end;
{
procedure inputTree1(var T: pointer);
var
        i: integer;
        p: pointer;
begin
        if (T = nil) then new (T);
        write('Nhap nut con cua ', T^.info, ' : ');
        readln(T^.info);
        write('Nhap so con cua ', T^.info, ' : ');
        readln(T^.numChild);
        for i:=1 to T^.numChild do
        begin
                new (T^.child[i]);
                inputTree1(T^.child[i]);
        end;
end;
}

function nutLa(p: pointer): boolean;        {Kiem tra p co la nut la ko}
begin
        if p^.numChild = 0 then nutLa := true
        else nutLa := false;
end;

procedure duyetTruoc(T: pointer);           {Duyet theo thu tu truoc}
var
        p: pointer;
        i: integer;
begin
        if T <> nil then
        begin
                writeln(T^.lab, ' = ', T^.info);
                {if (nutLa(T)) then writeln(T^.lab , ' la la');}
                for i:=1 to T^.numChild do
                        duyetTruoc(T^.child[i]);
        end;
end;


function max(a:item; b: item): item;
begin
        if a>b then max:=a
        else max:=b;
end;

function min(a:item; b:item): item;
begin
        if a<b then min:=a
        else min := b;
end;

{Ham tra ve gia tri trang thai khi dung minmax - thuat toan minmax}
function val(var q: pointer; c: char; Vp: item): item;
var
	i: integer;
begin
	if (nutLa(q)) then      {Neu la nut la thi lay ngay KQ gia tri cua nut do}
        begin
                {writeln(q^.lab,'->>> ', q^.info);}
                val:= q^.info;
        end
	else
	begin
		{if c = 'X' then Vq := -2 else Vq := 2;}
		for i:= 1 to q^.numChild do   {Duyet cac nut con cua q}
		begin
			if c = 'X' then       {Neu dang la luot X}
			begin
				q^.info:= max(q^.info, val(q^.child[i], 'O', q^.info));
				{writeln(q^.lab,'->>> ', q^.info);}
                                val := q^.info;
                        end
			else                    {Nguoc lai la luot O}
			begin
				q^.info:= min(q^.info, val(q^.child[i], 'X', q^.info));
				{writeln(q^.lab,'->>> ', q^.info);}
                                val := q^.info;
				break;
			end;
		end;
	end;
end;



procedure catTia(var T: pointer);  {Dua thuat toan vao cay}
begin
	if T <> nil then
	begin
		T^.info := val (T, 'X', T^.info);
	end;
end;


BEGIN
        clrscr;
        lb := 64;
        newMT(MT);
        {Khoi tao cau hinh ban dau}
        MT[1][1] := 'X'; MT[1][3]:= 'X'; MT[2][2] := 'X';
        MT[2][3] := 'O'; MT[3][1]:= 'O'; MT[3][3] := 'O';
        creatMT(MT, 'X', T);
        {inputTree1(T);}
        if T = nil then writeln('NIL');
        writeln('Truoc khi cat tia:');
        duyetTruoc(T);
        writeln;
        writeln('Qua trinh cat tia');
        catTia(T);
        writeln;
        writeln('Ket qua cat tia');
        duyetTruoc(T);
        readln;
END.