Yearly Where are the 7-men Thread

Endgame analysis using tablebases, EGTB generation, exchange, sharing, discussions, etc..

Yearly Where are the 7-men Thread

Postby jshriver » Sat Jul 12, 2008 9:00 am

It's now 2008 and even I can afford a 1-2tb every couple months. So disk space doesnt seem to be the issue anymore.
So where are the 7-men tables and has anyone have any updates?

Every 6months or so this topic comes up and we all seem to dredge up posts from 2004-2005'ish about someone doing something but nothing ever comes out. For the general comp. chess community I feel we really need resolve.

Worse case we should pull our programming talents together and write an opensource or even BSD style generator so we can just get the tables out there.

*rant over* :) I'm just anxious and feel I've and many others have been patient.
-Josh
User avatar
jshriver
 
Posts: 287
Joined: Tue Jan 31, 2006 5:59 am
Location: Toledo, OH, USA

7-man ...

Postby guyhaw » Sun Jul 13, 2008 8:15 am

Worth sizing the task before you get impatient about the fact that 7-man EGTs have not been published.
The extra man makes the EGTs 60x the size of a 'corresponding' 6-man EGT, which means much more RAM for efficiency. Many will be much deeper.
There were 365 6-man endgames, but there are 1001 7-man endgames - 396 Pawnless (200 4-3, 140 5-2 and 56 6-1), with 1001 = 525 + 350 + 126.
Switching from the DTM metric to the DTZ metric ~50% of the TBytes, which would neatly cancel the effect of moving from 1-byte to 2-byte indexed-entries.
So I think you are looking at 180+ TB of information: frankly, I'm amazed that MB/YK have computed any 7-man EGTs at all.
It would be good to have the best algorithm in place for the next storage technology breakthrough, but creation, dissemination and storage are issues for now.

If you want to create some 7-man EGTs, the best opportunity is to use Eiko Bleicher's FREEZER in conjunction with Nalimov's 6-man DTM EGTs.
Meanwhile, the best option is to learn from what you have.
g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: Yearly Where are the 7-men Thread

Postby Vegan » Sun Jul 13, 2008 3:17 pm

Is there a web site or that Freezer program?
Vegan
 

Re: Yearly Where are the 7-men Thread

Postby Elmika » Sun Jul 13, 2008 11:07 pm

Hi, so far I used to visit this forum as a guest. I see some problems to generate 7-men with Freezer. First of all there's a limit in database seize. You can't generate databases with more than about 500.000.000 positions. It's a very low limit I think. I don't know the reasons for this, but I think it's independent from your hardware. Because of this I often was unable to generate some databases I wanted so far. Secondly, there's a bug in Freezer. In certain cases Freezer does't recognize a stalemate. I discovered this bug and told it Eiko Bleicher. He will correct it for the next release of Freezer. Of course, Freezer is a very useful program and I often use it! But how can one be sure that there aren't other bugs without checking the source code? I don't belief the useful results without some little doubt. I also often use tablebases for my analysis and training and studying these endgames, but I'm always somewhat doubtful whether they really are totally correct. By the way, do you know a program for working with the tablebases (I use them alone and with Freezer and Wilhelm) similar to Freezer or Wilhelm with other features?
Elmika
 
Posts: 9
Joined: Sun Jul 13, 2008 10:26 pm

Re: Yearly Where are the 7-men Thread

Postby Vegan » Mon Jul 14, 2008 12:42 am

Could be a problem with the compiler and/or the system call being made to write larger files. I am a skilled C++ programmer so I can talk.
Vegan
 

Re: Yearly Where are the 7-men Thread

Postby Dhanish » Tue Jul 15, 2008 8:58 am

Vegan wrote:Is there a web site or that Freezer program?


http://www.freezerchess.com/

Elmika wrote:Hi, so far I used to visit this forum as a guest. I see some problems to generate 7-men with Freezer. First of all there's a limit in database seize. You can't generate databases with more than about 500.000.000 positions. It's a very low limit I think. I don't know the reasons for this, but I think it's independent from your hardware. Because of this I often was unable to generate some databases I wanted so far. Secondly, there's a bug in Freezer. In certain cases Freezer does't recognize a stalemate. I discovered this bug and told it Eiko Bleicher. He will correct it for the next release of Freezer. Of course, Freezer is a very useful program and I often use it! But how can one be sure that there aren't other bugs without checking the source code? I don't belief the useful results without some little doubt. I also often use tablebases for my analysis and training and studying these endgames, but I'm always somewhat doubtful whether they really are totally correct. By the way, do you know a program for working with the tablebases (I use them alone and with Freezer and Wilhelm) similar to Freezer or Wilhelm with other features?


Hi Elmika,

Welcome to the Forum.

I have not used Freezer, and there is no demo version available. Could you compare the features of Freezer and Wilhelm? I am familiar with Wilhelm and I think it cannot be used for positions with material which are not covered by the available Tablebases. Though there is some engine along with Wilhelm, I have not made use of it.

About other programs, there is a post below about another similar program Hoffman (claiming to be better than Freezer), which somehow I could not make work.

Then, there is ChestUCI, which can also be used to access Nalimov tablebases in any UCI engine GUI.

Also, Scid can give statistics upto 5man positions.

What else?

Regards,
Dhanish
Dhanish
 
Posts: 47
Joined: Fri Sep 14, 2007 5:25 am

Re: Yearly Where are the 7-men Thread

Postby Elmika » Tue Jul 15, 2008 2:48 pm

To get a fist survey of the features of Freezer you should look through the website of Freezer. There are severals examples and an instruction (see "examples" and also "download").

Comparison of Freezer and Wilhelm:

Wilhelm only can use your available Tablebases (definitely up to 6-men except for 5-1, 7-men or more I don't know) to make some useful statistics, to give the estimation of the position in DTM and DTC, to fix some pieces and make statistics with the remaining ones and so on. You know that.

Freezer however uses your available Tablebases and the rules defined by yourself to generate new databases. It's especially useful for the case of fortresses or blocked pawn situations. You can generate databases with more than 6 men, because you can hold the database size small enough by freezing (--> the name Freezer) some of the pieces to particular squares or areas.
Some examples: 1) Your rook and some pawns build a fortress for your king against the opponents queen. Maybe you can "prove" (besides bugs) the draw by freezing your rook to one or two squares and your king to a small area behind the rook. If the side with the queen cannot win in this case, then it definitely cannot do so in the real situation (with more possibilities for the rook side). 2) You can study pawn endgames with many blocked pawns (I sometimes have more than 10 pawns). You may freeze most of them and search a break through for your king.
With Freezer you cannot make statistics but generate databases (also with more than 6 men) similar to Tablebases.

I think up to 6 men Freezer and Wilhelm complete one another well.

I don't use the engine along with Wilhelm (it's probably a poor one). For more than 6 men situations I only use Fritz with Tablebases and hopefully from August (?!) Rybka with Tabelbases.

Regards,
Elmika

Sorry Josh, you want to generate 7-men here. We should start a new topic "How do you use your Tablebases?".
Elmika
 
Posts: 9
Joined: Sun Jul 13, 2008 10:26 pm

Re: Yearly Where are the 7-men Thread

Postby Vegan » Wed Jul 16, 2008 12:23 am

Arena can set up positions and can put any one of 250 engines to work on it. Most chess programs can do deep positional analysis easily. Arena is free too.
Vegan
 

Re: Yearly Where are the 7-men Thread

Postby Dhanish » Wed Jul 16, 2008 6:22 am

Elmika wrote:To get a fist survey of the features of Freezer you should look through the website of Freezer. There are severals examples and an instruction (see "examples" and also "download").
...

Regards,
Elmika


Hi Elmika,

Thankyou for your comments, which confirm my understanding. Of course, such positions occur rarely and I am not able to decide whether to buy or not.

How much time does generating the database take? Is it feasible on a single processor machine? Would it be possible to analyse positions of the type: 3R4/2n5/2P5/2k5/r7/2PK1B2/8/8 w ?

Regards,
Dhanish
Dhanish
 
Posts: 47
Joined: Fri Sep 14, 2007 5:25 am

Re: Yearly Where are the 7-men Thread

Postby Elmika » Thu Aug 28, 2008 6:23 pm

[/quote]
...Of course, such positions occur rarely and I am not able to decide whether to buy or not.

How much time does generating the database take? Is it feasible on a single processor machine? Would it be possible to analyse positions of the type: 3R4/2n5/2P5/2k5/r7/2PK1B2/8/8 w ?

[/quote]

Hi Dhanish,
sorry, I´m late. I was bussy. I don´t think that such positions occur so rarely. In games maybe, but not in analysis, training, study... The question is, wheater you often deal with such positions or not.
About the generation time on my machine (2CPU 2 GHz, 2 GB RAM):
- whole KQ-K takes about 2-3 sec.
- whole KBN-K with the help of 3-piece-TBs about 2 min 5 sec
- most interesting positions I use Freezer for about 15 min - 1h 30 min
Your position is definitey near the limit of Freezer: many pieces with many unblocked pawns.
Your position is interesting. I´ll try it soon. The idea is to freeze the black pieces near the pawns. If this holds for Black, then the position is a draw. But I´m not sure, wheater the try will be successful. The problem is near the limit as I mentioned, but I don´t know on which side of the limit. :)
Regards, Elmika
Elmika
 
Posts: 9
Joined: Sun Jul 13, 2008 10:26 pm

Freezer ...

Postby guyhaw » Sat Aug 30, 2008 2:16 pm

It is available from http://www.shredderchess.com/chess-program/freezer.html and I recommend it.

If you haven't got the relevant 6-man EGT, you can generate it (when there are 'blocked Pawns') from the 5-man EGTs and FREEZER. This is v useful, and I used it to examine the famous KRP(a2)KbBP(a3) position of some years ago (which was somewhat wrongly analysed by JvdH and colleagues in Holland).

Generating the 6-man EGTs took v little time, as the position of the two Pawns was v limited: it's more like generating a 4-man EGT.
g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: 7-man ...

Postby Oded Ross » Thu Mar 26, 2009 7:54 pm

guyhaw wrote:Worth sizing the task before you get impatient about the fact that 7-man EGTs have not been published.
The extra man makes the EGTs 60x the size of a 'corresponding' 6-man EGT, which means much more RAM for efficiency. Many will be much deeper.
There were 365 6-man endgames, but there are 1001 7-man endgames - 396 Pawnless (200 4-3, 140 5-2 and 56 6-1), with 1001 = 525 + 350 + 126.
g

How many of them have been published to date? Is there any list of the 7-man EGT already explored?
Oded Ross
 
Posts: 3
Joined: Thu Mar 26, 2009 6:50 pm

Re: Yearly Where are the 7-men Thread

Postby Kirill Kryukov » Mon Oct 05, 2009 4:35 am

jshriver wrote:It's now 2008 and even I can afford a 1-2tb every couple months. So disk space doesnt seem to be the issue anymore.
So where are the 7-men tables and has anyone have any updates?

Here is one interesting post from Rybka forum:

Victor Zakharov wrote:After reading this thread I’ve made a conclusion that most people can’t imagine how difficult is the process of creating the tablebases. So here are my 2 pence to this topic.

It is true that an experienced person can write a 7-men tablebase generator in one-two days. The only problem with such a program is that it either will work for ages (using disk all the time) or will need about 3 TB RAM (and then it will be several times quicker). 3 TB RAM is 1000 times more than a modern PC has. Fortunately, it is possible to implement slicing, i.e. splitting the tables to the parts that do not much depend on each other.

The major tricks in 7m generation are connected with optimizations in speed, RAM and final table size on the disk. There are trivial optimizations like considering symmetries, there are average optimizations like compression, slicing tables in the limited RAM, and there are huge optimizations for significant reducing number of operations and dimensions. These significant optimizations are the key for the solution of the problem in reasonable time.

Usually different optimization targets contradict each other. For example for reducing dimensions it is logical to exclude impossible positions. So the program will need less memory and disk size. It is easy to discover that two kings can’t be in touch with each other. But it is not easy to exclude the positions where on the white move the white queen attacks the black king. Discovering king capturing and proper indexing slows down the program several times and adds years to the final date.

So developers frequently have not-pretty choice between reducing dimensions and raising calculation time. I believe that there were many developers who started their own generation project (the initial idea of how to generate is quite simple). But most of them quickly understood that there is no universal trick to avoid huge complexity of chess endings for modern computers.

We should not forget that sizes invoke major technical problems with debugging (imagine program failure after a month of calculations), hardware stability, verification, backups and so on. The developer should devote significant part of his life for the solution of the Problem. For my estimation, Nalimov worked 15 years for his 5 and then 6-men tables. Not everyone is ready to make such big efforts for such a long period.

And surely a cost of hardware is significant. So the entering fee is expensive.

Some known large-dimension problems were solved using distributed calculations. Unfortunately 7-men generation process can’t use the technique of distributed calculations with many networked computers. Having some 7-men position you may need to know evaluation of any position in the current ending (and in the minor endings). The theoretical number of 7-piece positions with the pawns is about 2,500,000,000,000 ( = 64*63*62*61*60*59*48). So you need 5TB to manage them. Now you can understand that the programmers need think thoroughly about every decision they make in their program.

BTW, Nalimov opened his code for operating with 6-men tablebases. But he didn’t make public the generation program. For my opinion there was a lot of different tricks in his code. And these tricks were not the best part of the code. Possibly he even didn’t have universal program but generated special programs for different classes of endings. (Sorry, this is just some thoughts, not the facts.)

So after reading of all this you may understand why the progress of 7-men generation is not well visible. Only one brave and successful group is well-known: Yakov Konoval and Mark Bourzutschky. But there is no reliable information what progress is achieved and what is estimated time for finish. The only thing that is clear from announced generation time that their algorithm is better than Nalimov’s one.

And finally let’s imagine that 7-men tablebases has been generated. The lower estimation for their size in compressed form is 100 TB. I believe that one useful ending like KRPPKRP will demand hundreds of gigabytes on disk. Is anybody ready to download such data and to keep this on the disks? Only a few persons in the world may have hardware that will allow them to use 7-men in engine search. So the only way of using the tables is on-line access via web-services.

It is too early to wait 7-men tables for everyday life. It is too early even to speak about standards for TB7-access and to ask about engine support of them.

I agree with every word of it.

Except, as far as I know, Nalimov's generator is public. Look here for example.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: Yearly Where are the 7-men Thread

Postby koistinen » Tue Oct 06, 2009 8:26 pm

Kirill Kryukov wrote:
jshriver wrote:It's now 2008 and even I can afford a 1-2tb every couple months. So disk space doesnt seem to be the issue anymore.
So where are the 7-men tables and has anyone have any updates?

Here is one interesting post from Rybka forum:

Victor Zakharov wrote:After reading this thread I’ve made a conclusion that most people can’t imagine how difficult is the process of creating the tablebases. So here are my 2 pence to this topic.

It is true that an experienced person can write a 7-men tablebase generator in one-two days. The only problem with such a program is that it either will work for ages (using disk all the time) or will need about 3 TB RAM (and then it will be several times quicker). 3 TB RAM is 1000 times more than a modern PC has. Fortunately, it is possible to implement slicing, i.e. splitting the tables to the parts that do not much depend on each other.

...


I agree with every word of it.

Except, as far as I know, Nalimov's generator is public. Look here for example.


Some tricks are:
First trick - don't keep much information about each position in ram.

Don't use distance directly, instead only store what you need to compute the next iteration.
Compute only wins for white and losses for black.

When computing new black losses:
Use 1 bit/wtm position, for white win or illegal position.
Use 1 bit/wtm position, for new white win
For each black position, if there is no legal move that avoids loss and one legal move reaches a new white win, it is a new black loss.

When computing white wins:
Use 1 bit/btm position, for black losses.
Use 1 bit/btm position for white win or illegal position.
For each white position, if it is not already won and a legal move reaches a black loss, it is a new white win.

White wins are computed by or-ing the previous white wins with the new white wins.

So far, we are down to 3 bits of ram per position.

After using mirroring and the like we need <3*2^(7*6-3) bits of ram. ~= 192 GB

Second trick - partition the tables so that each part can be computed separately.
Say you construct the index by joining the positions of the pieces like this:
BBWWxyz, i.e. two black pieces,, two white and then the remaining 3.
Then, by fixing the position of the two pieces of the side whose moves you are not examining (except for possible mirroring) you reduce the size to 1/512..
There is a downside that you get to do disk reads and writes in blocks of only 64^3 bits but that can be helped so you get blocks 8^3 times larger. i.e. ~= 32 KB or 16 MB
Using the larger block size the reduction is only to 1/64, but 3 GB is still not overmuch on a pc of today.

Third trick is examining moves for bitboard size chunks at a time in order to use less cpu.

So, while plenty of disk space is needed to store the results, you don't need all that much ram to do the computation.

I discovered parts of this in discussion on this site (special credits to h.g.muller) and there are other ways to partition the computation.

With the first two tricks you should need 3GB, not 3TB of ram.
Is my explanation clear and have I made some mistakes?
koistinen
 
Posts: 80
Joined: Fri May 02, 2008 7:59 pm
Location: Stockholm


Return to Endgame Tablebases

Who is online

Users browsing this forum: No registered users and 3 guests

cron