Author: Uri Blass
Date: 03:33:06 04/03/04
Go up one level in this thread
On April 03, 2004 at 06:05:08, Vasik Rajlich wrote:
>On April 02, 2004 at 09:56:26, Uri Blass wrote:
>
>>On April 02, 2004 at 04:31:58, Vasik Rajlich wrote:
>>
>>>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.
>>
>>If too many things are different then you can still have general search code
>>that says
>># if defined(MTD)
>> searchMTD(...)
>># endif
>># else
>> search(...)
>># endif
>>>
>>>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?
>>
>>The idea is that the general code is about search and not about chess.
>>The problem should be of course to fill the relevant functions.
>>
>>The same code can be used as selective search and as brute force dependent on
>>the content of the functions that I do not give.
>>
>>I have function that tell the program if there is no chance to fail high(the
>>function can always return that there is a chance to fail high and in that case
>>the search is not selective but it also can tell often that there is no chance
>>to fail high and in that case the search is selective).
>>
>>The question if it is fast or intelligent is also dependent on the content of
>>the rest of the code.
>>
>>
>>>
>>>It makes sense to experiment a bit when you are starting, but I think you're
>>>past that point.
>>
>>I think that I am only a beginner in chess programming and there are a lot of
>>ideas that I did not try.
>>
>>I need some general clear code that will help me and other programs in
>>experimenting.
>>
>>Uri
>
>Well, if the goal is a research tool for beginners, maybe it could be useful.
>
>However, a real-world chess engine needs a clear path. It's like a car, you
>don't take the axel from an economy car, add the muffler from the formula 1,
>steering wheel from the limousine, etc. You decide what you want from you car,
>and then do your research within that domain.
>
>I suppose chess engine development goes through several phases.
>
>Phase 1: Initial development, learning the documented techniques, basic
>debugging. 3-6 months, should yield an engine somewhere around 2200-2400 on
>modern hardware.
>Phase 2: Wild, purposeless testing. Addresses the tough problems - real
>evaluation, true selective search & qsearch, move ordering, etc. At this point
>the author still has no clue what is going on, so this is a dose of reality.
>Should last about 3 months. Engine improves in this time mainly from debugging
>and eval, not from any real breakthroughs.
>Phase 3: Focused improvement. The author has the big picture, has made some
>global design decisions, and improves within this framework. Results are very
>engine-specific.
>
>Maybe you can make a tool which is useful for phase 2.
>
>Vas
I do not see engine developement as 3 step process.
I believe that a lot of programmers never tried some ideas like evaluating
probabilities in the evaluation(at least I did not do it).
I also did not try MTD and a lot of possible search ideas like NP and NP2(I read
that they exist but I did not learn exactly what they do).
The tool that I want to make should help people to try new ideas.
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.