Lots of bugs

[H.G.Muller]

BTW, messing with alpha and beta is never completely safe, so whether the code shown above is correct also depends on how you handle the case where you get a score between the original and adjusted window limit (which is not shown here). E.g. if your window was {0, 100} (centi-Pawn) in a d=8 node, and you get a TT hit on a d=8 entry with lower bound +50, so that you adjust the window to {50, 100} to do a d=8 search... When that search then gives you a score of +25, which will be an upper bound (as 25 < 50), and you would return it like nothing happened, the parent node would now take it as an exact score (-25, lying in its window {-100, 0}), while in fact it was a lower bound, and the true score could very well have been +800. (And the daughter node would not have returned you a PV, as that node was very well aware the score was just a bound, and no move was found.)

[ppyvabw]

Hi,

Sorry to resurrect an old thread, but my problem relates to my original post; seems silly to start a new thread.

I am, happy with how my engine is working now, having solved most of the obvious bugs. Except one, which continues to defeat me....(I'm not even certain it's a bug, or an expected consequence of what i am trying to do which I should either forget about, or impose some kind of fix)

I extract the PV from the TT table to print it out after each iteration. So I play the best move from the root (which is a pv node), then play the best move from the next ply, and so on until there are no more PV nodes. This seems to work fine normally, except on occasions it prints out an infinite repetitive sequence of moves. Sometimes the period of the sequence is 4 moves long, but often it is longer. I think this occurs in situations where the position repeats itself, and so there is a 'cyclical sequence' of moves in the TT table. I guess this would happen in positions where a 3 move repetition is likely, but it happens more often than I would expect.

I have made it print out the TT entries to try to find what's wrong, but it's not very illuminating. Does anyone have any ideas about what might be causing this?

[hyatt]

You will always have to deal with two problems when trying to retrieve a PV from the hash table.

(1) cycles, as you have seen. Simplest solution is after each move is extracted, do a repetition check. Stop when you repeat as you have just hit a cycle.

(2) wrong moves. PV moves can get overwritten, particularly those deeper in the tree you search. So you can retrieve a move that does NOT lead to the terminal position of the PV. You can always call evaluate at the end of your PV to see if the score matches the backed-up score. On occasion it won't. That's why the so-called triangular array approach is so much better.

[H.G.Muller]

Indeed, you will often see a non-mate score together with a PV that ends in checkmate. This happens because the PV retrieval grafted a sub-tree for sub-optial defense onto the PV 'after the fact'.

[ppyvabw]

.... That's why the so-called triangular array approach is so much better.

I have been in half a mind to do that, but my understanding was that developers had abandoned that approach in favour of storing the PV in the transposition table (or a separate PV hashtable). But to my mind, the problems in making sure the PV does not get over-written just seem impossible to overcome.

If I were to do that, what would I do if I got an exact TT hit at the beginning of a call to my search function that fell within (alpha,beta). Surely that would shorten the PV, because it would just return the score and not store the PV in the table? Or would I just not check for exact TT hits, as they happen rarely, and continue to search such a node anyway to make sure I got the PV.

[H.G.Muller]

Indeed, the problem with the triangular array method is that you will get shortened PVs on hash cutoffs. To provide this some engines use the hack of not taking hash cutoffs in the PV. In theory this is bad, and perform significantly worse in end-game positions like Fine #70, although the Elo loss might be unmeasurable. A less drastic method would be to retrieve the missing part of the PV from the hash table at the point where you do get the hash cutoff, and ignore the scores. (Which is basically what not taking the cutoff does, except that it does not ignore the scores, and overwrites the with scores of possibly lower depth.)

The only absolutely correct way is to hash the entire PV (rather than just the best move) for PV nodes (i.e. nodes with 'exact' score bound), and copy that PV back to the triangular array when you take a hash cutoff.

[ppyvabw]

I've spent the last few days experimenting with this; I don't think what I have done is exactly a triangular PV table, but I have passed pointers (I'm using C++, so I used a reference to a std::vector) to each call of my search function, and subtended that vector to the best move if a node falls within the bounds. It kind of works -- in so far as it has alleviated the cyclical problem I was having -- however it does some buggy things -- I'm, sure I'll solve those though eventually.

Are there programs that hash the entire PV? Isn't there the possibility that the hashtable could become huge, because you don't a priori know the storage requirements, so presumably you'd have to have some kind of variable length structure?

[H.G.Muller]

Crafty does this, but AFAIK it is the only one.

As approximately 0% of the nodes stored in the hash table are PV nodes, it would be very wasteful to reserve space for a full PV in every hash entry. I understood that Crafty uses a separate hash table to store the PVs. E.g. you could take a table with 200 times fewer entries, each the double length (i.e. 32 bytes) of a normal hash entry, so that they can hold 16 moves in normal encoding. That would only take 1% extra memory. Hash entries with EXACT flag would have a PV stored in that table, and you could use the normal hash key to access it.

Another design could be to have a table of 64K entries, where you keep the unused entries in a linked list so that you can quickly allocate one. And use the 16-bit move field of a regular hash entry to hold the number of the entry that stores its PV.

Personally I planned to do it like this (but so far never got to actually do it): Normally my depth-preferred part of the table consists of pairs of entries (where the least deep will be replaced if a deeper one arrives, and otherwise will bounce the new one to the always-replace slot). Nodes with exact scores would always requisition both entries: the normal info would be stored in the first entry of the pair, and the second entry would then store the PV in 1-byte-per-move encoding. On probing you can test the bound-type flag of the first entry to decide whether the second entry is available.

[ppyvabw]

Hi,

I did have a go at hashing the PV today, before I read your reply.

To do my new PV thing, I wrote a c++ class that is basically just a c++ vector as a private member (which can just be arbitrarily extended) but I have overloaded the [] and + operators so that if I do something like pvline, it will return the pv move at that ply or return a nullmove if it has reached the end of the pv. The + operator just prepends the pv from subsequent nodes to the best move at the current node (if it falls within the bounds).

Today, I simply added that class to my transposition table, and if there is an exact TT hit that falls within (alpha,beta), it returns the score, but also returns the pv from the hash table by reference. If there is no PV in an entry, the only storage requirement is whatever space an empty vector takes -- which I don't know.

Given your reply though, I can't help thinking that what I have done must be wrong, if Crafty is the only program to do this. Seems too easy.