Worst advice

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.
brtzsnr
Posts: 433
Joined: Fri Jan 16, 2015 3:02 pm
Contact:

Re: Worst advice

Post by brtzsnr » Mon Aug 10, 2015 5:02 pm

For young engines the move generation and sorting consume the most amount of time. Two reasons for this: 1) move are generated even if a hash move is already available 2) evaluation is extremely basic, possible just the material and position.

Stronger engines do various tricks to avoid generating or sorting the moves and, additionally, they have very complicated evaluation function. It's curious that a better eval improves the (internal) nps.

mvk
Posts: 589
Joined: Tue Jun 04, 2013 8:15 pm

Re: Worst advice

Post by mvk » Mon Aug 10, 2015 5:15 pm

Henk wrote:So question is: What was the worst idea you implemented
Any speed improvement below 2,000 cycles per node.
[Account deleted]

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

Re: Worst advice

Post by jdart » Mon Aug 10, 2015 5:35 pm

Nobody should be doing 1). If you have a hash table, you probe it first, before movegen. That is not complicated.

--Jon

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

Re: Worst advice

Post by Robert Pope » Mon Aug 10, 2015 6:40 pm

jdart wrote:Nobody should be doing 1). If you have a hash table, you probe it first, before movegen. That is not complicated.

--Jon
But how do you know the probe returned a legal move? Stronger engines will have special validation routines, but younger engines often do a movegen and then see if the probe is in the movelist.

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Worst advice

Post by cdani » Mon Aug 10, 2015 6:49 pm

Robert Pope wrote:
jdart wrote:Nobody should be doing 1). If you have a hash table, you probe it first, before movegen. That is not complicated.

--Jon
But how do you know the probe returned a legal move? Stronger engines will have special validation routines, but younger engines often do a movegen and then see if the probe is in the movelist.
During a lot of time, Andscacs (and sure a lot of engines) was generating all the legal moves without bitboards with a lot of for loops, and was validating all the moves like the hash one searching in the list of moves generated. Of course this was sloooow, but I had something that was working and I knew sometime I will improve. Now it uses all the tricks one can think about to speed things. Is just a step after another. Make it work, and you will have time to improve it.

Dann Corbit
Posts: 10124
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Worst advice

Post by Dann Corbit » Mon Aug 10, 2015 7:17 pm

Was it the advice that was bad or the implementation of the advice?

Now, bitboards can be quite unnatural when you are not used to them yet.
But in the long run, I think that the advice was very good.
I guess that if you take your time and work through the issues, eventually you will be glad that you switched.

Look at the top ten on this list:
http://www.computerchess.org.uk/ccrl/4040/

Guess which of them are bitboard engines...
Answer:
All of them.

It's not a coincidence.

It is also true that array based engines can be very strong. But for 64 bit CPUs and 64 bit operating systems, bitboards are better.

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

Re: Worst advice

Post by jdart » Mon Aug 10, 2015 7:22 pm

You are only going to store a move in the hash table if it was generated, validated and executed previously for the position. So the only reason you'd get an invalid move would be a hash collision or an overwrite of hash table data while you are reading it (if using lockless hashing). To avoid this you do need to validate.

But I've done this forever .. version 1.0 of Arasan had a hash_move_valid method (not using movegen).

--Jon

Joost Buijs
Posts: 987
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Worst advice

Post by Joost Buijs » Mon Aug 10, 2015 7:48 pm

Robert Pope wrote:
jdart wrote:Nobody should be doing 1). If you have a hash table, you probe it first, before movegen. That is not complicated.

--Jon
But how do you know the probe returned a legal move? Stronger engines will have special validation routines, but younger engines often do a movegen and then see if the probe is in the movelist.
With a 64 bit key validation is not really necessary.

I have a move validation routine which I only use when I want to check if my transposition table is not malfunctioning.
Sometimes I let it run for an hour or so, and it never detects a single invalid move, and this is in a multithreaded search.
To be 100% on the save side you can of course make sure that an invalid move won't crash your engine.

Henk
Posts: 5827
Joined: Mon May 27, 2013 8:31 am

Re: Worst advice

Post by Henk » Mon Aug 10, 2015 7:57 pm

Dann Corbit wrote:Was it the advice that was bad or the implementation of the advice?

Now, bitboards can be quite unnatural when you are not used to them yet.
But in the long run, I think that the advice was very good.
I guess that if you take your time and work through the issues, eventually you will be glad that you switched.

Look at the top ten on this list:
http://www.computerchess.org.uk/ccrl/4040/

Guess which of them are bitboard engines...
Answer:
All of them.

It's not a coincidence.

It is also true that array based engines can be very strong. But for 64 bit CPUs and 64 bit operating systems, bitboards are better.
Are you talking about using bitboards for move generation or bitboards for evaluation ? No need to tell me that bitboards are fine for detecting passed pawns.

Using bitboards for move generation was at least one month of misery with these stupid bit shifts that always shifted to the wrong direction.

Dann Corbit
Posts: 10124
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Worst advice

Post by Dann Corbit » Mon Aug 10, 2015 8:18 pm

Henk wrote:
Dann Corbit wrote:Was it the advice that was bad or the implementation of the advice?

Now, bitboards can be quite unnatural when you are not used to them yet.
But in the long run, I think that the advice was very good.
I guess that if you take your time and work through the issues, eventually you will be glad that you switched.

Look at the top ten on this list:
http://www.computerchess.org.uk/ccrl/4040/

Guess which of them are bitboard engines...
Answer:
All of them.

It's not a coincidence.

It is also true that array based engines can be very strong. But for 64 bit CPUs and 64 bit operating systems, bitboards are better.
Are you talking about using bitboards for move generation or bitboards for evaluation ? No need to tell me that bitboards are fine for detecting passed pawns.

Using bitboards for move generation was at least one month of misery with these stupid bit shifts that always shifted to the wrong direction.
The advantage of bitboards is mostly in evaluation.
Direction of shift will be wrong if you number your bits differently than the intention of the bitmap.

For instance, if you have a1 as bit 0 or bit a8 as zero, the math will clearly be different.

It seems that everyone is using magic bitboards now, which are even stranger looking than rotated bitboards. But since it is a perfect hash function, it is not surprising that it looks a little odd. Perfect hash functions always look a little odd, since you have to finagle the hash to have a distinct value for every known input. So the advice for perfect hash routines is to use an existing generator and just verify that the routines work and then use them (with proper credit as due, of course).

Post Reply