Help please with alpha-beta

[Alexandr Novikov]

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).

thanks, I will do recursion search. you're completely right

[hgm]

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?

No, it means there still is an error somewhere. It should play exactly the same. Alpha-beta pruning should also prune nodes that do not affect the result.

[Henk]

Hi friends! I am a beginner chess programmer , this is my hobby, so do not judge strictly. I wrote a simple chess program with graphics interface(pascal abc net). It's five ply or depth (I do not understand the difference between them) search with minimax method. My search procedure without reduction and my code looks like this:
//--------------------------------------------------------------------------------------
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;
//-------------------------------------------------------------------------------------- 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;
//--------------------------------------------------------------------------------------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;
//--------------------------------------------------------------------------------------procedure five_ply;
var .....
black_move_generator;
for i:=0 to bcnt - 1; //all possible black moves
make_move;
evaluate; //call evaluate function
if i = 0 then best_score4 := eval else
if eval < best_score4 then best_score4 := eval; // min
unmake_move;
//--------------------------------------------------------------------------------------
Minimax works fine, but I do not understand both should work alpha beta( Please, explain me, how on my pseudo code should work alpha beta. I know, that for a-b very important moves ordering and i have simple moves ordering.
thank you in advance.
best
Alexandr Novikov
p.s.I do not want to read other people code, I want to understand everything myself

Better copy a standard solution and start annoying others with questions like "I don't understand .. could you explain .."

Always these useless hobbies.

[AlvaroBegue]

Here's what I recommend:
(1) Implement perft. This will let you check that your move generation and making/undoing moves work correctly. Also it will give you a very simple example of recursion to get started with.
(2) Implement NegaMax. The code for this is slightly more complicated than perft, but it's still easy to follow.
(3) Modify NegaMax to use alpha-beta pruning.

That's a straight-forward path to getting a working alpha-beta implementation, with relatively manageable steps, and you can stop and test for correctness after each step.

[Alexandr Novikov]

I'm trying to implement recursion search, but I see many problems with castls, promotion and enpassant on deep iterations. what would you advise?

[AlvaroBegue]

I'm trying to implement recursion search, but I see many problems with castls, promotion and enpassant on deep iterations. what would you advise?

Before you can consider writing your search, you should make sure you have a decent board implementation that knows about all the rules of the game (except perhaps for three-fold repetition, which can be handled elsewhere).

In order to represent the state of the board you need to know the configuration of the board (an array of small integers will do), the set of castling moves that are still legal (kingside/queenside for white/black), whose turn it is, which pawn might be captured en passant, and the number of moves since the last time a pawn was moved or a capture happened (to implement the 50-move rule).

Recursive search has very little to do with this. Write perft (which is a recursive function) to test that you got your move generation right.

[Joost Buijs]

I'm trying to implement recursion search, but I see many problems with castls, promotion and enpassant on deep iterations. what would you advise?

First you have to make sure that your move-generator, make-move and unmake-move are bug free.
The easiest way to check this is by a perft function which should give the right node count for certain positions you can find everywhere on the net.

A very basic recursive negamax with a-b in Pascal will look approximately like this:

Code: Select all

function search(alpha, beta, depth : integer) : integer;
var i, cnt, score : integer;
begin
  if depth <= 0 then begin
    search &#58;= evaluate;
    exit;
  end;
  cnt &#58;= move_generator;
  for i&#58; = 0 to cnt - 1 do begin
    make_move;
    score &#58;= -search&#40;-beta, -alpha, depth - 1&#41;;
    unmake_move;
    if score > alpha then begin
      if score >= beta then begin
        search &#58;= score;
        exit;
      end;
      alpha &#58;= score;
    end;
  end;
  search &#58;= alpha;
end;

Of course you have to swap colors on every call.

[hgm]

I don't see how that can have anything to do with recursion. Recursion is just using the same piece of code, instead of needlessly duplicating it. Otherwise there should be no differece.

[Alexandr Novikov]

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?

[Alexandr Novikov]

i think i have good move generator. my program analyzes over 2 000 000 positions per second on my core i7 in single mode. i used mac mashine with parallels desktop for chess programming