My egtb generator is generating helpmates

[EricLang]

I just built my first egtb with black having a piece to.
wtm en btm positions are stored in 1 file.
Up until now generating seemed good (still with my slow forward moving retrograde analasys).
With a bare black king the algorithm works but now it generates helpmates.

Let's take this position in KQKQ:

Code: Select all

WK = a1
WQ = e1
BK = c1
BQ = d1
White To Move

White wants to play Qe1-e5 because it sees a DTM = 2.
This is very wrong because BLACK mates with Qd1-a4#
This is really a helpmate.
What is the smartest way to handle this problem?

[h.g.muller]

It seems you are generating wins for both sides at the same time, and do not distinguish wins for black and wins for white. White should go for the shortest mate-in-n that is a win for white, (making the predecessor a mate-in-n+1), and if thee is none, to an undecided position (in which case the position remains undecided). And if there also is none of that, it should move to the longest mated-in-n that is a win for black. With btm, just the other way around.

My generator just generates wins for one side (white) at the time. If you ant to know them for the other side, you should run the end-game with reversed colors. Then on white moves it picks the move to the lowest DTM, (or remains undecided), but on black moves it goes for undecided first, and otherwise largest DTM. (Which is always the successor through which we just found the position through unmoving from newly-won positions, when we generate DTM in increasing order.)

[EricLang]

It seems you are generating wins for both sides at the same time, and do not distinguish wins for black and wins for white.

That I discovered today, yes.
So it should be easier to generate 2 files, one for wtm and one for btm? I still have to learn a lot, but I'll manage. It costs time.

[notnale]

For complicated positions, wouldn't it be more efficient to generate both at once?
One idea I had was using negative numbers for losses, 0 fr a draw, and positive numbers for wins

[EricLang]

Getting confused...
How can I generate DTM=0 entries in a wtm-file?? they do not exist! So how can you store any DTM then?

[h.g.muller]

For complicated positions, wouldn't it be more efficient to generate both at once?
One idea I had was using negative numbers for losses, 0 fr a draw, and positive numbers for wins

You can do that if you store the actual DTM, and have enough bits available to split the coding space in sets for white wins and black wins. In the old EGTB generator for which the code is posted on my website, I use 1 bit per wtm position, and 7 bits per btm position, packed together in 1 byte. The latter should hold the DTM, so the scheme allows me to go upto DTM=125, (I use some special codes for 'undecided', 'stalemate' and 'king capture'), which is already too small for some end-games.

The 'turbo' version also uses the DTM field for storing the move count of black moves to undecided (or stalemate) positions, and use negative numbers for that. This causes a large speedup, but makes the coding space even more crowded.

For really big TBs (pawnless 6- and 7-men) you cannot even afford 7 bits per position. The 7-men generator I am working on uses only 1 bit per position, and there such tricks are not possible. Anything extra you want to indicate immediately doubles the required storage and time (as the time is dominated by shuttling the stored data to and from a slow storage medium). If you generate them separately, the time will also double, but the required amount of storage not.

To Eric: it is not a matter of having separate files; a position can never be won for black and for white at the same time, so you can store them in the same TB. You just have to make sure the program can distinguish them. This takes one extra bit per position..

[EricLang]

Hmm... So I have to store this bitbase too (at least in endgames where black does have more than just a king).
I am hesitant to store this in the dtm-byte, because in 6 men endgames the remaining 7 bits are not enough to store dtm's that are >127.
Maybe I have to make the datastructure for 3,4,5 men different from 6,7 piece files.

For 3,4,5 men I could use the least significant bit because mates >127 do not exist.
For 6,7 men I could maybe setup a bitbase-block in the file.

[h.g.muller]

Getting confused...
How can I generate DTM=0 entries in a wtm-file?? they do not exist! So how can you store any DTM then?

I am not sure what you mean here. In principle, the side to move is one of the chararacteristics identifying the position. If pieces are on the same squares, but the other side is to move, the positions are different, and have their own entry in the EGTB. Wtm positions can have DTM=0 if white is checkmated in that position. Such positions only occur as wins for black. DTM>=1 positions occur both as wins for white and wins for black, depending on who has the move. That is why you have to clearly distinguish those.

It is not possible to generate the wtm and btm files separately, as black and white moves alternate, and DTM=n+1 btm positions only communicate with DTM=n btm positions through the mediation of DTM=n wtm positions. If you count the DTM in ply, rather than moves, this is even more obvious. But you can generate the list of positions won to white separately from those won to black.

[h.g.muller]

Hmm... So I have to store this bitbase too (at least in endgames where black does have more than just a king).
I am hesitant to store this in the dtm-byte, because in 6 men endgames the remaining 7 bits are not enough to store dtm's that are >127.
Maybe I have to make the datastructure for 3,4,5 men different from 6,7 piece files.

For 3,4,5 men I could use the least significant bit because mates >127 do not exist.
For 6,7 men I could maybe setup a bitbase-block in the file.

Our postings cross each other, so the order is a bit garbled...

But I think it is a very good idea in general to use completely different code for (pawnless) 3-5 men and >=6 men. The 5-men fit in RAM even if you use 1 or 2 bytes per position per side to move. The >=6-men do not. For something that fits in RAM, you don't care much how large the data set is, (as long as it still fits), as the most efficient algorithms typically need a separate DRAM access for each position you reach anyway, and they skip the rest. The entries you need in each cycle are typically so sparse that the probability you can fetch many together in the same cache line is small, even when you use only a single bit per position (512 positions per cache line).

As soon as the Hard Disk is involved, the minimum unit you can read and write is far larger, and skipping huge stretches in general does not result in time savings, as you have to wait until the skipped data rotates away underneath the head. So in practice it always takes as much time as reading the entire data set. So it is crucial to minimize the size of this set, and tricks like storing move counts never save you enough time in computation to make up for the extra bits they require in storage.

[notnale]

I'm not really knowledgeable about the relative speeds of memory and hard drives, but if the disparity is big enough, would it make sense to store a compressed version on the hard drive and decompress it whenever you access it?

[h.g.muller]

On my 2.4GHz Core 2 Duo I can do 900MB/sec in dirty cache replacements (i.e. one read + one write). Read only would give 3.5GB/sec. On a hard disk 50MB/sec read or write would already be a good speed.

So there is a significant factor between the two, and what you suggest is certainly worthwile. In the 7-men generator I am building, I do compress the data set indicating the most-recent generation of assigned DTx by run-length coding, where the run-length itself is encoded with a code of a variable number of bits (4 or 8 ) to get shorter codes for the more-frequently occurring short run lengths.

[koistinen]

I bought a new computer last month with Athlon 64 Phenom x4 9950 and nominally 8400 MB/s memory.
I measured the memory speed with read+simple computation+write and got about 8000 MB/s (counting read+write as 2 operations).
Before I decided on it I looked at the memory benchmarks at Tom's Hardware and it seems that AMD is about twice the speed of Intel using the sam memory capsules. This is something Intel is supposed to have fixed, but I have not yet seen any benchmark that shows this.

On my Samsung Spinpoint F1 1TB disk I have measured 120 MB/s read speed and write speed was about the same.
I have heard of reading and writing in the same pass but don't know if this is possible with normal cheap disks.
(It was lower at the end, but 80 GB easily fits in the fast part.)

Compression is something I think is best added once the tablebase generator code is in a working state.
Exception, using one bit per position in tables is a kind of compression that is best included from the start.

[h.g.muller]

How exactly do you measure the speed of your hard disk? Create a file far larger than your memory, and then read it sequentially? And especially for writing, do you write in an existing file?

I did a benchmark under Windows XP on my laptop, alternating seeks in an existing file on an NTFS partition with 2MB contiguous reads or writes, but the writing was horrendously slower than the reading. (Something like 3 sec read, and 24 sec write, IIRC.)

[koistinen]

I use GNU/Linux.
To test device /dev/hda at beginning I type:

dd if=/dev/hda of=/dev/null bs=80M count=1K

To test a 1TB disk near end I type:

dd if=/dev/hda of=/dev/null bs=80M count=1K skip=11k

(skips 11k*80MB=880GB so test is at end of disk)

With a sata drive the device would likely be /dev/sda or with more recent distributions /dev/.static/sda or similar.
The dd block copying program reports average copying speed when it is done.

[h.g.muller]

OK, I tried this on my laptop, (currently the only computer where I have Linux installed), for 1K blocks of 8M, and it was reaching a spead of 31MB/s. This should be somewhere halfway the disk. (I have a 120GB disk, and the irst 40GB consists of Windows partitions. I tried this on /dev/sda7, which is the Linux system partition, which should start directly after it.

For writing you just copy from /dev/null to /dev/hda.. ?

[koistinen]

For writing I copy from /dev/zero to a dedicated partition. (/dev/null is always empty, no matter how much you write to it.)
It is safe to test reading from the windows partition, writing is of course not safe. Read and write speed ought to be about the same speed when not involving a file system much.

[h.g.muller]

OK, thanks. I am getting more and more convinced that it is essential to do this under Linux in order to get acceptable performance. Until recently, I had no experience with Linux whatsoever, though. So I am learning now how to do elementary things, like editing and compiling. This is why I had a slight pause in the development of my 7-men builder. I have a Linux now running on my native laptop. Before, I tried running Linux under Windows in VirtualBox, but performance-wise this turned out to be a very bad idea; I could not nearly get the disk I/O speeds I am seeing now I really installed Linux in a separate partition. (Fortunately I could easily do that, as I had replaced a crashed 40GB HD by a 120GB one, as it was the smallest one I could buy, but the recovery software only worked if I fooled it into thinking the disk was 40GB as well. So I had still 80GB left to make Linux partitions! )

I will install Linux on my 'big' machine as well. (OK, it is a by now pathetic E6600 (2.4GHz Core 2 Duo) with only 1GB DDR2 DRAM.) I do have 2 physical hard drives on that, although they are also not as big as I thought: only 500GB in total, rather than each... But it will probably be smart to write the 7-men generator in such a way that it distributes the tablebase over two files (which in practice will be the raw partitions in /dev/hda* or /dev/sda*, dedicated to EGTB generation), so that it can double the bandwidth.

I am not sure the machine I have now will be up to the task. To run my 7-men algorithm I would at least need to equip it with another 1GB of RAM, and my disks probably would fill up before the building of a generally won EGTB is finished. Although 350GB, distributed over 2 disks, might be enough for end-games that do not require too many cycles. (My primary disk is currently partitioned as a 58.5GB Windows partition, and a 174GB unused partition, while the secondary disk is a single 232GB partition, completely unused. So I could take 58.5GB away from the latter, to install Linux plus a swap partition, and then I would have 2 x 174GB for building the tablebase.) I don't want to invest too much in this old machine; I am looking to buy a new PC based on the Core i7, but I want to wait until Intel releases the 8-core version of that. Although multiple cores is quite useless for tablebase generation, my Chess engine (which I plan to convert to SMP) will need as many cores as it can get...

[h.g.muller]

I succeeded in installing an Ubuntu on the so far unused disk of my C2D, after some initial problems with the display. I tested the tranfer rate as you described, and I get a speed or 58MB/sec on /dev/sda2, and 62MB/sec on /dev/sdb3 (the partitions I reserved for EGTB generation), reading 8GB at the beginning of the partition. Writing on them gave the same speed as reading.

So when I use the disks in parallel, it should be possible to reach a transfer rate of 120MB/sec. As one cycle involves reading and writing 518 x 64 chunks of 2.5-3.5M, say 100GB, that would amount to 840 sec read transfer time + 840 sec write transfer time per cycle. This is ignoring seek time. The transfer time adds up to under 30 min per iteration. But I guess the writing speed I timed is without verification (otherwise I don't see how it could be as fast as reading), and the process might not be reliable enough to afford this. So add 50% for verification, and another 50% for seek time, and we have 1 hour per cycle.

As a DTZ50 EGTB has at most 50 cycles, this means it should be possible to generate a pawnless 7-men in 50 hours, or about 2 days.