CCRL Discussion Board

I am not sure how you arrived at that "quick conclusion". You mention only 6 pawnless 7-men games, and there are more than 6,000 KRPPKRP games. That is somthing like 0.1% My impression is that pawnless 7-men are completely unimportant. This is why I am so interested in generating EGTBs by ...

It seems to me you are only making life difficult for yourself by using the black King for this. Like you say, it is black that has to do two ply in a row, due to verification. With the white King you won't have that problem. There was another reason why I used only white pieces to determine symmetr...

I have found even a slight refinement on the King scanning. If we want to distribute a King move over two passes, we can do the first pass in the order: a1, b1, b2, a2, a3, b3, b4, a4, a5, ...., b8, a8, c1, d1, d2, c2, d3, ... where we treat all diagonal moves between (a, b) files, (c,d) files (so n...

If I keep only one white piece dynamic in the slice that is loaded in RAM, (and all black pieces), I usually restrict the white King to this triangle. If it is the white King that is dynamic, and an unmove brings it outside the triangle, you have to mirror it back into it through the appropriate com...

Well, the memory seems to be the biggest problem. For pawnless 6-men, that is. They have 8G entries. I am not sure they could be compressed to anything less than 4GB RAM. But fortunately most 6-men contain Pawns, and a P-slice with even a single Pawn is only 1G positions. (and any additional Pawn wo...

To minimize the working set during TB generation, to make sure it fits in the CPU caches, it can be very useful to work by K-slice. A slice is a set of positions that have certain 'static' pieces always on the same square, all other pieces (the 'dynamic' ones) being put in every possible constellati...

I am interested (but, alas, not very knowledgeble) in the subject of compression, for the purpose of limiting the storage requirement during EGTB generation. The algorithm I plan to use processes the table base each cycle slice by slice, each slice being defined by keeping certain (white) pieces fix...

I decided to take an early retirement per April this year. 8) Otherwise the Shogi engine would not have been on the list, and the SMP stuff is a wish that only came up when I saw the announcement of the Nehalem CPU. But you can see why, up to now, I did not make much progress on the EGTB building. :...

My main interest is in on-the-fly building of pawny DTZ50 EGTBs. In particular I want to be able to build P-slices with 4 non-Pawns (e.g. KRKR or KRKB), and then be able to use that to calculate the required P-slices with 3-5 Pawns added (depending on their advancement and blocking). So that my engi...

First of all: 6-men have 64G positions Because of the 8-fold symmetry this reduces to 8G positions. As for the (2+4)-men the memory requirement is just over the edge (1.7GB + 0.5GB > 2GB), trying to squeeze out a few broken positions might be worthwile here, as even a few percent of savings counts....

I did a kind of back-of-the-envelope calculation on what would be needed to build 6-men pawnless bitbases entirely in RAM. A pawnless 6-men has 8G positions. The idea would be to keep this in RAM as compressed data, and use my slice-by-slice algorithm for the generation, packing and unpacking the da...

Ah, OK, now I see what you mean. Sorry for the confusion. You are talking about btm positions in which black can escape to a non-won wtm position in a successor EGTB. So such a position would, when it is hit as a potentially lost position, during the 3rd (verification) ply always revert to 'undecide...

I would not recommend building the black wins and the white wins simultaneously. They need different access patterns, and their storage need just add. (The wtm positions need many states there.) Just build them separately. When the building is finished you no longer need to distinguish the lost posi...

To start with your last question: of course you can use anything that is sais here as you see fit. This is the reason I post it in public. If you treat the Rook as two pieces, you would have to do separate passes to treat it. This seems bad. But you can treat multiple white pieces in one pass, only ...

Thats exactly the part I dont quite get, how do you calculate the retrograde white King moves, if they are all from different parts in the matrix. You slice the matrix by row in stead of by column. Then they are from the same part of the matrix again. So when transferring a slice between disk and R...

OK, I think I see what you mean now. The problem is that if you expand the set to also include all positions a formerly fixed piece can come from, these pieces can also reach other positions from these extra position. So you would start loading things in duplicate. The only exceptions I can think of...

I understand how you do the first pass, but how are you going to do the passes for the other white pieces? How are you going to do the moves with these, if you only have tables where they are fixed to certain squares? You save the other white pieces for another pass through the TB. Say you are doin...

Doing this, you would reduce the required ram space by 50%(using 4bit instead of 8bit), so you still wouldn't come around streaming the data from the HD like in your described algorithm. I am not sure why you say that, or why you link it to the algorithm. I think this way of representing the data i...

Another thought on storing the EGTB in RAM while building: We could split the DTX field into a 4-bit frequently accessed part ('quickDTx'), plus an 'overflow' byte stored elsewhere. The 4-bit field would encode 'undecided' positions as 0, positions that have DTx specified in the overflow byte as 15,...

In my algorithm a cycle advances the state by a full move, calculating the btm lost-in-(N+1) positions from the btm lost-in-N positions. The wtm intermediate positions are only needed as a bitbase, to prevent duplication of work. The building process thus generates 3-ply triees: one white retrograde...

Good idea and this should solve the problem for a while. One always has to keep all black positions as fast accessible as possible (in RAM). So if you ignore the index-optimizations you could solve engames with up to 5 black pieces (64^5 Byte=1GB Ram) Then, are you using any index-optimizations (mi...

Dhanish wrote:The average download speed is about 20kB/s .

This is definitely something we should be able to beat by local generation...

A generator that is streaming IO-bound (as opposed to random access bound) would be a major advance. Well, I think this is what my algorithm should be able to deliver: For a 3+3 men EGTb, say, I would split each cycle in two passes, one pass treating the (retrograde) moves of first white piece plus...

The rate of generation was 10 KB/s on a 1 GHz dual PIII. Well, like I said, HD speeds of 50MB/s are more or less standard now, so if building an EGTB takes 50 cycles, and each cycle a read and a write of the complete EGTB, that makes the generation 100 times slower. So if I will not reach a generat...

Well I am no expert on compression either, but I think that encoding during generation might only work for generally drawn endgames. For others it might be difficult, for example if you have a block of 256kb and you find you need 1 more bit at the beginning of the block, you will have to shift all ...