PVS problems

[Santinorua]

I have been trying to implement PVS in my engine, but for some reason, it increases the total node count instead of decreasing it. (around 5% higher)

I think that my move ordering is quite good:
- Hash move
- Promotions
- Captures with SEE >= 0 (ordered by MVV/LVA)
- Killer moves
- Quiet moves (ordered by history, butterfly heuristics, counter moves history, and see)
- Captures with SEE < 0 (ordered by MVV/LVA)

(note that SEE is also used in quiet moves to penalize those that move a piece to a square where it can be captured).

Also, the number of Re-Searches is low:

Code: Select all

Null Window Searches: 3345957
Re-Searches: 984 (0.0294086%)

The code I’m using looks something like the following pseudocode (I use the copy-make approach):

Code: Select all

int Negamax(Board *board, int depth, int alpha, int beta){
    (...)
    for (int i = 0; i < numberOfLegalMoves; i++){
        Board newBoard = *board;
	newBoard.makeMove(moves[i]);
	int score;
	if (i == 0) {
            score = -NegaMax(&newBoard, depth - 1, -beta, -alpha);
        } else {
            Board boardForReSearch = newBoard;
            score = -NegaMax(&newBoard, depth - 1, -alpha-1, -alpha);
            if (score > alpha && beta - alpha > 1) { // Also tried (score > alpha && score < beta) but nothing changed
                score = -NegaMax(&boardForReSearch, depth - 1, -beta, -alpha);
            }
        }
        (...)
    }
    return alpha
}

If anyone knows what is happening please let me know.

PS: English is not my native language so i'm sorry if anything is wrong, but I hope I made myself clear.

[Lunar]

Have you tried testing playing strength between the two versions? The number of nodes visited for any single given position is not a great proxy for strength

[Santinorua]

Yes, the new version is much weaker. This is expected, since PVS should result in a stronger engine because it reduces the total number of nodes searched, but my version does not do that.

[smatovic]

There was recently another post in regard of PVS:

TT/PV interaction and unexpected SPRT results with PVS
viewtopic.php?t=85141

Ikd if it is of any use for you though.

--
Srdja

[Santinorua]

Yes, I have read that post, but it doesn't help me because in the post the problem is that although it produces fewer nodes it reduces playing strength, whereas in my case, it does not reduce node count. Also, that post doesn't seem to have been resolved

[smatovic]

Hmm, and here is another unresolved one:

PVS weaker than plain alpha-beta
viewtopic.php?p=978373#p978373

--
Srdja

[abulmo2]

I have been trying to implement PVS in my engine, but for some reason, it increases the total node count instead of decreasing it. (around 5% higher)

You probably did something wrong... On a very simple engine running a small benchmark I get a reduction of 40% of the total node count.

Also, the number of Re-Searches is low:

Code: Select all

Null Window Searches: 3345957
Re-Searches: 984 (0.0294086%)

Well, Re-Searches only happen on PV nodes. On a small bench with a basic engine I got the following number: (using llvm-cov on real code)

Code: Select all

  372|  56.8M|	while ((move = movearray_next(movearray)) != 0) {
  373|  55.7M|		search_update(search, move);
  374|  55.7M|			if (is_pv) {
  375|  32.0k|				if (movearray_is_first_move(movearray, move)) {
  376|  1.05k|					score = -search_pvs(search, -beta, -alpha, depth - 1);
  377|  30.9k|				} else {
  378|  30.9k|					score = -search_pvs(search, -alpha -1, -alpha, depth - 1);
  379|  30.9k|					if (alpha < score && score < beta) {
  380|    983|						score = -search_pvs(search, -beta, -alpha, depth - 1);
  381|    983|					}
  382|  30.9k|				}
  383|  55.7M|			} else {
  384|  55.7M|				score = -search_pvs(search, -alpha -1, -alpha, depth - 1);
  385|  55.7M|			}
  386|  55.7M|		search_restore(search, move);

Thus, I get 983 Re-Searches for 30,900 null-window searches on PV nodes (about 3.2%) and 55.7 millions of overall searches (about 0.0018%). So your 0.029% is either too high or too low depending on what you measure.

The code I’m using looks something like the following pseudocode (I use the copy-make approach):

Code: Select all

        Board newBoard = *board;
	(...)
	newBoard.makeMove(moves[i]);
	(...)
        Board boardForReSearch = newBoard; <= IS THIS NECESSARY
        (...)
    }
    return alpha
}

If anyone knows what is happening please let me know.

I think there is a lot of board copy... this will slow down your engine, but shall not change the node count.

[Santinorua]

I think there is a lot of board copy... this will slow down your engine, but shall not change the node count.

I realised that, a few minutes after I wrote it in the post, but thank you anyways.

Thus, I get 983 Re-Searches for 30,900 null-window searches on PV nodes (about 3.2%) and 55.7 millions of overall searches (about 0.0018%). So your 0.029% is either too high or too low depending on what you measure.

The 0.029% is comparing to null window searches, so it is too low, but i don't know why. Any ideas as to what might be the cause of the problem?
I will keep debugging to look for the problem.

Thank you very much for the information on your tests.

[Santinorua]

I have to correct myself:

The 0.029% is comparing to null window searches, so it is too low

That was because i was not taking into account if a null search was being executed in a pv node or not, if I meassure it the same way as you, the results are the following:

Low depth search across different positions (3,509,328 nodes in total):

Code: Select all

Null Window Searches: 27203
Re-Searches: 932 (3.42609%)

High depth search across different positions (47,900,797 nodes in total):

Code: Select all

Null Window Searches: 67644
Re-Searches: 2015 (2.97883%)