Stuck on Alphabeta

Code, algorithms, languages, construction...
Post Reply
kuket15
Posts: 7
Joined: Mon Dec 07, 2015 1:17 pm

Stuck on Alphabeta

Post by kuket15 » 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. :cry:
My doubt today (actually not just one :roll: ) is about Alphabeta.

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

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 >= 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 :mrgreen: .

Thanks in advance,

Luca

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Stuck on Alphabeta

Post by hyatt » 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...

H.G.Muller
Posts: 190
Joined: Sun Jul 14, 2013 10:00 am
Real Name: H.G. Muller

Re: Stuck on Alphabeta

Post by H.G.Muller » 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.

kuket15
Posts: 7
Joined: Mon Dec 07, 2015 1:17 pm

Re: Stuck on Alphabeta

Post by kuket15 » 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. :mrgreen:
Thanks again for your time.

Luca

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Stuck on Alphabeta

Post by hyatt » Wed Dec 09, 2015 4:47 pm

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

kuket15
Posts: 7
Joined: Mon Dec 07, 2015 1:17 pm

Re: Stuck on Alphabeta

Post by kuket15 » Wed Dec 09, 2015 5:02 pm

hyatt wrote:Maybe you mean you "see the light through the trees?" :)
yeah, it fits perfectly! :D

Post Reply