7-men EGTB Bounty

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

7-men EGTB Bounty

Postby Kirill Kryukov » Thu Jul 31, 2008 8:30 am

The idea is to encourage creation of a useful 7-men EGTB generator and probing code, and construction of 7-men tablebases, by creating a bounty fund that will be paid to the first successful developer.

Introduction

Few years ago I already saw reports about some long checkmates in 7-men endings. Clearly some generators and tablebases exist already, but they are not freely available. Also there is a number of skillful developers who can do this, but are currently not motivated enough to invest time and efforts necessary to create such generator. The idea is to motivate creation and open release of the 7-men generator. So I propose to create a prize fund that will be paid to the winner - the first successful creator of the complete 7-men EGTB solution.

We need to set requirement to such solution. A "solution" should probably include a generator, verification and probing code (free, open source and portable), and some basic set of tablebases. We will need to select a few people who will perform the verification of submitted solutions. We will also need a person who will collect the money and then send it to the winner.

Requirements to a 7-men EGTB Solution (under construction and review)

A successful 7-men EGTB solution should include 1. Generator. 2. Probing code. 3. A set of pre-computed tablebases.

Requirements to the tablebase format:
  • Four kinds of metrics must be fully supported: DTZ50, WDL50, DTZ, WDL.
  • En-passant should be taken into account. (It's OK to not store the EP positions in the tables as long as the tables are EP-correct and the probing code performs the necessary search automatically.)
  • A metric used must be recorded in the file name or in the file itself (preferably in both).
  • A compression method used should be recorded in the file (allowing future update of the compression method).
  • Every tablebase file should contain a checksum or a signature for integrity checking. (Preferably of at least MD5 strength).
Requirements to the generator:
  • Open source, released under an OSI-approved license
  • Does not depend on non-free code (like Nalimov's code).
  • Can generate all 3-to-7 piece tablebases (except 6-1 which is not required), without depending on any other tablebases.
  • Handles dependencies automatically.
  • Is able to convert a DTZ* table into a corresponding WDL* table.
  • Does not require lesser DTZ* tables for generating the next DTZ* table (can use WDL* instead).
Requirements to the probing code:
  • Open source, released under an OSI-approved non-viral license (allowing commercial closed source use).
  • Does not depend on non-free code (like Nalimov's code)
  • Written in standard C
  • Does not take forewer to initialize
  • Can return WDL50, DTZ50, WDL or DTZ, depending on request and on tablebase files present.
  • Includes API for verifying the tablebases integrity (using a checksum embedded in every file).
  • Includes API for probing a position by FEN string
Requirements to the set of pre-computed tablebases.
  • At least one pre-computed tablebase from each category: 52 52p 43 43p.
Optional features (bonus)
These features are not required, but will be appreciated. Also used in a tie situation.
  • Speed of probing WDL and WDL50.
  • Size of the tables. The smaller the better.
  • Generation speed. (Including the ability to generate WDL and WDL50 directly without generating DTZ or DTZ50 first).
  • Support for 6 vs 1 tables.
  • Castling (tables for positions with castling rights).
  • Support for any metric WDL(k) and DTZ(k), in addition to the required WDL50 and DTZ50.
  • An example engine adopted to use the new tablebases in search. (Any open source WB or UCI engine should be OK).

Open questions

Competition format: prize (several complete solutions may compete in performance and features) vs bounty (the first successful solution wins)

Should we require a set of generated tablebases to accompany eash solution? If so, which set of the tablebases? (The rest will be generated by the community).

Should we require that a generator can work on certain hardware, particularly RAM and disk space?

Should we require that a generator can complete generation in some reasonable time?

Should we set any standard for a probing API?

Who will verify the solutions and who will manage the funds?

Should we require an example engine to be adopted to use the probing code? (Any open source engine will be fine).

Should all the prize money be paid to the winner immediately, or should a part of it be saved to keep him motivated to maintain the generator. For example, half is paid immediately, another half one year later assuming he fixed any issues discovered in this one year.

There are many details to consider, so please post your ideas, concerns, suggestions, etc... I will update the first post with the relevant information.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 7-men EGTB Bounty

Postby jkominek » Thu Jul 31, 2008 1:50 pm

Kirill Kryukov wrote:The idea is to encourage creation of a useful 7-men EGTB generator and probing code, and construction of 7-men tablebases, by creating a bounty fund that will be paid to the first successful developer.

An interesting idea! And you've introduced a novelty. Traditionally the prize originator is a multi-millionaire, as in Peter Diamandis. Do you want to call it the TB-Prize?

Kirill Kryukov wrote:We need to set requirement to such solution. A "solution" should probably include a generator, verification and probing code (free, open source and portable), and some basic set of tablebases.

To establish coverage I think there would need to be at least one example from each category: 61 61p 52 52p 43 43p. Consumers of the work no double would want the most useful tables first, but that's not the way it goes.

That's all I have to add for now.

john
jkominek
 
Posts: 142
Joined: Mon Dec 04, 2006 9:02 am
Location: Pittsburgh, PA

Re: 7-men EGTB Bounty

Postby Kirill Kryukov » Thu Jul 31, 2008 2:31 pm

jkominek wrote:An interesting idea! And you've introduced a novelty. Traditionally the prize originator is a multi-millionaire, as in Peter Diamandis. Do you want to call it the TB-Prize?

TB-Prize is too general, as there may be more TB-Prizes in future? (8-men for example :-)) I also like the word "bounty". (owing to the ancient game "King's Bounty"). :-) (Not that it matters too much though, any name is OK as long as we talk about the same thing).

Not being a multi-millionaire is certainly a big limitation. So this bounty will have to be community-funded. Once we agree on reasonable conditions, we will announce it everywhere and ask people to donate according to how badly they want to see usable 7-men EGTB.

jkominek wrote:To establish coverage I think there would need to be at least one example from each category: 61 61p 52 52p 43 43p. Consumers of the work no double would want the most useful tables first, but that's not the way it goes.

Good idea. And I agree that kpppkpp certainly won't be one of the required sets. But may be at least one pawnful sets in each of those categories?
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 7-men EGTB Bounty

Postby h.g.muller » Thu Jul 31, 2008 4:46 pm

Don't worry, I will write the 7-men generator for free. Just wanted to upgrade WinBoard first, though.

Most 7-men EGTBs are useless from the viewpoint of winning Chess games, btw. Those that are relevant contain several Pawns, and those are trivial to generate with the memory sizes of today.
h.g.muller
 
Posts: 216
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: 7-men EGTB Bounty

Postby Dhanish » Fri Aug 01, 2008 3:46 am

Hi Kirill,

An excellent idea, as long as we are able to fi(u)nd a sufficiently attractive "bounty"!

Some thoughts:

If we change the metric from DTM, the existing 6men Nalimov tablebases will go waste? And all these efforts at distribution?

As I understand it, the tablebase data is free, but the access code is licensed. If somebody can write another code (open source and free) for the access, would it be sufficient?

In that case, it would be better to stay with DTM?

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

Re: 7-men EGTB Bounty

Postby Kirill Kryukov » Fri Aug 01, 2008 2:47 pm

h.g.muller wrote:Don't worry, I will write the 7-men generator for free. Just wanted to upgrade WinBoard first, though.

Hi H.G.! That will be terrific! But please forgive me that I am still worrying. Unclear parts about your generator are: 1. ETA. 2. License. 3. Metric, performance, etc. By having a defined feature set requirement we may be lucky to get a generator of a dream. Also community-funded bounty will allow everyone interested to contribute, not just to wait passively. And if you succeed and claim the bounty, there is no harm either? :-)

h.g.muller wrote:Most 7-men EGTBs are useless from the viewpoint of winning Chess games, btw. Those that are relevant contain several Pawns, and those are trivial to generate with the memory sizes of today.

This will be up to the community to decide. There are some completeness freaks out there. (I know a few :-)) Also, pawnful tables would probably require pawnless (or N-1 pawnful) sets during the computation anyway? So essentially every 4-3 set has to be computed before you can compute kpppkpp.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 7-men EGTB Bounty

Postby Kirill Kryukov » Fri Aug 01, 2008 3:00 pm

Dhanish wrote:If we change the metric from DTM, the existing 6men Nalimov tablebases will go waste? And all these efforts at distribution?

As I understand it, the tablebase data is free, but the access code is licensed. If somebody can write another code (open source and free) for the access, would it be sufficient?

Well 7-men tables of course need 6-men tables. So a successful generator will need to handle this without using Nalimov's code. Nalimov's code is not free, so currently we use it only because there are no alternatives.

Whether we will need to dump the Nalimov's tables or not is a question, but personally I would not stick to Nalimov's tables if we have a new format backed by a free code. Actually Nalimov's tablebases will be still around for some time because so many engines are using them.

I also hope that a replacement 6-men tables (if it comes to this) will be more compact than Nalimov tables (due to different metric, or better compression).

Dhanish wrote:In that case, it would be better to stay with DTM?

I don't know... DTZ would be good enough for me, and it's more compact than DTM.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 7-men EGTB Bounty

Postby Kirill Kryukov » Fri Aug 01, 2008 3:02 pm

Dhanish wrote:As I understand it, the tablebase data is free, but the access code is licensed. If somebody can write another code (open source and free) for the access, would it be sufficient?

Probably yes, but I doubt it is the best solution.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 7-men EGTB Bounty

Postby kronsteen » Fri Aug 01, 2008 5:20 pm

Greetings,

I’m a French chess amateur, and I enjoy tablebases a lot. Here are my opinions about your proposals :

Metrics :

Code should be able to provide some kind of DTx. I find DTM more fun and more in the spirit of the game, but maybe space savings by using DTC or DTZ are too much important consideration.

WDL may be considered as an “optional compression mode for final data storage with information loss” but not a goal in itself, even if it may be of some use for practical purposes, as WDL convey far less information and leave hungry about how to win won positions, how difficult/long it might be, etc... . Also, WDL generation is immediate from DTx TBs, and I don’t believe that a code generating only WDL would be significantly faster to run, or easier to achieve.

Goals :

Full release of 7-men may not be expected before 2020, I think. Most useful TBs for practical players are unfortunately last ones to be generated as they contain 3, 4 or 5 pawns (top of list is probably krppkrp, “last stone” kpppkpp is also of great interest). Also, pawnless TBs, which are first to be generated, are completely worthless for regular players as they almost never happen in practical game. So it seems imperative to define short-medium term less ambitious goals which may be more suitable for a first attempt. What I think of is :

- Generate TBs for endings whose general result is still not clearcut (regardless of their interest to practical players). The purpose is to raise new knowledge and nothing else. There are a lot of good candidates. Pawnless species with heavy piece duplication (such like knnnkqn) are ideal first targets. First rule of thumb is to consider “not clearcut” endings with delta in material balance of 1 or 3 (according to scale p=1 bn=3 r=5 q=9)

- Providing some fun results like unearthing new long win records, amazing reciprocal zugzwangs, etc… . Full DTM krbnkqn is a dream in itself

- Awaking standard chess community’s interest with some reasonably reachable TBs which may be of some practical use (I think of krrpkrr as the best candidate). But such effort will only provide samples which won’t cover much of practical game

Selecting purposeful goals will allow TB targeting strategy, and capability limitation in first generation code which won’t need to be able to generate every of the 1001 7-men TBs.


Performance :

What may be suggested is a code capable of generating most complex targeted TBs on a high-end RAM/CPU/hard drive PC, within a long but still manageable time such as 1 or 2 weeks. No need to perform faster as 7-men is a very long term project and every single TB, how long its generation might be, is a milestone in itself.


Marc Bourzutschky's first work seem very fitting to all this stuff. Good idea is simply to go ahead, extend and release what he began to undertake.

Good luck in your future attempts, it’s a really wonderful project :D
kronsteen
 
Posts: 88
Joined: Fri Aug 01, 2008 11:20 am
Location: France

Re: 7-men EGTB Bounty

Postby Mark » Sat Aug 02, 2008 2:50 pm

What is Marc Bourzutschky doing with tablebases now? Is there any way to build on what he has already done?
Mark
 
Posts: 13
Joined: Tue Jun 24, 2008 11:15 am

Re: 7-men EGTB Bounty

Postby Kirill Kryukov » Sun Aug 03, 2008 3:33 am

Hi kronsteen! Welcome to the forum and thanks for your thoughts!

kronsteen wrote:Metrics :

Code should be able to provide some kind of DTx. I find DTM more fun and more in the spirit of the game, but maybe space savings by using DTC or DTZ are too much important consideration.

WDL may be considered as an “optional compression mode for final data storage with information loss” but not a goal in itself, even if it may be of some use for practical purposes, as WDL convey far less information and leave hungry about how to win won positions, how difficult/long it might be, etc... . Also, WDL generation is immediate from DTx TBs, and I don’t believe that a code generating only WDL would be significantly faster to run, or easier to achieve.

Yeah, I tend to like DTx too. I think DTZ may be the metric of choice, because it allows to save much space compared to DTM.

kronsteen wrote:Goals :

Full release of 7-men may not be expected before 2020, I think. Most useful TBs for practical players are unfortunately last ones to be generated as they contain 3, 4 or 5 pawns (top of list is probably krppkrp, “last stone” kpppkpp is also of great interest). Also, pawnless TBs, which are first to be generated, are completely worthless for regular players as they almost never happen in practical game. So it seems imperative to define short-medium term less ambitious goals which may be more suitable for a first attempt. What I think of is :

- Generate TBs for endings whose general result is still not clearcut (regardless of their interest to practical players). The purpose is to raise new knowledge and nothing else. There are a lot of good candidates. Pawnless species with heavy piece duplication (such like knnnkqn) are ideal first targets. First rule of thumb is to consider “not clearcut” endings with delta in material balance of 1 or 3 (according to scale p=1 bn=3 r=5 q=9)

- Providing some fun results like unearthing new long win records, amazing reciprocal zugzwangs, etc… . Full DTM krbnkqn is a dream in itself

- Awaking standard chess community’s interest with some reasonably reachable TBs which may be of some practical use (I think of krrpkrr as the best candidate). But such effort will only provide samples which won’t cover much of practical game

Selecting purposeful goals will allow TB targeting strategy, and capability limitation in first generation code which won’t need to be able to generate every of the 1001 7-men TBs.

Should not it be up to the community to select what sets to generate? I think we should just enable some sort of coordination, to avoid wasting the effort doing something twice. For example we can use a forum thread where everyone posts what they are generating, and someone maintains the list in the first post.

Eventually everything will be generated, but people running the generators will choose the order they like. They may of course agree with your reasoning, but they as well may have their own idea what sets are more important or interesting. :-)

kronsteen wrote:Performance :

What may be suggested is a code capable of generating most complex targeted TBs on a high-end RAM/CPU/hard drive PC, within a long but still manageable time such as 1 or 2 weeks. No need to perform faster as 7-men is a very long term project and every single TB, how long its generation might be, is a milestone in itself.

So, say, 2 weeks for a kbnpkrp on a reasonably high-end machine. This needs some thought.. For example performance should be easy to verify at the time of the generator review.

kronsteen wrote:Marc Bourzutschky's first work seem very fitting to all this stuff. Good idea is simply to go ahead, extend and release what he began to undertake.

Yes he may be close to be able to claim the bounty if he like it.

kronsteen wrote:Good luck in your future attempts, it’s a really wonderful project :D

Thanks!
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 7-men EGTB Bounty

Postby Kirill Kryukov » Sun Aug 03, 2008 3:35 am

Mark wrote:What is Marc Bourzutschky doing with tablebases now?

No idea.

Mark wrote:Is there any way to build on what he has already done?

Possibly, as soon as he releases anything to the public.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 7-men EGTB Bounty

Postby kronsteen » Sun Aug 03, 2008 10:41 am

I you think of DTZ, I may think that DTZ50 (i.e TBs taking into account 50-move rule) may be even a better idea, as it saves even more space and rises a new very interesting aspect of the game. I don't know what work has currently be achieved about DTZ50 (5 men ? Some 6 men ? Specific interface for analysis ?) but it is clear that DTZ50 7-men must rely on DTZ50 5/6-men and not currently available DTM or DTC 5/6-men. This makes DTZ50 5 and 6-men a necessary, and very heavy, preliminary work. But it may be worth it, as full set of DTZ50 6-men is bound to weigh far less than 1.2 TB and may be a good add-on to your site.

DTZ50 will probably rise some very interesting new knowledge about some endings like knnkp or kqpkq (and many 6-men). It will also need developing of a new interface which takes into account, in position evaluation, how many non-zeroing half moves are still left before 50-move draw claim.

About goals, preferences and priority settings, this is clearly open discussion in community, and what I provided are only first and personal ideas, which have to be completed by other's opinions and points of view. But I got this started because I think that serious debate about them should be achieved before moving to practical work, as they will engage work for a long time and contain some crucial choices such as metric selection and acceptable code limitations.

kbnpkrp generation in 2 weeks seems challenging with today's hardware, unless some skillful programmer builds a very fast code. It is a good baseline, but if it proves too hard to achieve and/or verify, limiting this test to easier TBs (those pawnless and/or with piece duplication) may be more suitable, as we can reasonably expect more power when moving to the most complex TB type. Remember, first released 6-men (at Bob Hyatt's ftp) were 33 pawnless with 1 duplicated piece on board.
kronsteen
 
Posts: 88
Joined: Fri Aug 01, 2008 11:20 am
Location: France

Re: 7-men EGTB Bounty

Postby koistinen » Sun Aug 03, 2008 12:51 pm

As DTR is only a little harder than DTZ50 and gives correct answer for default rules, I think DTR should be the goal.
(DTZ is easier than DTM.)
To compute DTR, compute DTZ for both odd and even game50 and as soon as the set of wins with game50=N is the same as the set of wins with game50=N+1 you need only compute for game50=N+2*d as game50=N+1+2*d will have exactly the same positions won from then on.
My guess is that for most endgames, N could be less than 10.
koistinen
 
Posts: 80
Joined: Fri May 02, 2008 7:59 pm
Location: Stockholm

Re: 7-men EGTB Bounty

Postby syzygy » Sun Aug 03, 2008 4:52 pm

I don't think DTZ50 will save much space over DTZ. If it does, the compression algorithm needs fixing. Only very few positions will have DTZ>50, so few that it should not have a noticeable impact on the compressed size.

(IMO compression should not be done on a byte-level, but on a position-level basis. Encoding positions as two bytes (to cope with large DTZ/DTC/DTM values) and compressing at byte-level, or packing 5 WDL-values into one byte and compressing at byte-level, will inherently lose compression efficiency.)

I agree with koistinen that having DTR will be interesting as a final goal, but I am not convinced that it is only a "little harder" than DTZ/DTZ50.

koistinen wrote:To compute DTR, compute DTZ for both odd and even game50 and as soon as the set of wins with game50=N is the same as the set of wins with game50=N+1 you need only compute for game50=N+2*d as game50=N+1+2*d will have exactly the same positions won from then on.

I'm not sure I understand this. First of all it's not immediately clear to me what you mean by "game50". I might be able to figure out if I try a little harder, but in any case it seems you would want to limit DTR to DTR=50. Why not compute DTR values without any limit on the number of moves? I don't think it is very interesting to know what positions cannot be won with a hypothetical "20 move rule", but it would be interesting to know what positions can and cannot be won with a hypothetical "100 move rule".

However, computing DTR seems quite complicated. The most obvious way of generating them needs two counters per position: one for DTR, one for DTZ. The problem is that there will be long winning paths with constant DTR. I'm not sure you are taking this into account...
syzygy
 
Posts: 162
Joined: Sun Aug 03, 2008 4:02 pm

Re: 7-men EGTB Bounty

Postby Kirill Kryukov » Mon Aug 04, 2008 1:43 am

kronsteen wrote:I you think of DTZ, I may think that DTZ50 (i.e TBs taking into account 50-move rule) may be even a better idea, as it saves even more space and rises a new very interesting aspect of the game.

I do like the DTZ50 idea a lot, since we are probably thinking about practically useful tablebases, rather than theoretically interesting.

kronsteen wrote:I don't know what work has currently be achieved about DTZ50 (5 men ? Some 6 men ? Specific interface for analysis ?) but it is clear that DTZ50 7-men must rely on DTZ50 5/6-men and not currently available DTM or DTC 5/6-men. This makes DTZ50 5 and 6-men a necessary, and very heavy, preliminary work. But it may be worth it, as full set of DTZ50 6-men is bound to weigh far less than 1.2 TB and may be a good add-on to your site.

Yes, I am afraid that we will have to re-generate all 3 to 6-men tablebases as well.

kronsteen wrote:DTZ50 will probably rise some very interesting new knowledge about some endings like knnkp or kqpkq (and many 6-men). It will also need developing of a new interface which takes into account, in position evaluation, how many non-zeroing half moves are still left before 50-move draw claim.

About goals, preferences and priority settings, this is clearly open discussion in community, and what I provided are only first and personal ideas, which have to be completed by other's opinions and points of view. But I got this started because I think that serious debate about them should be achieved before moving to practical work, as they will engage work for a long time and contain some crucial choices such as metric selection and acceptable code limitations.

kbnpkrp generation in 2 weeks seems challenging with today's hardware, unless some skillful programmer builds a very fast code. It is a good baseline, but if it proves too hard to achieve and/or verify, limiting this test to easier TBs (those pawnless and/or with piece duplication) may be more suitable, as we can reasonably expect more power when moving to the most complex TB type. Remember, first released 6-men (at Bob Hyatt's ftp) were 33 pawnless with 1 duplicated piece on board.

I am not sure we need performance requirement at all. If we have good tablebase format, generator and probing code, then I expect many people to donate CPU time. It's best to hear the potential bounty hunters idea about the performance requirement.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 7-men EGTB Bounty

Postby Kirill Kryukov » Mon Aug 04, 2008 1:46 am

koistinen wrote:As DTR is only a little harder than DTZ50 and gives correct answer for default rules, I think DTR should be the goal.
(DTZ is easier than DTM.)
To compute DTR, compute DTZ for both odd and even game50 and as soon as the set of wins with game50=N is the same as the set of wins with game50=N+1 you need only compute for game50=N+2*d as game50=N+1+2*d will have exactly the same positions won from then on.
My guess is that for most endgames, N could be less than 10.

I'm not sure I follow. Is there an explanation about DTR somewhere? If we make DTR a requirement, we will need a very easy to understand reasoning behind this choice. A community-funded bounty has to have very clear goals and communication if we hope to raise any funds.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 7-men EGTB Bounty

Postby Kirill Kryukov » Mon Aug 04, 2008 1:50 am

syzygy wrote:I don't think DTZ50 will save much space over DTZ. If it does, the compression algorithm needs fixing. Only very few positions will have DTZ>50, so few that it should not have a noticeable impact on the compressed size.

DTZ50 has not only space advantage over DTZ. DTZ50 is also more relevant to the game of chess which we are interested in.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 7-men EGTB Bounty

Postby Kirill Kryukov » Mon Aug 04, 2008 2:12 am

One idea.. How about requiring tablebases that can handle castling? Or is it too difficult?

By incorporating castling and DTZ50 (or DTR) we can have the first fully chessically correct tablebase format. :)
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 7-men EGTB Bounty

Postby syzygy » Mon Aug 04, 2008 2:33 am

Kirill Kryukov wrote:
syzygy wrote:I don't think DTZ50 will save much space over DTZ. If it does, the compression algorithm needs fixing. Only very few positions will have DTZ>50, so few that it should not have a noticeable impact on the compressed size.

DTZ50 has not only space advantage over DTZ. DTZ50 is also more relevant to the game of chess which we are interested in.

I'm afraid DTZ50 for 7-piece positions will only be relevant for computer-computer matches, as no human will be able to approach perfect play vs. perfect 7-piece knowledge. And if computer-computer matches is what you're really interested in, then I don't see the point in having a 50-move rule at all. I think the 50-move rule was mainly created to secure the mental health of human players.

DTZ tablebases will uncover deep (and purely theoretical) wins that will attract lots of attention, and I doubt that they will be of less practical relevance than DTZ50 tablebases.

Anyway, my main point is that the space advantage cannot be a deciding factor. DTZ50 will have some speed/storage advantages during generation though, but I don't think those are decisive either since most 7-piece combinations are not balanced enough to have DTZ>50 positions (I think). Lastly, depending on the generator, DTZ50 could lead to somewhat simpler programming.

Of course a generator for DTZ can be easily converted to a generator for DTZ50. So at the moment the discussion itself could be said to be academic.

The longer I think about DTR, the more I become convinced it is out of reach for now.
syzygy
 
Posts: 162
Joined: Sun Aug 03, 2008 4:02 pm

Re: 7-men EGTB Bounty

Postby jkominek » Mon Aug 04, 2008 4:45 am

Almost two years ago to the the day, in a teaser that might be considered this forum's earliest bounty hunting, kp1139 ventured willingness to pay for 7-men generator development. No telling how serious he was at the time since nothing came of it. Is the interest still extant?

jk

From the thread "Nalimov 7men?"
kp1139 wrote:What would this take? I would be willing to pay a coder to generate this code. assume a huge amount of memory would be needed, perhaps a sun system running unix could do this?

I cannot imagine the size of these databases, but would be a very interesting undertaking.

Any ideas?

Matt
jkominek
 
Posts: 142
Joined: Mon Dec 04, 2006 9:02 am
Location: Pittsburgh, PA

Re: 7-men EGTB Bounty

Postby kronsteen » Mon Aug 04, 2008 9:49 am

To follow on discussion about metric choice :

DTZ/DTZ50

The more I think about DTZ50, the more I like it. Space saving and relevance to real chess sound like big arguments.

DTZ has the advantage of being immediately connectable to existing 6-men in DTM format (which is not the case of DTZ50) but it will lead to strange knowledge providing DTZ evaluation for 7-men and DTM evaluation for 6-men or less. If we are to reprocess all 3-6men to DTZ in order to avoid this, better to shift to DTZ50 right now.

DTZ50 compared with DTZ will cut down TB size only for endings where there are a lot of z>50 positions. True, only few endings have this property, but they are also most interesting ones. If cutting down krbnkrb TB size allows easier access for studying this specific ending, it may be worth it. Ineffectiveness of DTZ50 to cut down full 7-men set is to be considered when we’ll move to downloading those numerous very unbalanced (and uninteresting) endings such as kqrrkbn in order to grant access to endings with lots of pawns, but it is long term view.

DTZ50 has drawbacks, nevertheless. Main one is that DTZ50 hurries pawn pushes which preserve the win but may be considered as bad moves as they make win harder in subsequent play. DTZ case is even worse as it can advise pawn pushes which fall into “cursed positions” (see below). On endings such as krpkr, contrary to DTM, DTZ(50) can’t show sound preliminary manoeuvres in order to push pawn in better circumstances. But DTM has also its own drawbacks with presenting shortest lines whose subtleties are not understood by humans, and can’t engineer slower routes which may be more understandable. So we have to live with TB drawbacks, whatever the metric choice.

DTZ50 TBs may identify a new type of positions, “cursed positions” (or any other term) which are those theoretical wins which are turned into a draw by 50-move rule. Discrimination between genuine draws and cursed positions is very interesting, won’t take much space storage and is immediate for 5-6 men as we have already access to DTM TBs. For 7-men, it will need a little more computing, as it forces recursive algorithm to run beyond z=50 in order to unearth cursed positions.

DTZ50 will also allow to show “spoiled positions” (or a term of your choice), i.e winning positions according to 50 move rule which are turned into a draw because of the non-zeroing moves that have been previously played in order to reach them. This is of great interest for practical play. Take for instance a kqpkq position from a human game where 40 non-zeroing moves have already been played. DTZ50 TB will allow analysis such as “ok. You’ve been wandering about for 40 moves, and forced now into a pawn push in next 10 moves. Is it a way to do it which preserves the win, or has the position been spoiled by your unperfect previous play ?”. DTM can’t perform this.


DTR :

DTR definition, which can be found in March 2008 post « how to determine DTZ ? » is smallest k for which given position is a win according to a k-move rule. If I’m not mistaken, trouble with DTR is that it is unpractical to show winning lines in won positions, as WDL is. Take for example a won position which is 10 moves away from next zeroing move, but whose DTR is 20 as inferior side can force 20 move distance between consecutive zeroing moves in subsequent play. From this position, many moves by winning side will still lead to positions evaluated as DTR=20, and DTR won’t allow discrimination between moves which make real progress and some moves which set the clock backwards. It is so big drawback that I may think it rules out DTR.

syzygy wrote:However, computing DTR seems quite complicated. The most obvious way of generating them needs two counters per position: one for DTR, one for DTZ. The problem is that there will be long winning paths with constant DTR. I'm not sure you are taking this into account...


This seems to be the same point of view

Also, I find DTR knowledge not enough in “real chess” direction. Playing with k-move rule is a chess variant, but it is real chess only for k=50. k-move game may be considered as belonging to the same category as chess with fantasy pieces or chess on different board sizes, which are fun and for which TB generation is also fun, but real chess may be considered as greater priority. I also believe that FIDE’s position to apply 50-move rule to all endings, regardless of theroretical results raised by TBs, is a firm one, and not to be expected to change soon. It may have a deep influence on the play on endings such as knnkp, but that’s the way world wants chess to be.
kronsteen
 
Posts: 88
Joined: Fri Aug 01, 2008 11:20 am
Location: France

Re: 7-men EGTB Bounty

Postby Kirill Kryukov » Mon Aug 04, 2008 10:14 am

syzygy wrote:I'm afraid DTZ50 for 7-piece positions will only be relevant for computer-computer matches, as no human will be able to approach perfect play vs. perfect 7-piece knowledge. And if computer-computer matches is what you're really interested in, then I don't see the point in having a 50-move rule at all. I think the 50-move rule was mainly created to secure the mental health of human players.

50-move rule is an important part of the chess known to the world today, whether we like it or not. The division into computer chess and human chess is artificial. Human-computer matches were played with the 50-move rule in use. World Computer Chess Championships are played with 50-move rule. When you play computer-computer matches, most GUIs will adjudicate the game by 50-move rule when it happens, there is no option to disable this in many GUIs I know. So as long as we are talking about chess, 50-move rule is an important part of the picture.

syzygy wrote:DTZ tablebases will uncover deep (and purely theoretical) wins that will attract lots of attention, and I doubt that they will be of less practical relevance than DTZ50 tablebases.

We already have seen some long checkmates reported by Marc Bourzutschky. Yes they attracted a lot of attention. The result is that no one is working in this direction anymore, and we don't have any usable 7-men tablebases.

syzygy wrote:Anyway, my main point is that the space advantage cannot be a deciding factor. DTZ50 will have some speed/storage advantages during generation though, but I don't think those are decisive either since most 7-piece combinations are not balanced enough to have DTZ>50 positions (I think). Lastly, depending on the generator, DTZ50 could lead to somewhat simpler programming.

Of course a generator for DTZ can be easily converted to a generator for DTZ50. So at the moment the discussion itself could be said to be academic.

The longer I think about DTR, the more I become convinced it is out of reach for now.

I agree that speed and size advantages are not the most important points, but they may be considerable when choosing between 1 TB and 1.5 TB to download.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 7-men EGTB Bounty

Postby Kirill Kryukov » Mon Aug 04, 2008 10:22 am

kronsteen, thanks for your thoughts, I am now convinced that DTR is out of the question, as it is not optimized for practical play.

kronsteen wrote:The more I think about DTZ50, the more I like it. Space saving and relevance to real chess sound like big arguments.

DTZ has the advantage of being immediately connectable to existing 6-men in DTM format (which is not the case of DTZ50) but it will lead to strange knowledge providing DTZ evaluation for 7-men and DTM evaluation for 6-men or less. If we are to reprocess all 3-6men to DTZ in order to avoid this, better to shift to DTZ50 right now.

I think we better recompute the whole 3-6 collection for consistency. DTZ or DTZ50 should be much smaller than DTM anyway, so it will be a big help handling the 6-men tables.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 7-men EGTB Bounty

Postby syzygy » Mon Aug 04, 2008 8:06 pm

kronsteen wrote:DTZ has the advantage of being immediately connectable to existing 6-men in DTM format (which is not the case of DTZ50) but it will lead to strange knowledge providing DTZ evaluation for 7-men and DTM evaluation for 6-men or less. If we are to reprocess all 3-6men to DTZ in order to avoid this, better to shift to DTZ50 right now.

Once 7-piece generation becomes feasible, regenerating all 6-piece tables will be a very minor undertaking.

DTZ50 compared with DTZ will cut down TB size only for endings where there are a lot of z>50 positions. True, only few endings have this property, but they are also most interesting ones. If cutting down krbnkrb TB size allows easier access for studying this specific ending, it may be worth it.

But those interesting tables will only have very few positions with DTZ>50. So few that cutting down to DTZ50 will have a negligible effect on compressed size. It will be far far less than 0.1% in my estimation.

Is studying KRBNvKRB more interesting with or without the 50-move rule? I can't answer that question, but my feeling is that taking into account the artificial 50-move rule makes for less interesting results. For example end game composers don't care about the 50-move rule. (And in real games these positions won't happen, at least not to an extent that it impacts ELO rating.)

DTZ50 has drawbacks, nevertheless. Main one is that DTZ50 hurries pawn pushes which preserve the win but may be considered as bad moves as they make win harder in subsequent play. DTZ case is even worse as it can advise pawn pushes which fall into “cursed positions” (see below).

Correct, but to avoid the DTZ problem you mention, you really need DTZ50 and not e.g. DTM. DTM will move to "cursed positions" probably far more often than DTZ. (DTM could draw a won 7-piece position without a single capture or pawn push. DTZ will at least go for a capture or pawn move leading to a "won" position that could however be drawn on the 50-move rule. DTZ50 avoids these problems. Ok, this could probably be avoided by taking into account the 50-move rule when generating DTM, but this is not typically done to my knowledge. It wouldn't be DTM but DTM50.)

DTZ50 TBs may identify a new type of positions, “cursed positions” (or any other term) which are those theoretical wins which are turned into a draw by 50-move rule.

I'm not sure DTZ50 will "identify" those positions. DTZ50 will not be able to tell your cursed positions apart from genuine draw positions. (DTR would be.)

Or do we not have the same idea of DTZ50? I guess in principle one could compute DTZ tables while treating all "lower" tables as DTZ50 (by treating >50 positions as draws when probing them). This would almost allow you to discriminate between genuine draws and "cursed positions". The ones you miss are the positions that can be converted in less than 50 moves into "cursed" positions. I don't think this is what is meant by DTZ50 tables, but the idea is interesting. You'll lose the little compression benefits real DTZ50 would give, but again that's too small to be a deciding factor.

(Actually, it should probably be possible to also catch the positions I just wrote you would miss... but that would considerably complicate generation.)

Discrimination between genuine draws and cursed positions is very interesting, won’t take much space storage and is immediate for 5-6 men as we have already access to DTM TBs. For 7-men, it will need a little more computing, as it forces recursive algorithm to run beyond z=50 in order to unearth cursed positions.

Ok, we agree on the running beyond z=50. However, DTM has wins that are in fact cursed and there's no way to know, apart from building DTZ50 for 5-6 men.

DTZ50 will also allow to show “spoiled positions” (or a term of your choice), i.e winning positions according to 50 move rule which are turned into a draw because of the non-zeroing moves that have been previously played in order to reach them.

Agreed. DTZ can do it "almost" as well as DTZ50.

If I’m not mistaken, trouble with DTR is that it is unpractical to show winning lines in won positions, as WDL is. Take for example a won position which is 10 moves away from next zeroing move, but whose DTR is 20 as inferior side can force 20 move distance between consecutive zeroing moves in subsequent play. From this position, many moves by winning side will still lead to positions evaluated as DTR=20, and DTR won’t allow discrimination between moves which make real progress and some moves which set the clock backwards. It is so big drawback that I may think it rules out DTR.

Exactly. I think usable DTR requires two values per position both during generation and stored on disk: (DTR value, number-of-moves-to DTR=value-1). I was thinking of using DTR and DTZ side-by-side (DTZ to make progress while DTR is constant), but I doubt that that would work properly. (Essentially DTZ could lead to a conversion into a position with increased DTR. The equivalent of a cursed position.)

It could be a nice project to compute 5-piece DTR tables.

Also, I find DTR knowledge not enough in “real chess” direction. Playing with k-move rule is a chess variant, but it is real chess only for k=50.

I wanted to counter-argue that DTR will also solve the problem you just mentioned (can you still save a position after playing an inferior line?), but I realize it does not. I have to agree that purely for practical play, DTZ50 is (theoretically ;)) optimal.

However, in my personal view using a k-move rule for any k is a fantasy-variant ;)

I also believe that FIDE’s position to apply 50-move rule to all endings, regardless of theroretical results raised by TBs, is a firm one, and not to be expected to change soon.

I thought each tournament can choose to use a different k.
syzygy
 
Posts: 162
Joined: Sun Aug 03, 2008 4:02 pm

Next

Return to Endgame Tablebases

Who is online

Users browsing this forum: No registered users and 1 guest