Search readability

[Rein Halbersma]

Old post from me on the computer draughts forum: http://laatste.info/bb3/viewtopic.php?t=4037 where I prototype a parameterized search function using C++ templates (inspired by the Boost.Graph library).

[Joost Buijs]

That is THE reason I discontinued this bad practice several years ago.

I have a single Search() procedure, and a simple Quiesce() procedure. I have one special case, QuiesceEvasions() that I will get rid of pretty soon...

By merging everything in the search the source code will shrink by a factor 2 or 3 but the readability will be less, now every function is very well defined and readable.

I'm sure that when I spend a few days on it that I can merge everything in let's say 3 functions, but I feel very reluctant to spend time on a cosmetic change.
Somehow I'm a little bit chess tired, I didn't touch my source code for the last 1,5 years besides fixing one or two bugs.

A couple of weeks ago I decided to revive my old Draughts program, I made a new bitboard move generator for it using magics and behold now it is 4 times faster compared to the old mailbox one.
This gives me a lot more fun because it is new, after 40 years of programming chess (with a break of 10 years) I feel like I have seen it all.

[Joost Buijs]

Old post from me on the computer draughts forum: http://laatste.info/bb3/viewtopic.php?t=4037 where I prototype a parameterized search function using C++ templates (inspired by the Boost.Graph library).

By the way, talking about Draughts, I tried to contact Gijsbert Wiesenekker from GWD (who is a former colleague of mine), it seems he disappeared from the earth, his website is down and he does not respond to emails.
Since he is still active in Draughts programming I wonder if you have any idea where and how I might reach him?

[Joost Buijs]

Please forget my previous message, I just received an email from Gijsbert.
Like we say in here Holland 'Als je over de duivel spreekt...'.

[hgm]

I usually have a very long Search routine, which does about everything except evaluation. When I put every task in a well-localized section, each section headed by a comment box, this does not really make readability much different from when each section would have been a separate routine. The sections usually are:

Code: Select all

* Legality check (King capture)
* Hash probe & cutoff
* In-check test (if not from hash)
* Stand pat (when in QS)
* Null-move (otherwise)
* Move generation
* IID loop
*   Loop over moves
*     Next-move extraction (sorting)
*     Move decoding / key calculation (side effects)
*     Repetition detection
*       MakeMove
*       Recursion
*       UnMake
*     Abort handling
*     Score minimaxing
*   Stalemate correction
*   Move re-sorting (for next iteration)
*   Next-depth/bounds determination (PVS and LMR researches!)
* Hash store
* Cleanup & return

The main annoyance here is MakeMove, as I need its functionality also for making input moves. Which would lead to code duplication if I don't make it a subroutine. But it needs access to a lot of variables already available in Search, and passing all these variables to a subroutine is not really attractive.The cleanest way probably is to locate all these variables in an 'undo struct' local to Search, and pass a pointer to that struct to MakeMove and UnMake. The MakeMove at game level can then use its own undo struct, local to the protocol interpreter, filled by the move parser. I used that method in HaChu.

But often I use the 'exit-from-the-first-floor' method, where I call Search() at game level to make the move for me, suppressing the corresponding UnMake for the move that needs to be made by putting an 'Exit' section immediately before UnMake, which returns from Search when the current move matches the input move.

[Henk]

I used memento design pattern for undo. But I removed it few years ago.

See https://en.wikipedia.org/wiki/Memento_pattern

If I don't see parameter lists I have more problems to understand what it does.

if foo1(a, b) then I know that it may be dependent on a and b.
if foo2(a, b, c, d, e, f, g, h, i) then I suspect something might be wrong for it might be too complex.

Extreme case:
What if value of a function dependent on whole database. Maybe one record in the database causing a bug for it contains a wrong value and we have no clue where.

[bob]

That is THE reason I discontinued this bad practice several years ago.

I have a single Search() procedure, and a simple Quiesce() procedure. I have one special case, QuiesceEvasions() that I will get rid of pretty soon...

By merging everything in the search the source code will shrink by a factor 2 or 3 but the readability will be less, now every function is very well defined and readable.

I'm sure that when I spend a few days on it that I can merge everything in let's say 3 functions, but I feel very reluctant to spend time on a cosmetic change.
Somehow I'm a little bit chess tired, I didn't touch my source code for the last 1,5 years besides fixing one or two bugs.

A couple of weeks ago I decided to revive my old Draughts program, I made a new bitboard move generator for it using magics and behold now it is 4 times faster compared to the old mailbox one.
This gives me a lot more fun because it is new, after 40 years of programming chess (with a break of 10 years) I feel like I have seen it all.

You can still structure things reasonably cleanly. But when you duplicate code, you invite bugs. My evaluation could be a bit faster with separate cases for white and black. But back to that having to change two different pieces of code problem. Having done it both ways, I prefer zero duplication when practical.

[kbhearn]

That is THE reason I discontinued this bad practice several years ago.

I have a single Search() procedure, and a simple Quiesce() procedure. I have one special case, QuiesceEvasions() that I will get rid of pretty soon...

By merging everything in the search the source code will shrink by a factor 2 or 3 but the readability will be less, now every function is very well defined and readable.

I'm sure that when I spend a few days on it that I can merge everything in let's say 3 functions, but I feel very reluctant to spend time on a cosmetic change.
Somehow I'm a little bit chess tired, I didn't touch my source code for the last 1,5 years besides fixing one or two bugs.

A couple of weeks ago I decided to revive my old Draughts program, I made a new bitboard move generator for it using magics and behold now it is 4 times faster compared to the old mailbox one.
This gives me a lot more fun because it is new, after 40 years of programming chess (with a break of 10 years) I feel like I have seen it all.

You can still structure things reasonably cleanly. But when you duplicate code, you invite bugs. My evaluation could be a bit faster with separate cases for white and black. But back to that having to change two different pieces of code problem. Having done it both ways, I prefer zero duplication when practical.

i know this is going to make you cringe, but you could always convert to 'just a little' c++ and use templates to get the advantage of specific white/black code if it really is a significant gain without resorting to duplication.

[Joost Buijs]

That is THE reason I discontinued this bad practice several years ago.

I have a single Search() procedure, and a simple Quiesce() procedure. I have one special case, QuiesceEvasions() that I will get rid of pretty soon...

By merging everything in the search the source code will shrink by a factor 2 or 3 but the readability will be less, now every function is very well defined and readable.

I'm sure that when I spend a few days on it that I can merge everything in let's say 3 functions, but I feel very reluctant to spend time on a cosmetic change.
Somehow I'm a little bit chess tired, I didn't touch my source code for the last 1,5 years besides fixing one or two bugs.

A couple of weeks ago I decided to revive my old Draughts program, I made a new bitboard move generator for it using magics and behold now it is 4 times faster compared to the old mailbox one.
This gives me a lot more fun because it is new, after 40 years of programming chess (with a break of 10 years) I feel like I have seen it all.

You can still structure things reasonably cleanly. But when you duplicate code, you invite bugs. My evaluation could be a bit faster with separate cases for white and black. But back to that having to change two different pieces of code problem. Having done it both ways, I prefer zero duplication when practical.

Duplicating things is bad practice because it is difficult to maintain, I agree.
The PV and non PV code is different enough and not really a duplicate, but the SMP and non SMP code is almost a 100% duplicate besides some locking and atomic stuff.
When I want to change this I'll have to use templates (like in my evaluation function), otherwise the performance will be hurt by the additional if/then/else constructs.
On the other hand I don't see a reason why I would change this because the old code is more or less closed.

[bob]

That is THE reason I discontinued this bad practice several years ago.

I have a single Search() procedure, and a simple Quiesce() procedure. I have one special case, QuiesceEvasions() that I will get rid of pretty soon...

By merging everything in the search the source code will shrink by a factor 2 or 3 but the readability will be less, now every function is very well defined and readable.

I'm sure that when I spend a few days on it that I can merge everything in let's say 3 functions, but I feel very reluctant to spend time on a cosmetic change.
Somehow I'm a little bit chess tired, I didn't touch my source code for the last 1,5 years besides fixing one or two bugs.

A couple of weeks ago I decided to revive my old Draughts program, I made a new bitboard move generator for it using magics and behold now it is 4 times faster compared to the old mailbox one.
This gives me a lot more fun because it is new, after 40 years of programming chess (with a break of 10 years) I feel like I have seen it all.

You can still structure things reasonably cleanly. But when you duplicate code, you invite bugs. My evaluation could be a bit faster with separate cases for white and black. But back to that having to change two different pieces of code problem. Having done it both ways, I prefer zero duplication when practical.

Duplicating things is bad practice because it is difficult to maintain, I agree.
The PV and non PV code is different enough and not really a duplicate, but the SMP and non SMP code is almost a 100% duplicate besides some locking and atomic stuff.
When I want to change this I'll have to use templates (like in my evaluation function), otherwise the performance will be hurt by the additional if/then/else constructs.
On the other hand I don't see a reason why I would change this because the old code is more or less closed.

Don't forget templates also increase the cache footprint, which is another performance loss.