Talk:Computer chess
|
|
| Contents |
Introductory paragraphs corrected and clarified
The previous introduction erroneously gave the impression that computer chess dates back to 1769; I clarified that this was a hoax and linked to The Turk as appropriate. I then noted circa 1950 as the earliest realization of legitimate computerized chess (according to Bill Wall's timeline; the link to which I added to the external links section). Also the commentary on the motivations and success of chess computerization were separated into a new paragraph and refactored a bit.JimD 00:42, 2004 Jul 27 (UTC)
Computers won't solve chess
Removed from main page: Theoretically, at some point in the future, a computer will be able to play all possible chess games and determine the optimal move for any given board position (using Moore's Law as a guide, it probably won't happen until 2030). For example, the fastest chess programs can "look ahead" and completely finish the last 15 moves in a game (because of "pre-calculated" endgame tables). This is possible because there is a finite number of ways the chess pieces can be arranged on the chessboard.
- Finite, yes, but very, very large. As noted at the beginning, the number of possible board positions is probably greater than the number of elementary particles in the universe. Moore's misquoted law says computers double in speed every 18 months, but to search one more possible move on a chessboard typically requires a factor of 16 increase. Computers in 2030 (by Moore's Law) are a mere million times faster, which gets you all of 5 more moves. --Belltower
Mathematically, YES, chess is solvable but almost impossibly so. Please refer to the thorough discussion which already transpired on the following page: http://en.wikipedia.org/wiki/Talk:Chess (See section 10.) --OmegaMan
Computer chess
Isn't GNUchess is vastly weaker than other widely distributed software? Fritz or Rebel could defeat most master players under tournament conditions, but I am not sure GNUchess could. Can anyone confirm or contradict? Thanks. --Karl Juhnke
From the main article: "Minor variations to the rules would either make chess a trivially easy task for a computer to win, or conversely leave even elaborate computers easy pickings for amateur players." Really? What minor variations? Does anyone have a citation for this? -- The Anome
- It is partly a supposition on my part, but I believe a good one. It is based on the facts that a) the different algorithms for playing various board games (checkers, chinese chess, othello, etc.) are all variations on minimax searching with pruning heuristics, and that in some of these computers can be beaten by rank amateurs, but others computers are the undisputed world champions. Secondly, it is a general characteristic of tree search algorithms like this that they are *extremely* fragile—a minor change in the pruning heuristics and suddenly things go to pot. --Robert Merkel
I, too, am curious what "minor variations" you have in mind. For example, I understand that it doesn't particularly tip the balance of power between computers and humans to play FischeRandom chess, or chess at material odds. The variations at which computers are known to stink relative to humans all seem to me to involve major rule changes, e.g. bughouse.
The reason computers excel at some games and do poorly at others depends, AFAIK, mostly on the presence/absence of a quick, reliable static evaluation function. In chess you get a very fast and reasonably accurate static evaluation simply by counting up material. Similarly for pruning heuristics, the most important thing is to keep examining a position as long as there are captures, checks, or promotions. Otherwise the static evaluation is OK.
In the absence of any specific examples of how a small change in rules makes a big change in computer playing strength relative to human playing strength, isn't the contested sentence purely speculative? --Karl Juhnke
Nice edit, Axel, issue resolved. Does that mean we should delete the talk section about it? --Karl Juhnke
No, we usually junk talk entries only if the discussion refers to a completely different version than the current one. AxelBoldt
Answer to GNUchess question and more suggestions
With regards to the question about GNUchess, yes GNUchess is weak even in comparison with freeware products like Crafty, Yace, Ruffian etc. The last, Ruffian is as of June 2003, generally acknowledged as the strongest chess engine you can get without paying a cent. The strongest engine of which source is available is Crafty, by Dr Hyatt, (author of Clay Blitz mainframe—a 2 time winner of World chess championships in the 80s). Crafty is a chess engine with a long history. I'm surprised it doesn't get a mention.
GNUchess is no pushover though. Depending on hardware and time controls, perhaps only FIDE rated players about 2100 can be certain to match Gnuchess, though weaker players can win one or two games.
Does anyone think it's a good idea to include information about endgame tablebases? Maybe a small mention on how many chess engines (200+ at last count) are conforming to one of the two communication protocols, Xboard or Universal Chess interface (UCI) which allows engines to be used in various interfaces both commerical (Chessmaster, Fritz etc[.]) and non-commerical (Winboard, Arena, Eboard, Knights, etc[.])
I'm new to this, so I'm not sure what's the best way to go about adding entries.
Some external links
Endgame Tablebase FAQ (http://www.aarontay.per.sg/winboard/egtb.html)
List of engines and ratings (http://wbec-ridderkerk.nl/)
Some info about Winboard/UCI engines (http://www.aarontay.per.sg/Winboard/article.html)
Various other things that could be added to the article
- Early history of the chess computers (including the theoretical work of Babbage, Zermelo, Quevedo, Von Neumann, Shannon and Turing)
- The russian BESM
- How chess AI work led to the development of alpha-beta searching.
- The ITEP versus Kotok-McCarthy match
- The development of custom chess hardware (à la Machack 6 and BELLE)
- The Fredkin Prize
- The International Computer Chess Association
- The ICCA journal
- Levy's Computer Chess Compendium
- Non-bruteforce approaches to chess AI, for example the TDLeaf algorithm
--Imran
Well isn't the ICCA journal now the ICGA? Interesting ideas, maybe I'll work on one of them, but on a new page maybed?
- Yes, it's operated under the name of ICGA since the first issue of 2000. --Imran 14:56 24 Jun 2003 (UTC)
Is there some confusion on there being more than one David Levy? The link here goes to an astronomer whose website makes no mention of chess—this needs sorting and/or disambiguating (or at least some mention of chess being added to David Levy's profile). --/Mat 22:46, 6 Apr 2004 (UTC)
- If someone want to write up an article about the Chess David Levy here's some information I found about him,
- Born: March 14, 1945
- Won the 1997 Loebner Prize
- Founder and Chief Organiser of the annual Mind Sports Olympiad,
- Founder of Computer Olympiads
- Founder of World Computer Chess Championships
- Since 1999 the president of the International Computer Games Association.
- --Imran 11:25, 7 Apr 2004 (UTC)
Our article here says that Leonardo Torres y Quevedo built his rook and king versus king-playing machine in 1890. This agrees with this webpage (http://www.hornpipe.com/ba/ba10c.htm), but disagrees with this one (http://www.chessbase.com/newsdetail.asp?newsid=1799) from Chessbase and this rather detailed piece (http://www.cs.us.es/~perer/publicac/ltq/leonardo.html) in Spanish which both claim it was 1912. I don't know which is correct myself; I just wanted to note the discrepancy and ask if anybody knew with absolute certainty which is correct. I'm tempted to believe 1912 myself, since that Spanish-language page looks rather well researched. --Camembert
- A bit more on this: the Oxford Companion to Chess, in its "Automaton" entry, states this machine was first exhibited in 1914. This suggests a 1912 build date more than it does 1890, though the OCC doesn't actually offer a date for its construction. Still, I think the balance of evidence suggests 1912, and since nobody has come up with anything completely comprehensive, I'm going to change the article to 1912. --Camembert
Inclusion of Arimaa
I notice that a reference to Arimaa was added to this page and then deleted. It's true that Arimaa isn't as well known as Go, but the people who do know about Arimaa are predominantly AI researchers. That is to say, the importance of Arimaa as an area of AI research far exceeds its importance as a strategy game. Furthermore, there is a $10,000 standing prize offer for writing an Arimaa program that can beat the top humans. If a reference to Arimaa from this article isn't yet appropriate, then I predict that in a year or two it will be, as the game continues to prove itself to be interesting and intractible to computers. --Fritzlein 18:31, 11 Nov 2004 (UTC)
So is it still out of the question? lysdexia 06:34, 12 Nov 2004 (UTC)
I would prefer to NOT include Arimaa within this article. For that matter, Go (board game) as well.
This article is entitled "Computer chess" and NOT "Computer board games". This is a significant distinction. Although the broad definition of "chess variants" is nearly interchangeable with "board games", the specific definition is not. Of course, I cannot judge for everyone else which definition we should be using.
I think it is instructive to point-out that at Zillion Of Games, a universal board game program, their webmaster and game expert Ed van Zon has devised an index of 14 categories for placing all 1023 download entries (as of Nov. 14, 2004).
Zillions Of Games | Game Index (http://www.zillions-of-games.com/games)
Please note that only the "checkmate" category (274 entries) and the "checkmate combo" category (56 entries) contains entries intelligibly related to chess, shogi or xiang-qi which are commonly known as "chess variants".
Furthermore, please note that Arimaa is properly categorized as a "breakthru-race game" and Go (board game) is properly categorized as a "territory game". Hence, their mention in an article such as this one is questionable. BadSanta
I vote against including many other games in this category. I'd like to make an exception for Go as a really well known example, illustrating why chess as a game might be different then other board games. If we include other board games, where do we draw the line? Until Arimaa has replaced Go as the obvious counter example, i'd say to leave things as they are. Sander123 16:33, 15 Nov 2004 (UTC)
Go is a much more obvious counter-example than Arimaa, partly because millions of people play Go whereas hundreds (or only dozens?) of people play Arimaa, and partly because the gap between the best computers and the best humans is much larger for Go than it is for Arimaa. The one thing that would qualify Arimaa for this page is its superficial similarity to chess, i.e. using the same board and pieces. But Arimaa plays so much differently than chess, I agree with those who are uncomfortable calling it a chess variant. --Fritzlein 01:16, 8 Feb 2005 (UTC)
Endgame
Also, the Nalimov tablebases do not consider the fifty move rule, under which a game where fifty moves pass without a pawn move or capture is automatically drawn. This results in the tablebase returning erroneous results in some positions such as "Forced mate in 66 moves" when the position is actually a dead draw because of the fifty move rule.
I thought that the 50-move rule had a specific exemption for positions for which theory predicted a result in a larger number of rules? Such databases surely count as "theory". David.Monniaux 14:52, 3 May 2005 (UTC)
- There used to be exceptions to the fifty move rule for material imbalances which could theoretically take more than 50 moves to win, but these have now all been scrapped (how this relates to the article, I don't know, but I thought I'd better mention it). --Camembert
- Well, it certainly relates: there are positions where the computer may know how to win (due to endgame libraries), but only in > 50 moves, which leads to a drawn game if the exceptions I alluded to is not present. Of course, this is not really a problem: the endgame libraries can probably be curtailed to endings in < 50 moves. David.Monniaux 06:39, 5 May 2005 (UTC)
- It actually touched off considerable debate when endgame tablebases first discovered forced wins of longer than 50 moves without capture or pawn advance. The initial reaction of the majority of chess players was that the 50-move rule should NOT impose a draw if one player has a forced win on the board that might take longer than 50 moves. The 50-move rule was never intended to cut off perfect winning play from a given position, only to cut off pointless play. On the other hand, it soon became clear that in practice it was difficult to categorize what positions deserved extended opportunity to win. As increasingly long forced wins were discovered, a consensus grew that the "purist" position was untenable in practice. Either the drawing rule would have to become a "250-move" rule in all cases, or there would have to be a ridiculously complex system for determining how long one would be allowed to play on.
- An additional consideration is that most humans don't have an understanding of pawnless positions that would allow them to convert a won position in, say, 100 moves, if they can't convert it in 50. In essentially every human versus human chess game, if there have been 50 moves without capture or pawn advance, then truly no one is making progress, and extending the game would not so much allow one side to execute good technique as allow one side to play on hoping for a blunder.
- The fifty move rule has once again become standard, and with good reason, but the purist mode of thinking is so intuitive and entrenched that it still requires explicit explanation as to how a "mate in 66" can also be "dead drawn". --Fritzlein 15:29, 6 May 2005 (UTC)