JS Schach's alpha-beta approximation

[Gerd Isenberg]

I just had a look to Roland Chastain's Moustique sources based on JS Schach by Jürgen Schlottke from the early 90s, written in Turbo Pascal.
I found the maxwertung aka bestEval search routine interesting, direct recursion without negamax, suboptimal approximation of alpha-beta.

https://github.com/rchastain/moustique/ ... h.txt#L551

https://github.com/rchastain/moustique/ ... e.pas#L390
https://github.com/rchastain/moustique/ ... r.pas#L226

Here some C like pseudocode of that routine:

Code: Select all

int bestEval (int alpha, int depth, bool maxplayer) {
  int score, beta = maxplayer ? -32000 : +32000;
  // generate moves ..
  while (getMove() )  {
    // copy-make
    if (depth > = depth2calculate)
      score = eval(...); 
    else
      score = bestEval(beta, depth+1, !maxplayer);
    if (maxplayer)  {
      if (score > beta) beta = score;
      if (beta > alpha) break;
    } else { // minplayer
      if (score < beta) beta = score;
      if (beta < alpha) break;
    }
  }
  return beta;
}

initially called with:

Code: Select all

bestEval (32000, 1, true);

Eval is called inside the move loop - there seems to be no q-search. For the maxplayer, the alpha-beta semantic is reversed.
What are the primary deficits of this approach?

[Ras]

What are the primary deficits of this approach?

Without QS, I think the horizon effect will be much more prominent - unless QS is hidden in eval().

[Gerd Isenberg]

What are the primary deficits of this approach?

Without QS, I think the horizon effect will be much more prominent - unless QS is hidden in eval().

Sure, It seems I missed an extra condition that the move was not a capture in the pseudo code to decide about eval (material only) or recursive search call.

Code: Select all

int bestEval (int alpha, int depth, bool maxplayer)
{
  int score, beta = maxplayer ? -32000 : +32000;
  // generate moves ..
  while (move = getMove() )  {
    // copy-make
    if ( (depth >= depth2calculate && !move.isTactical() ) || (depth >= maxDepth) )
      score = eval(...); 
    else
      score = bestEval(beta, depth+1, !maxplayer);
    if (maxplayer)  {
      if (score > beta) beta = score;
      if (beta > alpha) break;
    } else { // minplayer
      if (score < beta) beta = score;
      if (beta < alpha) break;
    }
  }
  return beta;
}

So I mean deficits of the approach with passing one bound only and the cut-off condition.

[hgm]

Some programs (such as the Jocly generic AI for chess variants) do indeed use SEE on the last-moved piece as eval term. This cures the worst horizon effects, as it thwarts the strategy of manoeuvring such (often by sacrificing minor material to force the opponent to use his ply for recapture, lest the sacrifice would turn into a gain) that you can capture a fat piece on the last move before the horizon through a bad capture.

It is actually a pretty good way to handle variants where a capture search tends to explode, such as Tenjiku Shogi. In the latter quiet manoeuvring with a Fire Demon (a weapon of mass destruction) often gains much more than capturing individual pieces, so it makes sense to keep QS as light as possible there, so that the full-width search can be deeper.

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.

[Gerd Isenberg]

Some programs (such as the Jocly generic AI for chess variants) do indeed use SEE on the last-moved piece as eval term. This cures the worst horizon effects, as it thwarts the strategy of manoeuvring such (often by sacrificing minor material to force the opponent to use his ply for recapture, lest the sacrifice would turn into a gain) that you can capture a fat piece on the last move before the horizon through a bad capture.

Yes, that is not the case here, it calls pure material eval inside the move loop only if the made move was not a capture (if I understand the Pascal code correctly).
https://github.com/rchastain/moustique/ ... e.pas#L409

My focus was on the alpha-beta like routine.

[Roland Chastain]

I found the maxwertung aka bestEval search routine interesting, direct recursion without negamax, suboptimal approximation of alpha-beta.

Hello! Thank you for the discussion and for your careful reading of Jürgen Schlottke's code. I liked this program, because it plays very fast and gives the impression of playing quite well, with a funny style (IMHO). Sorry, I have nothing more interesting to say.

[Ras]

So I mean deficits of the approach with passing one bound only and the cut-off condition.

I find the labels pretty confusing because alpha and beta seem to have reversed functionality. In conventional terminology, alpha is always initialised to the worst case value in every node, not to the -beta from the parent node. In all paths except the leftmost one, I think this leads to a larger search tree.

[Gerd Isenberg]

So I mean deficits of the approach with passing one bound only and the cut-off condition.

I find the labels pretty confusing because alpha and beta seem to have reversed functionality. In conventional terminology, alpha is always initialised to the worst case value in every node, not to the -beta from the parent node. In all paths except the leftmost one, I think this leads to a larger search tree.

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

[Roland Chastain]

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.

[Gerd Isenberg]

I found the maxwertung aka bestEval search routine interesting, direct recursion without negamax, suboptimal approximation of alpha-beta.

Hello! Thank you for the discussion and for your careful reading of Jürgen Schlottke's code. I liked this program, because it plays very fast and gives the impression of playing quite well, with a funny style (IMHO). Sorry, I have nothing more interesting to say.

Hi Roland,
thanks for hosting and retouching those interesting sources. 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.

https://github.com/rchastain/moustique/ ... h.txt#L797

Code: Select all

if (id=252) or (id=248) then
begin
  rechentiefe:=3;      {Rechentiefe des Computers in Halbzügen}
  Maxtiefe:=5;         {Maximale Rechentiefe bei Schlagzügen}
end;