Author: Bruce Moreland
Date: 14:31:56 08/07/00
Go up one level in this thread
On August 06, 2000 at 22:00:48, Tom Kerrigan wrote:
>On August 05, 2000 at 10:02:35, Larry Griffiths wrote:
>
>>On August 04, 2000 at 06:18:26, Bruce Moreland wrote:
>>
>>>On August 02, 2000 at 22:29:07, Larry Griffiths wrote:
>>>
>>>>I am looking for a simple code sample of alpha-beta (with negamax maybe).
>>>>Would someone post an example here, or direct me to a good URL?
>>>>
>>>>Larry.
>>>
>>>Alpha-Beta:
>>>
>>>int ab(int alpha, int beta, int depth)
>>>{
>>> if (depth == 0)
>>> return eval();
>>> while (moves()) {
>>> int val;
>>>
>>> make_move();
>>> val = -ab(-beta, -alpha, depth - 1);
>>> unmake_move();
>>> if (val >= beta)
>>> return beta;
>>> if (val > alpha)
>>> alpha = val;
>>> }
>>> return alpha;
>>>}
>>>
>>>The above doesn't handle checkmate and stalemate. Negamax or PVS or whatever is
>>>cool but it's more complex and it's only a 10% speed enhancement, so if you
>>>haven't got alpha-beta right yet, get that right first.
>>>
>>>Alpha-beta is very similar to min-max. If you want to do min-max, just take out
>>>the "if (val >= beta)" line and the line following it.
>>>
>>>bruce
>>
>>The example above is indeed the one that I had implemented but
>>I used it several times in my program.
>>
>>> if (depth == 0)
>>> return eval();
>>> while (moves()) {
>>> int val;
>>
>>> // GENERATE CAPTURE MOVES...
>>
>>> make_move();
>>> val = -ab(-beta, -alpha, depth - 1);
>>> unmake_move();
>>> if (val >= beta)
>>> return beta;
>>> if (val > alpha)
>>> alpha = val;
>>
>>> // GENERATE NON-CAPTURE MOVES...
>>
>>> make_move();
>>> val = -ab(-beta, -alpha, depth - 1);
>>> unmake_move();
>>> if (val >= beta)
>>> return beta;
>>> if (val > alpha)
>>> alpha = val;
>>> }
>>> return alpha;
>>>}
>>
>>I found that it was hitting the return alpha statements and returning -infinity
>>which I assume is due to checkmate or stalemate, but I have not verified that
>>yet.
No, it's called a fail low. This will happen a high percentage of the time.
Think about it. The most common way you can get this "return beta" statement to
execute is if you just returned alpha.
Sorry I didn't answer directly, I wasn't around.
You probably still have bugs though. It's hard to debug this kind of code.
>>Would you use this Bruce, or would you suggest a different algorithm?
>
>Repetition of code is generally bad. You can use a counter to tell you what
>stage of move generation you're in.
It depends upon how out of control it gets, and the degree to which you are
willing to let readability suffer in order to optimize for performance.
Sometimes a little repetition causes less trouble than a trickier solution.
People who come along later to look at code are very easily faked out.
>Your best option, though, is probably to just generate all the moves at once and
>then search 'em. You can worry about multi-stage move generation later. It
>doesn't give you a very big performance increase. My program generates all the
>moves at once and it searches ~700k NPS on an 800MHz PIII.
I think this is also probably true.
bruce
>
>-Tom
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.