Time assignment to children

[matthewlai]

Fixed null move for NCS (reduction of 0.0003 turned out to be best), and re-enabled it for both (fixed R=3 for dcs, which is best for dcs).

Code: Select all

Rank Name          Elo    +    - games score oppo. draws 
   1 Giraffe ncs    13    6    6  3210   53%   -13   16% 
   2 Giraffe dcs   -13    6    6  3210   47%    13   16% 

Now ncs is 26 +- 12 Elo better.

Obviously your mileage will vary.

[voyagerOne]

I didn't spend time reading all the posts but had an idea that is somewhat similar:

We store the move count in our stack for each ply we play and use that count as a way to help predict lmr.

Example A:

ply1: 2
ply2: 1
ply3: 4
ply4: 2


Example B:

ply1: 13
ply2: 9
ply3: 22
ply4: 11


Let say at ply5 we do LMR. Example A may have a higher chance to fail high and we would need to do a full search compared to Example B.

It will be interesting to get data on the "move signature of the PV"
i.e. at which move number did we find the PV move on each ply.

We may than be able to predict LMR with better accuracy with a move signature.

[PK]

Good luck with Your project! I have read this thread only recently and I hope that it is possible to create a working engine with it, even if it turns out slightly weaker than normal alpha-beta. The only thing I don't quite understand is Your anti-LMR bias. After all LMR can be added to Your search very easily - just by building a table of multipliers for node counts of quiet moves, something like

Code: Select all

double lmr_node_mult[256] {1.25, 1.25, 1.20, 1.15, 1.10, 1.05, 1.0, 1.0, 0.95, 0.90 ...}

[matthewlai]

I didn't spend time reading all the posts but had an idea that is somewhat similar:

We store the move count in our stack for each ply we play and use that count as a way to help predict lmr.

Example A:

ply1: 2
ply2: 1
ply3: 4
ply4: 2


Example B:

ply1: 13
ply2: 9
ply3: 22
ply4: 11


Let say at ply5 we do LMR. Example A may have a higher chance to fail high and we would need to do a full search compared to Example B.

It will be interesting to get data on the "move signature of the PV"
i.e. at which move number did we find the PV move on each ply.

We may than be able to predict LMR with better accuracy with a move signature.

That is a pretty interesting idea and makes LMR more reasonable.

Not really related to my idea though

[matthewlai]

Good luck with Your project! I have read this thread only recently and I hope that it is possible to create a working engine with it, even if it turns out slightly weaker than normal alpha-beta. The only thing I don't quite understand is Your anti-LMR bias. After all LMR can be added to Your search very easily - just by building a table of multipliers for node counts of quiet moves, something like

Code: Select all

double lmr_node_mult[256] {1.25, 1.25, 1.20, 1.15, 1.10, 1.05, 1.0, 1.0, 0.95, 0.90 ...}

Thanks!

I already modified my engine to use it and it is slightly stronger (26 elo) than the original, so it's definitely possible to create a working engine with it. It is still alpha-beta by the way. Just not depth-based.

Indeed, it is easy to add LMR to it. I do have a strong bias against LMR, and it doesn't really to do with this approach.

I just don't think a fixed reduction schedule makes sense, whether it's in my node based search or a depth based search.

Imagine we have a position where there is one hash move, 2 winning captures, then 2 killer moves.

In this case reducing after 5 moves makes a lot of sense, because we are pretty confident that the move ordering is good, at least for the first 5 moves.

Now Imagine another position with 1 hash move, no winning captures, and no killer moves. In this case we are not nearly as confident in the move ordering, and following the same reduction schedule doesn't make sense.

That is my primary problem with LMR.

I am experimenting with allocating more nodes (equivalent to extending, or you can also think of it as reducing all other moves, and they are identical because everything is normalized) to hash moves, winning captures, and killers. And less to losing moves.

The effect should be similar to LMR, but much more reasonable. It won't go around reducing moves when we have no idea how good the move ordering is.

[voyagerOne]

LMR is time sensitive...the longer the time control the stronger it is.

Of course LMR will reduce some good/strong moves.
However, it will eventually find them in the next iteration(s).

LMR significantly reduce the EBF and is the major factor that modern engines can reach extreme depth.

[matthewlai]

Of course LMR will reduce some good/strong moves.
However, it will eventually find them in the next iteration(s).

That can be said for all reduction techniques - given enough time it will still find them. However, if LMR makes the search find those strong moves later, it made the search worse (in terms of finding those moves).

LMR significantly reduce the EBF and is the major factor that modern engines can reach extreme depth.

EBF doesn't really mean much when you are reducing so aggressively, because depth doesn't really mean much, and EBF doesn't mean anything without meaningful depth. Can you really say you have searched to depth 10, when you haven't seen 99.99% of the leaf nodes at depth 10?

At this point, depth is just an arbitrary number (and so is EBF).

In my program (using node-count based search) I defined a simple equation to map depth to node budget, because both CECP and UCI deeply assume that the engine is depth based. My definition of depth is therefore completely arbitrary. With LMR, I feel like their definition of depth is almost as arbitrary.

[bob]

Of course LMR will reduce some good/strong moves.
However, it will eventually find them in the next iteration(s).

That can be said for all reduction techniques - given enough time it will still find them. However, if LMR makes the search find those strong moves later, it made the search worse (in terms of finding those moves).

I think the two of you are "talking past" each other. LMR makes you need more plies to find a move, but in general you get there quicker because of LMR. So in terms of depth, it is worse. In terms of time, it is a winner, at least in the big majority of the chess positions...

LMR significantly reduce the EBF and is the major factor that modern engines can reach extreme depth.

EBF doesn't really mean much when you are reducing so aggressively, because depth doesn't really mean much, and EBF doesn't mean anything without meaningful depth. Can you really say you have searched to depth 10, when you haven't seen 99.99% of the leaf nodes at depth 10?

At this point, depth is just an arbitrary number (and so is EBF).

In my program (using node-count based search) I defined a simple equation to map depth to node budget, because both CECP and UCI deeply assume that the engine is depth based. My definition of depth is therefore completely arbitrary. With LMR, I feel like their definition of depth is almost as arbitrary.

Depth has been meaningless since the first search extension was added, because now some pathways are searched deeper than others. The old saying "all plies are not created equal" is spot-on today. The only thing that matters is time to find the right move.

[matthewlai]

Well, there is one unexpected problem. Overflow!

I am currently using int64_t to keep track of node budget, and it's getting close to overflow!

Node budget is not the same as node count because it specifies the size of the minimax tree. With ideal move ordering, we are looking at about sqrt() of that actually searched by alpha-beta.

Which means for a 64-bit number, it would actually overflow when node count gets to about 2^32.

Right now I am at about 50000000 after a few minutes (my engine is very slow), so it's not overflowing yet, but it's a little close for comfort, so I'm now looking for ways to increase the margin.

An 1 hour search, with a 10x faster NPS (which is totally realistic given how slow I am searching right now), and a few year's worth of Moore's law, it will overflow in no time!

I am ready for 128-bit .

[mvk]

Well, there is one unexpected problem. Overflow!

I am ready for 128-bit .

Or represent the node budget as log(nodes). Division becomes subtraction. Scale it such that you can use integer arithmetic. And then you find that you have, in fact, the equivalent of fractional depths