I can't wait until we get some critters of selective evaluation in those transposition tables... I hope you will make your engine as transparent as your process here. You might lose some ELO points though..
Perhaps prepare a 2 prong development, one for insane ELO is current engine tournaments formats and pools, and one for chess user analytical tool.
They may not be possible to maintain into one engine executable. However, at this point of strict alpha beta pruning (right, or i missed a blog), introducing transposition table, it may just be a matter of storage size.. and both objectives would not yet conflict.
I am eager to hear about diagnostic and internal output statistics about the dynamics of transposition table entries and hits (both). and how leaf evaluations of a single root search sub-tree, can grow in table storage size needs per input depth for example.
I also agree that starting the more common, abstract, or polyvalent notion of cache, is best presentation entry point.
And now i will go read your blog... in small chunks, digest and read again.... I just think this is a good thing you do, and wanted to let you know where my curiosity lies.. (together with my focus on full evaluation and input full position information, persistence and retrieval).
Perhaps prepare a 2 prong development, one for insane ELO is current engine tournaments formats and pools, and one for chess user analytical tool.
They may not be possible to maintain into one engine executable. However, at this point of strict alpha beta pruning (right, or i missed a blog), introducing transposition table, it may just be a matter of storage size.. and both objectives would not yet conflict.
I am eager to hear about diagnostic and internal output statistics about the dynamics of transposition table entries and hits (both). and how leaf evaluations of a single root search sub-tree, can grow in table storage size needs per input depth for example.
I also agree that starting the more common, abstract, or polyvalent notion of cache, is best presentation entry point.
And now i will go read your blog... in small chunks, digest and read again.... I just think this is a good thing you do, and wanted to let you know where my curiosity lies.. (together with my focus on full evaluation and input full position information, persistence and retrieval).
@dboing my code is already public and I don't have unrealistic ambitions about success in computer chess competitions. The code can be found here: github.com/likeawizard/chess-go and my current work is focused now in the bitboard branch and I hope to implement piece-square-tables and rewrite and optimize the whole evaluation code.
At some point I already had implemented T-tables and they seemed to work but I had suspicions of some bugs lurking in the code. I am quite confident about the Zobrist hashing working as intended so not sure where the bugs actually were as it was a very naive and simplistic implementation. I was also printing some primitive statistics about the sizes and transposition hits - number of hits divided by size of transposition table entries. In the openings and middle game the percentage was quite low 15~30% and in the endgame with only a few pieces the numbers kept growing to around ~300% which I think do make sense.
It was certainly not well optimized as it barely gave any significant performance gain in the early stages of the game but by lategame the depth increased dramatically.
At some point I already had implemented T-tables and they seemed to work but I had suspicions of some bugs lurking in the code. I am quite confident about the Zobrist hashing working as intended so not sure where the bugs actually were as it was a very naive and simplistic implementation. I was also printing some primitive statistics about the sizes and transposition hits - number of hits divided by size of transposition table entries. In the openings and middle game the percentage was quite low 15~30% and in the endgame with only a few pieces the numbers kept growing to around ~300% which I think do make sense.
It was certainly not well optimized as it barely gave any significant performance gain in the early stages of the game but by lategame the depth increased dramatically.
<Comment deleted by user>
@dboing I appreciate questions and comments a lot.
About iterative deepening - I implemented it right after the blog post about the tree search where I hinted at the approach briefly. And I made another blog about the support of timed play which iterative deepening was the key to. You can find it here- lichess.org/@/likeawizard/blog/time-control-support-is-here/q65JDjjf
I currently do not want to go into a detailed discussion about transposition tables as it is not done and I have not addressed the issue with the attention and care it deserves. I made a very quick implementation to test it out without rigorous understanding and testing. To address it very briefly the transpositions were stored in a hash map with the full Zobrist Hash and it made the distinction between three types of nodes - exact values and then upper/lower bound values. So when a transposition table hit occurred I either returned the eval directly on exact types and on upper/lower bound type nodes I would update alpha/beta accordingly.
You mentioned that you have difficulty with reading the code but the relevant places are here:
TTable definition: github.com/likeawizard/chess-go/blob/master/internal/evaluation/ttable.go
TTable check: github.com/likeawizard/chess-go/blob/master/internal/evaluation/alphabeta.go#L25
TTable store: github.com/likeawizard/chess-go/blob/master/internal/evaluation/alphabeta.go#L77
But as I said before - I would not waste much time on reading into it as it is work in progress that I have for now abandoned to pick up later.
About iterative deepening - I implemented it right after the blog post about the tree search where I hinted at the approach briefly. And I made another blog about the support of timed play which iterative deepening was the key to. You can find it here- lichess.org/@/likeawizard/blog/time-control-support-is-here/q65JDjjf
I currently do not want to go into a detailed discussion about transposition tables as it is not done and I have not addressed the issue with the attention and care it deserves. I made a very quick implementation to test it out without rigorous understanding and testing. To address it very briefly the transpositions were stored in a hash map with the full Zobrist Hash and it made the distinction between three types of nodes - exact values and then upper/lower bound values. So when a transposition table hit occurred I either returned the eval directly on exact types and on upper/lower bound type nodes I would update alpha/beta accordingly.
You mentioned that you have difficulty with reading the code but the relevant places are here:
TTable definition: github.com/likeawizard/chess-go/blob/master/internal/evaluation/ttable.go
TTable check: github.com/likeawizard/chess-go/blob/master/internal/evaluation/alphabeta.go#L25
TTable store: github.com/likeawizard/chess-go/blob/master/internal/evaluation/alphabeta.go#L77
But as I said before - I would not waste much time on reading into it as it is work in progress that I have for now abandoned to pick up later.
reupload of deleted post before #5. sorry.
Thank you for these details and links. Since your efforts come with the best documentation possible, (blog and discussion) starting from high level models that you can explain to yourself, and hence to others on the bandwagon.. I can't help but go haver a look over there....
I hope you don't mind if i keep asking questions, there, or here or in inbox.. I guess i could look at source-code before asking, but then i would also remark here..
So have you started using iterative deepening (did your tree blog cover that, i may have forgotten).
I was thinking that the transposition table made sense more in that context, but, it does already help in Alpha-beta pruning move ordering direction (if i am not mistaken in calling it such). In iterative deepening, since it would apparently increase the number of full evaluations in the intended input depth sub-tree, the hash table would really make it a time saving object, with lots of traffic in, and out (hits). You might get better results then.
I think i remember reading in the chess-programming wiki (hard to find again in that structure), that statistics about single root searches (trees), actually showed that on average (over some experimental spread not mentioned or remembered by me: must be many roots and depths), sorry, that on average it would save time, probably by allowing the memory of shallow evaluations to prevent un-needed expansions on the iterative depth direction.. Hence the transposition table becoming a crucial actor.
I wonder why you (and UCI actually....) do not also look at the whole dynamics by statistics on the entries as well.. And if you have a node typology**, then I think, to control and predict or optimize storage capacity, one would also benefit form having statistics of all node types... unless that makes for obvious ratios between some types..now in strict Alpha-Beta.. But with iterative deepening all sorts of heuristics could come into the picture and make my statistical curiosity, something interesting, also for others and yourself.
** some use the word topology, probably because it is about tree nodes and might change the treatment of further sub-tree expansion per node type, i don't know...
Thank you for these details and links. Since your efforts come with the best documentation possible, (blog and discussion) starting from high level models that you can explain to yourself, and hence to others on the bandwagon.. I can't help but go haver a look over there....
I hope you don't mind if i keep asking questions, there, or here or in inbox.. I guess i could look at source-code before asking, but then i would also remark here..
So have you started using iterative deepening (did your tree blog cover that, i may have forgotten).
I was thinking that the transposition table made sense more in that context, but, it does already help in Alpha-beta pruning move ordering direction (if i am not mistaken in calling it such). In iterative deepening, since it would apparently increase the number of full evaluations in the intended input depth sub-tree, the hash table would really make it a time saving object, with lots of traffic in, and out (hits). You might get better results then.
I think i remember reading in the chess-programming wiki (hard to find again in that structure), that statistics about single root searches (trees), actually showed that on average (over some experimental spread not mentioned or remembered by me: must be many roots and depths), sorry, that on average it would save time, probably by allowing the memory of shallow evaluations to prevent un-needed expansions on the iterative depth direction.. Hence the transposition table becoming a crucial actor.
I wonder why you (and UCI actually....) do not also look at the whole dynamics by statistics on the entries as well.. And if you have a node typology**, then I think, to control and predict or optimize storage capacity, one would also benefit form having statistics of all node types... unless that makes for obvious ratios between some types..now in strict Alpha-Beta.. But with iterative deepening all sorts of heuristics could come into the picture and make my statistical curiosity, something interesting, also for others and yourself.
** some use the word topology, probably because it is about tree nodes and might change the treatment of further sub-tree expansion per node type, i don't know...