Why search() reaching max ply of > 120 ?

[Michael Sherwin]

In RomiChess I extend mate threats from null move by two ply. However, no line is allowed to go more than 12 ply past the iteration depth.

[hgm]

I am not sure how this mate-threat extension works. Is it that the checking side, when it plays a null move in stead of the check, will get mated? (you still have not shown us the position...) In that case, I think the answer is to not add extensions, if there are multiple conditions that would trigger an extension. Just use the largest extension. In this case, if both the check and the mate threat request an extension of 1 ply, extend 1 ply.

[Sven]

You probably shouldn't do a null-move search at all if you are in check. What does your move generator think of capturing kings? Is that what is returning the mate score? If that's the case, you are effectively extending every mate evasion.

Everything is clear now. I added a debug variable to printout 'matethreat'; a node does nullmove and detected matethreat, so :
depth_to_search = depth + matethreat (depth +1). This is the depth printed and is the same as the previous depth; it also searches a check move, so the next depth also remains unchanged - and this repeats 'add-infinitum'.

I'll have to see what to do about matethreat or have some limits somehow.

I don't see that it is clear for you You probably will not solve this by having "some limits somehow", it is more of a basic issue, as already pointed out by Álvaro.

When being in check => extend (but do not try nullmove).

When not being in check => try nullmove, and possibly extend in case of mate threat.

You have a lot of entries in your dump with "matethreat" and "check" at the same time. By obeying the rules above your example would stop roughly at ply(16), entering qsearch with depth(0).

Sven

[Chan Rasjid]

I am not sure how this mate-threat extension works. Is it that the checking side, when it plays a null move in stead of the check, will get mated? (you still have not shown us the position...) In that case, I think the answer is to not add extensions, if there are multiple conditions that would trigger an extension. Just use the largest extension. In this case, if both the check and the mate threat request an extension of 1 ply, extend 1 ply.

When a side does nullmove(not in check) and :-
1) if x = nullmove(...) with x >= beta, it is a nullmove success and search() may just return beta;
2) if x <= minus-mate, then it indicates the null side has some form of 'matethreat' and the node is to be extended 1 ply by some expert opinion; rightly it should be the previous move that should have done the 1 ply extention, but it 'did_not_have_presciences', so every move of this node has to have depth = depth+1+ any other extension specific to the move.
In my situation, it means a check move with matethreat keeps extending by 2 ply many times over and so the depth don't go down and search() does not call qsearch until ply > 120.

The dump is here:

dump depth 1

ply(118), depth(1), matethreat(0), pc-type(4), move(h1h6), check(4), fifty(0)
ply(117), depth(2), matethreat(0), pc-type(5), move(b7c6), check(0), fifty(1)
ply(116), depth(2), matethreat(0), pc-type(2), move(b5c6), check(2), fifty(0)
ply(115), depth(3), matethreat(0), pc-type(5), move(b8b7), check(0), fifty(16)
ply(114), depth(3), matethreat(1), pc-type(6), move(a6b7), check(6), fifty(15)
ply(113), depth(3), matethreat(0), pc-type(5), move(a7b8), check(0), fifty(14)
ply(112), depth(3), matethreat(1), pc-type(6), move(c6a6), check(6), fifty(13)
ply(111), depth(3), matethreat(0), pc-type(5), move(b7a7), check(0), fifty(12)
ply(110), depth(3), matethreat(1), pc-type(6), move(d6c6), check(6), fifty(11)
ply(109), depth(3), matethreat(0), pc-type(5), move(b8b7), check(0), fifty(10)
ply(108), depth(3), matethreat(1), pc-type(6), move(c6d6), check(6), fifty(9)
ply(107), depth(3), matethreat(0), pc-type(5), move(c7b8), check(0), fifty(8)
ply(106), depth(3), matethreat(1), pc-type(6), move(g6c6), check(6), fifty(7)
ply(105), depth(3), matethreat(0), pc-type(5), move(d6c7), check(0), fifty(6)
ply(104), depth(3), matethreat(1), pc-type(6), move(e8g6), check(6), fifty(5)
ply(103), depth(3), matethreat(0), pc-type(5), move(e7d6), check(0), fifty(4)
ply(102), depth(3), matethreat(1), pc-type(6), move(g6e8), check(6), fifty(3)
ply(101), depth(3), matethreat(0), pc-type(5), move(f6e7), check(0), fifty(2)
ply(100), depth(3), matethreat(1), pc-type(6), move(e4g6), check(6), fifty(1)
ply(99), depth(3), matethreat(0), pc-type(5), move(f7f6), check(0), fifty(0)
ply(98), depth(3), matethreat(1), pc-type(1), move(h7h8n), check(3), fifty(1)
ply(97), depth(3), matethreat(0), pc-type(5), move(g8f7), check(0), fifty(0)
ply(96), depth(3), matethreat(1), pc-type(1), move(h6h7), check(1), fifty(5)
ply(95), depth(3), matethreat(0), pc-type(5), move(h7g8), check(0), fifty(4)
ply(94), depth(3), matethreat(1), pc-type(6), move(e8e4), check(6), fifty(3)
ply(93), depth(3), matethreat(0), pc-type(5), move(g6h7), check(0), fifty(2)
ply(92), depth(3), matethreat(1), pc-type(6), move(b8e8), check(6), fifty(1)
ply(91), depth(3), matethreat(0), pc-type(5), move(g7g6), check(0), fifty(0)
ply(90), depth(3), matethreat(1), pc-type(1), move(h5h6), check(1), fifty(3)
ply(89), depth(3), matethreat(0), pc-type(5), move(g8g7), check(0), fifty(2)
ply(88), depth(3), matethreat(1), pc-type(6), move(a7b8), check(6), fifty(1)
ply(87), depth(3), matethreat(0), pc-type(5), move(g7g8), check(0), fifty(0)
ply(86), depth(3), matethreat(1), pc-type(6), move(b8a7), check(6), fifty(1)
ply(85), depth(3), matethreat(0), pc-type(5), move(g6g7), check(0), fifty(0)
ply(84), depth(3), matethreat(1), pc-type(1), move(h4h5), check(1), fifty(1)
ply(83), depth(3), matethreat(0), pc-type(5), move(g5g6), check(0), fifty(0)
ply(82), depth(3), matethreat(1), pc-type(1), move(h2h4), check(1), fifty(17)
ply(81), depth(3), matethreat(0), pc-type(5), move(f4g5), check(0), fifty(16)
ply(80), depth(3), matethreat(1), pc-type(6), move(e8b8), check(6), fifty(15)
ply(79), depth(3), matethreat(0), pc-type(5), move(e3f4), check(0), fifty(14)
ply(78), depth(3), matethreat(1), pc-type(6), move(d7e8), check(6), fifty(13)
ply(77), depth(3), matethreat(0), pc-type(5), move(d4e3), check(0), fifty(12)
ply(76), depth(3), matethreat(1), pc-type(6), move(e7d7), check(6), fifty(11)
ply(75), depth(3), matethreat(0), pc-type(5), move(e5d4), check(0), fifty(10)
ply(74), depth(3), matethreat(1), pc-type(6), move(d7e7), check(6), fifty(9)
ply(73), depth(3), matethreat(0), pc-type(5), move(d6e5), check(0), fifty(8)
ply(72), depth(3), matethreat(1), pc-type(6), move(e8d7), check(6), fifty(7)
ply(71), depth(3), matethreat(0), pc-type(5), move(e7d6), check(0), fifty(6)
ply(70), depth(3), matethreat(1), pc-type(6), move(g6e8), check(6), fifty(5)
ply(69), depth(3), matethreat(0), pc-type(5), move(e6e7), check(0), fifty(4)
ply(68), depth(3), matethreat(1), pc-type(6), move(g5g6), check(6), fifty(3)
ply(67), depth(3), matethreat(0), pc-type(5), move(e5e6), check(0), fifty(2)
ply(66), depth(3), matethreat(1), pc-type(6), move(h6g5), check(6), fifty(1)
ply(65), depth(3), matethreat(0), pc-type(5), move(f5e5), check(0), fifty(0)
ply(64), depth(3), matethreat(1), pc-type(1), move(g2g4), check(1), fifty(28)
ply(63), depth(3), matethreat(0), pc-type(5), move(e6f5), check(0), fifty(27)
ply(62), depth(3), matethreat(1), pc-type(6), move(h7h6), check(6), fifty(26)
ply(61), depth(3), matethreat(0), pc-type(5), move(e7e6), check(0), fifty(25)
ply(60), depth(3), matethreat(1), pc-type(6), move(h6h7), check(6), fifty(24)
ply(59), depth(3), matethreat(0), pc-type(5), move(f6e7), check(0), fifty(23)
ply(58), depth(3), matethreat(1), pc-type(6), move(h7h6), check(6), fifty(22)
ply(57), depth(3), matethreat(0), pc-type(5), move(f7f6), check(0), fifty(21)
ply(56), depth(3), matethreat(1), pc-type(6), move(h6h7), check(6), fifty(20)
ply(55), depth(3), matethreat(0), pc-type(5), move(f8f7), check(0), fifty(19)
ply(54), depth(3), matethreat(1), pc-type(6), move(g6h6), check(6), fifty(18)
ply(53), depth(3), matethreat(0), pc-type(5), move(g8f8), check(0), fifty(17)
ply(52), depth(3), matethreat(1), pc-type(6), move(h6g6), check(6), fifty(16)
ply(51), depth(3), matethreat(0), pc-type(5), move(h8g8), check(0), fifty(15)
ply(50), depth(3), matethreat(1), pc-type(6), move(g5h6), check(6), fifty(14)
ply(49), depth(3), matethreat(0), pc-type(5), move(g7h8), check(0), fifty(13)
ply(48), depth(3), matethreat(1), pc-type(6), move(d8g5), check(6), fifty(12)
ply(47), depth(3), matethreat(0), pc-type(5), move(f8g7), check(0), fifty(11)
ply(46), depth(3), matethreat(1), pc-type(6), move(d7d8), check(6), fifty(10)
ply(45), depth(3), matethreat(0), pc-type(5), move(e7f8), check(0), fifty(9)
ply(44), depth(3), matethreat(1), pc-type(6), move(c6d7), check(6), fifty(8)
ply(43), depth(3), matethreat(0), pc-type(5), move(d6e7), check(0), fifty(7)
ply(42), depth(3), matethreat(1), pc-type(6), move(e8c6), check(6), fifty(6)
ply(41), depth(3), matethreat(0), pc-type(5), move(e7d6), check(0), fifty(5)
ply(40), depth(3), matethreat(1), pc-type(6), move(g6e8), check(6), fifty(4)
ply(39), depth(3), matethreat(0), pc-type(5), move(d7e7), check(0), fifty(3)
ply(38), depth(3), matethreat(1), pc-type(2), move(d3b5), check(2), fifty(2)
ply(37), depth(3), matethreat(0), pc-type(5), move(d6d7), check(0), fifty(1)
ply(36), depth(3), matethreat(1), pc-type(6), move(e4g6), check(6), fifty(0)
ply(35), depth(3), matethreat(0), pc-type(1), move(b6c5), check(0), fifty(0)
ply(34), depth(3), matethreat(1), pc-type(1), move(c4c5), check(1), fifty(7)
ply(33), depth(3), matethreat(0), pc-type(5), move(e5d6), check(0), fifty(6)
ply(32), depth(3), matethreat(1), pc-type(6), move(g6e4), check(6), fifty(5)
ply(31), depth(3), matethreat(0), pc-type(5), move(f6e5), check(0), fifty(4)
ply(30), depth(3), matethreat(1), pc-type(6), move(e4g6), check(6), fifty(3)
ply(29), depth(3), matethreat(0), pc-type(5), move(e7f6), check(0), fifty(2)
ply(28), depth(3), matethreat(1), pc-type(6), move(g6e4), check(6), fifty(1)
ply(27), depth(3), matethreat(0), pc-type(5), move(e6e7), check(0), fifty(0)
ply(26), depth(3), matethreat(1), pc-type(6), move(h7g6), check(6), fifty(1)
ply(25), depth(3), matethreat(0), pc-type(5), move(f7e6), check(0), fifty(0)
ply(24), depth(3), matethreat(0), pc-type(6), move(h5h7), check(6), fifty(0)
ply(23), depth(4), matethreat(0), pc-type(1), move(g7g6), check(0), fifty(1)
ply(22), depth(4), matethreat(0), pc-type(6), move(g4h5), check(6), fifty(0)
ply(21), depth(5), matethreat(0), pc-type(2), move(a4b3), check(0), fifty(0)
ply(20), depth(6), matethreat(0), pc-type(6), move(g5g4), check(0), fifty(11)
ply(19), depth(7), matethreat(0), pc-type(5), move(e7f7), check(0), fifty(10)
ply(18), depth(7), matethreat(1), pc-type(6), move(d5g5), check(6), fifty(9)
ply(17), depth(7), matethreat(0), pc-type(5), move(e6e7), check(0), fifty(8)
ply(16), depth(7), matethreat(1), pc-type(6), move(d8d5), check(6), fifty(7)
ply(15), depth(7), matethreat(0), pc-type(5), move(f6e6), check(0), fifty(6)
ply(14), depth(7), matethreat(1), pc-type(6), move(d5d8), check(6), fifty(5)
ply(13), depth(7), matethreat(0), pc-type(5), move(g6f6), check(0), fifty(4)
ply(12), depth(7), matethreat(1), pc-type(2), move(f1d3), check(2), fifty(3)
ply(11), depth(7), matethreat(0), pc-type(5), move(f7g6), check(0), fifty(2)
ply(10), depth(7), matethreat(1), pc-type(6), move(d8d5), check(6), fifty(1)
ply(9), depth(7), matethreat(0), pc-type(5), move(g8f7), check(0), fifty(0)
ply(8), depth(7), matethreat(0), pc-type(6), move(e7d8), check(6), fifty(0)
ply(7), depth(8), matethreat(0), pc-type(4), move(a8d8), check(0), fifty(1)
ply(6), depth(8), matethreat(1), pc-type(4), move(d1d8), check(4), fifty(0)
ply(5), depth(8), matethreat(0), pc-type(4), move(f8f2), check(0), fifty(4)
ply(4), depth(9), matethreat(0), pc-type(3), move(d2b3), check(0), fifty(3)
ply(3), depth(10), matethreat(-1), pc-type(2), move(c6a4), check(0), fifty(2)
ply(2), depth(11), matethreat(-1), pc-type(5), move(c1b1), check(0), fifty(1)
ply(1), depth(11), matethreat(0), pc-type(6), move(d4c3), check(6), fifty(0)
ply(0), depth(6), matethreat(0), pc-type(6), move(a3e7), check(0), fifty(0)

//position at root - white to move (a3e7, d4c3,...)
H1... ...A1
wR xX wB xX wR wK xX xX
wP wP wP xX wN xX xX wP
xX xX xX xX xX xX xX wQ
xX bP xX xX bQ wP xX xX
xX xX xX xX xX xX xX xX
xX xX xX xX xX bB bP xX
bP bP xX bN xX xX xX bP
xX bK bR xX xX xX xX bR

Rasjid

[Chan Rasjid]

In RomiChess I extend mate threats from null move by two ply. However, no line is allowed to go more than 12 ply past the iteration depth.

I am currently testing extensions without limiting the max number of plies per line allowed just to see how search works. Limiting extension as you do would never go to unexpected high plies. The other way without limit should work as long as matethreat is not added if the previous move was extended in which case there never could be any extension by 2 ply for a move.

Rasjid

[Chan Rasjid]

You probably shouldn't do a null-move search at all if you are in check. What does your move generator think of capturing kings? Is that what is returning the mate score? If that's the case, you are effectively extending every mate evasion.

Everything is clear now. I added a debug variable to printout 'matethreat'; a node does nullmove and detected matethreat, so :
depth_to_search = depth + matethreat (depth +1). This is the depth printed and is the same as the previous depth; it also searches a check move, so the next depth also remains unchanged - and this repeats 'add-infinitum'.

I'll have to see what to do about matethreat or have some limits somehow.

I don't see that it is clear for you You probably will not solve this by having "some limits somehow", it is more of a basic issue, as already pointed out by Álvaro.

When being in check => extend (but do not try nullmove).

When not being in check => try nullmove, and possibly extend in case of mate threat.

You have a lot of entries in your dump with "matethreat" and "check" at the same time. By obeying the rules above your example would stop roughly at ply(16), entering qsearch with depth(0).

Sven

My explanation is correct. Nullmove is never done when a node is in-check. search() could go on with the depth remaining the same from one call to the next if a move could be extended by 2 ply consecutively by the same side even if the intervening side does no extension... so qsearch() would never be called.

My situation was a nullmove was done and matethreat was detected and the node searches an extended check-move - so a full 2 ply extension for this move.

Rasjid.

[Chan Rasjid]

The position is this:
[d]r4rk1/p3n1pp/1pb5/8/2Pq2p1/Q7/P2N1PPP/2KR1B1R w - - 0 1

Rasjid

[hgm]

When a side does nullmove(not in check) and :-
1) if x = nullmove(...) with x >= beta, it is a nullmove success and search() may just return beta;
2) if x <= minus-mate, then it indicates the null side has some form of 'matethreat' and the node is to be extended 1 ply by some expert opinion; rightly it should be the previous move that should have done the 1 ply extention, but it 'did_not_have_presciences', so every move of this node has to have depth = depth+1+ any other extension specific to the move.
In my situation, it means a check move with matethreat keeps extending by 2 ply many times over and so the depth don't go down and search() does not call qsearch until ply > 120.

This obviously cannot work. As you can see from the trace, at some point one side will create a mate threat (Qb2# in the example), and then the other will start chasing the King over the board with checks. As the evasions are now all mate threats, (as Qb2# remains possible), both the evasions and the checks are extended. And the checking side can pretty much hold that up forever, without repetitions: chase the king over the board on many different squares, check it from a different direction if it returns to a square where it has already been, then check with a capture, so that it can go through the entire sequence again, allow an evasion that is a capture and go through the sequence again, etc., etc.

[Chan Rasjid]

When a side does nullmove(not in check) and :-
1) if x = nullmove(...) with x >= beta, it is a nullmove success and search() may just return beta;
2) if x <= minus-mate, then it indicates the null side has some form of 'matethreat' and the node is to be extended 1 ply by some expert opinion; rightly it should be the previous move that should have done the 1 ply extention, but it 'did_not_have_presciences', so every move of this node has to have depth = depth+1+ any other extension specific to the move.
In my situation, it means a check move with matethreat keeps extending by 2 ply many times over and so the depth don't go down and search() does not call qsearch until ply > 120.

This obviously cannot work. As you can see from the trace, at some point one side will create a mate threat (Qb2# in the example), and then the other will start chasing the King over the board with checks. As the evasions are now all mate threats, (as Qb2# remains possible), both the evasions and the checks are extended. And the checking side can pretty much hold that up forever, without repetitions: chase the king over the board on many different squares, check it from a different direction if it returns to a square where it has already been, then check with a capture, so that it can go through the entire sequence again, allow an evasion that is a capture and go through the sequence again, etc., etc.

I don't know what is meant by "This obviously cannot work" or what should be learned from this type of situation.

Rasjid.

[hgm]

What is meant is that you cannot indefinitely extend moves for both sides. Which is what your scheme does. Both mate threats and checks can go on indefinitely. So you cannot afford to extend the both without running into search explosions.

(Full-move) extensions are dangerous things. You can only afford them if there is a guarantee that the condition for extension cannot be permanent. We are just lucky that in orthodox Chess indefinite mutual checking is not possible, or even a simple check extension would not be affordable, and crash our engine. Like I exerienced in Xiangqi, Nightrider Chess or with unequal Kings.

This is also a big problem in drop games like Shogi. Check-drops are much more dangerous and relevant moves at the branchtips than captures. So a position where a check-drop is possible is hardly quiet. But considering them in QS leads to a search explosion, as the check-drops just go on forever: You drop, sometimes the dropped piece is captured, but other times he interposed a piece and you capture that (with check) to get a piece back in hand to drop that again with check, etc. I have not found a way to solve that yet.