Jump to content

Talk:Endgame tablebase

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 91.105.30.13 (talk) at 22:54, 10 January 2011 (→‎Surely this is an exaggeration?: new section). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Good articleEndgame tablebase has been listed as one of the Sports and recreation good articles under the good article criteria. If you can improve it further, please do so. If it no longer meets these criteria, you can reassess it.
Article milestones
DateProcessResult
February 24, 2007Good article nomineeNot listed
May 5, 2007Featured article candidateNot promoted
May 9, 2007Good article nomineeListed
August 24, 2007WikiProject A-class reviewNot approved
June 17, 2009Good article reassessmentListed
Current status: Good article
WikiProject iconChess GA‑class Mid‑importance
WikiProject iconThis article is within the scope of WikiProject Chess, a collaborative effort to improve the coverage of Chess on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ChessWikipedia:WikiProject ChessTemplate:WikiProject Chesschess articles
GAThis article has been rated as GA-class on Wikipedia's content assessment scale.
MidThis article has been rated as Mid-importance on the project's importance scale.
Note icon
This article is in the list of selected articles that are shown on Portal:Chess.

Beyond humans or computers?

I am not sure I am understanding the statement that something that has been done is "beyond the horizon of humans or computers" If it has been done then it has been done by a human or a computer (and abstractly speaking a human is a computer as well). The other option is that it has not been done, but I am assuming the article is claiming that tablebases with this much power have been done. There is not another option, unless that option is magic!

--74.194.27.5 (talk) 04:29, 5 December 2007 (UTC)[reply]

A note to reviewers from the Good Article committee

Although many users have contributed to this article, I am responsible for most of its content, and I am probably the most expert Wikipedian on this subject. I would like to anticipate 3 issues you might have with this article.

  1. Insufficient context. I've tried to avoid this, but inevitably, in an arcane topic such as this, there will be parts you don't fully understand. Please point them out.
  2. Missing references. Every statement I've made in the article comes from somewhere; I just haven't put in all the references because I was writing somewhat off-the-cuff. If you put "citation needed" tags in some places, I should be able to find the citations.
  3. Inconsistent style of referencing. I simply don't know how to do this correctly. A little guidance might be helpful.

When you've reviewed this article, please let me know on my talk page. Best regards, YechielMan 06:09, 11 February 2007 (UTC)[reply]

six-piece tablebase complete?

From what I understand, the six-piece tablebases are not complete yet. Can anyone verify that? Bubba73 (talk), 18:06, 16 June 2006 (UTC)[reply]

There are complete since quite some time, but not completely available for the public. --Enlil2 09:13, 2 August 2006 (UTC)[reply]

thank you. Someone (maybe you) put in that they are 1.2 terabytes in size. Bubba73 (talk), 14:42, 2 August 2006 (UTC)[reply]
They are complete. However, 5 vs. 1 are not complete bec. they are not needed, but some folks on the CCRL forum want to construct them anyway. In special cases like KNNNNK this makes some sense, but even then, KNNNK is generally a win. YechielMan 04:20, 6 February 2007 (UTC)[reply]

Image doesn't match text

The text gives a 262 move mate quoting a KRBKNN ending, but the diagram is KRNKNN. As I don't know which is correct I'll leave it to someone else to edit or change the diagram. ScottRShannon 01:49, 27 September 2006 (UTC)[reply]

Shredderbases

Should the Shredderbases be explained in this article or seperately? └ VodkaJazz / talk ┐ 17:44, 8 December 2006 (UTC)[reply]

  • There is an external link to a web server which uses Shredder's tablebases. If that's what you mean by "Shredderbases", then we've got it covered. Anyway this article is mostly about the concept of tablebases, without focusing on individual variants of product. YechielMan 04:17, 6 February 2007 (UTC)[reply]

GA failed

This article has been failed according to the GA criteria. The formatting of the inline citations need to be fixed, and more importantly, more need to be added. Look throughout the article and if there is any statement that somebody may question if it's verifiable add an inline citation. Look to other GA/FAs for examples. The article is interesting to read and has a lot of information, but needs better sourcing to pass. Add the citations before nominating again. Let me know if you have any questions on my talk page. --Nehrams2020 09:19, 24 February 2007 (UTC)[reply]

Earliest chess playing computer programs?

This article says: "In 1951, Alan Turing designed a primitive chess playing program, which assigned values for material and mobility; the program "played" chess based on Turing's manual calculations". However, the Los Alamos chess article says that it was written in 1956 and "was the first chess-like game played by a computer program." Now, I think there's a contradiction between these two pieces of information. Turing's program in 1951 vs. Los Alamos chess in 1956. I think one of the articles needs to be corrected. --ZeroOne (talk | @) 23:40, 24 March 2007 (UTC)[reply]

I'll try to check "How Computers Play Chess" for the dates. That should resolve the question. YechielMan 15:07, 25 March 2007 (UTC)[reply]
In The Computer Chess Compendium by David Levy there is an article Chess by Alan M. Turing from Faster Than Thought (B. V. Bowden, Editor), pp. 286-295. London, Pitman (1953). The program is written in english and while it is usually clear which move it would select there are some cases where it is ambigous. I'd say it is a chess playing program while Los Alamos chess is a chess playing computer program, so there is no contradiction between the two pieces of information. Epiteo 16:21, 2 May 2007 (UTC)[reply]

quality

I gave this artice a "B" on the quality scale, but it is likely that it deserves an "A". If anyone thinks so, change it. It is up for FA, so when that is decided one way or the other, the quality scale needs to be changed. Bubba73 (talk), 14:52, 30 April 2007 (UTC)[reply]

I have changed it already, I think it deserves A. Cheers,--Ioannes Pragensis 15:35, 5 May 2007 (UTC)[reply]

GA Pass

I am passing this as GA-class. As a casual chess player, I think it's reasonably clear to nonspecialists, but if you are planning on advancing it to FA, try to keep - and improve - that consistency. Otherwise, no complaints. Chubbles 05:50, 9 May 2007 (UTC)[reply]

Outstanding article

This is an outstanding article. Congratulations to the editor(s) that put it in this shape. One thing I would like to see is for 3, 4, 5, and 6-piece endgames: (1) how many combinations of material there are in each of these, (2) what is the total size of files for each. (3) maybe some similar statistics. Bubba73 (talk), 22:57, 16 July 2007 (UTC)[reply]

A class

Wikipedia:Version_1.0_Editorial_Team/Assessment says that class B "Commonly the highest article grade that is assigned outside a more formal review process." I have no objection to this article being in A Class, but does it need to have a formal review? Bubba73 (talk), 20:09, 26 July 2007 (UTC)[reply]

Since it passed GA above, perhaps it should be changed to GA, pending the review for it to be Class A. Bubba73 (talk), 21:54, 26 July 2007 (UTC)[reply]
This article is currently being assessed at Wikipedia:WikiProject_Chess/Review, please join the discussion. Voorlandt 07:55, 3 August 2007 (UTC)[reply]
The review is finished and the article has failed to go to A-class, so it is assessed as GA-class. You can find the conclusions of the review and hints for improvement at Wikipedia:WikiProject Chess/Review. Thanks to all for your contribution! SyG 13:10, 24 August 2007 (UTC)[reply]

You can see the archived discussion hereunder: SyG (talk) 09:02, 1 May 2008 (UTC)[reply]

Review of Endgame tablebase

This review is done in the scope of the WikiProject Chess and is transcluded from Wikipedia:WikiProject Chess/Review/Endgame tablebase. The edit link for this section can be used to add comments to the review.

Article stats

This article is accessed about 1300 times per month. Bubba73 (talk), 01:15, 4 May 2009 (UTC)[reply]

I actually spent a while the other day looking for the service that would give me this data... Here's the link: http://stats.grok.se/ —ZeroOne (talk / @) 09:54, 4 May 2009 (UTC)[reply]

Stalemated positions

The article says: Stalemated positions need not be worked from because every position that is not reached from a checkmated position is a stalemate.

Shouldn't this be drawn positions instead of stalemate? If you work backwards from all checkmate positions with a given set of pieces, all positions not reached are draws of one sort or the other - not necessarily stalemate. Bubba73 (talk), 01:20, 4 May 2009 (UTC)[reply]

Agreed. I have changed the text to: Other positions need not be worked from because every position that is not reached from a checkmated position is a draw. SyG (talk) 09:27, 4 May 2009 (UTC)[reply]

Humans

It might be good to note in the article that in the longer and more complicated cases, it is hard to impossible for humans to understand the reason for crtain moves. I've seen that mentioned in a few places.

In Pal Benko's June 1984 Chess Life column he discusses the tablebase for KBBkn. He gives two of the moves !?, one ?, and one ??. Of course, each of the moves in the tablebase is optimal in the sense of winning the quickest or delaying defeat as long as possible. Bubba73 (talk), 03:30, 4 May 2009 (UTC)[reply]

Yes, that is a good idea. That note could actually be incorporated into the infamous "Play chess with God" section. It might be enough to justify the existence of the section. —ZeroOne (talk / @) 10:39, 4 May 2009 (UTC)[reply]

Issues from former A-class review

As ZeroOne has started to work on it, for the sake of clarity I will list here the issues left from the former A-class review, and the answers that ZeroOne has now given. SyG (talk) 09:36, 4 May 2009 (UTC)[reply]

  •  Not done the caption for the picture in the lead seems too long. Actually, most captions are too long in the article. If these captions are really adding value, they ought to be incorporated in the text.
  •  Not done some words in British, others in American (however I do not see that as being really important)
  •  Done the sentence "Tablebases are generated by retrograde analysis, working backwards from a checkmated position" sounds obviously wrong, as tablebases also work backward from a stalemate position or from a drawn position.
I thought that retrograde analysis worked back only from won positions,since everything not reaching a won position is a drawn position. But someone more familiar with it than I am should see what is correct.
I have now modified this to reflect the fact that stalemated positions need not be worked from, because they are the ones that are not reached from checkmated positions. —ZeroOne (talk / @) 12:12, 2 May 2009 (UTC)[reply]
If you do not mind, I have moved your sentence to the section about "retrograde analysis", as it was not clear there that only won positions were subjected to retrograde analysis. SyG (talk) 09:44, 4 May 2009 (UTC)[reply]
Of course I don't mind. Whatever improves the article. :) —ZeroOne (talk / @) 10:02, 4 May 2009 (UTC)[reply]
  •  Done the sentence "Tablebases have solved chess for every position with six pieces or fewer" may precise that the "six pieces" include the Kings (may sound obvious to most, but not to me).
Seems to have been clarified by someone. —ZeroOne (talk / @) 12:12, 2 May 2009 (UTC)[reply]
  •  Done in the sentence "The results of the solution have profoundly advanced the chess community's understanding of endgame theory", what solution are we talking about ? what is endgame theory ? (there is no link)
The "solution" refers to the previous sentence, "Tablebases have solved chess for every position with six or fewer pieces" (emphasis mine). —ZeroOne (talk / @) 12:12, 2 May 2009 (UTC)[reply]
I have changed the results of the solution to the solutions, which is both shorter and clearer to me. SyG (talk) 09:47, 4 May 2009 (UTC)[reply]
  •  Done in the sentence "Positions which humans had analyzed as draws were proven to be decided", what do you mean by "decided" ? (not defined anywhere). To me, a "draw" is a decision.
Has been changed to "proved to be winnable" by someone. —ZeroOne (talk / @) 12:12, 2 May 2009 (UTC)[reply]
  •  Not done the sentence "Tablebases have enhanced competitive play" sounds like an opinion. Any reference ?
  •  Not done the sentence "They provide a powerful analytical tool, enabling students of chess to discover its deepest secrets", I don't know, somehow it just does not sound "encyclopedic", more something of a commercial add for a tablebase engine.
  •  Done in the sentence "In principle, it is possible to solve any game under the condition that the complete state is known and there is no random chance" I could point out that maybe we should explain/define what a game with random chance is, but that seems too nitty-gritty. Probably even the average Joe will know that.
I have now linked "random chance" to the game of chance article, that should be enough. —ZeroOne (talk / @) 12:12, 2 May 2009 (UTC)[reply]
Great. But now I doubt the sentence is true. Or more precisely what do we mean by "In principle" ? What about the physical limitation, that all atoms in the universe would not be enough to build a machine that could completely solve chess (or any sufficiently complex game, like Go) ? SyG (talk) 09:53, 4 May 2009 (UTC)[reply]
Well, the paragraph does continue "Other games, such as chess ..., have not been solved because their game complexity is too vast". The "...solve any game..." part also links to the solved game article, where a note is made that "for many non-trivial games such an algorithm would require an infeasible amount of time". —ZeroOne (talk / @) 23:34, 4 May 2009 (UTC)[reply]
"In principle" means that physical limitations and time are not taken into account. Bubba73 (talk), 00:54, 5 May 2009 (UTC)[reply]
OK, I have added that in the text. SyG (talk) 08:32, 5 May 2009 (UTC)[reply]
  •  Done in the sentence "Strong solutions are known for some simple games", why do you qualify the solution as "strong" ? What is a "strong solution" ?
"Strong solution" is defined in the solved game article and I have now quoted it into the sentence in this article. Unfortunately the sources used in solved game weren't available so I couldn't add links to them for now. —ZeroOne (talk / @) 12:12, 2 May 2009 (UTC)[reply]
I was able to retrieve a source and to add information about it into the article now. —ZeroOne (talk / @) 09:11, 3 May 2009 (UTC)[reply]
  •  Not done in the "Background" section, second paragraph, maybe we should mention the horizon effect to explain software's weaknesses in endgames ?
  •  Doing... all references should be wikified, e.g. "(Levy & Newborn 1991:25-38)" should be replaced by something like [63] (after the punctuation! ;-))
I don't know about that... Levy & Newborn is cited several times with the exact page numbers. If all references were converted to point to the same "[63]", we'd lose the information about the page numbers. At least Levy & Newborn are now cited consistently, and they are indeed cited using a template, {{Harvcol}}, so it must be an accepted way to cite sources in Wikipedia. —ZeroOne (talk / @) 09:22, 3 May 2009 (UTC)[reply]
Yes, my mistake. Several systems of referencing are accepted in Wikipedia, and Harvcol is one of them. But a given article should only have one single system of referencing, which is not the case for the moment. SyG (talk) 09:57, 4 May 2009 (UTC)[reply]
  •  Not done it would be cool to explain more in details the differences between Thompson tables, Nalimov tables, etc.
Indeed, it would. Maybe we should start a new section for the details. Right now the article pretty much takes all the tables for granted. This would be a good source for the differences: http://horizonchess.com/FAQ/Winboard/egtb.html#%5BA.2%5D —ZeroOne (talk / @) 11:08, 4 May 2009 (UTC)[reply]
  •  Not done the sentence "The stronger side can also win by capturing material, thus converting to a simpler endgame" should be rephrased as something like "The stronger side can also win by capturing material, thus converting to an endgame whose solution is known". Indeed, sometimes the computer goes to a much more complicated endgme (e.g. sacrificing pieces without reasons), just because it knows the solution of that last one.
  •  Done in the section "Step 1: Generating all possible positions" it should be made immediately clear that 40,000 is an approximation.
Done. —ZeroOne (talk / @) 09:22, 3 May 2009 (UTC)[reply]
  •  Doing... the paragraph on the conflict between pawns and symmetry is very interesting, and should be referenced.
I added a reference that says: "Pawns would break the front-back and diagonal symmetries, because they care about direction in their moves." A better source could be found but this should do for now. —ZeroOne (talk / @) 17:58, 3 May 2009 (UTC)[reply]
  •  Not done in the section "Step 3: Verification", maybe we should point out that it is not a verification of thruth, but only of self-consistency. I mean, the whole tablebase could be completely wrong and still self-consistent, and then the verification program would not detect the errors, right ?
  •  Done the sentence "(However, castling is allowed by convention in composed problems and studies.)" should contain links to "composed problems" and to "studies".
Done. —ZeroOne (talk / @) 10:44, 4 May 2009 (UTC)[reply]
  •  Not done the caption for the picture in the section "Using a priori information" is long and does not really bring information relevant for the subject of "a priori information"
  •  Not done in the section "Correspondence chess", I do not immediately see the link between the second paragraph and the title of the section. I mean, the 50-moves rule is applicable even in over-the-board games, in analysis session, in adjourned games, in computer chess, etc. So why should we mention it in the "Correspondence" section ?
  •  Not done the section "Endgame theory" is too long if the main article is considered to be "Endgame#Effect of tablebases on endgame theory". I do not see any need to double the information in each article, so maybe we should put a very short section in one of the articles, and a very expanded one in the other.
These two sections were written independently and have a different focus. The section in chess endgame concentrates on cases where tablebases overturned human opinions. Bubba73 (talk), 15:39, 4 May 2009 (UTC)[reply]
  •  Done there is a dead link to "Harold van der Heijden"
Not an issue anymore, the article has been created. —ZeroOne (talk / @) 09:28, 3 May 2009 (UTC)[reply]
  •  Doing... what is the purpose of the section "Play chess with God" ? It sounds trivia to me, and too short to be a section on its own.
The discussion below was moved here from under its own header, "Play chess with God", started by SunCreator. —ZeroOne (talk / @) 10:28, 4 May 2009 (UTC)[reply]
This section title is unencyclopedic. SunCreator (talk) 19:24, 2 May 2009 (UTC)[reply]
I don't see much of a problem with that section. The title is a title used in the article referenced. Most of the section is a quote from that article. I think it helps explain it. Bubba73 (talk), 03:37, 3 May 2009 (UTC)[reply]
Well, SyG is concerned about the same matter in his review, and I tend to agree with SunCreator and SyG. The section does sound like trivia and feels too short to stand on its own. Maybe the content could be incorporated into the other sections. —ZeroOne (talk / @) 09:26, 3 May 2009 (UTC)[reply]
Why use a quote in the section title? It's just strange. Everyone does not have the same concept of God. Perfect play or something similar would be cleaner imo. SunCreator (talk) 16:30, 3 May 2009 (UTC)[reply]
"Play chess with God" isn't that bad a title, we even have an article called God's algorithm. It is not linked to from this article, though, even though God's algorithm links here. If a link to God's algorithm could be incorporated into this article, it would be neat. —ZeroOne (talk / @) 18:02, 3 May 2009 (UTC)[reply]
OK, the section can go. The link there no longer works, but this might be the same. Bubba73 (talk), 00:55, 4 May 2009 (UTC)[reply]
The link works again. —ZeroOne (talk / @) 11:42, 4 May 2009 (UTC)[reply]

Nunn

John Nunn wrote three books based on data from endgame tablebases. Perhaps that can be mentioned. Bubba73 (talk), 06:28, 5 May 2009 (UTC)[reply]

Sure. It seems that John Nunn has written quite a few chess books. To which ones of them are you referring to? —ZeroOne (talk / @) 09:08, 5 May 2009 (UTC)[reply]
These three:
  • Nunn, John (1995), Secrets of Minor-Piece Endings, Batsford, ISBN 0-8050-4228-8
  • Nunn, John (1999), Secrets of Rook Endings (second ed.), Gambit Publications, ISBN 1-901983-18-8
  • Nunn, John (2002), Secrets of Pawnless Endings (2nd ed.), Gambit Publications, ISBN 978-1-901983-65-4
They are all based on his in-depth study of tablebases. Bubba73 (talk), 15:55, 5 May 2009 (UTC)[reply]
The first one deals with the cases of a minor piece and pawn versus a minor piece (except when bishops are on opposite colors); and two bishops versus one knight. The second deals with rook and pawn versus rook endgame, broken down by the position of the pawn. The third deals with pawnless chess endgames: rook versus a minor piece, queen versus a rook, queen and minor piece versus a queen, rook and minor piece versus a rook, queen versus rook and minor piece, queen versus two minor pieces, and then briefly covers a few others. Bubba73 (talk), 16:45, 5 May 2009 (UTC)[reply]

GA Reassessment

This discussion is transcluded from Talk:Endgame tablebase/GA1. The edit link for this section can be used to add comments to the reassessment.

I will be doing the GA Reassessment on this article as part of the GA Sweeps project.

The article is well written and cogent. The wikilinks are solid and topical. The Lead is a good summary of the article. The images are solid though a few of the captions are a bit long.

The checklinks tool is down right now so I did a random selection of the links in the Reference section. Links 14, 35 and 52 appeared to be either unavailable or dead. Please check these and repair if necessary.

Otherwise the article appears to meet the GA Criteria and I will keep it as GA. H1nkles (talk) 15:29, 17 June 2009 (UTC)[reply]

Thanks for this review. I have reduced the size of the longest captions, and I have updated the url of the links you rightly cited as dead. SyG (talk) 14:59, 20 June 2009 (UTC)[reply]

Step 1: Generating all possible positions

This paragraph contains inaccuracies and is rather weak. Especially the sentence "Several hundred of these positions are illegal, impossible, or symmetrical reflections of each other, so the actual number is somewhat smaller." is with respect to "impossible, or symmetrical reflections" nonsense. The number of illegal positions can be calculated. Better is to remove the reference to Levy and Newborn and precise the calculation as follows:

David Levy, How Computers Play Chess
abcdefgh
8
d4 black cross
c3 black cross
d3 black cross
b2 black cross
c2 black cross
d2 black cross
a1 black cross
b1 black cross
c1 black cross
d1 black cross
8
77
66
55
44
33
22
11
abcdefgh
The ten unique squares (with symmetry)

Once a metric is chosen, the first step is to generate all the positions with a given material. For example, to generate a DTM tablebase for the endgame of king and queen versus king (KQK), the computer must describe 34,968 unique legal positions. This number derives from a symmetry argument. The Black king can be placed on any of ten squares: a1, b1, c1, d1, b2, c2, d2, c3, d3, and d4 (see diagram). On any other square, its position can be considered equivalent by symmetry of rotation or reflection. Thus, there is no difference whether a Black king in a corner resides on a1, a8, h8, or h1. Multiply the case of the Black king in the corner by 60; the other three places at the edge with 58, and the remaining six cases with the 55 squares for the White king and this all by the 62 remaining squares for placing the White queen. The product (60+3×58+6×55)×62 = 34,968. [1]

  1. ^ See also Stiller 1995:93-98.

Otto (talk) 20:38, 23 August 2009 (UTC)[reply]

Yes I agree. (Since symmetry has been "broken" by choosing the position of the (say) Black king among those 10 squares, the only "equivalent" positions arise when the king is on one of the 4 squares on the diagonal. In that case one can require the White king to be not above the diagonal to remove all redundancy. Also, I don't think there are "impossible" positions either, if the kings are at a minimum distance of 1 square: I think any such position can indeed be reached.)
OTOH, the whole procedure outlined here is contradictory to the claim that Tablebases are generated by retrograde analysis, working backward from a checkmated position. See the separate talk section I created further below for discussing that - thank you! — MFH:Talk 21:21, 3 February 2022 (UTC)[reply]

Chess ist just an example

Databases exist for checkers as well. for 8x8 checkers 10 piece table bases exist. Here is an example of a win in 140 moves: http://pages.prodigy.net/eyg/Checkers/longest-10pc-mtc.htm They also exist for chess variants http://www.gothicchess.com/javascript_endings.html -Koppapa (talk) 11:09, 6 June 2010 (UTC)[reply]

Mmm, true. That means the whole structure of the article should be changed, or the article should be renamed. :-( SyG (talk) 21:11, 11 January 2011 (UTC)[reply]

Surely this is an exaggeration?

"If and when such seven-piece tablebases become complete, composing a traditional miniature chess problem will become obsolete."

Why? The number of positions in a seven-piece tablebase would be freaking gigantic; surely composers will still prefer to compose the traditional way, using the tablebase to confirm validity, rather than browsing through the tablebase to find positions that make good chess problems. The tablebase doesn't know anything about human notions of aesthetics, difficulty of solution, and problem themes; so far at least, one still needs a human composer to construct problems with these elements. Or if the writer of that sentence was worried that solving miniatures would become obsolete, surely official championships could simply deny solvers access to a tablebase while they solve. 91.105.30.13 (talk)

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Endgame_tablebase&oldid=407157316"