Alpha-beta pruning algorithm with Delphi

I'm trying to get round to writing more often and to do my own research with some interesting and complicated algorithms. Given to my great passion for different types of algorithms, in AI , I have found one very interesting and here you can get it build with Delphi 2010. With this solution, you'll be able to add values to the leaves and run the algorithm to find the nodes that will be evaluated and others that will be pruned. I've used my little framework to build the structure (using a GDI render) and then only focus on the algorithm that was the important part. Alpha-beta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm. It is a search with adversary algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. Alpha-beta pruning is a sound optimization in that it does not change the result of the algorithm it optimizes (Algorithmist.com). 

The pseudo-code is quite simple, and it looks like this:

The structure of the application is very simple and the most difficult part is the simulation process where you need to draw every step of the algorithm.

You can download the application from here (Thundax Alpha-beta pruning) and play with it to understand how the algorithm works.

This video shows the execution of the program:

The code of the algorithm is explained as follows:

Alpha-beta algorithm:

function TViewMinimax.alphabeta(Node: TNode; alpha: integer; beta: integer): integer;
var
    i: integer;
    ret: integer;
begin
    if Node.isLeaf then
        ret := Node.Value
    else
    begin
        for i := 0 to Node.children.Count - 1 do
        begin
            alpha := max(alpha, -alphabeta(Node.children.Items[i], -beta, -alpha));
            case Node.player of
                tMAX:
                    begin
                        Node.Value := alpha;
                        SetAlpha(Node, alpha);
                        Node.visited := true;
                    end;
                tMIN:
                    begin
                        Node.Value := -alpha;
                        SetBeta(Node, alpha);
                        Node.visited := true;
                    end;
            end;
            if beta <= alpha then
                Break;
        end;
        ret := alpha;
    end;
    result := ret;
end;

Drawing the nodes by using a pre-order method for iterating the binary tree:

procedure TViewMinimax.Draw;
begin
    preorder(Self.FMinimax.root);
end;

procedure TViewMinimax.preorder(root: TNode);
begin
    if Assigned(root) then
    begin
        if root.children.Count > 0 then
        begin
            DrawLine(root, root.children.Items[0]);
            DrawLine(root, root.children.Items[1]);
            preorder(root.children.Items[0]);
            preorder(root.children.Items[1]);
        end;
        DrawRectangle(root);
    end;
end;

procedure TViewMinimax.DrawRectangle(Node: TNode);
begin
    Fcanvas.Font.Name := 'Arial';
    Fcanvas.Brush.Style := bsSolid;
    if Node.visited then
        Fcanvas.Brush.Color := clRed
    else
        Fcanvas.Brush.Color := clWhite;
    if Node.selected then
        Fcanvas.Brush.Color := clGreen;
    Fcanvas.Pen.Width := 2;
    Fcanvas.Pen.Color := clBlack;
    Fcanvas.Rectangle(Node.position.x - gap, Node.position.y - gap, Node.position.x + gap, Node.position.y + gap);
    Fcanvas.TextOut(Node.position.x - 5, Node.position.y - 5, Inttostr(Node.Value));
    Fcanvas.Brush.Color := clWhite;
    if (Node.isLeaf) and (Node.Order <> 0) then
        Fcanvas.TextOut(Node.position.x - 5, Node.position.y + 15, Inttostr(Node.Order));
    if not Node.isLeaf then
    begin
        case Node.player of
            tMAX:
                begin
                    if Node.alpha <> 0 then
                        Fcanvas.TextOut(Node.position.x - 65, Node.position.y - 10, Inttostr(Node.Order) + ': a=' + Inttostr(Node.alpha));
                    if Node.newAlpha <> 0 then
                        Fcanvas.TextOut(Node.position.x - 65, Node.position.y + 5, Inttostr(Node.NewOrder) + ': a=' + Inttostr(Node.newAlpha));
                end;
            tMIN:
                begin
                    if Node.beta <> 0 then
                        Fcanvas.TextOut(Node.position.x - 65, Node.position.y - 10, Inttostr(Node.Order) + ': ß=' + Inttostr(Node.beta));
                    if Node.Newbeta <> 0 then
                        Fcanvas.TextOut(Node.position.x - 65, Node.position.y + 5, Inttostr(Node.NewOrder) + ': ß=' + Inttostr(Node.Newbeta));
                end;
        end;
        if Node.text <> '' then
        begin
            Fcanvas.Brush.Color := clyellow;
            if (Node.newAlpha = 0) and (Node.Newbeta = 0) then
                Fcanvas.TextOut(Node.position.x - 53, Node.position.y + 5, Node.text)
            else
                Fcanvas.TextOut(Node.position.x - 53, Node.position.y + 20, Node.text)
        end;
    end;
end;

Setting up the Minimax Algorithm:

procedure TForm1.Start1Click(Sender: TObject);
var
    vminimax: TViewMinimax;
    minimax: TMinimax;
    words: TStringList;
    alpha, beta: integer;
begin
    minimax := TMinimax.Create;
    if Edit1.Text <> '' then
    begin
        words := TStringList.Create;
        SplitTextIntoWords(Edit1.Text, words);
        minimax.AddNumbers(words);
    end;
    minimax.CreateTree;
    Memo1.Lines.Clear;

    Image1.Canvas.Brush.color := clwhite;
    Image1.Canvas.Rectangle(0, 0, Image1.Width, Image1.Height);

    vminimax := TViewMinimax.Create(Self.Image1.Canvas, minimax, Memo1);
    if CheckBox1.Checked then
        vminimax.time := 1000
    else
        vminimax.time := 0;
    alpha := alphavalue;
    beta := betavalue;

    vminimax.Draw;
    Self.Image1.Canvas.TextOut(951, 25 - 5, 'MAX');
    Self.Image1.Canvas.TextOut(951, 127 - 5, 'MIN');
    Self.Image1.Canvas.TextOut(951, 228 - 5, 'MAX');
    Self.Image1.Canvas.TextOut(951, 328 - 5, 'MIN');

    Start1.Enabled := false;
    CheckBox1.Enabled := false;
    vminimax.alphabeta(minimax.root, alpha, beta);
    vminimax.Draw;
    Start1.Enabled := true;
    CheckBox1.Enabled := true;

    FreeAndNil(words);
    FreeAndNil(minimax);
    FreeAndNil(vminimax);
end;

Splitting the text into numbers (comma separated values):

procedure SplitTextIntoWords(const S: string; words: TstringList);
var
    startpos, endpos: Integer;
begin
    Assert(Assigned(words));
    words.Clear;
    startpos := 1;
    while startpos <= Length(S) do
    begin
        while (startpos <= Length(S)) and (S[startpos] = ',') do
            Inc(startpos);
        if startpos <= Length(S) then
        begin
            endpos := startpos + 1;
            while (endpos <= Length(S)) and not (S[endpos] = ',') do
                Inc(endpos);
            words.Add(Copy(S, startpos, endpos - startpos));
            startpos := endpos + 1;
        end;
    end;
end;

Related links:

• Alpha-beta pruning Wikipedia.
• Alpha-beta pruning Java.
• Alpha-beta algorithm.
• Algoritmo Minimax.