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.