Not differentiating root and non-root / pondering approach

[bob]

6b) With P=0.9 (Harald Lüßen uses this number), A has only T/10 nodes left, so you can easily see that this will never take A one ply deeper. Even with bf=1.0 (impossible), the next full ply would require 0.9*T nodes.

To be more precise, the number of required nodes for the next ply would be something like 0.9*T/(N-1) since with the hypothetical bf=1.0, each iteration would take the same number of nodes. This is getting nonsense so I should have chosen a better example, like bf=1.5 (still hypothetical):

lim(0.3+0.2+0.1333+0.0889+...) = 0.9, so the next full ply would take 1.5*0.3*T = 0.45*T nodes which is far more than the available 0.1*T.

And no current engine has bf=1.5 AFAIK.

Sven

Depends on the position. I see sub-1.0 branching factors on positions like fine#70, as an example...

[Harald]

For my engine, I think I am doing something different from most engines, and I wonder if there are any drawbacks.

1) I use the transposition table to keep track of PV (the PV printing routine just follows the hash move at each position to get the PV).

That I think can only affect thinking output and not strength, so this is a minor issue.

2) I don't differentiate between root and non-root nodes. When it's the engine's turn to move, it just calls negamax on the root position, and then return the hash move from the transposition table when negamax returns (if not interrupted). My code is carefully written so that the "root" negamax call will always store a hash move in the TT. It also allows clean implementation of aspiration window. Unlike most (actually every I have seen) engines, it doesn't generate a list of legal moves, and call negamax on each resulting position.

It seems to work quite well for my engine, but does it have any negative impact that I didn't see?

3) pondering. Instead of guessing opponent's move and thinking on the resulting position like just about every engine under the sun does, my engine just "think as the opponent", filling up the hash table.

I decided to do it this way because I noticed that, for "quiet" positions, ponder hits are quite rare, and the whole effort would be wasted if the opponent doesn't make the predicted move (or 2), and for "violent" positions (recaptures for example), it doesn't really matter anyways.

What are the real world differences between these two approaches in terms of strength?

Many thanks

You are throwing away a lot of processing time. You should average at _least_ 50% on ponder hits over the course of a game, correctly predicting the opponent's move thru your PV. Searching from the opponent's perspective simply costs you one ply that you would be getting if you ponder the best move you found as most do...

In another thread recently, you stated that most of the time in a search is spent on the PV, so the loss of time caused by searching from the opponent's perspective would not be that great. It could be worth a test just to see how many ELO difference it makes.

You are losing a whole ply, I would think it easy to see why. Because you are searching for the best move for the opponent, rather than yourself, that ply is important. What it means is that for whatever percent of the time you correctly predict, you will be searching 1 ply less than when you do not predict correct. one ply is measurable in terms of lost Elo...

No that is not true. We are not losing 1 ply.
At the moment when the opponent makes his move you may have searched
2000000 nodes. In the case of a right prediction we may have spent
1800001 nodes for that move also, that is the same 1800000 nodes and entries
in the hash table. At least the most important high depth entries.
Just 200000 nodes are wasted for other opponent moves.
To complete the ply after resuming the search in our thinking time
we are just 200000 nodes behind.
In the case of a misprediction you have to start at zero and we are 20000
nodes ahead.
Do not forget that after the opponent moved we just continue searching
in our allocated time as long as we want. The time stamps of a finished ply are
just milestones at certain node counts in the whole search time.

Harald

I'll make this simple.

Case one, the Crafty mode of pondering. Crafty makes a move and immediately assumes you will make the second move in the PV. It starts to ponder. After 180 seconds it has searched 20 plies deep and you make a move. I can choose to make a move right now (instantly) and accept a 20 ply search after 180 seconds of effort, or I can decide to continue searching, where an additional ply is going to double the total time and I can make a 21 ply move after 360 seconds.

Case two, the mode being discussed. You make a move, and then "flip sides" to begin searching. After 180 seconds you have again reached a depth of 20. But that is 20 plies for the opponent, _not_ for you. When the opponent moves after 180 seconds, if you move instantly you have a 20 ply search from his perspective, but only 19 plies from your perspective completed.

You _do_ lose a ply. It is also trivial to prove that if you predict correctly > 50% of the time, the way I do it is the _only_ way to do it that makes any sense at all from a time utilization perspective...

Your analysis is flawed, because it is based on the same kind of math I use for the normal pondering mode. You believe most of the effort is on the first move you search. And you are correct. But you ignore that most of the effort spent on _that_ move is spent on various other moves lower in the tree, _not_ necessarily the "best" moves. The cost is more pronounced than you believe.

I now believe that Bob Hyatt is right and the classic ponder method (CPM)
is better than the discussed alternative ponder method (APM).
But I also think that the depth argument is the wrong reason and it is not a proof.
The reason is that the lost 1 depth is only at the root of the search and is
worth a few nodes and moves only. The positions and best moves in the hash
table are more important. (*)

I prefer the node count argument and I played with some szenarios.
I also made a few assumptions in favour of the APM to make it easier for me.
- The hash table is big enough to store all (relevant) informations and PVs.
- The opponent plays his move after we did 2 million ponder nodes.
- There are only a few additional nodes to ponder on for the discussed APM,
and the opponent plays one of those moves.
- The APM has the same hits as the CPM and the APM has also hits when CPM misses.
- We look at the moves the APM is behind or ahead in the search.

I. 60% prediction rate, the APM ponders 40% move A, 30% move B, 20% move C, 10% move D, 0% move E
hits: APM searched 800000 nodes
miss: APM searched 600000 nodes
miss: APM searched 400000 nodes
miss: APM searched 200000 nodes
miss: APM searched 0 nodes
After 10 such situations:
6 x 1200000 nodes behind = 7200000 nodes behind
1 x 600000 nodes ahead = 600000 nodes ahead
1 x 400000 nodes ahead = 400000 nodes ahead
1 x 200000 nodes ahead = 200000 nodes ahead
1 x 0 nodes ahead = 0 nodes ahead
==> 6000000 nodes behind

II. 60% prediction rate, the APM ponders 90% move A, 10 x 1% moves B..K
hits: APM searched 1800000 nodes
miss: APM searched 20000 nodes
After 10 such situations:
6 x 200000 nodes behind = 1200000 nodes behind
4 x 20000 nodes ahead = 80000 nodes ahead
==> 1120000 nodes behind

III. 50% prediction rate, the APM ponders 90% move A, 1 x 10% move B
hits: APM searched 1800000 nodes
miss: APM searched 200000 nodes
After 10 such situations:
5 x 200000 nodes behind = 1200000 nodes behind
5 x 200000 nodes ahead = 1200000 nodes ahead
==> 0 nodes behind

IV. 30% prediction rate, the APM ponders 3 x 30% moves A..C, 10 x 1% moves D..M
hits: APM searched 600000 nodes
miss: APM searched 600000 nodes
After 10 such situations:
3 x 1400000 nodes behind = 4200000 nodes behind
7 x 600000 nodes ahead = 4200000 nodes ahead
==> 0 nodes behind

V. 10% prediction rate, the APM ponders 10 x 10% moves A..J
hits: APM searched 200000 nodes
miss: APM searched 200000 nodes
After 10 such situations:
1 x 1800000 nodes behind = 1800000 nodes behind
9 x 200000 nodes ahead = 1800000 nodes ahead
==> 0 nodes behind

VI. 30% prediction rate, the APM ponders 40% move A, 30% move B, 30% move C
hits: APM searched 800000 nodes
miss: APM searched 600000 nodes
miss: APM searched 600000 nodes
After 10 such situations:
3 x 1200000 nodes behind = 3600000 nodes behind
4 x 600000 nodes ahead = 2400000 nodes ahead
3 x 600000 nodes ahead = 1800000 nodes ahead
==> 600000 nodes ahead, but this is a very constructed unreal example

My result is: In typical normal situations and under reasonable
assumptions and parameters the CPM seems to be better than the APM.
But the APM is not as bad as Bob's depth argument would suggest.
Especially in unclear situations the APM may catch up with the CPM.

(*) The depth stored in the hash table entries is 1 less in the APM than in the CPM.
It may or may not lead to more cut-offs. At least the depth has to change
by an amount of 2 to be in effect for Black's positions or White's positions.
If this hash-depth is an important argument for the CPM then please
make it more clear when you explain it to us the next time.

Harald