TT Mate scores

Code, algorithms, languages, construction...

Re: TT Mate scores

Postby rgoomes » Wed Feb 17, 2016 6:32 pm

hyatt wrote:My point was not that you needed the - 1 or + 1, but that you have to carefully look. For example, why not do this:

when you store a mate score, display the tree and print the actual score and the stored score. When you hit on a position with a mate score, display the position, the table score, and the adjusted mate score. You should quickly see what is going wrong.

You could use a simple mate in 3, searched just deeply enough to see it. Then make the expected move and see what kind of table scores you get back (which ought to be mate in 2). That will be a tiny amount of output with the displays I recommended above.


Thanks for the the tip. I tested a simple mate in two K vs KR and immediately found a problem. I noticed that I was storing mate values in the table for positions that didn't have mate (for example king vs king). Later I found that sometimes the best score passed to the store function was incorrect. After fixing this and adjusting correctly the mate scores everything worked for many test positions, except one thing.. sometimes the principal variation had illegal moves. For example for the first test position I get this output:

Code: Select all
info depth 1 score cp 500 nodes 30 nps 29999 time 1 pv b3a3
info depth 2 score cp 600 nodes 255 nps 7727 time 33 pv b3a3 d8c8
info depth 3 score cp 600 nodes 1269 nps 30951 time 41 pv b3a3 d8c8 b7f7
info depth 4 score cp 700 nodes 6492 nps 150976 time 43 pv b3a3 d8c8 b7f7 c8b8
info depth 5 score cp 700 nodes 27997 nps 538403 time 52 pv b3a3 d8c8 b7f7 c8b8 a3a2
info depth 6 score cp 700 nodes 108269 nps 1244471 time 87 pv b3a3 d8c8 b7f7 c8b8 a3a2 b8c8
info depth 7 score cp 700 nodes 417761 nps 1952154 time 214 pv b3a3 d8c8 b7f7 c8b8 a3a2 c6c5 f7f3
info depth 8 score cp 800 nodes 1776687 nps 2400928 time 740 pv b3a3 d8c8 b7f7 c8b8 a3a2 c6c5 f7f6 b8b7
info depth 9 score mate 6 nodes 6722469 nps 2523449 time 2664 pv b3a3 d8c8 b7f7 a2a1r a3a1 c8b8 a1a2 c6c5 a3a8 c8b7 a3a2
info depth 10 score mate 6 nodes 24682574 nps 2597071 time 9504 pv b3a3 d8c8 b7f7 a2a1r a3a1 c8b8 e1f2 c6c5 a1e1 b8a8 e1e8
info depth 11 score mate 6 nodes 85643666 nps 2590395 time 33062 pv b3a3 d8c8 b7f7 a2a1r a3a1 c8b8 e1f2 c6c5 a1e1 b8a8 e1e8


The pv for depth 9 (the first time it finds mate) has a strange sequence "a1a2 c6c5 a3a8 c8b7 a3a2" with illegal moves. I'm not sure why this happens but I have to investigate it more. If I don't find a solution, I'll open a new post if needed.

Thank you again!
rgoomes
 
Posts: 15
Joined: Sat Feb 21, 2015 9:41 pm

Re: TT Mate scores

Postby PsyMar » Thu Feb 25, 2016 10:28 am

I think I see the issue.

Code: Select all
      if(val > alpha){
         alpha = val;
         if(val >= beta)
            break;
         update_pv(it, ply);
      }


Here, if the value >= beta, you exit the loop and go on to store this alpha in the transposition table, but you don't update the PV, meaning the PV could have erroneous moves after the current position. I'm guessing that it's leftover moves from elsewhere in the search that gives you a PV with illegal moves. On subsequent depths, beta is likely set higher by the depth that found mate, and so this problem doesn't occur.

Hope this helps.
PsyMar
 
Posts: 1
Joined: Tue Mar 10, 2015 10:56 pm

Re: TT Mate scores

Postby rgoomes » Thu Feb 25, 2016 7:45 pm

PsyMar wrote:I think I see the issue.

Code: Select all
      if(val > alpha){
         alpha = val;
         if(val >= beta)
            break;
         update_pv(it, ply);
      }


Here, if the value >= beta, you exit the loop and go on to store this alpha in the transposition table, but you don't update the PV, meaning the PV could have erroneous moves after the current position. I'm guessing that it's leftover moves from elsewhere in the search that gives you a PV with illegal moves. On subsequent depths, beta is likely set higher by the depth that found mate, and so this problem doesn't occur.

Hope this helps.


Thank you, but I was already doing that. The problem is somewhere else. As you can see, I'm doing this now:
Code: Select all
if(val > bestscore){
   bestscore = val;
   bestmove = *it;

   if(val > alpha){
      alpha = val;
      update_pv(it, ply);

      if(alpha >= beta)
         break;
   }
}


and then storing in the table:
Code: Select all
tt_store(b, bestmove, score_to_tt(bestscore, ply), orig_alpha, beta, depth);


Lately I've been pretty busy and I don't have time to work on my engine, but I did found a position (8/pp4k1/4p3/3p3Q/3P4/Pn2B1KN/1Pq5/8 w – – 0 46) where the mate scores were wrong (reporting mate in 6 when it's really mate in 8). All this problems only happen when the hashing is enabled.
rgoomes
 
Posts: 15
Joined: Sat Feb 21, 2015 9:41 pm

Re: TT Mate scores

Postby hyatt » Fri Feb 26, 2016 2:32 am

Shoot... that is where ALL of my hash-related bugs have shown up. :) (when hashing is enabled.)
hyatt
 
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Location: University of Alabama at Birmingham

Re: TT Mate scores

Postby rgoomes » Sun Feb 28, 2016 11:12 pm

hyatt wrote:Shoot... that is where ALL of my hash-related bugs have shown up. :) (when hashing is enabled.)


hehehe :)

I just found the problem.. It was pretty simple. I was calculating the node type(flag of the transposition table in the code) after adjusting the best score to be stored in the transposition table.. It now shows the correct mate score after the fix!

About the wrong principal variation it's also simple why it has illegal moves, but I am not quite sure how to address this correctly. Basically the problem is when I'm in a PV-node and I found a hash hit, I just return the score and then the pv could never be updated. One solution is to print the incomplete pv, but for example when it's a mate score it is a bit odd just to show the first moves of the mate sequence. Of course the pv will be replaced at the next depth but.... How do I fix this correctly?
rgoomes
 
Posts: 15
Joined: Sat Feb 21, 2015 9:41 pm

Re: TT Mate scores

Postby hyatt » Mon Feb 29, 2016 5:45 am

You have to fix that. If you get an exact score from hash, do EXACTLY what you do when you calculate and back up a score in quiesce. Ie cut the PV off at previous ply (since there is no move here with an exact score coming from the table...
hyatt
 
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Location: University of Alabama at Birmingham

Re: TT Mate scores

Postby sandermvdb » Sun Apr 02, 2017 7:17 pm

Sorry for bringing up an old thread but I am still struggling a bit with mate scores. I understand that you need to fix a mate score when retrieving or adding it to the transposition table. But should you also do this if it is not an EXACT score? I guess not (but I could be wrong...).
sandermvdb
 
Posts: 24
Joined: Wed Jun 01, 2016 3:52 pm

Re: TT Mate scores

Postby sandermvdb » Sun Apr 02, 2017 9:07 pm

sandermvdb wrote:Sorry for bringing up an old thread but I am still struggling a bit with mate scores. I understand that you need to fix a mate score when retrieving or adding it to the transposition table. But should you also do this if it is not an EXACT score? I guess not (but I could be wrong...).


The reason I am asking this is that I was storing scores in the TT that were > MAX or < MIN. But this only happened if my searchdepth was greater than the matescore that was already found, which is logical! Mate-distance-pruning takes care of this so when I enable this, I don't get this problem.

So also UPPER and LOWER scores should be adjusted (but I could be wrong... ;) ).
sandermvdb
 
Posts: 24
Joined: Wed Jun 01, 2016 3:52 pm

Re: TT Mate scores

Postby H.G.Muller » Sun Apr 02, 2017 10:23 pm

Indeed, all scores and bouns should be adjusted, because the way you propagate them through the minimax tree is basically wrong, and that would break things when you try to transfer them to another node through the TT. The point is that you already give a mated-in-N score to the leaf, when in fact it is a mated-in-N score in the root, and a mated-in-0 score in the leaf. So everywhere along the branch, except in the root, the score used in the search routine is wrong. By subtracting the distance to the root you convert it to the true score (representing the distance from that node to the mate leaf).
H.G.Muller
 
Posts: 167
Joined: Sun Jul 14, 2013 10:00 am

Previous

Return to Programming and Technical Discussions

Who is online

Users browsing this forum: Bing [Bot] and 1 guest