Interest in using GPU's for EGTB generator

[hgm]

For the 500+ cpus it would probably be best if they worked on different independent endgames in parallel. This way you sould be getting the best scaling.

The GPUs are more challenging, because they have to work on the same endgame. What do the others think of my proposal to use the additional processors to do more than just one leap per itereration? What benefit could we expect?

I don't understand what algorithm you would use. The bottleneck in the algorithm is probing daughter positions to see if they are already decided. If you have to probe in every leave node, doing two levels gives you N*N probes where a single level gives you only N probes. And it is the probes that consume all the time.

The problem is that a 7-men working set is about 500 GB. So it won't fit in RAM, you will have to use the hard disk. And the bottleneck is how fast you can shuttle the data from and to disk. What would help is a system with 500+ disk drives...

[Edmund]

For the 500+ cpus it would probably be best if they worked on different independent endgames in parallel. This way you sould be getting the best scaling.

The GPUs are more challenging, because they have to work on the same endgame. What do the others think of my proposal to use the additional processors to do more than just one leap per itereration? What benefit could we expect?

I don't understand what algorithm you would use. The bottle-neck in the algorithm is probing daughter positions to see if they are already decided. If you have to probe in every leave node, doing two levels gives you N*N probes where a single level gives you only N probes. And it is the probes that consume all the time.

Note: in the following by iteration I mean one cycle of the egtb generation process ie going through each permutation of the pieces on the board once

I think it is well applicable to the algorithm you describe on your website. The bottle-neck is the harddrive-I/O .. I suggest to use the data in the ram to solve as much as possible per iteration.

For example take the extreme example KQQNKBB with both bishops on the opposite color-square of the white king. If we now consider white K and N as fixed and white QQ and black KBB as dynamic (5 pieces .. 64^5=1G positions)

Most positions can be solved within one iteration, as the white king and knight don't need to be touched to reach the mate or the conversion to a won-subendgame.

So if the old algorithm would be:
1) get one slice from the HD to the RAM
2) for each btm white-won position make one white retro move
2.1) mark position as wtm white-won position
2.2) for each black retro move
2.2.1) if all black forward moves result in a position marked as wtm white-won, mark position as btm white-won
3) put the slice back to the HD
4) continue with the next slice

Now there would be two possible additions:
either you perform point 2 several times
or you could extend the 2.2.1 point:
2.2.1) for each black forward move
2.2.1.1) if position not marked as wtm white-won
2.2.1.1.1) for each white forward move
2.2.1.1.1.1) if position is btm white-won mark 2.2.1.1 as wtm white-won
2.2.1.1.1.2) else for each black forward move
2.2.1.1.1.2.1) for each position not wtm white-won
2.2.1.1.1.2.1.1) continue with 2.2.1.1

The problems would be a) getting this task done efficiently with multiple processors and b) I am not sure whehter it would be possible to get exact dtc scores or just win/not win information

[hgm]

OK, I see this can work if one side really has over-kill; you can then freeze what it does not need. (Unfortunately there are not many like that, neither are they very interesting.) In fact this is exactly what I am planning to do with P-slices (where the P are frozen). Such end-games are typically won through promotion, and when the end-game itself is balanced enough to be interesting, there will be an over-kill situation after promotion. So you can afford to freeze pieces of the winning side, (in particular his Pawns), and he will still be able to win.

So basically I would like to built tablebases under rules restricting what the winning side is allowed to do, and iterate that process by relaxing the restrictions, hoping to fully decide the P-slice before all restrictions have been lifted. Initially you would freeze all Pawns of the winning side, and consider all captures and promotions of the losing side as escapes. If you could not always win under thos restrictions, you would also allow non-promotion Pawn pushes, then allow Promotions that do not produce a second Queen, etc. This should quickly decide, say, most KQPKP slices without having to draw on information from KQQKP, KQPKQ, KQQKQ, KNNKQ, etc.

In most end-games of interest, pieces need to cooperate to achieve anything, though. E.g. in KBNK you could not make much progress if B or N were frozen, and the win-front would die out after two or three moves.

[Edmund]

OK, I see this can work if one side really has over-kill; you can then freeze what it does not need. (Unfortunately there are not many like that, neither are they very interesting.) In fact this is exactly what I am planning to do with P-slices (where the P are frozen). Such end-games are typically won through promotion, and when the end-game itself is balanced enough to be interesting, there will be an over-kill situation after promotion. So you can afford to freeze pieces of the winning side, (in particular his Pawns), and he will still be able to win.

So basically I would like to built tablebases under rules restricting what the winning side is allowed to do, and iterate that process by relaxing the restrictions, hoping to fully decide the P-slice before all restrictions have been lifted. Initially you would freeze all Pawns of the winning side, and consider all captures and promotions of the losing side as escapes. If you could not always win under thos restrictions, you would also allow non-promotion Pawn pushes, then allow Promotions that do not produce a second Queen, etc. This should quickly decide, say, most KQPKP slices without having to draw on information from KQQKP, KQPKQ, KQQKQ, KNNKQ, etc.

So do you think GPUs could be used for this?

Initially you would freeze all Pawns of the winning side, and consider all captures and promotions of the losing side as escapes.

Why not look them up in subendgames?

[hgm]

Because I assume that these are not available. So it would save time if you don't have to generate them. Now sub-end-games where you lose a piece are cheap, but also very unlikely to bring you any wins. Pawn losses might not be fatal, but do not alter the size of the P-slices. So my feeling is that it would pay off to first try if you can win without squandering away your Pawns. Letting the opponent promote would be outragously expensive, and give the lowest prospects for wins of all. Except per haps if there is a double-conversion where the Queen can immediately be taken. So it would be acceptable to probe or generate sub-end-games where the promoting Pawn simply disappears.

[Martin Brown]

The problem is that a 7-men working set is about 500 GB. So it won't fit in RAM, you will have to use the hard disk. And the bottleneck is how fast you can shuttle the data from and to disk. What would help is a system with 500+ disk drives...

Doesn't that mean that with the advent of fast solidstate drives with extremely low seek times and RAID capable configuration that it would be possible to provide TB class backing store for these types of computation. And that would surely be preferable to classic HD technology.

[hgm]

I don't know much about solid-state drives. Seek time is not a major bottleneck on hard-disks, though, with a good algorithm. So I guess the major factor is cost per bit.