JS Schach's alpha-beta approximation

[Gerd Isenberg]

Further the cut-off conditions seem too weak to me >= instead of >, or <= instead of <
https://github.com/rchastain/moustique/ ... e.pas#L417

If I understand correctly, you would suggest to try the following modification?

Code: Select all

    if FActive = AColor then
    begin
      if LValue > LBeta then
        LBeta := LValue;
      if LBeta >= AAlpha then
        LStop := TRUE;
    end else
    begin
      if LValue < LBeta then
        LBeta := LValue;
      if LBeta <= AAlpha then
        LStop := TRUE;
    end;

I could try it at once.

Yes

[Ras]

Fixed depth of 3 without iterative deepening and max depth 5 for captures should be quite fast. And at that depth the deficits missing deep cutoffs is not that important.

I modified my engine to overwrite alpha with -MAX in search and QS. Main depth (without QS) 4 is about even, 5 takes 50% longer, 6 three times as long, and it goes downhills from there. A match over 500 games at 10 seconds per game (no depth limitation) shows a loss of 436 Elo.

[Gerd Isenberg]

Fixed depth of 3 without iterative deepening and max depth 5 for captures should be quite fast. And at that depth the deficits missing deep cutoffs is not that important.

I modified my engine to overwrite alpha with -MAX in search and QS. Main depth (without QS) 4 is about even, 5 takes 50% longer, 6 three times as long, and it goes downhills from there. A match over 500 games at 10 seconds per game (no depth limitation) shows a loss of 436 Elo.

Interesting. Guess when you replace score >= beta by score > beta it is even worse.

[Ras]

Interesting. Guess when you replace score >= beta by score > beta it is even worse.

With that change in addition, depth 5 stays at about +50% time while depth 6 is already four times as much, so that's worse. The same match now loses 512 Elo, i.e. even more, but that could as well be statistical noise with just 500 games.

[Roland Chastain]

I made an experimental version on the engine with this modification:

Code: Select all

    if FActive = AColor then
    begin
      if LValue > LBeta then
        LBeta := LValue;
      if (LBeta > AAlpha) or (LBeta = AAlpha) and (ADepth > 2) then
        LStop := TRUE;
    end else
    begin
      if LValue < LBeta then
        LBeta := LValue;
      if (LBeta < AAlpha) or (LBeta = AAlpha) and (ADepth > 2) then
        LStop := TRUE;
    end;

(Without the limitation to depth > 2, the engine was playing illegal moves.)

In the current state of the program, it doesn't make any perceptible difference, but I will try to find a way to make the difference visible. I think of improving the log file, so that one can see the number of nodes.

@Ras
I have to explore your program. Until now, I just explored your Linux scripts, where I learned many things.

Thank you both for that very interesting discussion.

[Ras]

In the current state of the program, it doesn't make any perceptible difference

I think that's because my program searches only the first move in a node with full window of (alpha; beta) while the others have a scout window of (alpha-1; alpha). The test change was equivalent to removing the scout window and replacing it with (-INF; alpha), which is why the difference is so pronounced. If you don't have such a scouting yet, then the difference won't have that much of an impact.

I have to explore your program. Until now, I just explored your Linux scripts, where I learned many things.

Thanks.

[silentshark]

As to avoiding negamax: it requires all code that appears in duplicate to be split into separate sections for max- and the min-player, differing only in the < and > operators. For a very basic search this is not really a problem (the required single conditional is easily predicted). But in principle isuch duplication makes the code more difficult to maintain, as there is no guarantee both sections will always remain equivalent. And in more advanced search, where there are more score-based decisions, such duplications woul pop up all over the place.

Lol, this is what my program does, and has always done. That's because it was written in the early 1990's, and I was trying to figure all this stuff out without knowing what other programs did. I wrote stuff based on the ideas in Levy's 'How Computers Play Chess' book, and it remains in that kind of limbo state for ever more.

[Gerd Isenberg]

I made an experimental version on the engine with this modification:

Code: Select all

    if FActive = AColor then
    begin
      if LValue > LBeta then
        LBeta := LValue;
      if (LBeta > AAlpha) or (LBeta = AAlpha) and (ADepth > 2) then
        LStop := TRUE;
    end else
    begin
      if LValue < LBeta then
        LBeta := LValue;
      if (LBeta < AAlpha) or (LBeta = AAlpha) and (ADepth > 2) then
        LStop := TRUE;
    end;

(Without the limitation to depth > 2, the engine was playing illegal moves.)

That looks like an unrelated bug to me.

In the current state of the program, it doesn't make any perceptible difference, but I will try to find a way to make the difference visible. I think of improving the log file, so that one can see the number of nodes.

@Ras
I have to explore your program. Until now, I just explored your Linux scripts, where I learned many things.

Thank you both for that very interesting discussion.

You are welcome.

[Roland Chastain]

That looks like an unrelated bug to me.

Maybe. I would need to check again the code. If I remember correctly, the same procedure that searches for the best move is also used to evaluate moves legality. Inside the procedure the capture of the king is allowed. An illegal move is just considered as a very bad move. So I imagine that if the tree is cut too low, the program becomes blind to "check after move" situations.

[Roland Chastain]

Yep, alpha beta have reversed semantics. Larger search tree due to missing deep cutoffs. Further the cut-off conditions seem too weak to me >= instead of >, or <= instead of <
https://github.com/rchastain/moustique/ ... e.pas#L417

One year later, I found a (very simple) way to accurately measure the effect of this change. The result is that the program plays the same moves, but two or three times faster!

Commit.

Thanks again Gerd.