Chasing longer mates with TT

[lojic]

I've been refining my transposition table, and while I expect some bugs still exist, it definitely strengthens the play in the cases I've tested, except the following position where it plays very stupidly:

FEN: 8/8/8/8/2K5/5Q2/6PP/4k3 w - - 0 100 (I use 100 to ensure my engine plays with the endgame PST :) )

Here are the best moves found at each depth with a score when I don't return the score directly from the TT (I still use the best move found in the TT for ordering). The engine proceeds directly to mate in the least number of moves. I annotated "good" if the move did not length mate, and "bad" if it did lengthen mate.

Code: Select all

Best move (1) [11.8] Kc4-d5 bad
Best move (2) [11.7] Qf3-e3 bad
Best move (3) [11.8] Qf3-e3 bad
Best move (4) [11.8] Kc4-d4 good
Best move (5) [11.9] Qf3-d3 bad
Best move (6) [11.9] Kc4-d4 good
Best move (7) [11.95] Ph2-h4 good
Best move (8) [999.93] Kc4-d4 good (mate)

And here are the best moves found when I do return the score directly from the TT. The engine starts moving the white king away!

Code: Select all

Best move (1) [11.8] Kc4-d5 bad
Best move (2) [11.7] Qf3-e3 bad
Best move (3) [11.8] Qf3-e3 bad
Best move (4) [11.8] Kc4-d4 good
Best move (5) [11.9] Qf3-d3 bad
Best move (6) [11.9] Qf3-d5 bad
Best move (7) [12] Pg2-g3 good
Best move (8) [999.93] Kc4-d4 good (mate)
Best move (9) [999.95] Kc4-b3 good (mate)
Best move (10) [999.95] Kc4-c5 bad (longer mate)
Best move (11) [999.95] Kc4-c5 bad (longer mate)

In my alpha-beta, I use the following code to score shorter mates higher. I add the depth (I start at 0 at the root and increase) to MIN-SCORE which is -100000 centipawns.

Code: Select all

(if (is-king-in-check? b)
  (fx+ MIN-SCORE depth)
  0)

So, excluding the TT, my engine will pursue shorter mates with the above code. I expect I didn't properly account for this logic in the context of the TT.

Here's the code to read the TT entry. I think it's typical - using EXACT, ALPHA and BETA types.

Code: Select all

;; Returns (values score move). If no matching entry found, both score and move are #f
(define (read-tt-entry key draft alpha beta)
  (let ([ entry (vecref tt-table (hash-index key)) ])
    (if (and entry (fx= key (tt-zobrist-key entry)))
        ;; Entry found, and it matches the key
        (let ([ best-move (tt-best-move entry) ])
          (if (fx>= (tt-draft entry) draft)
              ;; We have sufficient draft
              (let ([ score (tt-score entry) ]
                    [ type  (tt-type entry)  ])
                (cond [ (fx= NODE-EXACT type)                          (values score best-move) ]
                      [ (and (fx= NODE-ALPHA type) (fx<= score alpha)) (values alpha best-move) ]
                      [ (and (fx= NODE-BETA type) (fx>= score beta))   (values beta best-move)  ]
                      [ else                                           (values #f best-move)    ]))
              ;; Insufficient draft, we can't use the score, but return
              ;; best move
              (values #f best-move)))
        ;; Nothing found
        (values #f #f))))

Before I go on a deep dive debugging this, I just thought I'd check to see if this might be a common problem with TT & mate.

[mvanthoor]

I don't understand. Are you trying to find a bug with mate scoring in the hash table?

For this position, a hash table isn't even needed to see the mate. My engine can see it in about 0.1 second:

Code: Select all

info score cp 1215 depth 1 seldepth 2 time 0 nodes 20 nps 0 pv c4d4
info score cp 1200 depth 2 seldepth 4 time 0 nodes 244 nps 0 pv f3e3 e1f1 e3e4
info score cp 1215 depth 3 seldepth 6 time 0 nodes 1449 nps 0 pv c4d4 e1d2 f3f2 d2c1
info score cp 1240 depth 4 seldepth 8 time 2 nodes 10216 nps 5108000 pv c4d4 e1d2 f3e4 d2c1
info score cp 1240 depth 5 seldepth 10 time 14 nodes 78623 nps 5615929 pv c4d4 e1d2 f3e4 d2c1 d4d5
info score mate 4 depth 6 seldepth 12 time 101 nodes 556553 nps 5510426 pv c4d4 e1d2 f3f2 d2c1 d4c3 c1b1 f2b2
info score mate 4 depth 7 seldepth 14 time 732 nodes 4020071 nps 5491900 pv c4b3 e1d2 f3e4 d2d1 b3c3 d1c1 e4e1
info score mate 4 depth 8 seldepth 16 time 5407 nodes 29488438 nps 5453752 pv c4b3 e1d2 f3e4 d2d1 b3c3 d1c1 e4e1
info score mate 4 depth 9 seldepth 18 time 39850 nodes 215566133 nps 5409439 pv c4b3 e1d2 f3e4 d2d1 b3c3 d1c1 e4e1

[lojic]

I've been refining my transposition table, and while I expect some bugs still exist, it definitely strengthens the play in the cases I've tested, except the following position where it plays very stupidly:

FEN: 8/8/8/8/2K5/5Q2/6PP/4k3 w - - 0 100 (I use 100 to ensure my engine plays with the endgame PST :) )
...

<sigh> it figures - seconds after I post I review the code yet again and notice I was not writing a TT entry in the case of mate/stalemate for some reason. Adding the TT entry for mate/stalemate fixed the problem. Sorry for the noise!

[lojic]

I don't understand. Are you trying to find a bug with mate scoring in the hash table?

For this position, a hash table isn't even needed to see the mate. My engine can see it in about 0.1 second:

Code: Select all

info score cp 1215 depth 1 seldepth 2 time 0 nodes 20 nps 0 pv c4d4
info score cp 1200 depth 2 seldepth 4 time 0 nodes 244 nps 0 pv f3e3 e1f1 e3e4
info score cp 1215 depth 3 seldepth 6 time 0 nodes 1449 nps 0 pv c4d4 e1d2 f3f2 d2c1
info score cp 1240 depth 4 seldepth 8 time 2 nodes 10216 nps 5108000 pv c4d4 e1d2 f3e4 d2c1
info score cp 1240 depth 5 seldepth 10 time 14 nodes 78623 nps 5615929 pv c4d4 e1d2 f3e4 d2c1 d4d5
info score mate 4 depth 6 seldepth 12 time 101 nodes 556553 nps 5510426 pv c4d4 e1d2 f3f2 d2c1 d4c3 c1b1 f2b2
info score mate 4 depth 7 seldepth 14 time 732 nodes 4020071 nps 5491900 pv c4b3 e1d2 f3e4 d2d1 b3c3 d1c1 e4e1
info score mate 4 depth 8 seldepth 16 time 5407 nodes 29488438 nps 5453752 pv c4b3 e1d2 f3e4 d2d1 b3c3 d1c1 e4e1
info score mate 4 depth 9 seldepth 18 time 39850 nodes 215566133 nps 5409439 pv c4b3 e1d2 f3e4 d2d1 b3c3 d1c1 e4e1

Given I clearly stated the problem was specifically with the TT and mate, it's almost as if you didn't read the original post at all, and simply jumped at the chance to mention the speed of your engine again. I don't blame you; I know you're very excited about your Rust engine, and it is much faster than mine.

But, while I have you here, I'm curious about your "seldepth" statistic. What does it represent? It seems to be always double your depth. Are you using check extensions to search deeper?

[lojic]

I've been refining my transposition table, and while I expect some bugs still exist, it definitely strengthens the play in the cases I've tested, except the following position where it plays very stupidly:

FEN: 8/8/8/8/2K5/5Q2/6PP/4k3 w - - 0 100 (I use 100 to ensure my engine plays with the endgame PST :) )
...

<sigh> it figures - seconds after I post I review the code yet again and notice I was not writing a TT entry in the case of mate/stalemate for some reason. Adding the TT entry for mate/stalemate fixed the problem. Sorry for the noise!

Double <sigh> - I'm debugging too fast, and haste makes waste. I had commented out some code in the TT to narrow it down to the EXACT entries, but I inadvertently left it commented out when fixing the omitted TT entry addition, so I thought I fixed it, but the results are identical afterward, so I'll keep debugging. I'll also double check things before continuing to post to cut down on future noise ...

[Ras]

Adding the TT entry for mate/stalemate fixed the problem.

The next thing is mate distance adjustment for mate scores (both winning and losing ones). Otherwise, when you use the hash table in the next move turn, the hash table will have wrong mate distances relative to the new root. See older threads like http://www.talkchess.com/forum3/viewtop ... =7&t=74411 for details.

[mvanthoor]

Given I clearly stated the problem was specifically with the TT and mate, it's almost as if you didn't read the original post at all, and simply jumped at the chance to mention the speed of your engine again. I don't blame you; I know you're very excited about your Rust engine, and it is much faster than mine.

Sorry, that wasn't my intention. I've read your entire post, and it seems to me that you are doing everything correctly. You say that the engine works fine without the TT, and it goes after shorter mates, (so you probably are using the "minus checkmate + ply" way of doing things). You also store the mate score in the hash table, so it should be fine there as well.

Therefore it seems you understand what should be done, but are possibly coding it incorrectly. I cannot help with this, because I can't understand your code.

If you want to test the hash table exclusively, I think you can better set up something like a K+P vs K end game.

Without a hash table, many engines can't find the mate (Rustic can't), because it can't see far enough ahead. You'll need at least 5 ply's for the promotion, and another 10 ply's for the mate, in the best scenario. If your hash table works correctly however, the engine should basically race to depth 30 or something in a few seconds (because there are so many transpositions it can take advantage of), and see the promotion and mate within seconds.

As said, I looks to me as if you understand WHAT you need to code, but made a mistake somewhere in the code, and that's the part I can't help with. The only thing I wanted to show is that for this position, you don't _need_ a hash table, so it's hard to actually test it specifically.

But, while I have you here, I'm curious about your "seldepth" statistic. What does it represent? It seems to be always double your depth. Are you using check extensions to search deeper?

It only doubles the depth in this particular example. "seldepth" is the selective depth. You extend while in check "if in_check { depth += 1}" to prevent going into qsearch while in check (which is bad). Also, if you are in qsearch which searches on top of the depth you are searching, and thus adds ply's, seldepth becomes higher. Later, move reductions and/or other extensions can modify seldepth as well.

In the end, it is basically the greatest depth the engine reached while searching.

[mvanthoor]

<sigh> it figures - seconds after I post I review the code yet again and notice I was not writing a TT entry in the case of mate/stalemate for some reason. Adding the TT entry for mate/stalemate fixed the problem. Sorry for the noise!

Congrats... as I said, you seem to understand what needs to be done, but made a mistake somewhere, with which I (and I think many others here) can't help because of the programming language you use. That is one of the main drawbacks of using a language that is so far removed from the 'normal' imperative/object-oriented way of doing things.

edit: posts seem to be crossing one-another...

Double <sigh> - I'm debugging too fast, and haste makes waste. I had commented out some code in the TT to narrow it down to the EXACT entries, but I inadvertently left it commented out when fixing the omitted TT entry addition, so I thought I fixed it, but the results are identical afterward, so I'll keep debugging. I'll also double check things before continuing to post to cut down on future noise ...

My only advice is... slow down writing the code. Test more often, and smaller pieces. The reason why my hash table (and entire engine) takes so long is because I test each and every function separately. If you make a mistake somewhere in the engine's basics (where the hash table also belongs to), it will cost you hundreds of Elo down the line. Some bugs you might never find if they stack on top of one another.

[lojic]

Adding the TT entry for mate/stalemate fixed the problem.

The next thing is mate distance adjustment for mate scores (both winning and losing ones). Otherwise, when you use the hash table in the next move turn, the hash table will have wrong mate distances relative to the new root. See older threads like http://www.talkchess.com/forum3/viewtop ... =7&t=74411 for details.

Thanks - I'll check out that thread. I've based much of my TT implementation on this archived article by Bruce Moreland, but he doesn't mention anything about mate scoring/adjustments. I haven't been able to find a good pseudocode description of the the basic search w/ TT.

[mvanthoor]

Thanks - I'll check out that thread. I've based much of my TT implementation on this archived article by Bruce Moreland, but he doesn't mention anything about mate scoring/adjustments. I haven't been able to find a good pseudocode description of the the basic search w/ TT.

I assume almost most people are using that article as the basis of their hash table, me included. It is one of the best ones out there.