Author: Tom Kerrigan
Date: 19:00:48 08/06/00
Go up one level in this thread
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.
>
>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.
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.
-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.