Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: sharing thoughts about general search code

Author: Vasik Rajlich

Date: 01:31:58 04/02/04

Go up one level in this thread


On April 01, 2004 at 21:33:00, Uri Blass wrote:

>I decided that there is probably no hope that movei will become commercial with
>all the competition of smart people like Tord(and in any case sharing ideas is
>not going to reduce the chances that it is going to happen) so I decided to
>share my thoughts about searching that I still do not use in movei.
>
>I want to have some general search code(not only for chess) when it will be
>possible to implement failsoft,failhard,mtd and many search ideas by the right
>defines.
>
>I still do not have defines for different possibilities but I decided to post
>the following heavy commented code that is based on ideas that I thought about
>search but I do not use most of the ideas that are in this code for movei.
>
>I hope that other people will help me to make this code more general to allow
>also ideas like mtd if the right things are defines and to change things to have
>fail hard and fail soft and to add general code for the iterate function and the
>hash functions.
>
>The idea is that there is going to be some general search code not only for
>chess that every programmer will be able to use as a basis.
>
>part of the procedures or the functions may be empty in the first versions or
>return a constant(for example in case that the program does not use iid it may
>have return infinite in the function that calculate if to use iid.
>
>int Search(int depth,int alpha,int beta,int verify)
>{
>   int last,Newdepth,val;
>   int first_alpha=alpha;
>   int iidfirst=first_move[ply];
>   int valmax=alpha;
>   /*there is a move stack similiar to a lot of programs
>     we always have first_move[0]=0 and first_move[i] ro be sum of perft 1 in
>the positions in the line that leaded
>     to the position.*/
>
>   int i=first_move[ply];
>   int reduction;
>   /*the function gen generates legal moves*/
>    gen();
>
>
>	last=first_move[ply+1];
>	/*last-i is the number of moves of the side to move
>
>	hash did not help to prune and the same for null move so now you need to do
>internal iterative deepening
>	to find first move to search in the right conditions*/
>	reduction=iid_reduction(depth,alpha);
>	if (depth>reduction)
>	{
>		/*it is important to start with the right move
>		do search to reduced depth to find a move and stop when a move generate
>cutoff*/
>		while (i<last)
>		{
>			makemove(gen_dat[i].m);
>			val=-Search(depth-reduction,-beta,-valmax,verify);
>			undomove();
>			if (val>valmax)
>			{
>				valmax=val;
>				iidfirst=i;
>			}
>			if (val>beta)
>				break;
>
>		}
>		replace_move_data(i,valmax);
>		i=first_move[ply];
>	}
>
>    while (i<last)
>	{
>		/*probability_to_fail_high_too_small also consider the previous moves
>		if for example good captures were already searched then I may decide based on
>evaluation and depth that
>		probability to fail high is too small and return alpha but in previous move I
>did not know it because
>		I still hoped that the score will be above alpha
>		both good_chance_to_fail_high and probability_to_fail_high_too_small may use a
>function that evaluate probability
>		but I do not suggest to call a function that evaluate probability because it
>may be cheaper to do some lazy evaluation
>		and not to evaluate exact probability in order to know if the probability is
>too small and only if the lazy evaluation
>		fails to calculate exact probability*/
>		if (probability_to_fail_high_too_small(depth,alpha))
>			return alpha;
>		/*the function sortmove find the next move to search and put it in place i in
>the global move stack
>		it is logical to spend more time if the depth is bigger
>		so the function gets not only the number of move in the move stack but also
>the depth*/
>
>		sortmove(i,depth);
>		/*it is possible that I cannot decide for all moves that there is no chance
>that they will fail high
>		but I may decide for the next move that it is not going to fail high
>		I expect the function to say yes very fast in most cases and the only cases
>when I expect no chance for
>		the move to fail high is when the move is quiet move and the evaluation enough
>below alpha*/
>		if (chance_fail_high_this_move(depth,alpha,i))
>		{
>			makemove(gen_dat[i].m);
>			/*first we check for draw by repetition or by endgame*/
>			if (TryDraw())
>				return 0;
>			/*now we calculate the extensions so we can use later the hash tables to
>decide if to prune the move*/
>			Newdepth=depth+extensions();
>			if (TryHashTables(Newdepth)>=beta)
>				return beta;
>			/*I will also try ETC here in case that the depth is big enough by generating
>all moves and
>			I need to write code for it*/
>			if (nullconditions(depth))
>			{
>				reduction=calculate_null_reduction();
>				donullmove();
>				gen();
>				/*starting_q_search_depth is simply a parameter that I give qsearch in the
>beginning and I need it because
>				I search different in different plies of the qsearch*/
>				if (reduction<Newdepth)
>					val=-Search(Newdepth-reduction,-beta,-beta+1,verify);
>				else
>					val=-Quies(-beta,-beta+1,starting_q_search_depth);
>				undonullmove();
>				if (val>=beta)
>				{
>					if (verify==1)
>					{
>						depth--;
>						verify=0;
>					}
>					else
>						return val;
>				}
>			}
>			if (depth <= 0)
>			{
>				gen();
>				return -Quies(-beta,-alpha,starting_q_search_depth);
>			}
>			else
>			{
>				if (depth>small_depth)
>				{
>					/*evalprobability search every legal move to depth-small_depth in order to
>give exact evaluation
>					that is going to be used for evaluating probabilities for every move to be
>best
>					when the probabilities are going to be used to decide later about
>reductions or extensions
>					and singular extension may be a private case
>					I also think about having updateprobability function that update
>probabilities for all moves
>					when I call it only when the remaining depth is big enough.
>
>					I think also to store in the hash tables relatively small tree with
>probabilities when I update
>					the probabilities in all the nodes of that tree every time that I get new
>information like changing
>					the root score or fail high or fail low when the depth is big enough.*/
>
>					evalprobability(depth);
>				}
>				/*in cases of reduction I want to investigate later only in case of
>unexpected fail high
>				Reduction_Condition happens when the probability was not small enough to
>prune but still small*/
>				if (Reduction_Conditions())
>				{
>					val=-Search(Newdepth-PLY-Ply_Reduction(),-beta,-alpha,verify);
>					if (val>alpha)
>						val=-Search(Newdepth - PLY, -beta, -alpha,verify);
>
>				}
>				else
>				val = -Search(Newdepth - PLY, -beta, -alpha,verify);
>			}
>			undomove();
>			if (val >= beta)
>				return beta;
>			if (val > alpha)
>				alpha = val;
>		}
>		i++;
>
>    }
>    return alpha;
>
>
>}

Hi Uri,

One general comment: I've also had the idea to do both MTD (f) and PVS. Now I
realize that this is not feasible. Too many things are different.

The same holds true for a number of issues. Are you going to be essentially
selective, or essentially brute force? Are you going to be fast, or intelligent?

It makes sense to experiment a bit when you are starting, but I think you're
past that point.

Good luck.

Vas



This page took 0.01 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.