JS Schach's alpha-beta approximation

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

[dangi12012]

Hmm I can add here in this thread that when C++ templates are usable the whole quiesce search can come down to template specialisations and color and depth integer calculations go away.

Its because no cycle is wasted in "Am I at my max depth yet"? For all recursions below depth N. So that is really a high number of unnecessary stop recursion tests. You can see in the code that most tests go away in the code!
Also you have a specialisation template where you can decide if to do quiesce search to the maxdepth AND dont have any cpu instruction to test for "!Tactiacal Move below max depth"

I get 800M evals/s which is still way too slow IMO. Parallel versions of Alphabeta are needed (but the algorithm itself forces serialisation) so its a very hard problem to solve.

TLDR: 200% faster alphabeta

Code: Select all

#pragma once

#include <immintrin.h>
#include <stdint.h>
#include <bit>
#include <string>
#include <iostream>
#include <array>
#include <stdio.h>      
#include <stdlib.h>    
#include <algorithm>

namespace Quiesc {

    constexpr int calc_depth = 7;
    constexpr int max_depth = 12;

    int g_seed;
    inline int eval() {
        g_seed = (214013 * g_seed + 2531011);
        return (g_seed >> 16) & 0x7FFF;
    }

    //Quiet move search extension here
    inline bool StopExpand(int depth) {
        //return depth >= calc_depth && !move.isTactical()) || (depth >= maxDepth)
        return depth >= calc_depth;
    }

    int bestEval(int alpha, int depth, bool maxplayer) {
        int score, beta = maxplayer ? -32000 : +32000;

        int movelist = 22;
        //while (getMove()) {
        while (movelist--) {

            if (StopExpand(depth))
                score = eval();
            else
                score = bestEval(beta, depth + 1, !maxplayer);
            if (maxplayer) {
                if (score > beta) beta = score;
                if (beta >= alpha && depth > 2) break;
            }
            else { // minplayer
                if (score < beta) beta = score;
                if (beta <= alpha && depth > 2) break;
            }
        }
        return beta;
    }

    template<int depth, bool maxplayer>
    int bestEval(int alpha) {
        int score, beta = maxplayer ? -32000 : +32000;

        int movelist = 22;
        //while (getMove()) {
        while (movelist--) {
            score = bestEval<depth + 1, !maxplayer>(beta);
            if constexpr (maxplayer) {
                if (score > beta) beta = score;
                if (beta >= alpha && depth > 2) break;
            }
            else { // minplayer
                if (score < beta) beta = score;
                if (beta <= alpha && depth > 2) break;
            }
        }
        return beta;
    }

    template<>
    inline int bestEval<calc_depth, true>(int alpha) {
        int beta = -32000;

        int movelist = 22;
        while (movelist--) {
            
            if ((beta = std::max(eval(), beta)) >= alpha) break;
        }
        return beta;
    }

    template<>
    inline int bestEval<calc_depth, false>(int alpha) {
        int beta = +32000;

        int movelist = 22;
        while (movelist--) {

            if ((beta = std::min(eval(), beta)) <= alpha) break;
        }
        return beta;
    }


    double Quiesc() {
        g_seed = 2168210766;
        auto t0 = std::chrono::high_resolution_clock::now();
        if (bestEval(32000, 1, true) != 29501) std::cout << "Programming Error";
        auto t1 = std::chrono::high_resolution_clock::now();
        return 1000.0 * 94136204.0 / std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count();
    }
    double Quiesc_Template() {
        g_seed = 2168210766;
        
        auto t0 = std::chrono::high_resolution_clock::now();
        if (bestEval<1, true>(32000) != 29501) std::cout << "Programming Error";
        auto t1 = std::chrono::high_resolution_clock::now();
        return 1000.0 * 94136204.0 / std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count();
    }

    void QuiescensePerf() {
        std::cout << "Quiesc: " << Quiesc() << "M Eval/s\n";
        std::cout << "Quiesc_Template: " << Quiesc_Template() << "M Eval/s\n";
    }
}

Additional Idea:
Instead of doing beta = eval(); if )beta <= alpha) break; One could have a eval() that evaluates four boards at once (with AVX2 if possible) and since the moves should be ordered anyways the likelyhood of having a break in the first 4 evals is high. AVX2 can do 4 comparisons in one clock cycle and the moveptr can be decremented by 4 at once (and not --, --, --, --)