Why search() reaching max ply of > 120 ?

[Chan Rasjid]

Hello,

My program has been plagued for some time with the full search sometimes reaching the near maximum ply of 120. I don't expect it to happen at all. From what I understand, it could happen only 'unnaturally' through perpetual checks. I currently don't limit my check extensions and almost extend all checks one full ply. But there is the codes for repetition detection and repeat nodes will not be searched. This repetition detection is not done in qsearch as I think perpetual checks cannot repeat there. I can't understand what is happening.

Does anyone know what is wrong?

Best Regards,
Rasjid

[AlvaroBegue]

Just debug your program. Print out the stack of moves that lead to the position with depth 120, and you will see what's going on.

[Chan Rasjid]

Just debug your program. Print out the stack of moves that lead to the position with depth 120, and you will see what's going on.

OK, I think it is the way to find out. I was thinking there is a simple explanation that I miss. The other thing is I am not sure nullmove is getting in the way.

I'll check again.

Thanks,
Rasjid

[Sven]

My program has been plagued for some time with the full search sometimes reaching the near maximum ply of 120. I don't expect it to happen at all. From what I understand, it could happen only 'unnaturally' through perpetual checks. I currently don't limit my check extensions and almost extend all checks one full ply. But there is the codes for repetition detection and repeat nodes will not be searched. This repetition detection is not done in qsearch as I think perpetual checks cannot repeat there. I can't understand what is happening.

Does anyone know what is wrong?

From your posting I am not yet sure what really happens.

a) Does your program sometimes reach depth 120 within full search, i.e. without even starting qsearch?

b) Or does it reach depth 120 within qsearch?

c) Or does it reach iteration no. 120 sometimes?

Case a) would sound for me like having at least two cooperative bugs, one in (check) extension code *and* one in repetition detection. I don't think that it could be only one bug in "rep" since you would not reach 120 plies of full search without extensions getting out of control. Also only wrong extension code should not drive you to depth 120 with a correct rep detection.

Case b) would mean that your qsearch does more than searching captures and promotions, since the number of consecutive qsearch moves until the game is over will never exceed 46 to my knowledge (2x8 promotions + 2x15 captures is definitely an upper bound although there is surely a smaller value for the upper bound).

Case c) can happen for instance if you find a forced draw and continue searching iteration by iteration, always finding the same PV. I would not worry too much about that one.


To proceed with debugging this problem, I would definitely follow the advice given by Álvaro and write a function that dumps the current line from the root node down to the current node, and call it whenever you enter a new node and the distance to the root node exceeds some "abnormal" limit, like 80 plies. To avoid getting 200 TB of output you might also want this special function to terminate the whole program after being called X times.

Nullmove usually does not match this pattern since it is a reduction, not an extension, so I would not suspect it here.

Sven

[Chan Rasjid]

Hello,

I can only dump the moves by unwinding the move-stack. It hits ply 119 at the start of full_search(), depth == 1, ply == 119.

check 6 means a queen move that checks - and check is always extended so it does no enter qsearch.

I can't fully understand. It seems a perpetual check by the queen without repetition of positions (I think there is no repeat nodes as my rep codes should have detected it and returns) - can it reach such a high ply.

dump depth 1

ply 118, move e8e5, check 6
ply 117, move c6d5, check 0
ply 116, move e5e8, check 6
ply 115, move c5c6, check 0
ply 114, move e4e5, check 6
ply 113, move c4c5, check 0
ply 112, move e5e4, check 6
ply 111, move d4c4, check 0
ply 110, move g3e5, check 6
ply 109, move e3d4, check 0
ply 108, move h4g3, check 6
ply 107, move f2e3, check 0
ply 106, move h3h4, check 6
ply 105, move f1f2, check 0
ply 104, move g3h3, check 6
ply 103, move g1f1, check 0
ply 102, move f3g3, check 6
ply 101, move f1g1, check 0
ply 100, move e3f3, check 6
ply 99, move g1f1, check 0
ply 98, move e2e3, check 6
ply 97, move f1g1, check 0
ply 96, move g4e2, check 6
ply 95, move g2f1, check 0
ply 94, move f4g4, check 6
ply 93, move h2g2, check 0
ply 92, move f3f4, check 6
ply 91, move h1h2, check 0
ply 90, move f4f3, check 6
ply 89, move g1h1, check 0
ply 88, move h3h1, check 4
ply 87, move f2g1, check 0
ply 86, move f5f4, check 6
ply 85, move c7f4, check 0
ply 84, move g6f5, check 6
ply 83, move e3f2, check 0
ply 82, move h8h3, check 4
ply 81, move f2e3, check 0
ply 80, move e4e3, check 1
ply 79, move f3f2, check 0
ply 78, move e5e4, check 1
ply 77, move e4f3, check 0
ply 76, move h5g6, check 6
ply 75, move f5e4, check 0
ply 74, move e8h5, check 6
ply 73, move e6f5, check 0
ply 72, move h5e8, check 6
ply 71, move f7e6, check 0
ply 70, move g4h5, check 6
ply 69, move e6f7, check 0
ply 68, move f3g4, check 6
ply 67, move f5e6, check 0
ply 66, move g2f3, check 6
ply 65, move e4f5, check 0
ply 64, move h3g2, check 6
ply 63, move f3e4, check 0
ply 62, move h4h3, check 6
ply 61, move f2f3, check 0
ply 60, move h3h4, check 6
ply 59, move f1f2, check 0
ply 58, move g3h3, check 6
ply 57, move e1f1, check 0
ply 56, move f4g3, check 6
ply 55, move e2e1, check 0
ply 54, move d4d3, check 1
ply 53, move f3e2, check 0
ply 52, move h2f4, check 6
ply 51, move f2f3, check 0
ply 50, move h7h2, check 6
ply 49, move e3f2, check 0
ply 48, move d5d4, check 1
ply 47, move d4e3, check 0
ply 46, move e6e5, check 1
ply 45, move d3d4, check 0
ply 44, move h6h7, check 6
ply 43, move e3d3, check 0
ply 42, move h4h6, check 6
ply 41, move f2e3, check 0
ply 40, move h3h4, check 6
ply 39, move f1f2, check 0
ply 38, move e3h3, check 6
ply 37, move e1f1, check 0
ply 36, move f3e3, check 6
ply 35, move f1e1, check 0
ply 34, move g4f3, check 6
ply 33, move g1f1, check 0
ply 32, move f3g4, check 6
ply 31, move h1g1, check 0
ply 30, move e3f3, check 6
ply 29, move g1h1, check 0
ply 28, move h3e3, check 6
ply 27, move g2g1, check 0
ply 26, move e3h3, check 6
ply 25, move g1g2, check 0
ply 24, move e4e3, check 6
ply 23, move f7c7, check 0
ply 22, move b7a8, check 0
ply 21, move c6b6, check 4
ply 20, move c8b7, check 0
ply 19, move g2g1, check 0
ply 18, move d4e4, check 6
ply 17, move c1c6, check 0
ply 16, move e3d4, check 0
ply 15, move g1g2, check 0
ply 14, move f3e3, check 6
ply 13, move h1g1, check 0
ply 12, move e2f3, check 6
ply 11, move g2h1, check 0
ply 10, move e3e2, check 6
ply 9, move g1g2, check 0
ply 8, move b3e3, check 6
ply 7, move g2h3, check 0
ply 6, move b6b3, check 0
ply 5, move d2a5, check 0
ply 4, move b7b6, check 0
ply 3, move a5b6, check 0
ply 2, move h4h3, check 0
ply 1, move a4a5, check 0
ply 0, move d7c8, check 0

Rasjid

[hgm]

If you only extend either checks or check-evasions, and not both, this should not be posible in orthodox Chess (where mutual perpetual check is not possible). As suggested, best way to debug is to print all moves in the branch leading to this high deplth.

In early versions of Fairy-Max there was a rare crashing problem smilar to what you describe. It was caused by a hash-key bug that strongly drove up key collision rate (not enough bits in the random function generating the Zobrist keys). This sometimes caused a collission between a position after null move, and a position where the King could be captured, making Fairy-Max falsely think it was in check (and thus extend its real moves search as alternative for the low-failing null move as if it was a check-evasion). If this hapened on a check, both the check and the evasion were extended, producing an infinite regression.

[Chan Rasjid]

Hello,

I found I could print out pc-type and fifty counter; the position is different as they are not reproducible.
type 1= pawn, 2 = bishop, 3=knight, 4=rook, 5=king, 6=queen.

Only checks is extended a full ply; other non-checking moves may be extended, but I can't dump them.

edit: pc-type pawn and check queen means and indirect check.

dump depth 1

ply(118), pc-type(1) move(f5g4), check(0) fifty(0)
ply(117), pc-type(1) move(g3g4), check(1) fifty(0)
ply(116), pc-type(5) move(g6h5), check(0) fifty(4)
ply(115), pc-type(6) move(h4h5), check(6) fifty(3)
ply(114), pc-type(5) move(g5g6), check(0) fifty(2)
ply(113), pc-type(6) move(h8h4), check(6) fifty(1)
ply(112), pc-type(5) move(f4g5), check(0) fifty(0)
ply(111), pc-type(1) move(g2g3), check(1) fifty(36)
ply(110), pc-type(5) move(e5f4), check(0) fifty(35)
ply(109), pc-type(6) move(d8h8), check(6) fifty(34)
ply(108), pc-type(5) move(f6e5), check(0) fifty(33)
ply(107), pc-type(6) move(d7d8), check(6) fifty(32)
ply(106), pc-type(5) move(f7f6), check(0) fifty(31)
ply(105), pc-type(6) move(d6d7), check(6) fifty(30)
ply(104), pc-type(5) move(f6f7), check(0) fifty(29)
ply(103), pc-type(6) move(b8d6), check(6) fifty(28)
ply(102), pc-type(5) move(e5f6), check(0) fifty(27)
ply(101), pc-type(6) move(b7b8), check(6) fifty(26)
ply(100), pc-type(5) move(e4e5), check(0) fifty(25)
ply(99), pc-type(6) move(b6b7), check(6) fifty(24)
ply(98), pc-type(5) move(d4e4), check(0) fifty(23)
ply(97), pc-type(6) move(c6b6), check(6) fifty(22)
ply(96), pc-type(5) move(c4d4), check(0) fifty(21)
ply(95), pc-type(6) move(d6c6), check(6) fifty(20)
ply(94), pc-type(5) move(d4c4), check(0) fifty(19)
ply(93), pc-type(6) move(e7d6), check(6) fifty(18)
ply(92), pc-type(5) move(e4d4), check(0) fifty(17)
ply(91), pc-type(6) move(g7e7), check(6) fifty(16)
ply(90), pc-type(5) move(e5e4), check(0) fifty(15)
ply(89), pc-type(6) move(f7g7), check(6) fifty(14)
ply(88), pc-type(5) move(d5e5), check(0) fifty(13)
ply(87), pc-type(6) move(c7f7), check(6) fifty(12)
ply(86), pc-type(5) move(e5d5), check(0) fifty(11)
ply(85), pc-type(6) move(c6c7), check(6) fifty(10)
ply(84), pc-type(5) move(e4e5), check(0) fifty(9)
ply(83), pc-type(6) move(f6c6), check(6) fifty(8)
ply(82), pc-type(5) move(d4e4), check(0) fifty(7)
ply(81), pc-type(6) move(e6f6), check(6) fifty(6)
ply(80), pc-type(5) move(c4d4), check(0) fifty(5)
ply(79), pc-type(6) move(d7e6), check(6) fifty(4)
ply(78), pc-type(5) move(b5c4), check(0) fifty(3)
ply(77), pc-type(6) move(c7d7), check(6) fifty(2)
ply(76), pc-type(5) move(a5b5), check(0) fifty(1)
ply(75), pc-type(6) move(b8c7), check(6) fifty(0)
ply(74), pc-type(5) move(b4a5), check(0) fifty(27)
ply(73), pc-type(6) move(c8b8), check(6) fifty(26)
ply(72), pc-type(5) move(c5b4), check(0) fifty(25)
ply(71), pc-type(6) move(b7c8), check(6) fifty(24)
ply(70), pc-type(5) move(d5c5), check(0) fifty(23)
ply(69), pc-type(6) move(g7b7), check(6) fifty(22)
ply(68), pc-type(5) move(e5d5), check(0) fifty(21)
ply(67), pc-type(6) move(f7g7), check(6) fifty(20)
ply(66), pc-type(5) move(d5e5), check(0) fifty(19)
ply(65), pc-type(6) move(c7f7), check(6) fifty(18)
ply(64), pc-type(5) move(e5d5), check(0) fifty(17)
ply(63), pc-type(6) move(c6c7), check(6) fifty(16)
ply(62), pc-type(5) move(e4e5), check(0) fifty(15)
ply(61), pc-type(6) move(f6c6), check(6) fifty(14)
ply(60), pc-type(5) move(d4e4), check(0) fifty(13)
ply(59), pc-type(6) move(e6f6), check(6) fifty(12)
ply(58), pc-type(5) move(e4d4), check(0) fifty(11)
ply(57), pc-type(6) move(d7e6), check(6) fifty(10)
ply(56), pc-type(5) move(d3e4), check(0) fifty(9)
ply(55), pc-type(6) move(g7d7), check(6) fifty(8)
ply(54), pc-type(5) move(c3d3), check(0) fifty(7)
ply(53), pc-type(6) move(f7g7), check(6) fifty(6)
ply(52), pc-type(5) move(b3c3), check(0) fifty(5)
ply(51), pc-type(6) move(c7f7), check(6) fifty(4)
ply(50), pc-type(5) move(c2b3), check(0) fifty(3)
ply(49), pc-type(6) move(d6c7), check(6) fifty(2)
ply(48), pc-type(5) move(d2c2), check(0) fifty(1)
ply(47), pc-type(6) move(h6d6), check(6) fifty(0)
ply(46), pc-type(1) move(e4e3), check(0) fifty(0)
ply(45), pc-type(6) move(b6h6), check(6) fifty(17)
ply(44), pc-type(5) move(e3d2), check(0) fifty(16)
ply(43), pc-type(6) move(d8b6), check(6) fifty(15)
ply(42), pc-type(5) move(d4e3), check(0) fifty(14)
ply(41), pc-type(6) move(c7d8), check(6) fifty(13)
ply(40), pc-type(5) move(e5d4), check(0) fifty(12)
ply(39), pc-type(6) move(d7c7), check(6) fifty(11)
ply(38), pc-type(5) move(d5e5), check(0) fifty(10)
ply(37), pc-type(6) move(e7d7), check(6) fifty(9)
ply(36), pc-type(5) move(e5d5), check(0) fifty(8)
ply(35), pc-type(6) move(f7e7), check(6) fifty(7)
ply(34), pc-type(5) move(d5e5), check(0) fifty(6)
ply(33), pc-type(6) move(g7f7), check(6) fifty(5)
ply(32), pc-type(5) move(e5d5), check(0) fifty(4)
ply(31), pc-type(6) move(b7g7), check(6) fifty(3)
ply(30), pc-type(5) move(d5e5), check(0) fifty(2)
ply(29), pc-type(6) move(b8b7), check(6) fifty(1)
ply(28), pc-type(5) move(d6d5), check(0) fifty(0)
ply(27), pc-type(1) move(b7b8q), check(6) fifty(0)
ply(26), pc-type(1) move(e3e2), check(0) fifty(0)
ply(25), pc-type(1) move(b6b7), check(0) fifty(0)
ply(24), pc-type(1) move(f4e3), check(0) fifty(0)
ply(23), pc-type(1) move(b5b6), check(0) fifty(0)
ply(22), pc-type(1) move(g5f4), check(0) fifty(0)
ply(21), pc-type(1) move(a4a5), check(0) fifty(0)
ply(20), pc-type(1) move(g6g5), check(0) fifty(0)
ply(19), pc-type(1) move(f2f4), check(0) fifty(0)
ply(18), pc-type(5) move(e7d6), check(0) fifty(0)
ply(17), pc-type(2) move(a3d6), check(2) fifty(2)
ply(16), pc-type(4) move(d8d6), check(0) fifty(1)
ply(15), pc-type(2) move(b2a3), check(2) fifty(0)
ply(14), pc-type(5) move(f7e7), check(0) fifty(0)
ply(13), pc-type(4) move(b7e7), check(4) fifty(1)
ply(12), pc-type(4) move(f8d8), check(0) fifty(0)
ply(11), pc-type(1) move(b4b5), check(0) fifty(2)
ply(10), pc-type(2) move(d8e7), check(0) fifty(1)
ply(9), pc-type(4) move(b5b7), check(4) fifty(0)
ply(8), pc-type(5) move(g8f7), check(0) fifty(0)
ply(7), pc-type(2) move(b3f7), check(2) fifty(0)
ply(6), pc-type(1) move(f6f5), check(0) fifty(0)
ply(5), pc-type(1) move(a3a4), check(0) fifty(0)
ply(4), pc-type(1) move(g7g6), check(0) fifty(0)
ply(3), pc-type(4) move(b7b5), check(0) fifty(0)
ply(2), pc-type(1) move(h7h6), check(0) fifty(0)
ply(1), pc-type(4) move(e7b7), check(0) fifty(0)
ply(0), pc-type(2) move(b6d8), check(0) fifty(0)

Best Regards,
Rasjid

[hgm]

For one, the moves don't mean much to us if we do not know the root position. But it seams that you are doing moves that are not checks (if that is what check(0) means), but are still extended (or you could have only one of those with root depth = 1). If you extend both checks and evasions, then you should expect this.

I once tried to figure out with Fairy-Max which was better: having a King that moves as a King, or one that moves as a Knight. No way. It always crashed. Because wih unequal Kings it is qite easy to have the 'Kings' chasing each other perpetally. In Xiangqi (or Nightrider Chess) mutual perpetual check is also possible, but not so easy to set up, so there such crashes are rare (lthough they do occur now and then).

[Chan Rasjid]

For one, the moves don't mean much to us if we do not know the root position. But it seams that you are doing moves that are not checks (if that is what check(0) means), but are still extended (or you could have only one of those with root depth = 1). If you extend both checks and evasions, then you should expect this.

I once tried to figure out with Fairy-Max which was better: having a King that moves as a King, or one that moves as a Knight. No way. It always crashed. Because wih unequal Kings it is qite easy to have the 'Kings' chasing each other perpetally. In Xiangqi (or Nightrider Chess) mutual perpetual check is also possible, but not so easy to set up, so there such crashes are rare (lthough they do occur now and then).

Yes, check(0) means non-checking move.

It is just a little beyond me.

I tried :-
1) only checks may be extended; some checks may not be extended; ie I disabled all other non-check extension except possibly at root.
2) I added repetition detection and fifty draw in qsearch() which may have checks and evasion.

fullsearch() still may still hit max ply > 120. Why?

Rasjid

[hgm]

You are saying that you only extend moves that deliver checks, and not those that evade check? If that is your intension, it obviously is not implemented properly. If you look at the sequence of moves you see that the search continues both after the checks and the evasions. If at d=1 an evasion would not be extended, you would be at d=0 after it (i.e. in QSearch), and you would not search any non-capture checks there (as is done in your stack-trace).