Collecting the best variation from hashtable

[Samuele Giraudo]

Hello,

In my program, I use 2 hashtables:
(a) One hashtable with a depth-preference replacement scheme ;
(b) One hashtable without preference for replacements (the entries are overwritten without look at the depth).

To collect the best variation (to have a best move and a best variation for the UCI protocol), I follow best moves in the (a) hashtable from the root position.

Intuitively, this have to work (even if I may have a cut line) but sometimes, when the (a) hashtable is filling, this don't work because the root position entree of (a) is overwriten and my program fail because he can not give a best move. This case happens about 1 time for 3 games.

This problem is strange because I freeze the root position entry of (a) at the beginning of my search_root function: this entry can be modified only by the root position with a greater depth (I use iterative deepening).

I have forgotten something ?


Otherwise, I know that their exists another idea to collect the best variation http://chessprogramming.wikispaces.com/ ... +variation but
I don't like this idea which involve to use a parameter pline and memcpy function. I am interested if you have other way to collect the best variation.

Regards,
Samuele Giraudo

[Zach Wegner]

Getting the PV from the hashtable is fine, but you really need to manually keep the best move at the root. It can be something very simple like "if (score > alpha && ply == 0) best_move = move;".

[Samuele Giraudo]

Strange because doing this, the variable best_move contains (rarely, about 1 time for 5 games) an illegal move.

[hgm]

I would say once per game, when you are checkmated...

[Sven]

I would keep two ideas separate:

- retrieving the principal variation of your search, which is mainly for displaying and perhaps testing/debugging purposes, and
- keeping track of the move that the engine currently would choose to play.

The latter must be part of your search algorithm, and you must do it right, since this is the goal of doing a search: the engine decides which move to play.

The former is kind of optional, your engine can play chess without knowing its current PV, or without displaying it perfectly. It is nice to have it, and many engines have it, it is a standard which is followed in most cases. But it is possible not to have it, while it is bad not to have a "best move choice" available all the time.

You have shown that you know several ways how to retrieve the PV. You have also seen that this may fail sometimes, especially when relying on the hash table (although there is most probably a bug responsible for it). But if you combine both ideas and rely on the PV in order to get the engine's move choice, then a failure to get the correct PV results in losing the game.

One possible alternative for you might be to have two search functions, one for the root node (returning a best value *and* a best move) and one for all other full search nodes, returning only a best value. This avoids frequent "if (ply == 0)" code, although that would work, too, of course.

Illegal moves should *never* make it into your best_move variable. Please check how you handle illegal moves, and how you initialize and set your best_move. The best_move variable should in general be initialized with some empty, undefined, zero of whatever value and should only be modified in case of a subtree returning a value better than the current best value (or alpha), which must not occur when detecting an illegal move.

As to HGM's statement: when checkmated, I would not even start a search. My assumption would be that a search is only started if the current position is not an end-of-game position. This can be done differently, of course, but I think it keeps things simple to search only when there is really a choice to be made.

Sven

[Samuele Giraudo]

Thanks for your replies.

I chose to keep the best move in the search_root function independently of the best variation read from the (a) hashtable.
It's work !