Not logged inRybka Chess Community Forum
Up Topic Rybka Support & Discussion / Rybka Discussion / A new solution for tablebases?
- - By h1a8 (***) Date 2007-12-22 18:16
I thought of a way to possibly greatly reduce the amount of tablebases needed.
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?
Parent - - By skulibj (*) Date 2007-12-22 18:57
I believe the big question is how much reduction in size are we talking about. Without thinking about it it could be whatever. Maybe it is just a 1% reduction. I don't know. This reduction is dependent on the "sight" of the program assumed. Theoretically the tablebase will reduce in size a lot when the plies are high enough and should go from 0% to 100% reduction when the plies the program sees gets higher and higher from 0 to some unknown interresting number. This would be an interresting graph to look at.

Interresting thought.
Parent - - By h1a8 (***) Date 2007-12-22 21:25
Actually it is a huge reduction.
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.
Parent - By Vempele (Silver) Date 2007-12-22 21:33

> 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).
Parent - - By Uri Blass (*****) Date 2007-12-22 23:03
No
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.

Uri
Parent - - By h1a8 (***) Date 2007-12-23 03:47 Edited 2007-12-23 03:51
I'm not sure what an array is. Its definitely possible to just delete all positions (in the arrays) where there is mate or draw in 5 or less in the 3-4-5-6 men tablebases.
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.
Parent - - By Banned for Life (Gold) Date 2007-12-23 06:08
You're missing Uri's point. It's not enough to reduce the amount of data in the file. You would also need to develop a new algorithm for indexing into the compressed file to pull out desired positions. The file is not currently indexed by distance to mate.

Alan
Parent - - By h1a8 (***) Date 2007-12-23 09:18
I think you missed my point. That is almost exactly what I was saying.
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).
Parent - - By Vempele (Silver) Date 2007-12-23 09:41
I think you missed his. Mapping the removed positions into contiguous locations is close to impossible without a huge performance deficit.

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.
Parent - By Sesse (****) Date 2007-12-23 11:28
In theory, you could perhaps set all values less than 5 to simply 0, and then rely on the lossless compression to do the rest. However, the gain is going be extremely small, and if you're going to make it lossy like this, you are basically making a poor reimplementation of bitbases anyway...

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 */
Parent - - By h1a8 (***) Date 2007-12-24 02:04 Edited 2007-12-24 02:07
I don't understand you at all. Each position in the tablebases have distance to conversion info. 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.
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.
Parent - By Vempele (Silver) Date 2007-12-24 08:53 Edited 2007-12-24 09:24

> 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!

(in KNPPkb).
Parent - By skulibj (*) Date 2007-12-23 17:02
Theoretically speaking it is possible to reduce the bit base like this isnt it? And the amount of space saving is dependent on when you stop telling the engine what to do cause you assume it can figure it out by herself?
Parent - By BB (****) Date 2007-12-24 01:58
It is practically impossible to make the array smaller by this strategy.

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).
Parent - - By Vempele (Silver) Date 2007-12-22 19:25
See here for a discussion about a similar idea.

> 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. :)
Parent - - By h1a8 (***) Date 2007-12-22 21:35
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). Some programmers already think that tablebases only provide a very small (if any) increase in strength. This has been somewhat verified for tablebases on slow hard drives. So having the program to think for itself when a mate in 5 exist is not going to be much of a decrease (if any).  But that is one of the reasons why I said it is not perfect. It's just that the engine would seriously benefit overall from it, especially in analysis (me thinks).

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.
Parent - By Vempele (Silver) Date 2007-12-22 21:43

> 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.
Parent - By BB (****) Date 2007-12-24 01:42
See here for a discussion about a similar idea.

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.
Parent - - By albitex (***) Date 2007-12-22 19:31
An interesting idea for the endgameses:  create some endings books!  To make some equivalent books to the openings books, but for the endgames.
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?
                          
Parent - - By Sesse (****) Date 2007-12-23 11:26
This is going to be basically useless. If any piece has moved, even the slightest, the entire book has to go out the window. I'm willing to bet that less than 0.1% of all non-obvious endgames would benefit from a ten-million-game book.

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 */
Parent - By albitex (***) Date 2007-12-23 21:16
Sesse perhaps you is right, but I would like to try.
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.
Parent - - By Vasik Rajlich (Silver) Date 2007-12-25 15:22
Without any really deep thinking, this doesn't seem important. Distances to mate are just not very important in general. When you're mating, you're mating.

Vas
Parent - - By Fulcrum2000 (****) Date 2007-12-25 15:24
When you're mating, you're mating.

I will remember this one ;)
Parent - - By BB (****) Date 2007-12-26 06:49
When you're mating, you're mating.

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].
Parent - By Banned for Life (Gold) Date 2007-12-26 07:10
Have you ever seen the sci-fi movie, "A Boy and His Dog"? I think the dog summed this up very well.
Parent - By Uly (Gold) Date 2007-12-26 21:20

> And when you're only halfway up,
> You're neither up nor down.


Then why can't we say "I'm halfway down"?
Parent - By Sesse (****) Date 2007-12-25 16:45
...or you're hitting the 50-move rule? =)

/* Steinar */
Up Topic Rybka Support & Discussion / Rybka Discussion / A new solution for tablebases?

Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill