By how much actually depends on how deep an average chess program can see exactly (every move and variation) in less than maybe 3 min with decent hardware.
For example, if every chess program can be programed to see at least 5 moves (10plies) exactly in under 3 min when a tablebase hit tells them that a mate in 6 or more exists, then it is possible to cut out all the tablebases that have a win, lose, or draw in 5 or less. When the program gets to the mate or draw in 5 from the mate or draw in x>5 then just let the program calculate the mate or draw in 5 from there on its own. The program itself could be programmed to do this. I feel all computer engines should see a mate in 4 or less without tablebases. So if a mate in 4 or less exists then the computer should find it without needing to consult with tablebases (or bitbases).
Now calculating the mate or draw in 5 is assuming to be done with strictly brute force search.
But with a more sophisticated and efficient search algorithm then this number (the tablebases to be cut) can go up to 6 or more moves (as long as every or nearly every move is seen). This technique works like a semi-bitbase technique.
Chess authors would have to talk to Nalimov about this or generate these type of tablebases themselves. Its possible to even store the reduced tablebases in ram or in a fast flash memory device. Now this technique isn't perfect (I can already think of a small flaw in it) but I am willing to bet that this technique is beneficial (either increases strength, allows more tablebases to be stored, or both). Vas (and significant others), what are your thoughts on it?
Say the average mate in tablebases is 20 moves. Cutting out the mate in 5 and less should cut at least 25% off the tablebases. I could be wrong here though.
> Cutting out the mate in 5 and less should cut at least 25% off the tablebases. I could be wrong here though.
Exponential growth (it flattens out, though).
It is not a huge reduction.
You assume that mate in 5 or shorter mate are 25% of the tablebases if the average mate is mate in 20.
There is no basis to this assumption and even if this assumption is correct I still do not see if huge reduction is possible
because of the way that tablebases are stored in the memory.
Tablebases are basically arrays of distances to mate.
Now if there are 1,000,000,000 positions that their distance to mate is stored in the array knowing that you do not need position number 5,7,...56784,...67889,... is not going to save much memory because there are no simple rule how to have a smaller array.
Translating position number 5 to chess position is easy but if you delete position number 5 and make position number 6 to be position number 5 then I see no practical way to translate number to chess position so it is practically impossible to make the array smaller by this strategy.
A query program can be created to find all these positions in the arrays and then either delete them or copy the array without them.
Tablebase hits will only be for mate or draw for x>5.
For example, if Rybka sees a mate in 12 in the tablebases then she follows it until mate in 5.
After that her brute force algorithm kicks in or regular algorithm (if short on time). She must
be programmed to do this for this to work well.
I stated this as an option for the query program (either draw out the positions by a special algorithm or create new bases by excluding them).
Let's take the extreme example: all of them end up outside the base. Congratulations: whatever method you're using to calculate the index, it's also smart enough to detect mates in 5 or less. Too bad it'd take 3 minutes to calculate it for any position.
I agree, however, that "just not storing the entries less than five" is a completely bogus idea, made by someone who obviously didn't program much :-)
/* Steinar */
I think it is fairly simple for human's to create a tablebase that contains only 5 and more distance to conversion.
If not then we are surely primitive lifeforms. I refuse to believe that.
All that needs to be done is create an algorithm to do this. And this is fairly simple for many.
The performance of such tablebases would be a hugh jump (not deficit as you are saying). The tablebase will only be used if the position occurs on the board.
Letting the computer calculate its own 5 or less move to mate or draw is just like letting it play without tablebases.
So the performance couldn't be a hugh deficit due to the simple fact that chess engines already play almost equally well without tablebases.
And note: This would only occur if the computer is in time trouble (which is rare). And if that is the case then the computer would already be
programmed to use its normal search algorithm in this situation.
> Now either subtracting the positions that have 5 and less or generating all the tablebases again, with a new program, while subtracting the positions that have distance of 5 or less in the process should be easy.
Sure, that's easy. But here's the problem: you need to be able to access it. For that, you need an index - basically, you have to calculate an order for all 6070893838 positions, any position's place in that order has to be calculated from the position itself and the 153258434 mates in 5 or less somehow have to be indexed to 1 through 153258434 or similar.
Basically, if you arrive at a position whose index is 78642358, you already know it's a mate in 5 or less without even probing or searching!
As Sesse mentioned, increasing the redundancy of the information (identifying all mate-in-1 to mate-in-5 scores) will help somewhat (not very much with this particular scheme) with the (Huffmanesque) compression techniques.
For a typical 6-piece TB, say NPP vs B, the data look like this:
wtm: Draws: 830488106
wtm: Broken: 192932832
wtm: Mate in 16+: 1607468276
wtm: Mate in 15: 228600887
wtm: Mate in 14: 247923081
wtm: Mate in 13: 286010299
wtm: Mate in 12: 356214817
wtm: Mate in 11: 433576295
wtm: Mate in 10: 470332285
wtm: Mate in 9: 448080668
wtm: Mate in 8: 376389061
wtm: Mate in 7: 270535902
wtm: Mate in 6: 169082895
wtm: Mate in 5: 92322856
wtm: Mate in 4: 35564474
wtm: Mate in 3: 15130303
wtm: Mate in 2: 5608032
wtm: Mate in 1: 4632769
So the gain in ignoring mate-in-X for X<=5 is quite small. The gain from identifying mate-in-(5T) with mate-in-(5T+4) for all T would be a bit better, but it's practicality is not clear (in my case, I have realtime 5-piece bitbases, so tablebases are only used when the position occurs on the board - thus their large size is not much of a worry).
> For example, if every chess program can be programed to see at least 5 moves (10plies) exactly in under 3 min when a tablebase hit tells them that a mate in 6 or more exists, then it is possible to cut out all the tablebases that have a win, lose, or draw in 5 or less.
Problems arise when the engine doesn't have 3 minutes to evaluate every internal node. It'd be much faster to just fetch the result from online TBs, though. :)
And the idea in the link is kind of similar but very different than the one I'm proposing. I'm fairly optimistic that my idea will work well.
> Actually this is not a problem. If the computer is in time trouble when it gets to mate in 5 (this is very rare except in blitz) then the computer can use its own original search algorithms to try to find mate (with pruning and such).
I was talking about internal nodes.
About three months ago, a similar idea (playbases) was described here (my browser scrolls down to one screen below the playbase post for some reason). It doesn't work that well time-wise (at least at 5 seconds per move, where the "stride" cannot be more than about 10 ply or so) - it seems to be difficult to prune the trees due to the large similarities in scores (for instance, if there is a mate-in-16 move, in many cases almost all moves will be no worse than mate-in-20). I never considered the space requirements, but they would probably be a factor of 3-5 times the bitbase size.
A lot of openings, develop him in a midrange game, that brings to of the classical endgames. These positions should be written in the book. And if the engine finds that the position to which has come is included in the book, then it should follow this (the book) and not to analyze anymore.
Obviously this book will have to be modifiable at the end user. As playing, the opening book can learn from the games. And we can add all the positions of endgames that we want.
The dimensions of the actual HDs in commerce (1 Tetra bit!) they allow to store hundreds of million of games.
To produce these positions of endgames, besides download them from game on internet or database of games, would need to create making her play the engineses among them.
But the matter is: this we would be able it anchors to call: "TO PLAY to chess?" Or would it be search mathematic?
If you have 1TB, you could just as well store the 6-man tablebases anyhow, which would most likely give you a lot more benefit (tiny as it is).
/* Steinar */
I have experimented the function Random for the openings. When I have played game, that they have crossed the variation of the opening from me traced (making to play hundreds of game with the function Random to Rybka), I have gotten a clean improvement of the performances of my Rybka. True being also that the openings they cross forced linie, while for the endgameses the possibilities are infinitely greater. But I am sceptic, in reference to the matter of the endless possibilities of movements in the chess. This is theoretically true, but in practice the real movements (real = profits, with a sense) they are very more limited in quantity.
We have seen that the game of the dame has been resolved (with the computer play).
I think both only matter of time for the chess.
I will remember this one ;)
When you're up, you're up.
When you're down, you're down.
And when you're only halfway up,
You're neither up nor down.
[My version of the Grand Old Duke of York].
/* Steinar */
Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill