pawn enumeration

[syzygy]

Please don't tell me you give a course programming somewhere

Except the: "How my methods can slow you down at modern hardware - let's start writing in the same cacheline with different threads"

My threads aren't writing in the same cacheline, unless by chance.

p.s. Forward generating is of course 60 times faster than any of your methods in normal OTB chess - google for Urban Koistinen.

Forward generation is inefficient. Doing 60 or 64 positions simultaneously will not solve that. Another problem with Urban's algorithm is that it seems nobody has ever succeeded in implementing it.

[diep]

DTM is not so clever nor anything similar. it's 1 or 2 bytes. If you use 50 move rule, you have still a 7 bits need an entry. That's way too much.

For up to 5 pieces, my WDL50+ tables are 438MB and my DTZ50+ tables are 668MB. The DTZ50+ tables are half-sided and make use of the WDL50+ information. So draws in DTZ50+ can be compressed as don't cares and win/loss values can be stored without a sign. I also store distances in full moves unless I potentially need plies for perfect 50-move rule play. There are lots of further tricks.

It's all about the compression.

How much is 5-piece WDL for diep? (And do you store both wtm and dtm or half-sided?)

So you're forced to WDL or you will need 1TB of SSD's.

I completely agree that during search one should use WDL (on SSD or in RAM) and not DTM or DTZ.

If you ever want a chance for having 7 men - storing more than win/draw/loss is gonna be a problem.

Currently in search i don't have compression. I had experimented with some supercompression. Might get it going one of these days as it's pretty much needed for the cluster. So i'm kind of forced. Need all 6 men in RAM simply. And right now i've got in total 18GB of RAM in cluster (8 nodes @ 64 cores).

The 5 men are not interesting to get real small. Getting the 6 men in a few gigabytes is more interesting.

For 5 men you can already build some heuristics for evaluation so to speak - some have done that. Ask Ed Schroder after how well Rebel plays KRPKR. I'm not sure of it though - but seems to me he did do genius job there.

So to speak the 50 move rule you can also avoid in the most important cases with some evaluation code - just recognize the KNN vs KP positions especially whether pawn is blocked and pawn not too far.

The interesting EGTBs are also the toughest ones to compress well if we speak about the 6 men.

The real interesting thing is the 7 men however. Relative spoken value of KRPKR is much higher than KRPPKR, other than the increased number of positions.

Yet i expect 7 men to have a few kick butt tables that are really worth it.

KRPPKRP might be one of them. With some monkey coding you get nowhere with that one.

Needs more systematic approaches.

Koistinen is a necessity there.

[diep]

Please don't tell me you give a course programming somewhere

Except the: "How my methods can slow you down at modern hardware - let's start writing in the same cacheline with different threads"

My threads aren't writing in the same cacheline, unless by chance.

p.s. Forward generating is of course 60 times faster than any of your methods in normal OTB chess - google for Urban Koistinen.

Forward generation is inefficient. Doing 60 or 64 positions simultaneously will not solve that. Another problem with Urban's algorithm is that it seems nobody has ever succeeded in implementing it.

Ah yes one guy did.

It's me.

But that's a different algorithm than Koistinen's. I give him the credit though as he invented the trick of doing 64 positions at a time. He really figured that one out.

Give him those credits will you.

Can't remember how many emails i had with Koistinen to puzzle it all out. Maybe a 200 or so?

The thing you want to do fast is the rewrite from black to white kings.
Realize it's all bitboards, you don't want to waste too many cycles a bit for the rewrite.

That's the most complicated part if i may say so - the rest is trivial.

Let me dig up something in some old generator code there...

[syzygy]

If you ever want a chance for having 7 men - storing more than win/draw/loss is gonna be a problem.

With current hardware 7-piece tables are just too big to handle in any reasonable way, let alone to use them during search. When I can generate them in RAM, I will start to get interested.

The 5 men are not interesting to get real small. Getting the 6 men in a few gigabytes is more interesting.

You have to start somewhere... If you can't compress the 5-piece, it might be hard to compress the 6-piece.

I will generate the 6-piece tables soon. I first need a bigger machine. Based on the ratio for Nalimov tables (I think 7 GB for 5, 1200 GB for 6), a reasonable estimate for my 6-piece WDL50+ tables would be 75GB. That's probably too pessimistic, since WDL should not increase as much in size when going to 6-piece as DTM. In any case, on a big enough machine most of it will fit in RAM.

[diep]

Ok that's gonna be quite some search.

Yet here's simple idea, works real fast and simple,
you create a few more bitmaps.

If you do a pass win in X for white, you lookup in all tables
in the format of the normal EGTB, with as difference the last piece
which is the black king.

All tables you lookup to are in this format.
Of course the mirrorring you do for the most significant piece, which always is a pawn if there are pawns and otherwise the first piece.

Then after the pass you rewrite those tables to having the white king as last.

That's how simple it is. Then normal forward works. This all goes at total warp speed. For clever tricks there is no time.

Koistinen himself wanted 4096 positions at the end, but that's not needed, you simply can reduce that to 60 as it's the 5th piece that one last king.

That's all. Everything else works the same as normal generation.

Goes full throttle.

it's very simple really - yet a genius trick from Koistinen and that end 20th century, start 21th one.

Where you can speed it up is by doing a fast rewrite.

[syzygy]

Another problem with Urban's algorithm is that it seems nobody has ever succeeded in implementing it.

Ah yes one guy did.

It's me.

But that's a different algorithm than Koistinen's.

So also that one guy did not

I give him the credit though as he invented the trick of doing 64 positions at a time. He really figured that one out.

Give him those credits will you.

I will. It's a very impressive algorithm. His attempts to explain his algorithm have certainly contributed to my interest in egtb generation. Last year I studied it again, but I concluded that it most probably doesn't suit my needs (which is fast RAM-based generation).

[diep]

If you ever want a chance for having 7 men - storing more than win/draw/loss is gonna be a problem.

With current hardware 7-piece tables are just too big to handle in any reasonable way, let alone to use them during search. When I can generate them in RAM, I will start to get interested.

The 5 men are not interesting to get real small. Getting the 6 men in a few gigabytes is more interesting.

You have to start somewhere... If you can't compress the 5-piece, it might be hard to compress the 6-piece.

I will generate the 6-piece tables soon. I first need a bigger machine. Based on the ratio for Nalimov tables (I think 7 GB for 5, 1200 GB for 6), a reasonable estimate for my 6-piece WDL50+ tables would be 75GB. That's probably too pessimistic, since WDL should not increase as much in size when going to 6-piece as DTM. In any case, on a big enough machine most of it will fit in RAM.

I disagree. Supercompressed 7 men will be really compressing better than 6 men. Not sure how tiny you'll get it, but let's take the interesting one:

KRPPKRP.

That's having 3 pawns you know, that really reduces the EGTB.

The 7 men in diep format are 585.845.413.676.228 entries
when counting all 3-6 men and the 4 vs 3, so not 5 vs 2 nor 6 vs 1.
I'd say ignore 5 vs 2 initially. If you have KQ vs King + 4 pieces that happens to be a draw instead of a win for queen, then you're just having
bad luck....

Of course generating all those EGTBs to get to the goal is a lot. It's 965 EGTBs all together (and in number of files nearly 2x bigger, as this is unique EGTBs, not number of files of white and black to move).

KRPPKRP is 295,125,079,056 entries.
That times 2 of course.

So it's 59.0GB uncompressed (times 2).

KRPPKR is uncompressed 6,769,796,880 entries
Default compression (not supercompression) it's having
sizes 224MB and 90MB.

If we project that in a stupid manner to the interesting 7 man EGTB
That's factor 43 larger for the 7 man.

224MB * 43 = 9.7GB. and the other one a lot smaller.

That's not supercompression yet though. Yet that fits easily onto a SSD
together with a lot of its 7 men brothers. I'd be prepared to buy a SSD for THAT.

Using that in search will be a huge advantage.

[diep]

Another problem with Urban's algorithm is that it seems nobody has ever succeeded in implementing it.

Ah yes one guy did.

It's me.

But that's a different algorithm than Koistinen's.

So also that one guy did not

I give him the credit though as he invented the trick of doing 64 positions at a time. He really figured that one out.

Give him those credits will you.

I will. It's a very impressive algorithm. His attempts to explain his algorithm have certainly contributed to my interest in egtb generation. Last year I studied it again, but I concluded that it most probably doesn't suit my needs (which is fast RAM-based generation).

You know, i forgot whether it was 1999 or 2000 already when i started chatting to Koistinen. In tournaments mid 90s Johan de Koning complains about his generator being so CPU bound and all this nonsense of Nalimov in his eyes (give the guy some credits for generating the most important 6 men i'd say) and uncle Bob with the huge RAM requirements of Nalimov as Johan's generator fits in a few hundreds of kilobytes, just it was eating that much CPU time. Johan was the first to complain about things being cpu bound if i remember well - not Bruce Moreland.

Then this guy Koistinen shows up and has a solution to generate EGTBs factor 60 faster, just for some i/o overhead, factor 2.5 or so (didn't exactly calculate it even - arrays were 400MB/s back then already).

That's really kick butt you know. Try to show up with factor 60 improvement in 2012 somewhere...

It allows the 7 men relative easy. Just i don't have the cash for buying that raid array. I do have the cpu power and spare machine for it...
(the old 16 core AMD barcelona 2.3Ghz would be nice to dedicate to this meanwhile its Tesla's can then parameter tune Diep - optimal usage of the machine then).

It's a set and forget project in such case.

[syzygy]

I disagree. Supercompressed 7 men will be really compressing better than 6 men.

Supercompressed is not interesting if it takes years to compress or if the compressed file cannot be randomly accessed.

Not sure how tiny you'll get it, but let's take the interesting one:

KRPPKRP.

That's having 3 pawns you know, that really reduces the EGTB.

It's having 7 pieces. That really increases the EGTB

The 7 men in diep format are 585.845.413.676.228 entries

Just for the KRPPKRP table, yes. Compressed size will be 10GB if you're lucky. I know you get a factor 1000 for all-win tables, but this is not one of them.

Of course generating all those EGTBs to get to the goal is a lot. It's 965 EGTBs all together (and in number of files nearly 2x bigger, as this is unique EGTBs, not number of files of white and black to move).

For suicide chess, there are 2646 tablebases with 5 piece or less. Going to 6 pieces adds 5754 more tables. I need a fast generator (and compressor) to ever get that done.

224MB * 43 = 9.7GB. and the other one a lot smaller.

That's not supercompression yet though. Yet that fits easily onto a SSD
together with a lot of its 7 men brothers. I'd be prepared to buy a SSD for THAT.

Using that in search will be a huge advantage.

We seem to agree on the 10GB estimate. And yes, this one would fit on an SSD. So I agree that it is feasible to use a small subset of 7-piece tables.

Actually what I have in mind is to at one point generate the 7-piece tables for positions having opposing white and black pawns on the same file (I think the Robbolito people did something like that for blocked pawns). I think this catches many of the interesting 7-piece positions, and generation is very feasible since you can slice to 5 pieces and you don't need to do promotions into 7-piece subtables.

[diep]

I disagree. Supercompressed 7 men will be really compressing better than 6 men.

Supercompressed is not interesting if it takes years to compress or if the compressed file cannot be randomly accessed.

Not sure how tiny you'll get it, but let's take the interesting one:

KRPPKRP.

That's having 3 pawns you know, that really reduces the EGTB.

It's having 7 pieces. That really increases the EGTB

The 7 men in diep format are 585.845.413.676.228 entries

Just for the KRPPKRP table, yes. Compressed size will be 10GB if you're lucky. I know you get a factor 1000 for all-win tables, but this is not one of them.

Of course generating all those EGTBs to get to the goal is a lot. It's 965 EGTBs all together (and in number of files nearly 2x bigger, as this is unique EGTBs, not number of files of white and black to move).

For suicide chess, there are 2646 tablebases with 5 piece or less. Going to 6 pieces adds 5754 more tables. I need a fast generator (and compressor) to ever get that done.

224MB * 43 = 9.7GB. and the other one a lot smaller.

That's not supercompression yet though. Yet that fits easily onto a SSD
together with a lot of its 7 men brothers. I'd be prepared to buy a SSD for THAT.

Using that in search will be a huge advantage.

We seem to agree on the 10GB estimate. And yes, this one would fit on an SSD. So I agree that it is feasible to use a small subset of 7-piece tables.

Actually what I have in mind is to at one point generate the 7-piece tables for positions having opposing white and black pawns on the same file (I think the Robbolito people did something like that for blocked pawns). I think this catches many of the interesting 7-piece positions, and generation is very feasible since you can slice to 5 pieces and you don't need to do promotions into 7-piece subtables.

My experience is that if you just use 1 drive, that you can run with around a 60GB of EGTBs (i have 'em uncompressed currently in search).

On that supercompression. It's not easy indeed - but i'll have a shot at it within not too long to get it working in search.

So far i only experimented, years ago with the supercompression. I have some good ideas on how to randomly look that up in O ( log n ).

That'll require some overhead.

As for suicide chess - Koistinens idea is not usable there.

For normal chess it's a genius trick allowing the 7 men. Let's cheer for that!

A trick reducing generation speed factor 60 in 21th century, think about it. It's even now, 12 years later incredible if i just think of it.

That supercompression - it's a big field compression in itself.

Note that i also have the Tesla's. If i keep it under 1000 watts i can have nearly a 1000 cores available for the EGTBs.

It's some work though to write the code for it. Maybe i'll do it!