Usually, hash tables contain information that is continuously written upon over and over during a game. However, when analyzing a single position it is possible to prime a meaningful storage of the information by moving pieces back and the forth from the starting position and confuting 'by hand' all the variations that the opponent might try.
For instance, in this position from the vinvin talckchess 2020 set:
[d]2bqrr1k/p5b1/1p1p2pp/nPpBp3/P1P1N2P/3PN1P1/R4P1K/3Q1R2 w - -
Stockfish 11 will try for a long time to play 1)h5 (+2.5). However, if you show it the right plan with 1)Nc3, 2)Be4 and 3)Ced5, by pausing 30 seconds or so between the alternative moves that the program will throw to you, after a while it will acknowledge that this is the right plan, giving it also a higher score (more than 3). Once learned that it this the right thing to do, Stockfish will stick to it, i.e., this information stored in the hash memory will not be lost even if you keep analyzing the original position over and over.
Now my question is. Is it possible to try to automatize this search of the best plan, by throwing (reasonable) moves to the program? Oxyron, made the interesting suggestion to run, after an infinite analysis, a match with another engine, in order to avoid being stuck in a wrong plan. I tried this suggestion but I had no luck. Any other method to fill up the hash table in a meaningful way?
Meaningful ageing of a hash table
Moderators: hgm, Rebel, chrisw
-
hgm
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Meaningful ageing of a hash table
What exactly do you want to automate? You want to have a GUI throw random moves at an engine in the hope that this will uncover a line that is better than the one the engine prefers itself?
This has very little to do with hash-table ageing. Most engines allow one to 'back-propagate' scores by analyzing a position, and then taking back the moves that led to it. Engines that very heavily prune and reduce tend to mask the best line by a satisfactory one, especially if it is a winning line; the score in that line will increase with depth (because you are winning), and alternative lines that at the same depth would be better are never able to get above it, because of the depth disadvantage they have.
On average (i.e. Elo-wise) this is the best way to search. But sometimes it backfires. It seems you want to have an external agent that overrules the optimized search strategy of the engine in the lower plies. Especially your requirement that it should try 'reasonable' moves there is problematic; it means you would still need some engine to decide what is reasonable, an engine that prunes much less (and will thus unavoidably be much weaker).
It would be much better if the engine used for analysis had an option to force this, and limit the reductions awarded in the first N ply.
Of course you could also start with doing a multi-PV search, forcing the engine to search the root moves it deems sub-optimal on par with the main line. And then hope that forcing the first move will be enough to make it discover the best plan. Once it has discovered this plan, you should be able to switch back to single-PV mode.
This has very little to do with hash-table ageing. Most engines allow one to 'back-propagate' scores by analyzing a position, and then taking back the moves that led to it. Engines that very heavily prune and reduce tend to mask the best line by a satisfactory one, especially if it is a winning line; the score in that line will increase with depth (because you are winning), and alternative lines that at the same depth would be better are never able to get above it, because of the depth disadvantage they have.
On average (i.e. Elo-wise) this is the best way to search. But sometimes it backfires. It seems you want to have an external agent that overrules the optimized search strategy of the engine in the lower plies. Especially your requirement that it should try 'reasonable' moves there is problematic; it means you would still need some engine to decide what is reasonable, an engine that prunes much less (and will thus unavoidably be much weaker).
It would be much better if the engine used for analysis had an option to force this, and limit the reductions awarded in the first N ply.
Of course you could also start with doing a multi-PV search, forcing the engine to search the root moves it deems sub-optimal on par with the main line. And then hope that forcing the first move will be enough to make it discover the best plan. Once it has discovered this plan, you should be able to switch back to single-PV mode.
-
giovanni
- Posts: 142
- Joined: Wed Jul 08, 2015 12:30 pm
Re: Meaningful ageing of a hash table
Well, I was hoping that following the Oxyron idea to play a short match among the engines after after an infinite analysis would have worked by pushing the search beyond a certain horizon. That was a way to automate things. Another attempt might be to combine moves from a multi-PV and see if you get it correct. A GUI like IDEA allows to partially do some of these things, but still there is a lot of manual input to do.
-
hgm
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Meaningful ageing of a hash table
I don't understand how this match is expected to help. The engine would surely play the moves that it considered best in the preceding infinite analysis, not? Or is the idea that you would let the opponent engine play the first move? That would only help if the other engine would see the correct plan.
If there exist other engines, the plans of which you consider worth following, it might be easier to run the analysis with both engines simultaneous. And then first follow the moves of the 'supporting' engine(s), by adding the initial part of its PV to the currrent game (forcing all engines to think about that plan), and then take the moves back to back-up the score. So that the main engine can then use that thoroughly investigated score for comparison with the line it would have preferred itself.
If there exist other engines, the plans of which you consider worth following, it might be easier to run the analysis with both engines simultaneous. And then first follow the moves of the 'supporting' engine(s), by adding the initial part of its PV to the currrent game (forcing all engines to think about that plan), and then take the moves back to back-up the score. So that the main engine can then use that thoroughly investigated score for comparison with the line it would have preferred itself.
-
giovanni
- Posts: 142
- Joined: Wed Jul 08, 2015 12:30 pm
Re: Meaningful ageing of a hash table
It was my understanding of Oxyron thinking that playing a, say, 10 games match /10 plies long, would allow to deepen the search and back propagate the final score to the root, ultimately leading to beta cutoffs in the hash table. Then, iterate the process with the improved HT, until the original score of the infinite analysis improves. However, I might have got all wrong and we should really listen to Oxyron about his point.
-
Ovyron
- Posts: 4556
- Joined: Tue Jul 03, 2007 4:30 am
Re: Meaningful ageing of a hash table
Who is this Oxyron? They sound like a very interesting person and I'd like to meet them.
But, anyway, there's no way to automate this, even in principle, because you have to somehow find those better moves to show them to the engine to fill the hash, but if you already have the moves then you don't need to do this (for instance, if Komodo found the moves then having them in Stockfish's hash isn't useful, just use Komodo to analyze the game as it clearly understands the position better, and use Stockfish to make sure Komodo isn't led astray.)
There could be analysis methods that uncover this better plan, such as extending the engine's line until its eval falls below the right line, uncovering it (this will not happen if the engine is misevaluating its preferred line and you need refutations to be inserted into it from elsewhere). Or excluding the main engine's moves from analysis so the alternatives are looked deeper (this will take forever if the right line is buried by several alternative lines that the engine prefers.)
Playing games could also work. The way you'd do it is playing with MultiPV=2 and take note of secondary choices of the engine, then whenever the engine likes a previous line better than what it is playing you takeback the moves and keep doing this for the alternative lines. If both lines have been tried you use exclude moves to ask for a third one for this position to have a place to return to if the other lines fall. The problem with this method is depth, because MultiPV is very costly you could have found the right line earlier if you used SinglePV in some position and you're just wasting time going to inferior lines that score better.
Another thing is "randomization", the engine plays a game once normally and takes note of the scores of the moves. Then on future games there's a window of centipawns that you use. If the second best move's score is within this window then the engine checks for the third one, and makes a list of moves within this range, and then chooses one at random. If it's a move that hasn't been played before it plays the game to completion normally, if not it checks for moves inside the window to play something different. This organically makes it try more varied moves near the root, but if the window is too small it may never try the right line's move, and if the window is too big it may spend most of its time playing irrelevant lines.
Playing the same game over and over to fill the hash with better moves so the root analysis is better only works if in one of those instances the mainline has been refuted and other preferred lines of the engine have been refuted so the engine switches to the right line.
But none of these methods guarantee that the right line would be found, so implementing them to an automaton could lead to disappointment after checking a position where you know the right line and seeing that the automaton can't find it.
The engine is already doing the best that it can to come up with the best move, if there was some other automatic way of finding better lines it'd have been implemented in top engines long time ago, but for problematic positions user interactions are necessary, and this is a reason centaurs play at a higher level than unassisted engines.
But, anyway, there's no way to automate this, even in principle, because you have to somehow find those better moves to show them to the engine to fill the hash, but if you already have the moves then you don't need to do this (for instance, if Komodo found the moves then having them in Stockfish's hash isn't useful, just use Komodo to analyze the game as it clearly understands the position better, and use Stockfish to make sure Komodo isn't led astray.)
There could be analysis methods that uncover this better plan, such as extending the engine's line until its eval falls below the right line, uncovering it (this will not happen if the engine is misevaluating its preferred line and you need refutations to be inserted into it from elsewhere). Or excluding the main engine's moves from analysis so the alternatives are looked deeper (this will take forever if the right line is buried by several alternative lines that the engine prefers.)
Playing games could also work. The way you'd do it is playing with MultiPV=2 and take note of secondary choices of the engine, then whenever the engine likes a previous line better than what it is playing you takeback the moves and keep doing this for the alternative lines. If both lines have been tried you use exclude moves to ask for a third one for this position to have a place to return to if the other lines fall. The problem with this method is depth, because MultiPV is very costly you could have found the right line earlier if you used SinglePV in some position and you're just wasting time going to inferior lines that score better.
Another thing is "randomization", the engine plays a game once normally and takes note of the scores of the moves. Then on future games there's a window of centipawns that you use. If the second best move's score is within this window then the engine checks for the third one, and makes a list of moves within this range, and then chooses one at random. If it's a move that hasn't been played before it plays the game to completion normally, if not it checks for moves inside the window to play something different. This organically makes it try more varied moves near the root, but if the window is too small it may never try the right line's move, and if the window is too big it may spend most of its time playing irrelevant lines.
Playing the same game over and over to fill the hash with better moves so the root analysis is better only works if in one of those instances the mainline has been refuted and other preferred lines of the engine have been refuted so the engine switches to the right line.
But none of these methods guarantee that the right line would be found, so implementing them to an automaton could lead to disappointment after checking a position where you know the right line and seeing that the automaton can't find it.
The engine is already doing the best that it can to come up with the best move, if there was some other automatic way of finding better lines it'd have been implemented in top engines long time ago, but for problematic positions user interactions are necessary, and this is a reason centaurs play at a higher level than unassisted engines.
-
peter
- Posts: 3186
- Joined: Sat Feb 16, 2008 7:38 am
- Full name: Peter Martan
Re: Meaningful ageing of a hash table
D'accord.Ovyron wrote: ↑Wed Mar 04, 2020 12:43 am The engine is already doing the best that it can to come up with the best move, if there was some other automatic way of finding better lines it'd have been implemented in top engines long time ago, but for problematic positions user interactions are necessary, and this is a reason centaurs play at a higher level than unassisted engines.
Yet the principal of backward analysis does work as we all know, btw. with A-B-engines still much better than with NNs, as far as I'm concerned, as for keeping moves and lines "in mind" going them backward with the engine. I don't say in hash, cause there's the big difference between NN and A-B I guess, NN-engines probably should keep things in NN- cache rather then in hash, don't know enough about it for sure, just spreading second hand readings mixed with own observation.
I talk about moves and lines the engine doesn't come up with on its own at once but "realizes" to be be better than its own trials by being "shown" them. One could argue NN- engines don't have to be shown as much moves and lines not being brought up on its own, not as much as A-B-engines have to, but that's a matter of taste to me, a matter of position, especially certain kind of tactical ones, anyhow NN- engines stick to their own favorite moves more then A-B-engines do in backward analysis, as for moves and lines that are clearly better then their own ones, of course I'm not talking about worse ones.
GUI- features like IdEA of ChessOk and "Deep Analysis" of chessbase do automate forward- backward- analysis combined with MV- mode and these automated features do work too.
Yet the lines that are brought up by the engines that way of course are still engine- lines of their own still. So best way to me to get the most out of such features by man- supported analysis is to add certain lines of interest to the tree to be analysed by hand and force the engine that way (over the GUI) to deal with them. Question remains, why not doing the forward-backward analysis by hand with the engine all the way at once, as for my personal pov it indeed is mostly the quickest way in all in all computing time, yet the time of man sitting at the screen can be shortened.
Still one of my biggest hopes as for such automated GUI- engine- features would be the algorithm Thomas Zipproth came up with to create Cerebellum with, Sirius- GUI offering that tool engine- independently, as it was said to come already some years ago, Sirius GUI sooner or later to arise, Thomas? Cerebellum instead of Cerebellum Light "only", as we have it now?
I'd still be very interested in that.
And then here things like learning files come in, tools of engines to keep only certain parts of the hash storing them and adding other parts of other hash- entries later on. I see that work too as for many years now, and I lament those of Houdini (up to version 4) and Shredder (12) not having been developed anymore in later versions.
The learning files of SF are several years old now yet already too, since Jeremy Bernstein came up with his Persistent Analysis of SF_PA, that did work well too, as for my personal pov, partly even better as newest Kinyama- code of "NN"- SFes does. Eman works well as for learning, S_XPro does, BrainLearn and ShashChess too, all of those could store more hash entries by time and depth of analysis than they do now as for my taste, yet anyhow I'm sure that's the way to go to keep up with NN- engines, maybe not "Elo- wise", but as for analyis of certain positions, opening lines and games.
Storing whole hash on disk and reload it, of course is a good way to keep analysis- results "in mind", yet it's limited by hardware as for disk space and time to write and read, automated or at least often repeated storage and reload would cost time too and wasn't useful for automated game play, disregarding manual restart of single games and parts of games with reload of whole hash.
Of course neural networks would be the most modern way of interactive training of certain positions of interest, mainly opening positions but (mid- and) endgames too, especially as for corr. chess. Yet there isn't much interest in interactive training of NNs up to now, compared to "zero- principle" as it seems, probably because of the bigness of data that's necessary for NN- training till now, as it seems.
Anyhow I appreciate very much the trials in that direction, the ones from Albert Silver (Fat Fritz), Dietrich Kappe (Ender- nets and Gials), Daniel Shawul (Scorpio) and all the others going that way.
Just my two cents about all of that rather important part of engine chess, what else but that has man to hope for at all, wanting to take part in the game anyhow anymore, if even "learning" and development all in all is just delegated to the engine or the NN or the database on their own?
Any other chances are more and more just "Der Waschmaschine beim Wäschewaschen zuschauen" as Chrilly Donninger used to call that, watching washing machines washing the laundry. Nowadays even more than that watching practically remis- laundry being washed on and on only.
Peter.
-
Ovyron
- Posts: 4556
- Joined: Tue Jul 03, 2007 4:30 am
Re: Meaningful ageing of a hash table
Do they? I was there as an Aquarium Beta tester since the first days of IdEA's inception, up until its final version, and I could never find an use for it, and I have the world record of 100% games lost with it (ALL the games where I used IdEA were lost, mainly because of the illusion that big numbers give; if after 100000 analyzed nodes a move beats another by 0.40cp it's surely the best one. Except it loses.)
No method where I tried to combine chessbase's Deep Position Analysis survived (there was always a faster method to find a move.)
I invite GUI developers to come up with an automated feature of chess analysis that works, and the idea here is that I don't analyze while I sleep, I could leave any automated feature analyzing while I can't, and have a tree of analyzed positions *for free* when I wake up to jump-start future analysis. And yet there has been nothing better than leaving my computer idle overnight, not even Infinite Analysis has proven fruitful (due to having to refute variations at higher depth.) Not even feeding the variations to CDBCN has proven fruitful, even though those are outsourced free resources!
But this is good, the day humans become obsolete because there's an automated method that always finds the best moves is the day computer chess dies, because we solved the problem, there's nothing else to do but quit.
-
peter
- Posts: 3186
- Joined: Sat Feb 16, 2008 7:38 am
- Full name: Peter Martan
Re: Meaningful ageing of a hash table
The answer is 42!
D'accord again overall, especially as for IdEA, to be honest, it always was somewhat to complicated for me, and I always missed the much easier way in chessbase (and Fritz)- GUIs, to let a .pgn with some variations and subvariations analyse backward overnight.
And of course the worth of automatical backward of such lines, maybe even combined with some forward in MV- mode too, always is as good as the tree you already have to be edited by the engine, and as a matter of fact I do my own analyses still almost always manually.
If I'm confident with a tree of lines of interest, I normally don't need any automatical analysis anymore, if I'm not, the automatic one won't be much better then the tree itself neither.
Yet an algorithm like the one used for Cerebellum (and even better not restricted to SF as an engine) could help to spare time with bigger trees, Cerebellum Light does work well as a book, and no, a book for engines isn't quite the most important thing we'd need as human players neither, but to deal with bigger databases as for editing of opening (and other) lines would be of human interest yet still, I guess.
And to let an engine learn from positions of human interest as for hash (NN-cache) or neural nets or learning files would be the point for me to try to get better tools as for the engines, and get them better useable and useful for users, which then can get better more easily and quickly in using them too.
Having said that all, of course all of this and any other kind of real "progress" of development, in the end yet will bring engine- chess nearer to remis- death than it is already now, and that's damned near already as for my personal pov.
You can see it most clearly in corr. chess, but that has for many years now just been the spearhead of engine- chess too, lesser hardware- TC simply follows in draw-rate over the years and over the progress of hardware and software, as long as you don't use more and more abnormal or out of balance- test postions and "books".
So its like digging the grave of its own of engine- engine- only- chess in a way too, but who cares, as long as humans will continue playing chess and use engines for that?
So my view is simply "nevermind". Others will look at that in a different way of course. Engine- engine game playing as a sport of its own and a one and only measurement for "elo-wise" progress is in big danger anyhow since quite a while, but maybe even more, if you start letting the engines not only learn the chess of their own on their own ("zero"- ly) but let them control the "progress", they make in that kind of development by themselves and on their own more and more too.
That reminds me of Ephraim Kishon's joke about the machine, that plants potatoes, harvests them, cooks and peels then and eats them up.
Peter.
-
Ovyron
- Posts: 4556
- Joined: Tue Jul 03, 2007 4:30 am
Re: Meaningful ageing of a hash table
It wasn't always like that, earlier version were much more easy to use and straight forward, I still remember the day I updated Aquarium and noticed I couldn't use IdEA anymore and the new way was so complicated that I spent weeks learning how to use the thing again.
I wonder if you can ask them if they can send you those old simpler versions, the problem with commercial software is that they only keep the last version that they sell, so while you can go and download Stockfish 1.0 for free no such alternative exist for old versions of Aquarium.
I've never seen anything noteworthy from Cerebellum's approach, it seems I can do what it does or better with Chess Openings Wizard's ability to analyze leaf nodes and backsolve. Bigger trees have always been problematic, the best thing I've found is splitting them into smaller trees, and generally I perform better if I make the conscious effort of keeping the analysis tree small.
If there's a variation that makes the tree explode with so many lines that I can't check them all I rather avoid it, so the question "what is the strongest you can play by keeping you analysis tree small and analyzing as few nodes as possible" is worth answering, because if you need a very large tree to find a move in a position, you probably messed up in a prior move leading up to it.