Code, algorithms, languages, construction...
-
rgoomes
- Posts: 17
- Joined: Sat Feb 21, 2015 9:41 pm
- Real Name: Ricardo Gomes
Post
by 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!
-
PsyMar
- Posts: 1
- Joined: Tue Mar 10, 2015 10:56 pm
- Real Name: Michael
Post
by 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.
-
rgoomes
- Posts: 17
- Joined: Sat Feb 21, 2015 9:41 pm
- Real Name: Ricardo Gomes
Post
by 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.
-
hyatt
- Posts: 1242
- Joined: Thu Jun 10, 2010 2:13 am
- Real Name: Bob Hyatt (Robert M. Hyatt)
- Location: University of Alabama at Birmingham
-
Contact:
Post
by hyatt » Fri Feb 26, 2016 2:32 am
Shoot... that is where ALL of my hash-related bugs have shown up.
![Smile :)](./images/smilies/icon_e_smile.gif)
(when hashing is enabled.)
-
rgoomes
- Posts: 17
- Joined: Sat Feb 21, 2015 9:41 pm
- Real Name: Ricardo Gomes
Post
by rgoomes » Sun Feb 28, 2016 11:12 pm
hyatt wrote:Shoot... that is where ALL of my hash-related bugs have shown up.
![Smile :)](./images/smilies/icon_e_smile.gif)
(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?
-
hyatt
- Posts: 1242
- Joined: Thu Jun 10, 2010 2:13 am
- Real Name: Bob Hyatt (Robert M. Hyatt)
- Location: University of Alabama at Birmingham
-
Contact:
Post
by 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...
-
sandermvdb
- Posts: 24
- Joined: Wed Jun 01, 2016 3:52 pm
Post
by 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
Post
by 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...
![Wink ;)](./images/smilies/icon_e_wink.gif)
).
-
H.G.Muller
- Posts: 190
- Joined: Sun Jul 14, 2013 10:00 am
- Real Name: H.G. Muller
Post
by 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).