CCRL Discussion Board

notnale:
For DTZ50 you need to store distance to win in half moves as it sometimes makes a difference. This means that there are over 100 possible values per position, even if you only care about wins by one side. With wins by either side there are over 200 possible values.

As DTR is only a little harder than DTZ50 and gives correct answer for default rules, I think DTR should be the goal. (DTZ is easier than DTM.) To compute DTR, compute DTZ for both odd and even game50 and as soon as the set of wins with game50=N is the same as the set of wins with game50=N+1 you nee...

It has been a while and I have had good time to think, thank you. Here are my views on how to use compression when computing 7-man endgame tablebases: A normal computer now has about 2-4 GB ram and 500-1000GB hard disk and can execute about 3-10 Gips (64-bit operations). For 4-3, 5-2 and 6-1 leapfro...

Yes, a negative count is a clear indication of overflow. Add a multiple of 2^32 to get the correct count.

h.g.muller: About my guess about needing double the cpu for leapfrog, that is for my idea of doing a full search at every step. In order to be able to do that quickly I can't limit the search to just the positions that need to be searched. Doing run length encoding with n bits costs in the worst cas...

h.g.muller: Thanks, that was a good explanation of leapfrog. Here is how I now understand it: In one cycle you read and write the wtm table twice and go 2 full moves forward, so you only need about 25 cycles to compute DTZ50. With a simple indexing scheme the main wtm table would contain 10*2^36 pos...

h.g.muller: I think I understand the grandparent part of your algorithm. I think run length code is the compression method to use to keep track of recent changes. The leapfrog part I don't quite understand. Mirroring seems a problem to me. Perhaps I have just not found a detailed enough description?...

h.g.muller:
I got to think this over, writing some code to test speed of examining all moves.
Previously I simply assumed that being about as quick as examining every move once individually would be enough.

I am still not sure how this works. If you have a separate 'layer' for each DTZ, how can you construct DTZ=7 from DTZ=6? You would have to know which positions have DTZ=0, 1, 2, ... , 5 as well. Or is layer N storing all DTZ <= N? Any position won with DTZ=N is also won with DTZ=N+1. In that way la...

h.g.muller: DTZ is another dimension of the table. So you have one table with white wins at DTZ=0 (black is checkmate), one with white wins at DTZ=1 (white make checkmate or conversion to win in 1 move), one with white wins at DTZ=2 (not stalemate, no conversion to subendgame where white doesn't win...

guyhaw: Nice to get back to discussing compression. In the context of EGTB all data can be recomputed so lossless is not very meaningful. I'd be more interested in what purposes the table might be compressed for and what different goals those purposes imply. I guess DTR is the same as DTZ50 and that...

Why would you need more than 1 bit per position per DTZ? Maybe it has something to do with unmoves? You only need 1 bit to tell if the position is a white win or not at a given DTZ. Also, I don't understand how you manage to examine both white and black moves while only looking at part of the TB. Pe...

I don't fully understand unmoves so I'll just discuss moves that connect one table with another. For KQRNKBN: Index squares as in table above. Split off high indexing in a high and a low index. Put the index of the black king in the high part. (10 possible values) Put the high part of the bishops in...

This is not about compression but I answer it here anyway. I am very interested in ways to reduce seeks. You were mentioning a 4K x 4K matrix, but to access such a matrix in column order would require 16M seeks (if it was stored sequentially by row), and I am afraid this will wear out my hard drive ...

I have deleted much from the quoted text. I am interested (but, alas, not very knowledgeble) in the subject of compression, for the purpose of limiting the storage requirement during EGTB generation. Now I am mainly interested in building EGTBs in RAM, which then would be the slow storage, the CPU c...

What goals do you think would be worthwhile regarding compression of EGTB:s? (besides reducing (local) storage requirements) Mandatory : direct indexing (block indexing), devoid of patent infringements Desirable : variable block size, better encoding speed, faster initialization when loading a tabl...

What goals do you think would be worthwhile regarding compression of EGTB:s? (besides reducing (local) storage requirements)