Help please with alpha-beta

[Henk]

Does your alternative algorithm cut off more redundant nodes ? Otherwise it's not that interesting. Better copy standard solution.

[hgm]

It is the standard solution, for the fail-hard case. The best_scoreN are the alpha, of the node that increment it. In the standard (recursive negamax) formulation that alpha is passed to daughters as beta (after sign flip), and beta is then passed to their daughters (again after sign flip) as alpha (Search(-beta, -alpha)). So in the end the current value of alpha (after having been increased by any move searched previously in that node) will be passed unmodified to the granddaughters as their start alpha. Which is what the statement best_scoreN := best_scoreN-2; does here.

And beta in the standard formulation would just be the -alpha of the parent, but since this is not negamax and no sign flips are used, it would be identical to alpha. So to test for beta cutoff you just compare best_scoreN against best_scoreN-1. Alpha and beta are just the best scores so far of all side branches below it for one side or the other. So that you know that when the score gets out of window there will always be one side that would deviate at an earlier level.

[Alexandr Novikov]

H.G.Muller,

procedure search;
var .....
black_move_generator;
for i:=0 to bcnt - 1; //all possible black moves
make_move;
first_ply; //call next iteration
if i = 0 then best_score := best_score1 else
if best_score1 < best_score then best_score := best_score1; //min
unmake_move;
//--------------------------------------------------------------------------------------
procedure two_ply;
var .....
white_move_generator;
for i:=0 to wcnt - 1; //all possible white moves
make_move;
tree_ply; //call next iteration
if i = 0 then best_score1 := best_score2 else
if best_score2 > best_score1 then best_score1 := best_score2; //max
unmake_move;
if (i > 0) and (best_score1 > best_score) then exit;
//-------------------------------------------------------------------------------------- procedure tree_ply;
var .....
black_move_generator;
for i:=0 to bcnt - 1; //all possible black moves
make_move;
four_ply; //call next iteration
if i = 0 then best_score2 := best_score3 else
if best_score3 < best_score2 then best_score2 := best_score3; // min
unmake_move;
if (i > 0) and (best_score2 < best_score1) then exit;
//--------------------------------------------------------------------------------------procedure four_ply;
var .....
white_move_generator;
for i:=0 to wcnt - 1; //all possible white moves
make_move;
five_ply; //call next iteration
if i = 0 then best_score3 := best_score4 else
if best_score4 > best_score3 then best_score3 := best_score4; //max
unmake_move;
if (i > 0) and (best_score3 > best_score2) then exit;
//--------------------------------------------------------------------------------------procedure five_ply;
var .....
black_move_generator;
for i:=0 to bcnt - 1; //all possible black moves
make_move;
six_ply;
if i = 0 then best_score4 := best_score5 else
if best_score5 < best_score4 then best_score4 := best_score5; // min
unmake_move;
if (i > 0) and (best_score4 < best_score3) then exit;
//--------------------------------------------------------------------------------------
procedure six_ply;
var .....
white_move_generator;
for i:=0 to wcnt - 1; //all possible black moves
make_move;
evaluate; //call evaluate function
if i = 0 then best_score5 := eval else
if eval > best_score5 then best_score5 := eval; // max
unmake_move;
//--------------------------------------------------------------------------------------

I guess it works, however, using these cuts, I get other moves(i don't use random if on example best_score4=best_score3). I don't know whether to completely match the moves in the game with cuts and no cuts. Time on the moves declined very much

[Henk]

H.G.Muller,

procedure search;
var .....
black_move_generator;
for i:=0 to bcnt - 1; //all possible black moves
make_move;
first_ply; //call next iteration
if i = 0 then best_score := best_score1 else
if best_score1 < best_score then best_score := best_score1; //min
unmake_move;
//--------------------------------------------------------------------------------------
procedure two_ply;
var .....
white_move_generator;
for i:=0 to wcnt - 1; //all possible white moves
make_move;
tree_ply; //call next iteration
if i = 0 then best_score1 := best_score2 else
if best_score2 > best_score1 then best_score1 := best_score2; //max
unmake_move;
if (i > 0) and (best_score1 > best_score) then exit;
//-------------------------------------------------------------------------------------- procedure tree_ply;
var .....
black_move_generator;
for i:=0 to bcnt - 1; //all possible black moves
make_move;
four_ply; //call next iteration
if i = 0 then best_score2 := best_score3 else
if best_score3 < best_score2 then best_score2 := best_score3; // min
unmake_move;
if (i > 0) and (best_score2 < best_score1) then exit;
//--------------------------------------------------------------------------------------procedure four_ply;
var .....
white_move_generator;
for i:=0 to wcnt - 1; //all possible white moves
make_move;
five_ply; //call next iteration
if i = 0 then best_score3 := best_score4 else
if best_score4 > best_score3 then best_score3 := best_score4; //max
unmake_move;
if (i > 0) and (best_score3 > best_score2) then exit;
//--------------------------------------------------------------------------------------procedure five_ply;
var .....
black_move_generator;
for i:=0 to bcnt - 1; //all possible black moves
make_move;
six_ply;
if i = 0 then best_score4 := best_score5 else
if best_score5 < best_score4 then best_score4 := best_score5; // min
unmake_move;
if (i > 0) and (best_score4 < best_score3) then exit;
//--------------------------------------------------------------------------------------
procedure six_ply;
var .....
white_move_generator;
for i:=0 to wcnt - 1; //all possible black moves
make_move;
evaluate; //call evaluate function
if i = 0 then best_score5 := eval else
if eval > best_score5 then best_score5 := eval; // max
unmake_move;
//--------------------------------------------------------------------------------------

I guess it works, however, using these cuts, I get other moves(i don't use random if on example best_score4=best_score3). I don't know whether to completely match the moves in the game with cuts and no cuts. Time on the moves declined very much

Do you think your code is maintainable. Or is this the output of a compiler ?

[hgm]

Well, you did not initialize the best_scores to that of two levels below, so I am not surprised it does not work correctly. It should not lead to other moves if it does work correctly. To make that happen it should be:

Code: Select all

procedure search; 
var ..... 
black_move_generator; 
best_score := +infinite;
for i:=0 to bcnt - 1; //all possible black moves 
  make_move; 
  first_ply; //call next iteration 
  if best_score1 < best_score then best_score := best_score1; //min 
  unmake_move; 
//-------------------------------------------------------------------------------------- 
procedure two_ply; 
var ..... 
white_move_generator; 
best_score1 := -infinite;
for i:=0 to wcnt - 1; //all possible white moves 
  make_move; 
  tree_ply; //call next iteration 
  if best_score2 > best_score1 then best_score1 := best_score2; //max   
  unmake_move; 
  if (best_score1 >= best_score) then exit; 
//-------------------------------------------------------------------------------------- 
procedure tree_ply; 
var ..... 
black_move_generator; 
best_score2 := best_score;
for i:=0 to bcnt - 1; //all possible black moves 
  make_move; 
  four_ply; //call next iteration 
  if best_score3 < best_score2 then best_score2 := best_score3; // min 
  unmake_move; 
  if (best_score2 <= best_score1) then exit; 
//--------------------------------------------------------------------------------------
procedure four_ply; 
var ..... 
white_move_generator; 
best_score3 := best_score1;
for i:=0 to wcnt - 1; //all possible white moves 
  make_move; 
  five_ply; //call next iteration 
  if best_score4 > best_score3 then best_score3 := best_score4; //max 
  unmake_move; 
  if (best_score3 >= best_score2) then exit; 
//--------------------------------------------------------------------------------------
procedure five_ply; 
var ..... 
black_move_generator; 
best_score4 := best_score2;
for i:=0 to bcnt - 1; //all possible black moves 
  make_move; 
  six_ply; 
  if best_score5 < best_score4 then best_score4 := best_score5; // min 
  unmake_move; 
  if (best_score4 <= best_score3) then exit;
//--------------------------------------------------------------------------------------
procedure six_ply; 
var ..... 
white_move_generator; 
best_score5 := best_score3;
for i:=0 to wcnt - 1; //all possible black moves 
  make_move; 
  evaluate; //call evaluate function 
  if eval > best_score5 then best_score5 := eval; // max
  unmake_move; 
  if (best_score5 >= best_score4) then exit;
//--------------------------------------------------------------------------------------

Note that you still have inconsistent naming with 'first_ply'.

[hgm]

Do you think your code is maintainable. Or is this the output of a compiler ?

The code is of course not maintainable in this form. In the early 80s a program was participating in the Dutch championship that was written in Fortran, which did not support recursion. So he had code like this. The program kept blundering away material in the strangest ways. Eventually it turned out that of the 7 copies of the search routine for each ply level, the 6th had the opposite comparison of what it should be.

[Alexandr Novikov]

Do you think your code is maintainable. Or is this the output of a compiler ?

The code is of course not maintainable in this form. In the early 80s a program was participating in the Dutch championship that was written in Fortran, which did not support recursion. So he had code like this. The program kept blundering away material in the strangest ways. Eventually it turned out that of the 7 copies of the search routine for each ply level, the 6th had the opposite comparison of what it should be.

my code will soon be reduced to normal view, just this is my first experience in writing a chess program

[Dann Corbit]

Recursive programming is so simple that anyone can understand it.
Using a stack would probably be slightly more efficient, but far harder to code and maintain.

If the OP does not understand recursion, then a web search for the term and then a 15 minutes exercise first of N! and then the Ackermann function, including tracing both in the debugger will show them everything they need to know.

A recursive chess program is clearly the right way for a beginner to do it.
Alpha-beta without recursion is horrible to contemplate (though if one is willing to do tedious things like maintaining your own stacks, then it can certainly be done iteratively).

[Alexandr Novikov]

H.G.Muller
one question please:
6 ply
without cuts : 1.e2e4 d7d5 2.e4d5 d8d5 3. b1c3 d5e6+
with cuts: 1.e2e4 a7a5 2.d2d4 e7e6 and etc

program with cuts plays differently. It's normal?

[Henk]

I remember a teacher at school having trouble with explaining code of towers of Hanoi problem.