Author: Urban Koistinen
Date: 21:56:53 04/08/01
Go up one level in this thread
On April 08, 2001 at 16:13:05, Vincent Diepeveen wrote: >On April 08, 2001 at 06:47:56, Aaron Tay wrote: >>So what do the experts think? Is the algorithim as good as he claims? Layman >>like me want to know! > >Yes the algorithm is good, but the math below is not correct. >A harddisk is not doing 40mbit/s when doing random lookups. Not even when block size is 256 Kbyte or more? >Also the algorithm is very cpu intensive when you try to get the EGTBs >smaller as 4096 * n where n is the position without the 2 kings at the >end. > >The big problem is that you need 4096 positions for the king >as otherwise the conversion from white to move to >black to move is going to use too much CPU time. It is enough to have 64 positions for the king. If there are no pawns it is best to have a king in the 10-square triangle because that way less mirroring of bitmaps need to be done. (12 out of 22 bitmaps for the king) >Anyway the programming is very hard. Too hard for me, as I haven't managed to do it. :( Perhaps it will be easier now that I have written the algo down more properly and discuss it. > I'm using this already for years >though. a 5 man goes real fast as it is all fitting within the memory >ram. About an hour. > >I don't get the discussion about whether a position is mate in 20 or 23. >I don't care personally whether a position is mate in 20 or 23. > >If i can get an egtb hit from a 6 man with just win/draw/loss/win50+/loss50+, >then that's excellent i think. The alternative is NOT using a 6 man, >as Nalimov is not going to generate 6 men with pawns real quick. > >This algorithm provides a basis for computing things way quicker. > >The BIG drawback of this algorithm is that you need 4096 positions for king, >because that's a huge increase in storage space when generating. >Actually the biggest increase is the I/O needed and with such huge >tables you DEFINITELY don't want Random I/O. If you solve that problem, >then you need loads of RAM to generate 6 men with pawn with this algorithm, >and that's a big problem as the ram needed is even bigger because the >table size is that big as you need at the end 2 kings. Counterexample: PR v RN Index: P43210k543R543k210R210r543210n543210K543210 The pawn is in one of 24 positions a7..a2,b7..b2, etc and each pawn position is examined in turn, just like Arlazarov&Futer did. When examining black moves, the white rooks top 3 bits can be in an outer loop. When examining white moves, the black kings top 3 bits can be in an outer loop. Now 2**(30-3) bits = 16 Mbyte of core is needed for each table and disk i/o can be done with block size of 2**(30-3-6) bits = 256 Kbytes. No more than 3 tables at a time need be in core at the same time. (With a little more clever coding 2 tables at a time are needed.) >So yes the algorithm works. But no it's not 64 times faster, but if >the problem is random i/o, then this is not going to help you much >as the random i/o only gets more than doubled. i/o is not random but very predictable and with a large block size. If you double the core size, the block size can quadrouple. Urban Koistinen
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.