Author: Guido
Date: 12:52:30 03/09/04
Go up one level in this thread
On March 09, 2004 at 08:45:07, Bob Durrett wrote: > >The solution is thousands of years old. It's called "devide and conquer." > >Simply get a large number of people to create the tablebases. > >For example, a seven-piece tablebase can be n mutually-exclusive types of >seven-piece endgames and then each person generate the tablebase for his/her >part. > >This assumes some coordination. I hereby nominate Nalimov to do that >coordination. > >Bob D. I developed three different algorithms to calculate EGTBs: 1) DMA (Direct Move Algorithm): this, I suppose, is the method used by Nalimov. This method is the most linear and simple to code but it is very slow if compared with other methods. It is the fast only in useless cases (e.g. kqqqk and similar) where the solution is found in few moves, while in well balanced endings the cost in CPU time of this method can be many times the cost of the fastest method. 2) RMA (Retrograde Move Algorithm): this, I suppose, is the method used by De Koning for CM9. This method is the fastest method (except for the above mentioned useless cases) but it is the most complicate one. 3) RDMA (Retrograde&Direct Move Algorithm): this is a method found by me that represents a good compromise between the DMA and RMA as for efficiency (CPU cost) as for easiness of the algorithm. The difficulties encountered in method 2 and 3 are due to the computation of positions where there are capture/promotion moves, because a retrograde move cannot reach such positions starting from positions belonging to the same tablebase (we would have to start from the dependent tablebases but this complicates more and more the problem). Computing the 4 men TBs I obtained for the three methods CPU times proportional to 8, 1 and 2 respectively. For 5 men the gains of method 2 and 3 increase a lot in respect to method 1 (until some tens times or more), but I have not experimental values of the ratios because at present I have no more space on my disks to redo calculations. For 6 and more men it is easy to expect that the gains of methods 2 and 3 will increase more and more in respect to method 1. So my question is if it is logical to spend "thousands of years" for producing tablebases when the same result, even if not so optimized in the indexing scheme, can be achieved with a small fraction of this time. Obviously if Nalimov has changed his algorithm, these considerations are clearly useless. Another reason to wait is that 64 bits PCs will be available in short and the splitting of big TBs will become unnecessary under Windows (under Linux a solution seems possible also with 32 bits PCs). Ciao Guido
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.