Author: Uri Blass
Date: 08:56:38 03/14/04
Go up one level in this thread
On March 14, 2004 at 04:09:58, Uri Blass wrote:
>On March 14, 2004 at 04:03:44, Uri Blass wrote:
>
>>On March 14, 2004 at 03:15:18, Uri Blass wrote:
>>
>>>On March 13, 2004 at 23:28:56, Dan Honeycutt wrote:
>>>
>>>>On March 13, 2004 at 20:43:01, Uri Blass wrote:
>>>>
>>>>>On March 13, 2004 at 20:29:34, Dan Honeycutt wrote:
>>>>>
>>>>>>On March 13, 2004 at 17:47:06, Uri Blass wrote:
>>>>>>
>>>>>>>On March 13, 2004 at 17:40:06, Russell Reagan wrote:
>>>>>>>
>>>>>>>>On March 13, 2004 at 17:32:49, Uri Blass wrote:
>>>>>>>>
>>>>>>>>>I think that you do not understand my idea
>>>>>>>>>
>>>>>>>>>I suggest to do exactly the same things in the same order but to check for
>>>>>>>>>repetition or hash cut off before calling search and not after calling search.
>>>>>>>>
>>>>>>>>Is this what you are wanting to do? Let's say the search normally looks like
>>>>>>>>this:
>>>>>>>>
>>>>>>>>int AlphaBeta(int depth, int alpha, int beta)
>>>>>>>>{
>>>>>>>> if (depth == 0)
>>>>>>>> return Evaluate();
>>>>>>>>
>>>>>>>> TryRepetition(); // <--------
>>>>>>>> TryHashTable(); // <--------
>>>>>>>> TryNullMove(); // <--------
>>>>>>>>
>>>>>>>> GenerateLegalMoves();
>>>>>>>> while (MovesLeft()) {
>>>>>>>> MakeNextMove();
>>>>>>>> val = -AlphaBeta(depth - 1, -beta, -alpha);
>>>>>>>> UnmakeMove();
>>>>>>>> if (val >= beta)
>>>>>>>> return beta;
>>>>>>>> if (val > alpha)
>>>>>>>> alpha = val;
>>>>>>>> }
>>>>>>>> return alpha;
>>>>>>>>}
>>>>>>>>
>>>>>>>>You are wanting to do this?
>>>>>>>>
>>>>>>>>int AlphaBeta(int depth, int alpha, int beta)
>>>>>>>>{
>>>>>>>> if (depth == 0)
>>>>>>>> return Evaluate();
>>>>>>>>
>>>>>>>> GenerateLegalMoves();
>>>>>>>> while (MovesLeft()) {
>>>>>>>> MakeNextMove();
>>>>>>>>
>>>>>>>> TryRepetition(); // <--------
>>>>>>>> TryHashTable(); // <--------
>>>>>>>> TryNullMove(); // <--------
>>>>>>>>
>>>>>>>> val = -AlphaBeta(depth - 1, -beta, -alpha);
>>>>>>>> UnmakeMove();
>>>>>>>> if (val >= beta)
>>>>>>>> return beta;
>>>>>>>> if (val > alpha)
>>>>>>>> alpha = val;
>>>>>>>> }
>>>>>>>> return alpha;
>>>>>>>>}
>>>>>>>>
>>>>>>>>Basically to avoid the extra function call?
>>>>>>>
>>>>>>>Yes
>>>>>>>Except that I thought to trynullmove in the beginning of the search.
>>>>>>>
>>>>>>>It may be better to try null move also not in the beginning of the search
>>>>>>>because it is possible that null move does not have search call and only call
>>>>>>>qsearch.
>>>>>>>
>>>>>>>Uri
>>>>>>
>>>>>>I don't think you want TryNullMove() where shown in the second example. After
>>>>>>MakeNextMove() you have a new position which could be a repetition or be in the
>>>>>>hash table. but TryNullMove() should come before GenerateLegalMoves().
>>>>>>
>>>>>>Dan H.
>>>>>
>>>>>I do not understand.
>>>>>The order is the same order in both examples.
>>>>
>>>>In the first example TryNullMove() comes before GenerateLegalMoves(). In the
>>>>second example TryNullMove() comes after GenerateLegalMoves().
>>>
>>>I look again in the examples I will fix them and try to explain why they should
>>>be the same in the next post.
>>>I also need to add pseudo code for iterate function to be clear.
>>>
>>>I think that the place of evaluate is wrong in the example that was given
>>>because I do not want to return evaluate before checking for repetition.
>>>checking for repetition is cheap and should be done first.
>>>
>>>Uri
>>
>>
>>
>>First example:
>>
>>int AlphaBeta(int depth, int alpha, int beta)
>>{
>> TryRepetition(); // <--------
>> TryHashTable(); // <--------
>> TryNullMove(); // <--------
>> if (depth == 0)
>> return Evaluate();
>> GenerateLegalMoves();
>> while (MovesLeft()) {
>> MakeNextMove();
>> Newdepth=depth+extensions();
>> val = -AlphaBeta(Newdepth - PLY, -beta, -alpha);
>> UnmakeMove();
>> if (val >= beta)
>> return beta;
>> if (val > alpha)
>> alpha = val;
>> }
>> return alpha;
>>}
>>
>>I suggest to replace it with the following code
>>
>>int AlphaBeta(int depth, int alpha, int beta)
>>{
>> if (depth == 0)
>> return Evaluate();
>> GenerateLegalMoves();
>> while (MovesLeft()) {
>> MakeNextMove();
>> Newdepth=depth+extensions();
>> TryRepetition(); // <--------
>> TryHashTable(); // <--------
>> TryNullMove(); // <--------
>> val = -AlphaBeta(Newdepth - PLY, -beta, -alpha);
>> UnmakeMove();
>> if (val >= beta)
>> return beta;
>> if (val > alpha)
>> alpha = val;
>> }
>> return alpha;
>>}
>>
>>
>>Let see what happens after make move that leads to alphabeta.
>>
>>After MakeNextMove(); I do in both cases:
>>
>>1)Newdepth=depth+extensions();
>>2)TryRepetition();
>>3)TryHashTable();
>>4)TryNullMove();
>>5)if (depth == 0)
>> return Evaluate();
>>
>>
>>Usually calls for alphabeta happen after MakeNextMove();
>>In cases that it does not happen then in the second case I need to care to do
>>the relevant steps in another function but these cases are rare so I do not care
>>about them.
>>
>>I need also to change my iterate function to take care about it.
>>Crafty also does it and has searchroot function that I will look at it.
>>
>>Uri
>
>Note only that I need if (depth<=0) return qsearch(alpha,beta,depth); and not
>if (depth==0) return evaluate() and
>I forgot to change it in the original code
>
>I only talked about things that are general for many good programs(having
>partial extensions so they do not reduce the depth by 1 and having extensions
>and qsearch)
>
>Practically my alphabeta and qsearch get more parameters.
>
>Uri
note also that if (depth==0) return qsearch can be also before the recursive
call.
code should be like this
int search(int depth,int alpha,int beta,int verify)
{
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
Newdepth=depth+extensions();
TryRepetition();
TryHashTable();
TryNullMove();
if (depth <= 0)
return -Evaluate();//practically it is calling qsearch
val = -Search(Newdepth - PLY, -beta, -alpha);
UnmakeMove();
if (val >= beta)
return beta;
if (val > alpha)
alpha = val;
}
return alpha;
}
Uri
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.