The 16 "missing" Nalimov files

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

Postby Lutz Nebe » Thu Jul 27, 2006 9:39 am

jshriver wrote:In retrospect, to make things run even smoother. I can setup a hidden area on my site for people in this forum download. That way I can get the files to other key distributors before releasing it to the public.

What do you all think? This would take some strain off my server by allowing it to be more easily shared via emule, especially initially. Figure once these go public it's going to be insane traffic :) will be fun watching the system stats though lol.

I could also send some to TapaniS.

-Josh


I would be happy to participate and share the files via emule. Currently I'm uploading KNNP-KN to Tapani's server, so my emule upload is limited to 30kB. Normally I can upload files with 50-60 kB. Tomorrow I will start my holidays for three weeks till 20.08. After that I will be ready to help you in any way needed.
User avatar
Lutz Nebe
 
Posts: 18
Joined: Tue Jun 27, 2006 9:47 am
Location: Koblenz, Germany

Kirill I still havent seen any comment about ....

Postby vb4 » Thu Jul 27, 2006 2:12 pm

Hi Kirill,

Regarding my previous post I had also mentioned that 3 egtb's that Mark made available to us have all the stats for both BTW and WTM but they dont show the Broken positions for BTM. I had posted the 3 positions in my prior post. Perhaps someone out here can tell me why this is so.

Thanks,

Les
vb4
 
Posts: 69
Joined: Sun Jul 23, 2006 5:57 am

FEG crunching

Postby jshriver » Fri Jul 28, 2006 4:39 pm

Greetings,

I have Feg running under wine, making knk knnk, knnnk, and finally knnnnk :)
I also have another machine crunching away at kbbbbk
Would it be possible to convert these to nalimov?
-Josh
User avatar
jshriver
 
Posts: 287
Joined: Tue Jan 31, 2006 5:59 am
Location: Toledo, OH, USA

Postby kp1089 » Fri Jul 28, 2006 11:56 pm

jshriver wrote:In retrospect, to make things run even smoother. I can setup a hidden area on my site for people in this forum download. That way I can get the files to other key distributors before releasing it to the public.

What do you all think? This would take some strain off my server by allowing it to be more easily shared via emule, especially initially. Figure once these go public it's going to be insane traffic :) will be fun watching the system stats though lol.

I could also send some to TapaniS.

-Josh


Hi--

I can upload at 200kBs across my 4 accounts. I have uploaded 2250+ GB so far through eMule, so I would like to be considered for distribution. My accounts are kp1089, merepawn, watcher, and blueblazes. Let me know if you would like to use my upload capacity.

kp1089
How small, of all that human hearts endure, that part that laws and kings can cause or cure. -- Samuel Johnson.
kp1089
 
Posts: 10
Joined: Tue Jan 24, 2006 7:54 am
Location: Skamania, WA

Re: Kirill I still havent seen any comment about ....

Postby guyhaw » Sat Jul 29, 2006 2:09 am

vb4 wrote:... I had also mentioned that 3 egtb's that Mark made available to us ... dont show the Broken positions for BTM. I had posted the 3 positions [endgames - gh] in my prior post.
Les


A slightly unfortunate feature of Nalimov-style stats is that if there are no index-entries of a category, the line is left out. For example, there might be no positions of depth 'n' although there are positions of depth n-1 and n+1.
Similarly, there might be no 'Broken positions' as now seems to be the case when the stm only has Pawns.
If there are to be no broken positions in the index, the indexing system must avoid 'positions' where the sntm is in check, where two men have been 'placed' on the same square and where there is no position corresponding to the index. I don't know exactly when this is possible.
g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: Kirill I still havent seen any comment about ....

Postby vb4 » Sat Jul 29, 2006 4:53 am

guyhaw wrote:
vb4 wrote:... I had also mentioned that 3 egtb's that Mark made available to us ... dont show the Broken positions for BTM. I had posted the 3 positions [endgames - gh] in my prior post.
Les


A slightly unfortunate feature of Nalimov-style stats is that if there are no index-entries of a category, the line is left out.

Hi Guy,

I have all the tbs files up to the set of 16 we are talking about now and in all cases each file has broken positions for both White and Black?? The 3 files I had listed in my earlier post did in fact have data for both WTM and BTM and all the other info but the only piece that was left out was the number of broken positions for just the BTM side?? I am not quite sure Guy I follow your explanation and if you could say it a diferent way perhaps or if someone else can explain it to me might be helpful. I just never saw that in all the files up to now so you can see why I am suspicious this just might be a simple error.

Thanks

Les
For example, there might be no positions of depth 'n' although there are positions of depth n-1 and n+1.
Similarly, there might be no 'Broken positions' as now seems to be the case when the stm only has Pawns.
If there are to be no broken positions in the index, the indexing system must avoid 'positions' where the sntm is in check, where two men have been 'placed' on the same square and where there is no position corresponding to the index. I don't know exactly when this is possible.
g
vb4
 
Posts: 69
Joined: Sun Jul 23, 2006 5:57 am

'Broken positions' in Nalimov indexes

Postby guyhaw » Sun Jul 30, 2006 10:03 am

[ Les ...]
Nalimov's EGT-indexing principles are ingenious and repay study. They may also have changed since he computed the KQK and KRK EGTs.
May I refer you to the 'Nalimov, Haworth & Heinz' paper (2000) on 'Space-Efficient Indexing', often cited as it is the first and (afaik) only account of Nalimov's approach: see http://www.tinyurl.com/law6k --> 'all publications'. I hope this will clarify the ideas used.
Clearly, an indexing scheme has to have a separate index for every reachable chess position. Since it is sometimes difficult to decide whether a position is reachable or not, a simpler idea is to have an index-entry for every position that is 'not obviously illegal'. All index-schemes prevent the Kings checking each other and know not to place another man on the same square as a King. They might also know how not to place Pawns on the 1st and 8th ranks.
In fact, all indexing schemes will have an index-entry for some positions which are obviously illegal - once all the pieces are 'in place'. For example, a 'distant check' by a Queen might have been blocked by the later placing of a R/B/N/P but wasn't. So, positions where the sntmK is in check are illegal and their index-entries are given a value denoting 'broken position' (if one wants a more accurate count of won/drawn/lost positions).
Nalimov's key idea was not to allow checks on the sntmK which cannot be blocked by the later placement of a man. For each man, there is a small set of squares where one would be giving such checks with that man on the sntmK, and these can be considered 'not available' to that piece. Line-pieces can make 'distant checks' which are blockable by the later placement of a man - but may not be, so there are always broken positions when a stm has line-pieces. Knights and Pawns only make unblockable checks.
Thus, where the stm only has no more than Ns and Ps, there should be no index-positions given to positions featuring a check by the stm. There may be other reasons why there are broken positions, and I've either forgotten the details or never known them.

Thus the Nalimov .tbs files for KPK, KNKN have no broken positions. Those for KNKP, KPKP and (a fortiori?) KPPKPP have wtm broken positions, which rather puzzles me. Ns and Ps may be colliding on squares, 'e.p.' may complicate things - I don't know.
There's a big trade-off between space and time here. The effort to manage a cleverer, more compact index-scheme takes time (especially when inverse-indexing from index-position to chess-position) and not every good idea may be considered worthwhile. YK-MB now, I believe, generate the EGT with one index-scheme and leave open the possibility of converting it to a more compact scheme for use later.

In case it's useful for others as it is for me, I attach a spreadsheet of Nalimov index-ranges, extracted - hopefully correctly - from the last version of his tbgen code that I have.
g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Postby Kirill Kryukov » Sun Jul 30, 2006 2:17 pm

kp1089 wrote:Hi--

I can upload at 200kBs across my 4 accounts. I have uploaded 2250+ GB so far through eMule, so I would like to be considered for distribution. My accounts are kp1089, merepawn, watcher, and blueblazes. Let me know if you would like to use my upload capacity.

kp1089

Hi kp1089! Those accounts are all yours? I thought they are four different people, all with quite good connection. Thanks for good contribution to the sharing! I think we exchanged some gigabytes with each other too.

I hope Josh (or whoever will do the distribution) will contact you and use your help in sharing the files. Thanks for offering your help!
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 'Broken positions' in Nalimov indexes

Postby mbourzut » Sun Jul 30, 2006 5:54 pm

guyhaw wrote:...
Thus the Nalimov .tbs files for KPK, KNKN have no broken positions. Those for KNKP, KPKP and (a fortiori?) KPPKPP have wtm broken positions, which rather puzzles me. Ns and Ps may be colliding on squares, 'e.p.' may complicate things - I don't know.
...


Collisions of pawns and pieces arise because the only way to avoid them would be to keep track which of the pieces are on the first or last rank. For example, a piece on a1 means an additional pawn has 48 squares, while a piece on a2 means an additional pawn has 47 squares. To avoid additional complications in the index computation Nalimov allows 48 squares for the additional pawn regardless, leading to positions with collisions being included.

Johan de Koning's key idea in his FEG program is that simplicity in an index scheme outweighs space considerations if one considers only compressed tablebases. Compression replaces repeated broken scores by shorter symbols, so that after compression there is little difference in size between a tablebase where some broken positions are skipped with a complicated index scheme, and a tablebase where those positions are kept and labeled "broken". Generation takes place using compressed data, so that the apparent space inefficiency never arises, leading to simpler and faster programs. Yakov Konoval also uses that idea in his program.

-Marc
mbourzut
 
Posts: 30
Joined: Fri Mar 03, 2006 7:48 pm

Postby jshriver » Mon Jul 31, 2006 4:47 am

Kirill Kryukov wrote:Hi kp1089! Those accounts are all yours? I thought they are four different people, all with quite good connection. Thanks for good contribution to the sharing! I think we exchanged some gigabytes with each other too.

I hope Josh (or whoever will do the distribution) will contact you and use your help in sharing the files. Thanks for offering your help!


Once I get the data, run md5sum against them to make sure nothing was broken during shipment, I'll send out the URL for the first set. Going to break them down to 25-30 gig chunks.

My big question now is, in what order do you all want the files to be available? Only sequence I know of right now is that kppkpp should be last.

-Josh
User avatar
jshriver
 
Posts: 287
Joined: Tue Jan 31, 2006 5:59 am
Location: Toledo, OH, USA

EGT-order ... and piece/pawn collisions

Postby guyhaw » Mon Jul 31, 2006 10:01 am

[re JS...] Probably best sense is to make available those EGTs with the least Pawns first, working 'up the mountain' to KPPKPP. This is because chess-engine use of (e.g.) KPPKPP will occasionally want to consult KQPKPP etc. Most interest will be in KPPKPP though.

[re MB...] Piece/pawn collision, ah yes. I remember 'reverse engineering' some small-endgame index-ranges with Eugene in 1999 in order to prise out the details. I think I said it was a good argument for 'placing' the Pawns after the Kings (even 'before the Kings' for P-profile partitioning). Then the index-ranges would be even smaller, but I guess that's academic as it's not a route you're going down anyway.
I think e.p. must be the issue re the KPKP broken positions.
g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: EGT-order ... and piece/pawn collisions

Postby mbourzut » Mon Jul 31, 2006 11:31 am

guyhaw wrote:[re MB...] Piece/pawn collision, ah yes. I remember 'reverse engineering' some small-endgame index-ranges with Eugene in 1999 in order to prise out the details. I think I said it was a good argument for 'placing' the Pawns after the Kings (even 'before the Kings' for P-profile partitioning). Then the index-ranges would be even smaller, but I guess that's academic as it's not a route you're going down anyway.
I think e.p. must be the issue re the KPKP broken positions.
g


no, most of the broken positions in KPKP are due to the black pawn colliding with one of the kings (kings are pieces too!), nothing to do with e.p.
mbourzut
 
Posts: 30
Joined: Fri Mar 03, 2006 7:48 pm

Still confused re EGTB's

Postby vb4 » Tue Aug 01, 2006 6:37 am

Going back to my several posts and the replies I am still a bit confused as to how just 3 positions that Mark generated as referenced in one of my earlier posts does not show the Broken positions with BTM?? I thank the guys that tried talking about Eugenes indexing stuff but to the best of my knowledge in all the egtb's that I have that Eugene generated including 6 pieces I dont recall any of them missing the broken positions for either BTM or WTM. Can someone please look into this since I must admit I am not sure I buy the indexing as the culprit. Why up to now has it always been ok and that only 3 EGTB's in this last set of 16 positions does this problem surface???


Thanks and still confused,

Les
vb4
 
Posts: 69
Joined: Sun Jul 23, 2006 5:57 am

Be assured ...

Postby guyhaw » Tue Aug 01, 2006 9:33 am

I believe you have all the information you need to understand this, at least a lot better, from the cited paper, MB and myself. I think the short answer is that Ps feature more in the 'last 16'.
There is no missing 'Broken position information': if it is not in the .tbs file, you can assume 'zero broken positions' in the same way as a 'missing' DTM-depth indicates 'zero positions at that depth'.
Meanwhile, you may be assured that the total (wtm or btm) of losses+draws+wins+brokens = the index-range indicated in Nalimov's code. I have personally included this x-check to make sure I didn't mis-transcribe information from .tbs-files to .xls-files.
g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: Be assured ...

Postby vb4 » Tue Aug 01, 2006 2:07 pm

guyhaw wrote:I believe you have all the information you need to understand this, at least a lot better, from the cited paper, MB and myself. I think the short answer is that Ps feature more in the 'last 16'.
There is no missing 'Broken position information': if it is not in the .tbs file, you can assume 'zero broken positions' in the same way as a 'missing' DTM-depth indicates 'zero positions at that depth'.
Meanwhile, you may be assured that the total (wtm or btm) of losses+draws+wins+brokens = the index-range indicated in Nalimov's code. I have personally included this x-check to make sure I didn't mis-transcribe information from .tbs-files to .xls-files.
g


Hello GuyHaw,

First thank you for your explanation regarding this subject.

Let me see that I understand your point. Your saying that regarding these 3 positions (krnkpp - krbkpp - kbnkpp) that there can exist broken positions for WTM but not for BTM?? If that is so why is it. I mean my thought was any position I can set up for white and make it WTM I can set up for black and make it BTM. That being the case you would think that if there exists broken positions for when its WTM then it would also apply if it was BTM??

Sorry Guy but still a bit confused,

Les
vb4
 
Posts: 69
Joined: Sun Jul 23, 2006 5:57 am

wtm and btm broken positions

Postby guyhaw » Tue Aug 01, 2006 2:45 pm

Les,
If your argument was correct, the number of wtm and btm broken positions would be the same for a given endgame. It very rarely is.
Your mistake is that a wtm position in KRNKPP is a 'KRN'-to-move position: switch colours to KRN=Black, and you have a btm position in KPPKRN (which is equivalent to a White position in KRNKPP). Lexicographically, the side with more men (or a 'later' force-profile using the order P-N-B-R-Q) is 'White'.
g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: wtm and btm broken positions

Postby vb4 » Tue Aug 01, 2006 7:01 pm

guyhaw wrote:Les,
If your argument was correct, the number of wtm and btm broken positions would be the same for a given endgame. It very rarely is.
Your mistake is that a wtm position in KRNKPP is a 'KRN'-to-move position: switch colours to KRN=Black, and you have a btm position in KPPKRN (which is equivalent to a White position in KRNKPP). Lexicographically, the side with more men (or a 'later' force-profile using the order P-N-B-R-Q) is 'White'.
g


Hi Guy

You are absolutely right. What I said only applies to egtb's with the exact same pieces for white and black. Setting that aside is there any other way Guy you can tell me why those 3 positions dont have broken positions different then the way you stated it before? It is hard for me to believe that there exists no position when its BTM with those 3 egtb's that could result in a broken position. Why does all the other positions that Eugene generated have the broken positions for WTM and BTM? or was that strictly coincidence?

Help <s>, I am still trying to understand the logic

Les
vb4
 
Posts: 69
Joined: Sun Jul 23, 2006 5:57 am

Re: wtm and btm broken positions

Postby mbourzut » Tue Aug 01, 2006 8:15 pm

vb4 wrote:
guyhaw wrote:Les,
If your argument was correct, the number of wtm and btm broken positions would be the same for a given endgame. It very rarely is.
Your mistake is that a wtm position in KRNKPP is a 'KRN'-to-move position: switch colours to KRN=Black, and you have a btm position in KPPKRN (which is equivalent to a White position in KRNKPP). Lexicographically, the side with more men (or a 'later' force-profile using the order P-N-B-R-Q) is 'White'.
g


Hi Guy

You are absolutely right. What I said only applies to egtb's with the exact same pieces for white and black. Setting that aside is there any other way Guy you can tell me why those 3 positions dont have broken positions different then the way you stated it before? It is hard for me to believe that there exists no position when its BTM with those 3 egtb's that could result in a broken position. Why does all the other positions that Eugene generated have the broken positions for WTM and BTM? or was that strictly coincidence?

Help <s>, I am still trying to understand the logic

Les


Les, if you had actually looked more closely at the Nalimov files you would know that these 3 files are not unusual at all, there are several dozen more. Any ending where Black has only pawns, and white has no pawns, will have no BTM broken positions.
mbourzut
 
Posts: 30
Joined: Fri Mar 03, 2006 7:48 pm

Re: wtm and btm broken positions

Postby vb4 » Wed Aug 02, 2006 5:51 am

mbourzut wrote:
vb4 wrote:
guyhaw wrote:Les,
If your argument was correct, the number of wtm and btm broken positions would be the same for a given endgame. It very rarely is.
Your mistake is that a wtm position in KRNKPP is a 'KRN'-to-move position: switch colours to KRN=Black, and you have a btm position in KPPKRN (which is equivalent to a White position in KRNKPP). Lexicographically, the side with more men (or a 'later' force-profile using the order P-N-B-R-Q) is 'White'.
g


Hi Guy

You are absolutely right. What I said only applies to egtb's with the exact same pieces for white and black. Setting that aside is there any other way Guy you can tell me why those 3 positions dont have broken positions different then the way you stated it before? It is hard for me to believe that there exists no position when its BTM with those 3 egtb's that could result in a broken position. Why does all the other positions that Eugene generated have the broken positions for WTM and BTM? or was that strictly coincidence?

Help <s>, I am still trying to understand the logic

Les


Les, if you had actually looked more closely at the Nalimov files you would know that these 3 files are not unusual at all, there are several dozen more. Any ending where Black has only pawns, and white has no pawns, will have no BTM broken positions.


Ahhhh I think I understand what you are saying! Geez it looks so obvious when it is stated that way. I apologize to Guy for not understanding what he was trying to say and thank you all for providing with this understanding.

Thanks

Les
vb4
 
Posts: 69
Joined: Sun Jul 23, 2006 5:57 am

Important: promoting to p1 for now :-)

Postby guyhaw » Mon Feb 16, 2009 12:08 am

.
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Previous

Return to Endgame Tablebases

Who is online

Users browsing this forum: No registered users and 2 guests

cron