OpenChess

Posted: **Mon Dec 07, 2015 1:58 pm**

After studying basics chess engines (mainly TSCP and VICE) I'm trying to write my own chess engine for pure fun.

My doubt today (actually not just one

) is about Alphabeta.

From Bruce Moreland's archives (and almost everywhere in the net) I've found the following code:

int AlphaBeta(int depth, int alpha, int beta)
{
    if (depth == 0)
        return Evaluate();
    GenerateLegalMoves();
    while (MovesLeft()) {
        MakeNextMove();
        val = -AlphaBeta(depth - 1, -beta, -alpha);
        UnmakeMove();
        if (val >= beta)
            return beta;
        if (val > alpha)
            alpha = val;
    }
    return alpha;
}

Now, looking at TSCP and VICE I found a slightly variation:

Code: Select all

int AlphaBeta(int depth, int alpha, int beta)
{
    if (depth == 0)
        return Evaluate();
    GenerateLegalMoves();
    while (MovesLeft()) {
        MakeNextMove();
        val = -AlphaBeta(depth - 1, -beta, -alpha);
        UnmakeMove();
        if (val > alpha) {
            if (val >= beta)
                return beta;
            alpha = val;
        }
    }
    return alpha;
}

So my question now should be pretty simple. Are they different in term of results? Are both good? Or I'm I supposed to use the second one?
If alpha < beta they does the same thing, otherwise the result should be different.

I'm sorry if my question has been asked somewhere and even if it looks pretty stupid, but I'm just trying to understand and I haven't found an answer elsewhere. And the desidere to learn isn't a fault yet

.

Thanks in advance,

Luca

Posted: **Mon Dec 07, 2015 7:43 pm**

They are the same...

if (val >= beta)
return beta;
if (val > alpha)
alpha = val;

Can be rewritten as

if (val > alpha) {
if (val >= beta)
return beta
alpha = val;
}

The latter is more efficient. The first block of code executes both if's, even if val is <= alpha (which is normal at an ALL node) The second block only executes one if at an ALL node. Otherwise they are functionally equivalent. If you don't follow, try alpha=10, beta= 20, and then go through it with val = 5, 15 and 25...

Posted: **Wed Dec 09, 2015 2:08 pm**

The point is that beta is always strictly larger than alpha. So val van only be larger than beta if it is also larger than alpha. So there is no need to make the >= beta test if val is not > alpha.

Posted: **Wed Dec 09, 2015 4:07 pm**

H.G.Muller wrote:The point is that beta is always strictly larger than alpha. So val van only be larger than beta if it is also larger than alpha. So there is no need to make the >= beta test if val is not > alpha.

Thank you both.

I'm trying different algoritms in a more simplistic zero-sum game and I can finally see a light at the end of the tunnel.
As Muller pointed out alpha < beta for every node. The fact was not so obvious to me and that was the reason of my question.

Thanks again for your time.

Luca

Posted: **Wed Dec 09, 2015 4:47 pm**

Maybe you mean you "see the light through the trees?"

Posted: **Wed Dec 09, 2015 5:02 pm**

hyatt wrote:Maybe you mean you "see the light through the trees?"

yeah, it fits perfectly!

OpenChess

Stuck on Alphabeta

Stuck on Alphabeta

Re: Stuck on Alphabeta

Re: Stuck on Alphabeta

Re: Stuck on Alphabeta

Re: Stuck on Alphabeta

Re: Stuck on Alphabeta