Speed more important than accuracy?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
johnwbyrd
Posts: 7
Joined: Tue Jan 20, 2015 2:22 am

Speed more important than accuracy?

Post by johnwbyrd » Thu Jan 29, 2015 7:33 pm

Dear wise chess programmers, I have an interesting riddle for you.

So I've written this fairly primitive chess engine that does a very basic evaluation. One of its evaluations is a mobility calculation, which is basically just the number of available moves in any position. It added this number to the results of the other evaluations, in order to bias toward that sort of position. It evaluates between 40k and 200k nodes per second depending on the complexity of the position.

Now I came to realize that it might be a better to choose a mobility score based on the number of moves currently available in this position less the number of moves available by the opponent after a null move. This would acknowledge when the other side has better play and reduce the score accordingly.

It was quick to implement but reduced the performance of the engine down to around 45k nodes per second in the worse case. But the scores were much more accurate.

Now I played the engine against itself and what do you know? The engine's ELO dropped like 95 points. WTF? I would have expected that a more accurate evaluation function would have produced better results, even if it were slower.

Has anyone else seen behavior like this? Am I just wrong in my assumptions? Is it better to have an incorrect but fast evaluation function?

Robert Pope
Posts: 510
Joined: Sat Mar 25, 2006 7:27 pm

Re: Speed more important than accuracy?

Post by Robert Pope » Thu Jan 29, 2015 8:57 pm

It should be clear that there is always a tradeoff between speed and accuracy, and you just have to test whether an addition is a net gain or loss.

Mobility is relatively expensive, so I use lagged mobility in my evaluation (the number of pseudolegal moves from the most recent 2 plies), with the thought that they should be relatively representative, but have almost no cost.

I'm not clear on your slowdown, though. Worst case of 45K nps is faster than your prior worst case (40K nps).

jorose
Posts: 269
Joined: Thu Jan 22, 2015 2:21 pm
Location: Zurich, Switzerland
Full name: Jonathan Rosenthal

Re: Speed more important than accuracy?

Post by jorose » Thu Jan 29, 2015 9:44 pm

I think of it like this: essentially an engine at its core is nothing more then an over-sized evaluation function. A perfect engine would search depth 1 and return either +mateScore, 0, or -mateScore. Obviously this is near impossible if not completely impossible. So how do we deal with this dilemma? Well we accept much greater error bounds for our evaluation function and just try to make it as good as possible. Since we can only make it so good however we improve the evaluation by letting our engine evaluate possible continuations and if he understands that some position in the future is inevitable he might be able to evaluate the current position that much better.

With this in mind what you are actually doing is not making your evaluation function "more precise" you are instead trading your evaluation functions vision of the future for a more precise evaluation of a single snapshot.

On top of this an evaluation function is only as good as how well its parameters are tuned. If we changed Komodos evaluation function so it thought all pawns were worth as much as a queen then chances are half the Talkchess message board would be able to beat it.

Since parameter tuning is a very hard problem in general (hence all the discussions with things like CLOP, SPRT or Texel's Tuning Method) you have to be very careful with adding new things to your evaluation function unless they are very easy to calculate quickly.

Modern engines are not just brute force machines, but they do utilise brute force to an effective degree.

User avatar
hgm
Posts: 23772
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Speed more important than accuracy?

Post by hgm » Thu Jan 29, 2015 9:47 pm

I once tried what I called 'static mobility' in Fairy-Max. The idea was to count the number of moves of each piece during move generation, both before and after null move, at the last level where you still do null move. (Which for Fairy-Max is d=1.) This is practically free, just one extra increment instruction in the inner loop of the move generator.

The total of all pieces was then added to the material evaluation, and all piece values were incremented with the mobility of that piece. So that when QS would make that piece go away, is mobility contribution would disappear with it. What it would miss is the mobility change of the pieces due to their movement during QS. (But I figured this was not a very persisten feature of the position anway: if a piece with good mobility moves to a square with much poorer mobility because it needs to capture something there, you could move it back to the good mobility position in a single move.)

Unfortunately this change also lowered the Elo by about 100 points.

I guess the lesson is that the mobility itself needs to be realistic, and the base piece values have to be pre-corrected for the average mobility, which I did not do. Having an inaccurate mobility probably only hurts, even when it doesn't slow down the nps.

Uri Blass
Posts: 8598
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Speed more important than accuracy?

Post by Uri Blass » Sat Jan 31, 2015 5:36 am

johnwbyrd wrote:Dear wise chess programmers, I have an interesting riddle for you.

So I've written this fairly primitive chess engine that does a very basic evaluation. One of its evaluations is a mobility calculation, which is basically just the number of available moves in any position. It added this number to the results of the other evaluations, in order to bias toward that sort of position. It evaluates between 40k and 200k nodes per second depending on the complexity of the position.

Now I came to realize that it might be a better to choose a mobility score based on the number of moves currently available in this position less the number of moves available by the opponent after a null move. This would acknowledge when the other side has better play and reduce the score accordingly.

It was quick to implement but reduced the performance of the engine down to around 45k nodes per second in the worse case. But the scores were much more accurate.

Now I played the engine against itself and what do you know? The engine's ELO dropped like 95 points. WTF? I would have expected that a more accurate evaluation function would have produced better results, even if it were slower.

Has anyone else seen behavior like this? Am I just wrong in my assumptions? Is it better to have an incorrect but fast evaluation function?
all top programs use mobility and of course you need to use mobility.
My comments are the following:

1)I guess that you probably do not write the code correctly if the reason for the elo loss is only the fact that mobility is expensive for you.

It clearly should not make you twice slower in nodes per second
and you need at least to be twice slower for 95 elo drop even with the same evaluation.

2)It may be possible that you overevaluate mobility.

I believe that even stupid mobility that simply count the number of legal moves of both sides and multiply it by 2(when 100 is the value of a pawn)
should be productive(after it you can try to improve your program again).


3)Having many moves is good but not all pieces are the same.
It is more important to have more moves for knights and bishops.
Less important to have more moves for rooks and less important to have more moves for the queen so instead of counting the number of legal moves it is better to count the number of legal moves of different pieces and multiply them by different numbers.

It may be even better to have an array of mobility because the difference between 0 moves and 1 move should be evaluated higher than the difference between 1 move and 2 moves and if the piece has many moves then more moves do not give much(and there is practically no difference between a bishop that has 10 moves to go and a bishop that has more moves to go).

jdart
Posts: 3834
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Speed more important than accuracy?

Post by jdart » Sun Feb 01, 2015 4:04 am

I agree. Mobility computation should not be very expensive, especially with bitboards.

Also, I don't know what kind of hardware you have, but on modern processors 1 million nodes/sec. is pretty common even with 1 core. So you may have a serious bottleneck not related to mobility.

--Jon

Post Reply