about planned changes in Movei

[Uri Blass]

Possible improvement in Movei that I hope to make are:

1)Having mobility evaluation that is not dependent on the number of moves of the opponent in previous move(already done but it is slightly slower unless I do more changes)
2)not having evaluation as part of make move or part of the move generator(already done but some information like the value of the maximal capture is still calculated in the move generator and it means that now some pruning tests can be done only after generating moves).

3)Having functions to generate captures and to generate captures and checks(still not done and movei does qsearch by generating all moves and searching for captures and checks later)

4)changing the structure of the program so Movei delay generating moves when it does not need it(something of it was done but most of it was not done).

5)seperating the expensive part of the evaluation that is static and the cheap part of the evaluation that is dependent on the path(still not done)
The idea of step 5 is to continue to step 6

6)Storing the result of the expensive static part in the hash so next time that Movei get the same position it can skip calculating it(still not done)

Note that all these changes except change 1 are basically speed improvement and maybe they are not important because they are not supposed to change the number of nodes for a given depth but inspite of it I dislike the fact that Movei is slower in nps after the new mobility evaluation(311 calculates near 480,000 nodes per second in the opening position when 313 calculates only near 380,000 nodes per second on the same A3000).


Uri

[Dann Corbit]

Scorpio has an evaluation hash.

I think it is a good idea for a complicated evaluation

[Volker Böhm]

Hi Uri,

I suggest to use lazy-eval. It is easy to implement, has little drawback and improves speed.

Example for an Eval:

int LazyEval(int alpha, int beta)
{
int res = Fast_Big_Numbers();
if (res < alpha - LargeMargin) return res + LargeMargin;
if (res > beta + LargeMargin)) return res - LargeMargin;

res += Medium_Numbers();
if (res < alpha - SmallMargin) return res + SmallMargin;
if (res > beta + SmallMargin)) return res - SmallMargin;
res += Small_Numbers();
return res;
}

The margin can easily be tested by counting "wrong-lazy-decisions" and "good-lazy-decisions". In Spike the wrong/good ration is very small.

Drawback:
1. Interaction with q-search foreward-pruning: some more nodes
2. The magins have to be recalculated when eval changes much
3. Eval-cache only for eval that didn?t had lazy-pruning

Greetings Volker

[Uri Blass]

Movei is not a program like other programs.
Movei evaluates every node in the tree.

Movei's evaluation is not function that return some integer but function that store information in global arrays and return no value.

The evaluation is one of the things that are stored.

The information later can be used for pruning.


Today movei's evaluation does not calculate 2 important arrays that are used for pruning and I am not sure if I should have a special function to calculate them or not to change the fact that I calculate them inside the move generator

The relevant global arrays are:
1)maxcapture[100] that simply tell me the value of the maximal possible capture or promotion of the side to move at some ply.

2)maxgoodcapture[100] that gives a fast estimate for the value of the maximal good capture(it is always smaller or equal to maxcapture)

Here is an example how today I use it inside part of the qsearch(note that maxgoodcapture[ply]>5 means practically that I expect to earn 500 centipawns from the capture so the expected evaluation after the capture is at least beta+400 and val is the evaluation of the position)

The idea is to save making moves and evaluation when I am almost sure that there is a decisive capture and alternatively to save making moves when it seems that no capture can increase the score above alpha.

the magic numbers(100,5,230 may not be a good way of programming but it is in Movei)


gen();
if (val>=beta-100)
if (maxgoodcapture[ply]>5)
return beta;
if (val+maxcapture[ply]*100<alpha-230)
return alpha;

I need to replace gen() by gencap() that I still did not write to do movei faster but I still did not decide when to calculate maxcapture and maxgoodcapture.

I can make a special function to calculate it or to do it part of the evaluation or to do it part of gencap();

I guess that I will have it as a seperate function but I am not sure if it is the best idea.

Uri

[Daniel Shawul]

Interaction with q-search foreward-pruning: some more nodes

you mean qsearch futility pruning? Deciding to prune a move before making it only saves cost of make move. That is if i do make the move
and go to next ply lazy eval will save me doing the whole eval and standing pat will immediately cut off. Since my makemove is very fast as compared to my eval, i don't do futiliy.

I need to replace gen() by gencap() that I still did not write to do movei faster but I still did not decide when to calculate maxcapture and maxgoodcapture.

I can make a special function to calculate it or to do it part of the evaluation or to do it part of gencap();

Uri, i assume your makemove is large as compared to your eval.
Otherwise the conventional lazy eval does exaclty what you are doing.

Daniel

[Uri Blass]

I think that my evaluation is more expensive than my makemove today, but my makemove is not very cheap.

What I do for pruning decision is not lazy evaluation of the position but lazy optimistic and lazy passimistic evaluation of the change after the best capture.

Today calculating the lazy optimistic and passimistic evaluation is part of the move generator.

The question is if to throw it out of the move generator.

If I throw it out of the move generator I have too options:

1)making it part of the evaluation.
2)making it a seperate function.

I guess that throwing it out of the move generator by option 2 is better.

Uri

[Daniel Shawul]

quote]I think that my evaluation is more expensive than my makemove today, but my makemove is not very cheap.

What I do for pruning decision is not lazy evaluation of the position but lazy optimistic and lazy passimistic evaluation of the change after the best capture. [/quote]

i now remeber that you generate your attack tables incrementally.
i don't(done in eval), so no need to decide if i should prune a move before i make it.

May be pruning the postion even before i generate moves that is right after evaluation by doing
score + big margin < alpha
might save some time.

If I throw it out of the move generator I have too options:

1)making it part of the evaluation.
2)making it a seperate function.

I guess that throwing it out of the move generator by option 2 is better.

option 1 is not good as your makemove is large.
option 2 might be better but i do not think it brings significant gain.
Because the function is probably going to be very costy, so you might be better off doing what you are doing now,IE interms of speed. But for a better code, it is good to take it out of move generator.

IMO-YMMV
Daniel