LMR and killer

[hgm]

Why should killers be exempted from LMR? If they are any good, they should fail high even at reduced depth, and then they would be re-searched to full depth anyway. Ths is what must have happened in the sibbling node where they first became killer.

A killer does not have such an extremely good chance to fail high. Much better than a randomly picked non-capture, of course, but that is hardly a recommendation. And if it fails low, the unreduced search would have been a waste of time. If the reduced search is 3 times cheaper than the unreduced search, it would be on average cheaper to first do the reduced search if the fail-high probability is less than 66% (2/3*(1 + 1/3) + 1/3*1/3 = 8/9 + 1/9 = 1). And you would probably eed a much better fail-high rate to break even, because the reduced search acts as IID for the unreduced search, and thus probably speeds up the latter.

[Uri Blass]

The main demage is of course in case that the killer fail low with reduced depth but could fail high with unreduced depth.
This demage means that the reduced search may be cheaper by your calculation but still worse in games.

The only way to know if reducing killer moves by LMR is good or bad is by testing in games.

[hgm]

There still is a way to approach this more conservatively, to minimize that danger. Before the move was killer, it had the reduction that was assigned to it by the static move ordering, and yet it was able to fail high and become killer in some sibbling. Initially other sibblings trying that move could first try it with its natural reduction, and irrespective of whether it fails low or high, then re-search it unreduced. Then they would know if a reduced search would have done the job as well. (This would only be not the case if the reduced search failed low, and the ureduced high.) This could be recorded with the killer. Once it has been tried often enough to confidently see that a reduced search is almost always enough, later sibblings could start applying ordinary LMR.

[F. Bluemers]

Is this standard?
I have tested making an exception for killers a couple of times but it was always worse in Dirty.I guess if the first N good captures fail the killers just won't help, except when there are no good captures but then the killers would be on the top of the movelist and not be reduced.

[hgm]

I thought it was standard to not reduce killers. But I am happy to hear that it can be preferable to reduce them.

I suppose killers are useful when in a previous ply you did not feel the need to rescue a piece that was attacked, because you were already ahead more than its value. When loss of the piece only marginally leave you ahead, it could be that on deeper search, when the opponent has something going for him that makes his score rise with depth, it turns out you cannot afford to give that piece away, and you had better save it. You would then often have to move it away, to a safe square, and the killer will tell you which piece you have to move, and where it will be safe. This could improve your score a lot, if it was a fat piece. Much more than a good capture of a lesser piece, which may not be enough to save the day.

[Evert]

I thought it was standard to not reduce killers. But I am happy to hear that it can be preferable to reduce them.

I think it is indeed somewhat standard. What I do remember is some discussion that having multiple killers is not so useful anymore these days (probably depends on effective branching factor), and the second killer is not so useful for move ordering, but it is a candidate for non-reduction (which is basically the opposite to what you suggested).

[hgm]

Perhaps it is not worth to worry about this so much, but I was a bit chagrined that after implementation of killer in my Tenjiku engine, although it seemed to give a general speedup of some 20%, it delayed finding the good move in the opening position from 7 ply (12 sec) to 12 ply (36 min) The subtle alteration of scores caused by forcing a deeper search of the killers is likely the cause of that.

But I guess the good move was mainly found by luck; it can only see that this move gains material at 9 ply when it searches it as PV. When non-PV the various reductions in the line add up, and the side branch only reaches the depth where it sees the gain when the nominal depth is 12 ply. So only because at 7 ply the move already happened to come up as best with a meager +0.13 score, the material gain it causes will be seen so early (i.e. at 9 ply).

And that it gets this +0.13 at 7 ply is a matter of chance, involving search instability caused by null-move pruning. In some later ply the line can be refuted by a null move, to a score upper bound of +0.03. Because at the point it is searched in one case the old PV already had a +0.03 score, this is considered sufficient. But in the other case the old PV turned out to have only +0.01. So +0.03 would not be a refutation, that null move would fail low, and real moves would be searched instead. Now the a-typical case here is that the best real move scores worse than the null move, because the Pawn chain for the side-to-move is still unbroken, so that in the next two ply he does not have a good development move, while the opponent has one. So not so much a zugzwang, as a 'positional threat' that proves incurable (but was not eligible for QS).

I guess it is unrealistic to try to preserve this lucky abounding of coincidences over search improvements. The whole problem would be solved by simply awarding the obligatory first-move Pawn push a better score in the evaluation, e.g. by penalizing the from-square in the Pawn PST. Then the correct opening move would already become PV from 1 ply on.

[Evert]

Ok, so it's a perhaps more a question of identifying threatening moves early. I would normally try to add some relevant evaluation terms to favour positions with such threats, but Tenjiku might be too volatile to make that work. I just don't know the game well enough.

Now the a-typical case here is that the best real move scores worse than the null move, because the Pawn chain for the side-to-move is still unbroken, so that in the next two ply he does not have a good development move, while the opponent has one. So not so much a zugzwang, as a 'positional threat' that proves incurable (but was not eligible for QS).

That should be something that can be detected as a pre-condition for the null-move though. I usually formulate my null-move condition as "side to move has a non-forced move that can be played", which is then coarsely implemented as having at least one piece (in addition to a king) that can do a triangulation.
So test if the stm has developed properly, and if not skip the null move and force him to do something (perhaps this can be done incrementally: keep track of pieces that have moved, and you can see if pawns have been pushed and if all leaping pieces that can be developed ok first have been developed). It's more bookkeeping, but it may be preferable to doing a board scan on such a large board.

[hgm]

This is not so easy to test statically. A move that looks good development could be tactically impossible.

I guess part of the problem here is that in general, when Pawn pushing is required for development of other pieces, this Pawn pushing itself should be considered a good development move. But in Tenjiku keeping a closed Pawn wall initially is important, for not allowing the Fire Demon entrance to your camp through its area move. So you don't want to encourage Pawn pushing in general. (Also in Chess you don't want all Pawns to be pushed; in micro-Max I arrange this by giving penalty for pushing Pawns when two files left or right there isn't a Pawn on the same rank. After moving up d- and e-Pawns, this discourages moving b-, c-, f- and g-Pawns.) Of course in Tenjiku I could just penalize a Pawn chain with no holes at all, to encourage pushing of at least one Pawn. But since it is so obvious which Pawn that should be, I might as well encourage pushing of that Pawn only.

I experimented a bit:

The old version, without killer, thinks this (j5j6 is the good opening move):

Code: Select all

 10	+4.14	22.5M	1&#58;37.54	<done>
 10	+4.14	21.3M	1&#58;33.90	j5j6 l13n11 k4i6 n11p9 j3k6 g12g11
  9	+0.13	6.6M	0&#58;31.57	<done>
  9	+0.13	5.1M	0&#58;24.92	j5j6 l13n11 m4m6 h12h11 m6m7 i12i11 k4f9 j13j4?
  8	+0.14	3.3M	0&#58;15.10	<done>
  8	+0.14	2.9M	0&#58;13.87	j5j6 l13n11 m4m6 h12h11 d1e2 g13g4? m1l2 d16e15
  7	+0.13	2.5M	0&#58;12.09	<done>
  7	+0.13	2.5M	0&#58;12.09	j5j6 o12o11 m4m6 f14e15 k4f9 j13j4?
  7	+0.01	714260	0&#58;03.79	d4d6 m13m11 g4g13? g12g11
  7	0.00	300090	0&#58;01.70	d1e2 d16e15 g4g13? g12g11 b5b6 m16l15
  6	+0.03	71003	0&#58;00.53	d1e2 d16e15 d4d6 j13j4? m1l2 m16l15
  5	+0.04	39898	0&#58;00.35	d1e2 d16e15 m1l2 m16l15 e4g6
  5	-0.50	37079	0&#58;00.34	d4d6 d13d11 i5i6 d11i6 i4k7
  4	+0.03	6795	0&#58;00.06	d4d6 j13j4? d1e2 d16e15
  4	0.00	799	0&#58;00.00	d1e2 d16e15 m1l2 m16l15
  3	+0.13	306	0&#58;00.00	d1e2 d16e15 m1l2
  2	0.00	8	0&#58;00.00	d1e2 d16e15
  1	+0.13	3	0&#58;00.00	d1e2

After I implemented killer:

Code: Select all

 13	+6.18	1580.5M	112&#58;46.84	<done>
 13	+6.18	1560.3M	111&#58;32.78	j5j6 l13n11 k4i6 n11p11 i6n11 n12n11
 12	+5.55	1422.3M	102&#58;20.53	<done>
 12	+5.55	1422.2M	102&#58;20.07	j5j6 l13n11 k4i6 n11p9 j3k6 g12g11 e4c6 j13j4+ k6j5 p9e9 i6a14+ d13d11 j5p11
 12	+0.58	1393.3M	100&#58;29.56	h5h6 g12g11 i4e8 h13f10 j3h5 j13j4+
 12	+0.06	1008.5M	73&#58;00.59	m4m6 d13d11 d4d6 l13n11 m6l7 k12k11 n4m4 m14j11 f4n12+ f13n5+ n12n11 n13n11
 11	+0.12	138.4M	9&#58;45.95	<done>
 11	+0.12	105.1M	7&#58;37.31	m4m6 g12g11 e4c6 h12h11 j5j6 l13n11 m6m7 i12i11 k4f9 j13j4
 10	+0.13	42.9M	3&#58;11.39	<done>
 10	+0.13	41.1M	3&#58;04.68	m4m6 g12g11 e4c6 h12h11 j5j6 o12o11 m1l2 g13g4 d1e2 d16e15
  9	+0.03	17.0M	1&#58;16.93	<done>
  9	+0.03	11.7M	0&#58;53.40	m4m6 g12g11 e4c6 h12h11 d4d6 d13d11 m6l7 d16e15 d1e2
  8	+0.04	9.2M	0&#58;41.34	<done>
  8	+0.04	9.1M	0&#58;41.04	m4m6 g12g11 e4c6 h12h11 d4d6 g13g4 d1e2 d16e15
  8	-0.02	5.6M	0&#58;25.23	f1e2 d16e15 m1l2 g12g11 e4c6 f13k8 g4g13
  8	-0.03	2.2M	0&#58;09.98	e1e2 g12g11 b5b6 d13d11 k3l2 f13k8 g4g13
  7	+0.04	655010	0&#58;03.14	e1e2 m16l15 m1l2 d16e15 d4d6 e13g11 c3d4
  7	-0.02	535015	0&#58;02.67	g4g13 g12g11
  7	-0.08	415940	0&#58;02.03	d4d6 d16e15 m4m6 d13d11 m6l7 m16l15 d1e2
  6	+0.03	169327	0&#58;00.86	d4d6 j13j4 j5j6 o12o11 d1e2 d16e15
  6	+0.02	65951	0&#58;00.39	d1e2 g12g11 e4c6
  5	+0.04	36988	0&#58;00.21	d1e2 d16e15 m1l2 m16l15 e4g6
  5	-0.50	34187	0&#58;00.21	d4d6 d13d11 i5i6 d11i6 i4k7
  4	+0.03	6529	0&#58;00.03	d4d6 j13j4 d1e2 d16e15
  4	0.00	779	0&#58;00.00	d1e2 d16e15 m1l2 m16l15
  3	+0.13	292	0&#58;00.00	d1e2 d16e15 m1l2
  2	0.00	8	0&#58;00.00	d1e2 d16e15
  1	+0.13	3	0&#58;00.00	d1e2

With killer, but giving a 20cP penalty for j5 being occupied:

Code: Select all

 12	+5.55	61.0M	4&#58;01.26	<done>
 12	+5.55	36.6M	2&#58;24.54	j5j6 l13n11 k4i6 n11p9 j3k6 g12g11 e4c6 j13j4+ k6j5 p9e9
 11	+2.82	18.5M	1&#58;12.42	<done>
 11	+2.82	15.9M	1&#58;02.62	j5j6 l13n11 k4i6 n11p9 m4m6 g12g11 e4c6 f13m6 m5m6 d16e15 d1e2
 10	+2.94	5.8M	0&#58;23.37	<done>
 10	+2.94	4.7M	0&#58;19.57	j5j6 l13n11 k4i6 n11p9 m4m6 f13m6 m5m6 g12g11 e4c6 d13d11 i4k4
  9	+2.84	2.1M	0&#58;08.89	j5j6 l13n11 k4i6 n11p9 m4m6 f13m6 m5m6 g12g11 e4c6 d16e15
  8	+0.22	377725	0&#58;01.81	j5j6 l13n11 m4m6 h12h11 m6m7 i12i11 k4f9 j13j4
  7	+0.33	154408	0&#58;00.84	j5j6 l13n11 m4m6 f14e15 k4f9 j13j4 d1e2
  6	+0.72	64067	0&#58;00.48	j5j6 l13n11 m4m6 h12h11 m6h11 h13j10
  5	+0.31	5475	0&#58;00.03	j5j6 o12o11 k4f9 j13j4 d1e2
  4	+0.20	1069	0&#58;00.01	j5j6 o12o11 k4f9 j13j4
  3	+0.32	369	0&#58;00.00	j5j6 o12o11 d1e2
  2	0.00	7	0&#58;00.00	j5j6 g12g11
  1	+0.20	4	0&#58;00.00	j5j6

[nionita]

In Barbarossa since the beginning I did reduce the killers but had in mind to extempt them some das from LMR. But when I implement it, it was a lost of a few Elos. So now Barbarossa reduces the killers just like any other move.