Generate EGTB with graphics cards?

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
phhnguyen
Posts: 1431
Joined: Wed Apr 21, 2010 4:58 am
Location: Australia
Full name: Nguyen Hong Pham

Re: Generate EGTB with graphics cards?

Post by phhnguyen »

hgm wrote: Fri Jan 04, 2019 8:53 am Well, if you would require several hundred times as much calculation per position as is really needed, I would have no difficulty believing that. So the key question is: how fast is your generator (on a single-threaded CPU)?
I think you know already, there is no magic in computer chess. Except the new code is a simple counter only and/or changing from accessing HDD to work completely in memory, in general you cannot make the code run simnifically faster just by cutting few functions or replacing them by some faster ones. Actually I have tried already the method no-converting indexes but the speeding was not much (under 5%), and abandoned it since it affected badly to other functions.

For Xiangqi do you know any good way to avoid calling incheck function?
hgm wrote: Fri Jan 04, 2019 8:53 am If that would be orders of magnitude slower than optimum, trying to cure it with faster hardware IMO would not be the best strategy. I would first take the best conceivable algorithm, and then address the hardware requirements of that.
I was talking not about faster hardware but about cheaper solutions and the hope is to use some graphics cards instead of expensive multi-core CPUs.

I am sure even the most optimum code may beat me maximum 5% of speed but it may lose in other aspects thus optimisation is not my worries in long term.
hgm wrote: Fri Jan 04, 2019 8:53 am Note that for Xiangqi efficient creation of EGT is pretty much an unsolved problem. The rules for perpetual checking and chasing are basically incompatible with the idea of retrograde generation. So although it is possible to do some end-games (namely those where one side only has defenders) in the conventional way, the more interesting ones (such as KRPKR, KRCKR) would need a completely different treatment, and I am not sure whether it is actually public knowledge how exactly to do that, and how much the solution hurts speedwise compared to not having to deal with perpetuals.
I agreed with Guo, the article in his link is a solution. It is for perpetual checks only but you can easily do the same for perpetual chases.
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
User avatar
hgm
Posts: 27768
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Generate EGTB with graphics cards?

Post by hgm »

I don't understand what you mean by "code being a simple counter". And I am not talking about faster code, but about faster algorithms. There are many algorithms for building EGTs, and they can differ orders of magnitude in speed. (And forget about hard disks, I am only talking about in-memory generation.) The same holds for search engines, btw. A stupidly written engine, such as the AI included in Jocly, can easily be 100 times slower than a smart one, e.g. because it calculates the material eval and hash key in every node from scratch. My Tenjiku Shogi engine (mailbox / attack-map based) typically does 500knps; the main competitor, the bitboard-based mShogi does 5knps. So yes, one can in general work miracles. If the subject has not yet been beaten to death by thousands of people for many decades, so that everyone does basically the same thing that has been shown to work best.

So it really was a serious question: how long do you take to generate, say, KBNK?

As to the perpetuals: I am not so sure that the same algorithm would work for perpetual chasing. Because chasing can heave multiple targets (which then is allowed), while there is only one King to check (which makes it forbidden). So the network of 'tainted' moves is not automatically a perpetual chase.
User avatar
phhnguyen
Posts: 1431
Joined: Wed Apr 21, 2010 4:58 am
Location: Australia
Full name: Nguyen Hong Pham

Re: Generate EGTB with graphics cards?

Post by phhnguyen »

hgm wrote: Sat Jan 12, 2019 5:52 pm So it really was a serious question: how long do you take to generate, say, KBNK?
Sorry I don’t know. I don’t generate EGTB for chess but for other chess variants.
hgm wrote: ...
Because chasing can heave multiple targets (which then is allowed)
Technically speaking, chasing multi-pieces is a draw. You can ignore that chase.
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
noobpwnftw
Posts: 560
Joined: Sun Nov 08, 2015 11:10 pm

Re: Generate EGTB with graphics cards?

Post by noobpwnftw »

Use a staged pre-move generator so that you do not need to call in_check() on quiet moves.
User avatar
hgm
Posts: 27768
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Generate EGTB with graphics cards?

Post by hgm »

phhnguyen wrote: Sun Jan 13, 2019 5:39 amSorry I don’t know. I don’t generate EGTB for chess but for other chess variants.
Well, then just tell us the time you need per position in the EGT. This should be fairly constant, for a given algorithm. KBNK has roughly 2M positions (with 8-fold symmetry), so if FairyGen solves that in about 1 sec, that makes 500 ns/position.
hgm wrote:Technically speaking, chasing multi-pieces is a draw. You can ignore that chase.
That is exactly the point. The algorithm described in the paper will finally leave you with a sub-graph of 'tainted moves' from which no escape is possible to a non-lost position. With checks-only these can then be declared a loss. But if some of the tainted moves are chases, this is no longer true: you might be able to stay in the sub-graph 'forever' without losing, because you switch between tainted moves that check and chase, or between moves that chase different targets. So you would have to do some clever analysis of the sub-graph, to see which nodes in it are truly lost.

I am not saying that this is an unslovable problem. But I don't think it has been solved.

I was a bit surprised by the claim in the paper that end-games where chases can happen are "too big to handle". For one this is a statement with an expiration date, so it might already not be true anymore. But in end-games like KRPKR or KRCKR it is definitely possible to chase the C or P. So if these end-games are solved correctly while ignoring the chase rules, it must mean that all situations where you can chase can be won by the (chased) strong side anyway by breaking the chase. It s not obvious why this should be so.
User avatar
hgm
Posts: 27768
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Generate EGTB with graphics cards?

Post by hgm »

noobpwnftw wrote: Sun Jan 13, 2019 6:20 am Use a staged pre-move generator so that you do not need to call in_check() on quiet moves.
This already sounds very suspect to me. Call in_check() while generating EGTs? None of my EGT generators does such a thing. It seems a complete waste of time.
noobpwnftw
Posts: 560
Joined: Sun Nov 08, 2015 11:10 pm

Re: Generate EGTB with graphics cards?

Post by noobpwnftw »

hgm wrote: Sun Jan 13, 2019 11:33 am
noobpwnftw wrote: Sun Jan 13, 2019 6:20 am Use a staged pre-move generator so that you do not need to call in_check() on quiet moves.
This already sounds very suspect to me. Call in_check() while generating EGTs? None of my EGT generators does such a thing. It seems a complete waste of time.
Of course, because you haven't wrote a generator that handles Xiangqi perpetuals.

For one, when initializing terminal positions for large tablebases, proving all legal moves can be reduced to proving only captures by a staged pre-move generator if the position is not in check, that's a big save.

And of course there are cases where mutual chases/checks can happen and they are therefore draw instead of loss for any side, but those are not possible with those trivial endgames. Mark/resolve those positions during iterations, also a separate counter for progression.

Can you provide an example position of such "unsolved" problem? I have already built KRCPKRC in DTC, if that helps you finding one.
User avatar
hgm
Posts: 27768
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Generate EGTB with graphics cards?

Post by hgm »

noobpwnftw wrote: Mon Jan 14, 2019 3:41 amOf course, because you haven't wrote a generator that handles Xiangqi perpetuals.
I conceed that, but I don't see how that would make much of a difference. For Chess EGTs you also have to recognize when the losing side is in check, as the initial seeds for 'won' positions. But I don't judge that per individual position, but selectively generate in-check positions in bulk. (E.g. by for every constellation of winning pieces I mark all squares they attack, and then evey complete position with the losing King on such a square has that King in check. If the winning side has sliders and the losing side other pieces than King, you have to make an exception for the positions where such another piece is on a square attacked by the slider, and the King is downstream of it. In Chess this this reduces the amount of work by a factor 64 or 4096.) The same method can be used for marking positions in the EGT where the winning side is in check.

Speeding up things by a factor 4096 can be quite useful. In Xiangqi the speedup might of course be smaller, as a King has only access to 9 squares, not 64.
Can you provide an example position of such "unsolved" problem? I have already built KRCPKRC in DTC, if that helps you finding one.

Wouldn't you get this position wrong, if you ignored prepetual chasing?:

[d]4k4/9/9/9/9/9/9/4ER3/1r7/1OE1K4 w

Or this one, if you do not distinguish checks and chases?:

[d]4k4/9/9/9/9/9/9/4ER3/Or7/4K1E2 w 0 1
noobpwnftw
Posts: 560
Joined: Sun Nov 08, 2015 11:10 pm

Re: Generate EGTB with graphics cards?

Post by noobpwnftw »

In Xiangqi many cannon attacks are "discovered", also knights have blockers, so that method would need quite a few exceptions, and some optimizations can be done in the pre-move generator to differentiate quiet moves from those which are likely to produce checks, and for the rest, call in_check(), as I said in my original message.

Chasing must be handled, but such cases do not exist in trivial endgames because you don't have another free moving piece to make it perpetual since chasing from both sides is draw. A combined chase and check is forbidden, so they can even share the same tainting bit.

In case of a tainted position during iterations, try to prove it has an lowering move in a secondary counter, if there is, raise the secondary counter so that you can ensure it first lowers the secondary counter then lowers the distance. You cannot have a indefinite loop because you would eventually run out of tainted moves that you do not know their immediate adjudications and have lower secondary counters.

Pick DTC on the bottom left of the page and see the results of your position, note that there are two counters.
http://www.chessdb.cn/query_en/?4k4/9/9 ... C1B1K4%20w
noobpwnftw
Posts: 560
Joined: Sun Nov 08, 2015 11:10 pm

Re: Generate EGTB with graphics cards?

Post by noobpwnftw »

And second, http://www.chessdb.cn/query_en/?4k4/9/9 ... /4K1B2%20w

The tricky part is to make DTM tablebases, where this secondary counter cannot exist. One easy way is to build DTC first, then use the secondary counter in distance propagation to ensure progression, but this will cause sub-optimal play because some moves can lower that counter indirectly, so to ensure optimal DTM play, the distance counter on those positions are set to the minimum among all non-tainted positions plus one and later gets fixed up with extra iterations, so the final distance counts those loops 0 or 2 depending on its chicken or egg.