How to collect PV?

[tttony]

I do it like this in C:

Code: Select all

   // .....
   move_t new_pv[64];
   // .....

This is a reason why HGM's solution better than Bruce Moreland's. When you start search each ply deeper, you create a hole of unused memory in stack (or in heap for less effecient languages).

yes, is in my TODO list to get rid of that array

[syzygy]

https://wiki.c2.com/?GlobalVariablesConsideredHarmful

W.A. Wulf, M. Shaw; Global Variables Considered Harmful, ACM SIGPLAN Notices 8:2, Feb 1973, pp. 80-86
...
This paper is outdated; nested lexical scoping is considered a very desirable feature these days. Here are counterarguments to each of the points above: (...)

https://en.wikipedia.org/wiki/Magic_num ... ogramming)

Accepted use
When a numeric literal lacks special meaning, then its use is not classified as magic; although what constitutes special is subjective.

Hmmm, does the number "10000" have a special meaning? Or was it just picked as a number that is "large enough"?

https://wiki.c2.com/?GotoConsideredHarmful

Here's a good rule of thumb: don't use backward GoTo statements. Notice that continue, break, and mid-function return statements are all forward gotos (and switch is a computed forward goto). EwDijkstra's argument does not apply to them. I have noticed subjectively that they aren't confusing, unless you jump into something else (like the middle of a loop - see DuffsDevice). I don't think there's anything wrong with using goto to do, for example, a double break. Forward gotos are also useful for jumping to cleanup code after an error - they're often much more readable than doing your real work inside an if statement, and they're always more readable than doing your real work in a terraced landscape of nested if statements.

Dijkstra's article made sense at the time (in 1968). Its title (not by him) has been interpreted widely out of context. Of course gotos like anything else can be abused, but introducing extra booleans just to get around typing "goto" (in fear that someone on the internet might get upset) is way more harmful. I'm surprised this is still being brought up.

https://critical.eschertech.com/2010/03 ... rithmetic/

The most common use of explicit pointer arithmetic in C is to increment a pointer while processing an array of data in a loop:

Code: Select all

for (T* p = arr; p != arr + numElements; ++p) {
    *p = foo(*p);
}

The expression arr + numElements is a classic C pointer to one-past-the-last-element of the array.

In other words, this is accepted idiom that every C programmer recognises and understands. (But the author is obviously a ++C programmer.)

To loop through a whole array, I would (nowadays) always use an array index because it is clearer, the compiler will not have any problem optimizing it, and the compiler might even be able to warn you of a mistake.

But in HGM's code the array index wouldn't be a local variable and probably would not be optimized away.
Also, the PV[10000] array is first and foremost a memory area within which strings of moves are being copied around in a somewhat clever/tricky way to optimize memory and cache usage. I think switching to array indexing isn't going to make it any easier to understand. If this code is present in multiple locations and a goto can't help to avoid that, then I might try to put it behind an inline function that can be invoked wherever needed.

https://www.codingrules.dev/rule-2

Rule 2: Don't use sentinel values if your language has a better alternative

A sentinel value is a value such as -1 or the empty string, that has a special meaning in the context of a program.

Using 0 to indicate the end of a list of moves is a problem now?

OK, you could keep track of the length of the PV (or of a "pointer to one-past-the-last-element" of the PV). But doing that just for the sake of not using 0 as a sentinel value is just bowing to mindless dogma, imho. Using -1 to signal the end of a list of non-negative integers or 0 to signal the end of a string or a list of PV moves is really perfectly fine. Or at least in C it is

[Aleks Peshkov]

The size of triangualar array with sentinel should be (MAX_PLY+1)*(MAX_PLY+2)/2, but it never will be close to full state in practice.

[syzygy]

The size of triangualar array with sentinel should be (MAX_PLY+1)*(MAX_PLY+2)/2, but it never will be close to full state in practice.

Perhaps in an endgame with no TT cutoffs in the PV that number could be reached.

[hgm]

Well, to be honest, I really had a problem recently in one of my engines, concerning the size of the PV array (using a 'magic constant' deemed large enough):

There is a Japanese style of mate puzzles called 'tsume', where every move of the checkmating site has to be a check (and this player usually does not have a King himself). This makes the branching ratio pretty low compared to a normal search, which is compensated for by having often ridiculously long mates (like mate in 56).

I equiped my engine HaChu with a mode for solving this. (Normally the engine would choke on positions without a King.) But when it chews on a tsume problem in this mode, it often reaches ridiculously high depths (for the amount of pruning it does). Where in a normal (Chu-Shogi) game it reaches depths of 8-10, in tsume it can easily run to over 30. And then the PV is much longer, because every move must be a check, and will thus benefit from a check extension. So for the more complex problems the move, PV and killer stacks were not large enough, and it would crash after exceeding a certain depth.

Also note that the code I presented, even though taken from a working example (KingSlayer), was only intended as pseudo-code. Of course when a numeric constant would appear in several places I would define it as a macro, for guaranteed consistency and easy changing. But for a one-time occurrence in a pseudo-code example, I think it would be better to just write an actaul number, to give an immediate idea of the order of magnitude.

[chesskobra]

...
https://wiki.c2.com/?GlobalVariablesConsideredHarmful
https://en.wikipedia.org/wiki/Magic_num ... ogramming)
https://wiki.c2.com/?GotoConsideredHarmful
https://critical.eschertech.com/2010/03 ... rithmetic/
]https://www.codingrules.dev/rule-2

We can maybe add a few more references.

From Wikipedia https://en.wikipedia.org/wiki/Goto "An alternative viewpoint is presented in Donald Knuth's Structured Programming with go to Statements, which analyzes many common programming tasks and finds that in some of them goto is the optimal language construct to use.[28] In The C Programming Language, Brian Kernighan and Dennis Ritchie warn that goto is "infinitely abusable", but also suggest that it could be used for end-of-function error handlers and for multi-level breaks from loops.[29]".
[28] Knuth
[29] Kernighan & Ritchie 1988, pp. 65–66, 3.8 Goto and Labels.