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:
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:
Hi the Delphi attachment couldn't be downloaded. Can you please refresh the link.
ReplyDelete