Help please with alpha-beta

[AlvaroBegue]

Variable depth is ply in my code?

In this code example "depth" means remaining depth until horizon. In your code "ply" means the distance from root to current node. When starting search at the root with depth=5, initially you are at ply=0. After making one move you are at ply=1, and you (normally) search its subtree with depth=4. Another three plies later you are at ply=4 and search with depth=1. Etc. I wrote "normally" since you might decide to search the current node to a higher or lower depth (this is for later).

I differ a bit. ply = 1 is the root of the tree, where depth=5. By the time I get to ply=5, depth = 0 and that is the last full-width ply of search, next call will be to quiesce rather than search....

IE a move at ply=1 takes me to ply=2, with that move being the FIRST move I search...

That is for Crafty, though, while most others start with 0 at the root. And I guess in the example above you are at depth=1 (not 0) when you get to ply=5.

I use the variable name `distance_to_root', which of course is 0 at the root. For the other number I use `depth' because I've done it for many years, but perhaps it would be more clear to call it `depth_left'.

[bob]

Variable depth is ply in my code?

In this code example "depth" means remaining depth until horizon. In your code "ply" means the distance from root to current node. When starting search at the root with depth=5, initially you are at ply=0. After making one move you are at ply=1, and you (normally) search its subtree with depth=4. Another three plies later you are at ply=4 and search with depth=1. Etc. I wrote "normally" since you might decide to search the current node to a higher or lower depth (this is for later).

I differ a bit. ply = 1 is the root of the tree, where depth=5. By the time I get to ply=5, depth = 0 and that is the last full-width ply of search, next call will be to quiesce rather than search....

IE a move at ply=1 takes me to ply=2, with that move being the FIRST move I search...

That is for Crafty, though, while most others start with 0 at the root. And I guess in the example above you are at depth=1 (not 0) when you get to ply=5.

What I meant was the NEXT call goes to q-search since depth will be 0 at ply=6.

I've not seen anyone talking about a "ply 0" search. That doesn't quite match up with the various papers written on alpha/beta and/or chess.

Most talk about ply=1 moves, which take you to ply=2 positions. Sort of a basic "origin" question since zero works, but most of this was done back when 0 was not a valid subscript in the pre-C days...

My interpretation has ALWAYS been that ply=1 is the initial position, you make moves at ply=1, which take you to ply=2 positions, and so forth...

[Joost Buijs]

J. B. Buijs, nice compact code. Variable depth is ply in my code?
what should be the initial value alpha and beta?
if I used the code provided by you it will be considered cloning?

It is just a very basic recursive negamax algorithm with a-b, I don't think that people will consider it cloning if you use this.

Initially the variable depth is the depth in plies you want to search.
The initial value for alpha normally has to be a negative number and the value for beta has to be positive, but this also depends upon your evaluation values.
I would say if you use something like search(-30000, 30000, 5); it should work for a 5 ply search.

With evaluation only and without a quiescence search it will play horribly though, this is because of the horizon effect, so a quiescence search is something you have to add as well.


The initial value for alpha should be smaller than the smallest evaluation value and the initial value for beta should be larger than the largest evaluation value, these will probably be the -checkmate and +checkmate values.

[Alexandr Novikov]

J. B. Buijs, thanks! it is a complete answer to my questions. I read somewhere that the recursive function calls , spent about 50 CPU cycles . It's true?
in q-search i must include only capture, promotions and checks?

[Alexandr Novikov]

J. B. Buijs,
see please your code adapted for my program

Code: Select all

function alpha_beta(alpha, beta, ply : integer) : integer; 
var i, cnt, score : integer; 
begin 
  if ply <= 0 then begin 
//    search &#58;= evaluate; 
    evaluate;
    alpha_beta &#58;= eval;
    exit; 
  end; 
//  cnt &#58;= move_generator; 
  if color = -1 then black_move_generator else white_move_generator;
  if color = -1 then cnt &#58;= bcnt else cnt &#58;= wcnt;
  
  if color = -1 and bcnt = 0 then
   begin
    bking_in_check;
    if bcheck = true then
     begin
      alpha_beta &#58;= 32000;
      exit;
     end else
     begin
      alpha_beta &#58;= 0;
      exit;
     end;    
   end;
   
  if color = 1 and wcnt = 0 then
   begin
    wking_in_check;
    if wcheck = true then
     begin
      alpha_beta &#58;= -32000;
      exit;
     end else
     begin
      alpha_beta &#58;= 0;
      exit;
     end;    
   end;
   
  for i &#58;= 0 to cnt - 1 do begin
   if color = -1 then
    begin
     f_fld &#58;= black_moves_list&#91;i&#93; div 100;
     t_fld &#58;= black_moves_list&#91;i&#93; mod 100;      
    end else
    begin
     f_fld &#58;= white_moves_list&#91;i&#93; div 100;
     t_fld &#58;= white_moves_list&#91;i&#93; mod 100;          
    end;
    make_move; 
    if color &#58;= -1 then color &#58;= 1 else color &#58;= -1;
    score &#58;= -alpha_beta&#40;-beta, -alpha, ply - 1&#41;; 
    unmake_move; 
    if score > alpha then begin 
      if score >= beta then begin 
//        search &#58;= score; 
        alpha_beta &#58;= score;
        exit; 
      end; 
      alpha &#58;= score; 
    end; 
  end; 
  alpha_beta &#58;= alpha; 
end; 

your remark please

[Joost Buijs]

J. B. Buijs, thanks! it is a complete answer to my questions. I read somewhere that the recursive function calls , spent about 50 CPU cycles . It's true?
in q-search i must include only capture, promotions and checks?

I really don't know how much overhead a function call gives, but I guess it will be a lot less than 50 CPU cycles.
Most of the time is spent in the evaluation function, which in my program takes about 600 a 700 CPU cycles.
So you really don't have to worry about a few extra cycles added by a function call.

In quiescence you can start with captures only, this is the most important, you can add promotions and checks later.
When the king is in check you have to do check evasion moves, and you can not use the stand pat criteria you normally use in quiescence.
To keep it simple you can call the normal search with depth 1 in case the king is in check and add check evasions to the quiescence search later.

[Joost Buijs]

J. B. Buijs,
see please your code adapted for my program

Code: Select all

function alpha_beta(alpha, beta, ply : integer) : integer; 
var i, cnt, score : integer; 
begin 
  if ply <= 0 then begin 
//    search &#58;= evaluate; 
    evaluate;
    alpha_beta &#58;= eval;
    exit; 
  end; 
//  cnt &#58;= move_generator; 
  if color = -1 then black_move_generator else white_move_generator;
  if color = -1 then cnt &#58;= bcnt else cnt &#58;= wcnt;
  
  if color = -1 and bcnt = 0 then
   begin
    bking_in_check;
    if bcheck = true then
     begin
      alpha_beta &#58;= 32000;
      exit;
     end else
     begin
      alpha_beta &#58;= 0;
      exit;
     end;    
   end;
   
  if color = 1 and wcnt = 0 then
   begin
    wking_in_check;
    if wcheck = true then
     begin
      alpha_beta &#58;= -32000;
      exit;
     end else
     begin
      alpha_beta &#58;= 0;
      exit;
     end;    
   end;
   
  for i &#58;= 0 to cnt - 1 do begin
   if color = -1 then
    begin
     f_fld &#58;= black_moves_list&#91;i&#93; div 100;
     t_fld &#58;= black_moves_list&#91;i&#93; mod 100;      
    end else
    begin
     f_fld &#58;= white_moves_list&#91;i&#93; div 100;
     t_fld &#58;= white_moves_list&#91;i&#93; mod 100;          
    end;
    make_move; 
    if color &#58;= -1 then color &#58;= 1 else color &#58;= -1;
    score &#58;= -alpha_beta&#40;-beta, -alpha, ply - 1&#41;; 
    unmake_move; 
    if score > alpha then begin 
      if score >= beta then begin 
//        search &#58;= score; 
        alpha_beta &#58;= score;
        exit; 
      end; 
      alpha &#58;= score; 
    end; 
  end; 
  alpha_beta &#58;= alpha; 
end; 

your remark please

Not so easy to tell at a glance if your code is correct.
In negamax you always return values from the view of the side on the move, so in case of checkmate you have to return -32000 for white as well as for black.

It is also difficult to see what is going on with your move-list, wcnt and bcnt.
They seem to be globally, probably indexed by depth or ply, it would make things much easier and more readable when you put these things on the stack and make them local to the search function.

[Dann Corbit]

If the recursion is tail recursion, optimizing compilers will remove it.
If the recursion is not tail recursion, your choice of algorithm is still hundreds of thousands of times more important than elimination of recursion.

First make it right. Then after it is fully correct, you might worry about making it faster.

It truly is a bad idea to prematurely optimize.

[Alexandr Novikov]

Dan, Here is an example on the optimization. Initially in my generator use the following code checks the exit off the board:

board_mask : set of integer = [0, 1, 2, 3, 4, 5, 6, 7,
10,11,12,13,14,15,16,17,
20,21,22,23,24,25,26,27,
30,11,12,13,14,15,16,17,
40,21,22,23,24,25,26,27,
50,21,22,23,24,25,26,27,
60,61,62,63,64,65,66,67
70,71,72,73,74,75,76,77]

if h+9 in board_mask ....

I then removed the set and write the following code

if(h+9>=0)and(h+9<=77) and ((h +9) mod <>8) and((h +9) mod <>9) then ...

I could not believe it , the speed of the program has increased almost fivefold

so I try not to miss the moments immediately affect performance

[hgm]

I can hardly believe it either, and normally 'mod 10' would be a very expensive operation. The compiler must have a very inefficient implementation of sets and the 'in' operation.

The standard way of doing this would be to define an array indexed by the (possibly invalid) square number that would tell you if the number was valid. Like

Code: Select all

var valid: array[-22:102] of boolean;

and then initialize it such that all numbers not on the board are 'false', and the others 'true'. The test would then reduce to

Code: Select all

if valid[h] then

Note that I omitted the test (h >= -22 and h <= 102), as normally you would want to test squares that were obtained by stepping over the board according to an allowed piece move, and that in Chess no piece from a valid square could step so far that you would get out of the range -22:102. So testing for that would be a waste of time.

In fact many people do not have a separate array for that, but already define the board itself with this size, and then place some dummy pieces ('boundary guards') on the invalid squares. The test would then become

Code: Select all

victim := board[toSqr];
if victim <> Guard then

and subsequently you could test for victim being a friend, foe or empty square and act accordingly.