Talk:Computer chess

From Wikipedia, the free encyclopedia

You have new messages (last change).

Contents

[edit] 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)

[edit] 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
I think solving chess is possible. --Aloril 11:29, 9 Sep 2004 (UTC)

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

I read the archived debate, and I find the topic absolutely fascinating. This is great stuff. Here's my take: We know chess is finite and therefore theoretically solvable. We also know that theoretically there might not be enough time available (whatever this means) to conduct the actual solving. However, no one knows what computing advances are on the way -- perhaps quantuum computers will be up to the task. Perhaps something else. From a purely logical standpoint, I think we have a duty to acknowledge that the game has a solution even if we don't have the capability of computing it yet. Whether that gets added to the article or not is another matter. It's a great article as is. Ikilled007 08:58, 25 February 2007 (UTC)

[edit] 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 Fritz, Rebel or any of the top chess programs are well above the strength of a FIDE Master (FM). Deep Fritz recently defeated the world champion. But as you say, GNU Chess is much weaker. Spiderpop 09:08, 1 March 2007 (UTC)

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

[edit] 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

List of engines and ratings

Some info about Winboard/UCI engines

Aaron Tay

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?

Aaron Tay

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, but disagrees with this one from Chessbase and this rather detailed piece 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

[edit] 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

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)

[edit] 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.

"a game where fifty moves pass without a pawn move or capture is automatically drawn."I thought this had to be declared a draw, since when is this automatic?

Right - it has to be claimed by one of the players, it is not automatic. Bubba73 (talk), 00:55, 13 February 2006 (UTC)

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)
Note also most humans can't defend positions to their maximum number of moves, so merely truncating the endgame table base to 50 moves might be fine for analysis, but might actually draw games against humans that would have been won in practice. There is no right answer - I suggest playing the best possible chess and claiming a moral victory if the computer has to accept a draw due to the 50 move rule, with mate in 2 on the board. Sometimes it really is how you play the game, and not the result that matters.
-- Simon
The 50 move rule is undoubtedly the most unnatural and least satisfactory rule in chess. Theoretically, it could be dropped entirely, as the 3 move repetition rule will eventually come into play in any position where true progress is impossible. It would be perfectly reasonable to drop the 50 move rule for chess between computers to produce a purer contest with more decisive games. For human players, the 50 move rule avoids the fatigue involved in games of hundreds of moves. With regard to positions like the Q+RP v Q ending where it takes 71 moves to get the pawn from the sixth rank to the seventh rank, it is not very useful to relax the 50 move rule between human players, as no human without a tablebase can approach accuracy in such an ending. The result of such an ending betwenn humans depends on whether the relative inaccuracy of the two players' moves permits a win in 50 moves. This is one reason that the relaxing of the 50 move rule for certain positions was dropped again, as it did not really add to the quality of human competition. Elroch 23:19, 12 November 2006 (UTC)

[edit] Anti-computer Chess

In the edit summary for 30 August 2005 13:48, Lenthe wrote

added link to a krabbe article about anti-computer chess. actually this article's enthousiasm about the strength of computers should be tempered a bit

It's an interesting link, but his premise seems bogus; why does a few less-then-optimal games and games played without the 50-move rule (a professional only rule) mean that computer chess isn't chess? Seems like a meatbag presumption against digital beings. The assumption that passing the Turing Test has anything to do with playing chess seems like pure anthropocentrism. The fact that someone has a playing style that can beat computers again means nothing, unless what you really mean is computer chess isn't human chess. As for today, Nemeth is effective against a number of PC-level programs, but a lot of playing styles have made a big hit when they first appeared and became less important when strategies were developed against them. Computers will likely be no different; new programming against Nemeth will be developed and it will just be a speed bump in the progress of better playing computers.--Prosfilaes 18:16, 30 August 2005 (UTC)

[edit] Quantum Computing?

In the "solving chess" section, I am completely uncomfortable with the paragraph focusing upon "quantum computing", a possible-only-if-the-theories-are-correct, future technology. Today, it is science fiction. Accordingly, I think it would be more responsible to remove its mention from this real technology article. --AceVentura

Quantum computing is not science fiction, it already exists; on a very small scale. It's a perfectly reasonable extrapolation to predict that chess might be solved using it, and the potential impact of quantum computing is being seriously considered on other areas such as cryptography. WolfKeeper

Wikipedia- Quantum Computing

http://en.wikipedia.org/wiki/Quantum_computing

Please note an article's link featured on this page entitled, "Unsolved problems in physics: Is it possible to construct a practical computer that performs calculations on qubits (quantum bits)?"

Although quantum computing may indeed become science fact or less inaccurately, real technology in the near or distant future, its basic possibility would not be debated by physicists if its future were assured. Upon closer inspection, this is a marginal case. I change my stand to neutral. Other editors may decide its fate. --AceVentura

[edit] Links

The link to http://www.brainsinbahrain.com/ seems to fail. The link to Computer-Chess Club links to a password request. Please, fix (if possible) this link, or I will erase them (or you can do). I do not know how to fix them (there is a misprint, or the websites changed their URL?). Gala.martin 19:37, 25 January 2006 (UTC)

[edit] Match drawn or tied?

The article lists matches as being drawn, for instance:

  • 2002, Vladimir Kramnik draws an eight-game match against Deep Fritz.
  • 2003, Kasparov draws a six-game match against Deep Junior.
  • 2003, Kasparov draws a four-game match against X3D Fritz.

I would prefer to say that games are drawn but matches are tied. Does anyone else have an opinion? Bubba73 (talk), 01:33, 13 February 2006 (UTC)

I think it's irrelevant whether to use "tie" or "draw". As the article you linked to suggests, a tie is the same as a draw. Fetofs Hello! 21:27, 22 March 2006 (UTC)
Yes, but we don't usually speak of a chess game being "tied", we say "drawn". Bubba73 (talk), 21:44, 22 March 2006 (UTC)
I agree that games are drawn but matches are tied. A tie implies equal number of points. Stephen B Streater 07:44, 9 April 2006 (UTC)

[edit] Endgame

I've edited this a bit. Here is some justiication.

[edit] Stored databases

With six pieces, the number of legal positions

< 64^6

= 68,719,476,736

With the board taking approx 7 bits per piece, this equates to 360GB. Thus a modern 10TB RAID array, which could be made available on the web, could store around 30 positions even if all the impossible-to-reach positions were allowed for.

[edit] Calculation at run time

OTOH, any single position could be solved in real time with enough RAM. Alpha-beta searching with a normal forward looking search with Win/Loss/Draw scoring would mean that only (in an ideal world) the square root of the number of positions would be searched before all relevant positions appeared in the database. With six pieces, this equates to 0.25M positions. Even with sub-optimal searching to the tune of thousands of times, with modern Macs supporting 16GB RAM, it be would a short matter to go through all positions allowed by the winning player strategy, thus solving a given position. Stephen B Streater 07:10, 9 April 2006 (UTC)

[edit] Brute Force vs. Strategy

I updated this section to conclude that rather than being a conflict between two completely different approaches, that the challenge is to find the middle ground between them that works the best.

I also updated the summary of the research of Adriaan de Groot to make it clear that these were his conclusions based on interviews, and not necessarily fact. I find it somewhat ludicrous to think that a master considers only 40 to 50 positions before making a move (but I do recognize that those were his conclustions, and he was a master). Bill Alexander

When I entered the First Inernational Computer Games Championship (it had a name something like that!) there was a big chess contingent and lots of grandmasters were there. They also thought they looked at around 40 positions. The consensus was that players at all levels looked at the same number of moves, but the good players looked at the right moves, with a branch factor of 1.3. Stephen B Streater 06:50, 14 May 2006 (UTC)
Well Bill, the problem is that a type A/Brute Force program simply calculates all possibilities to the limit of its time constraint and speed of its evaluation algorithm, that's how it got the name "Brute," it's an archaic, slow, inefficient approach. Adding parallel search/threads does not make the approach any smarter, it is still calculating all possibilities to the limit of its time constraint and speed of its evaluation algorithm. For example, let's say you add a second processor/thread, that would be like sending two people into the desert to search for a lost diamond ring, yes it will find the ring quicker than if only one person was searching for it, but it is still an inefficient approach. Type B, in the other hand, is the smart approach, it it discards the ridiculous moves and only calculates the moves that show promise, just like a human does. So back to the anology, a type B approach would be to ask the person who lost their ring where they were when they last were certain the ring was still in their possession, and then start the search from that last known position. This method is a lot smarter and efficient because instead of combing through an entire desert, you would only have to search a small percentage of the desert in order to find the ring. As you can see, these two approaches are entirely different, there can be no middle ground, a chess program is either type A or a type B, there is no type AB or BA or C. Do you understand what I'm trying to say? Dionyseus 07:53, 14 May 2006 (UTC)

I'm not sure ... Is a program that uses alpha-beta pruning a Type B program by definition? If so, then I am pretty sure that no one has ever written a strong Type A program - and we might as well drop this section from the article. I would call all the methods listed in the section Search Techniques methods that could be used by a Type A program, even though they end up limiting the search. The distinction is that they do so based on the results of previous searches.

Don't get me wrong, I think that good chess heuristics are absolutely crucial to making a good chess program. Besides pointing the computer in the direction of good moves generally, they allow it to search to find the best lines more quickly, and lead to many quick alpha-beta cutoffs, shortening the search time. I just have never seen a strong program that generates all the legal moves, uses some sort of pattern recognition to reduce this list to 10 or so, and then does a tree search on these. I certainly don't so easily give up on moves when I am playing chess.

By the way, I would be interested in references confirming that Deep Junior, Fritz and Hydra are Type B programs. I own a copy of Fritz, and use it often. Its diagnostics seem to indicate that its search is quite exhaustive (exhausting!). In general I would be interested in seeing some references that indicate that the opinion that Type B programs hold the future is held by someone besides you. Bill Alexander

Well the strength in type A programs came from their hardware. Back then it really did appear as if type A was the best approach because it was much easier to just calculate everything than the seemingly impossible task of making the engine smart. Deep Junior, Fritz, Shredder, and Hydra are all type B programs.
It's not black and white; there's a continuum between type A and type B, depending on how much chess knowledge gets built in.WolfKeeper 08:06, 15 May 2006 (UTC)
Take a look at 'Is Hydra as strong as Deep Blue?' in this Hydra FAQ, they explain that Deep Blue was the last type A/brute force searcher, and that Hydra is type B.
You're reading too much into this. Deep Blue was somewhat less sophisticated than the other programs it was contemporaneous with, because it was harder to build chess knowledge into silicon. Hydra has more flexible hardware and the team has simply been able to capitalise on this. Hydra is more sophisticated, but it's still type A. That's why it calculates 200+million moves per second; type B wouldn't do that.WolfKeeper 08:06, 15 May 2006 (UTC)
As for Deep Junior, Fritz, and Shredder, you can see for yourself that they are type B by going into menu 'Engine,' and then choosing 'Change Main Engine,' and then 'Engine Parameters,' and you can see that you can turn off some of the pruning and selective algorithms, but note that you cannot make them play as truly brute force, at least not in the Fritz 9 interface, I seem to remember that the Rebel 10 interface had an option that could force it to play in brute force mode. Dionyseus 03:43, 15 May 2006 (UTC)
That's not really true. All programs are somewhere between type A and type B. Hydra very probably has more chess knowledge than Deep Blue, but it's just a question of degree. Most programs try to evaluate a very, very large number of moves per second; and Hydra is the king of that right now. That's *very* type A behaviour. A type B program would evaluate *much* more slowly.WolfKeeper 08:06, 15 May 2006 (UTC)
The only reason Hydra can evaluate so many positions is because of its hardware, it can calculate just as fast as Deep Blue, but the difference is that Deep Blue was type A and was only able to reach a depth of 12 on average, whereas Hydra can reach depth 18 on average thanks to its type A approach.
It's not so simple. It uses a hybrid approach.WolfKeeper 20:16, 15 May 2006 (UTC)
If you make Rybka or Shredder play on Hydra's hardware, it is still a type B program, a type B program on very powerful hardware. Dionyseus 08:54, 15 May 2006 (UTC)
Hydra is a system of hardware AND software. Even if Rybka or Shredder was portable onto Hydra's hardware you'd doubtless end up disabling the chess coprocessors. Even if it might be possible to modify Rybka to use the coprocessors, would that still be Rybka? No. It wouldn't be either Hydra or Rybka, it would be a new engine.WolfKeeper 20:16, 15 May 2006 (UTC)
I have found this discussion to be very enlightening, and I stand corrected on a number of points. I still think that the conclusions in this section of the article too strongly favor Type B. I think the jury is still out about whether pruning prior to tree search produces the best chess. Bill Alexander
My personal view is that the current version as it stands gives readers a wrong impression that chess engines moved from Type B to type A and then back to Type B again in the 90s. From the reading of this discussion, pretty much everyone thinks this is wrong except for Dionyseus . Aarontay 20:09, 12 January 2007 (UTC)
Well can you name any type A engine/machine still in existence today? Deep Blue was really the last type A machine. Dionyseus 15:24, 15 May 2006 (UTC)
All of them. They're all type A programs, but with some features of type B. Type A and Type B are idealised things. It's quite incorrect to say that all current programs are type A or type B, they have aspects of both.WolfKeeper 20:03, 15 May 2006 (UTC)
No, they're not. You don't understand the differences in Type A and B. Here's the simple way to explain it: Type A programs evaluate all moves all possibilities. It would be like sending one person to find someone's ring in a desert, it's going to take that person millions of years to find it. If you add a processor, it is still Type A, it is like having two people looking for the ring in the desert, yes it will find the ring quicker than if there were only one person, but it is still a slow and inefficient method, it would take them thousands of years to search the entire desert. If you add 63 processors instead, it would still be Type A, 64 people searching for the lost ring in the desert, it still would take them years to search the entire desert. Type B, in the other hand, is the smart approach, a type B approach would be to ask the person who lost their ring where they were when they last were certain the ring was still in their possession, and then start the search from that last known position, instead of having to search the entire desert they only need to search a small portion of it. If you add 63 processors, it is still Type A, it would just make it a lot quicker. Dionyseus 00:30, 16 May 2006 (UTC)
Ok, a few points: a) I'm a professional software engineer. b) I've personally written several computer game searches, including chess c) I've read books on computer chess programming, so I do know something about it, so you can't bullshit me with talks about deserts.WolfKeeper 01:17, 16 May 2006 (UTC)
Type A, B were concepts outlined by Claude Shannon. His 'type A' program didn't even use alpha-beta pruning. Now, after alpha beta was invented, and added to a program, is that still a type A program? I think most people say yes. What about 'killer heuristic'? Again, mostly yes, some no, since killer heuristic works because of specific features of chess as a game. What about simple positional heuristics relating to King vulnerability? Debatable; yes, debateable no. So we have a fuzzy boundary, it depends what you think 'type A' is and isn't. And people will violently disagree. In fact I can quite reasonably take the position that no really successful program has ever been pure type A after the invention of alpha-betas. So given the extreme fuzziness of A/Bness, not only is it a stupid argument, I fundamentally disagree with the way you have edited the article to state that Deep Blue was type A and Hydra is type B. It really really, truly is not that simple, and you'd have to be very naive or ill-informed to argue about type-a or type b in anything more than a relative sense (obviously adding more chess knowledge makes something more type B). So yes, Hydra is more type B than Deep Blue, and Rybka is probably more type B than Hydra.WolfKeeper 01:17, 16 May 2006 (UTC)
I read the stuff about Deep Blue being a pure brute force machine and believed it for a while, but don't believe the hype, I found some of the papers on Deep Blue. It's so very wrong; Deep Blue was actually quite sophisticated, and had features like quiescence search/variable depth and so forth. It's not easy to beat Gary Kasparov, a pure type A program would never have won.WolfKeeper 01:17, 16 May 2006 (UTC)
Of course it's not easy to beat Garry Kasparov, but Deep Blue was able to win the match because it was capable of calculating 200 million positions per second and was able to reach on average a depth of 12 plies, in other words it was able to fully calculate all possibilites 6 moves ahead. That would also mean that it missed anything that was deeper than 6 moves, this is the folly of Type A programs, this is their major weakness. Hydra on the other hand can reach 18 plies on average, despite the fact that it calculates at the same speed as Deep Blue. Why is this? It's because Hydra is Type B and thus it doesn't bother calculating ridiculous moves and only considers what it thinks are good candidate moves. The Hydra team says this, I think they know more about computer chess programming that either of us Hydra FAQ. Dionyseus 01:50, 16 May 2006 (UTC)
They nowhere claim that they are a type B program. Do you have any other cite for your claim?WolfKeeper 02:56, 16 May 2006 (UTC)
You did not read the Hydra FAQ fully. Here, I'll post the relevant portion, and I'll put the most important portions in capital letters for you: "One example is the different search mechanism: Deep Blue and Hydra have about the same raw speed. Deep Blue searched in typical chess positions 12 moves (plies) deep, Hydra 18 plies. DEEP BLUE WAS THE LAST BRUTE-FORCE SEARCHER. Every possible combination was searched to 12 plies. HYDRA USES SOPHISTICATED PRUNING TECHNIQUES. SHE DOES NOT WASTE RESOURCES FOR IRRELEVANT VARIATIONS. Pruning away variations involves the risk to overlook some combinations, but the considerable greater search depth overcompensates this risk." If that doesn't convince you that Hydra is a Type B machine, then clearly you do not understand the differences between Type A and Type B. Dionyseus 03:15, 16 May 2006 (UTC)
I would not trust the Hydra FAQ has a unbiased source. They are clearly trying to downgrade the achievements of Deep blue. But as is well known, while Deep Blue is more "brute force" than Hydra they *do* stuff like singular extensions, so they extend some lines more than others....Aarontay 20:15, 12 January 2007 (UTC)
According to you, it's something to do with deserts isn't it?WolfKeeper 03:30, 16 May 2006 (UTC)
I repeat, it does not say that it is a type B machine. Do you have any cites that says that it is, or that any other programs are for that matter?WolfKeeper 03:30, 16 May 2006 (UTC)
Read the Computer Chess article here on Wikipedia for an explanation of what Type B is. Here's a quick explanation: "Shannon suggested that type B programs would use a "strategic AI" approach to solve this problem by only looking at a few good moves for each position. This would enable them to look further ahead ('deeper') at the most significant lines in a reasonable time." Dionyseus 05:07, 16 May 2006 (UTC)


I don't think null move pruning , extensions count as "strategic AI". Aarontay 20:15, 12 January 2007 (UTC)
Deep Blue was not a trivial brute-forcer; it used some sophisticated technicques--it does not do anywhere close to "examining every possible position for a fixed number of moves using the minimax algorithm." Both of them search millions of positions, and exclude a large number of them from further searching. It's not true, as they imply in the FAQ, that Deep Blue searched all positions equally; in fact, the Deep Blue team pioneered some innovations in quiessent search, where the program looks at some variations very deeply. The difference between the two is a matter of degree, not kind.
Deep Blue pioneered innovation in quiescent search? I read it was singular extensions. That's not quite the same as quisecene search. Aarontay 03:31, 11 January 2007 (UTC)
And you're being awfully condensending here. A little politeness might go a long way.--Prosfilaes 05:11, 16 May 2006 (UTC)
Well I'm quite familiar with Wolfkeeper for I had to endure mediation with him in the past. I did not intend to offend with the capital letters, I just wanted to make sure he would see it since it seemed as if he had somehow not read it the other two times that I provided the link. Dionyseus 07:07, 16 May 2006 (UTC)

I'd like to look at this type A / type B concept from a different angle. I wrote a brute force program which about ten years ago could manage a few million nodes per second on my Risc PC. It used a simple positional evaluation on the first ply to sort the moves. For the depth search, it scored by counting only piece values, using alpha-beta windowing with zero width (most moves came out as score zero, giving almost perfect cut-offs). By using iterative deepening and remembering the best move from early positions to help the sort order, I could generally search 12 ply exhaustively (max 18 ply in simple positions), with a quiessant search for the capture of up to another 12 ply, though this usually ended immediately. The increase in ability as I increased the search depth was fascinating to watch. It could thrash everyone except real chess players - because the brute force didn't allow for positional information. This program makes all other Type A programs look like type B, because they are implicitly using positional AI in their positional evaluations. To me, there is type A, and then a long line which stretches out past Deep Blue, Hyrda and the rest increasingly towards Type B which effectively is at infinity. There is no Type B point, because a better positional evaluation will always be possible. And better positional evaluation is effectively a mini pruned search. Stephen B Streater 08:43, 16 May 2006 (UTC)

I think what has really happened is that people have redefined type-B. It sounds so much better to say that my program is an intelligent strategy type-B whereas your program is a just a stupid brute-force type-A...

Having actually read Shannon's paper :) he has type-A as a fixed depth search, and type-B doing 1) "evaluate only at reasonable positions, where some quasi-stability has been established" i.e. quiessant searching and 2) "select the variations to be explored by some process so that the machine does not waste its time in totally pointless variations."

Now, just about everyone, even those calling their programs type-A, has been doing quiessant searching for ages. It's easier, for one thing.

Back in the 60s, 70s and 80s, people doing type B did things like have complicated decision-making - 'plausible move generators' - to chose which moves to look at in any one position. Now people are just doing null move pruning (i.e. assuming that at least one move exists that won't make things worse for the player making it) and some of them are calling it type-B.

Indeed, if you look at the top programs whose source is available, including an earlier version of the current computer chess champion, they're typically doing fixed depth full width search plus quiessant searching plus null move pruning and... twiddling with the evaluation function, nothing more. The search has moved since Shannon's day from minimax to alpha-beta to negascout, but they're still A's in my book.

Anyone using some of the claimed type-B programs for analysis knows there's either some pruning going on or the evaluation varies depending on depth (e.g. becomes 'material only' after a certain depth) - what's not seen in a 12 ply search is sometimes seen in a 6 ply search, 6 plies down the predicted line - but I seriously doubt that the pruning is much more than null move pruning. (And they're still searching millions of nodes, rather than searching a few thousand more intelligently.)

Does a simple 'if a is less than b' comparison count as the artifical intelligence that used to be implied by "type-B"? Probably not.

Or if it does, we are all type-B now. Lovingboth 09:38, 11 July 2006 (UTC)

Fully agree with your analysis, and I say that as a chess program author and researcher. The final paragraph about the resurgence of Type-B programs is completely incorrect. Really, the type-A/B distinction is a relic of the dinosaur age of computing, back when the hard problem was rationing out your 1000 nodes per second. Exhaustive search computer chess is the clear winner, due to the exponential increases in processor speed, memory, and disk space. --IanOsgood 23:11, 10 October 2006 (UTC)

Fully agree. But if we really *want* to talk about type A/B I would still say most modern programs are still mainly Type A with some aspects of Type B. Also when most people say Type B they think of more intelligent human-like selection of moves (plausible move generator mentioned above), which most modern programs don't do obviously, though there is pruning based on domain and non-domain heuristics (e.g Null move heuristic).Aarontay 03:31, 11 January 2007 (UTC)

[edit] On commercial chess computers, why was info deleted?

I have a hard time understanding how Wikipedia doesn't have any mention of the first commercially available chess computer (the Chess Challenger 1 by Fidelity Electronics). That is a key piece of information in the history of dedicated chess computers! And it is not well documented around the web except for a few German sites dedicated to this subject. I had added a couple of sentences with links to my site (www.chesscomputers.org) with mode information on this including details on the patent and the history of the company. I know it was a link to *my* site but I believe the information is very relevant. Those paragraphs were deleted. Any reason why? I'm not angry but just trying to understand how the collaboration and editing process works.

Thanks

--Isousa 00:26, 16 May 2006 (UTC)

Is your site a recognised reliable source? Stephen B Streater 08:44, 16 May 2006 (UTC)


I have references to information that can be verified, such as patent number, link to companies and actual pictures of documents, addresses, video interviews, all of which can be researched by anyone. For example, references to the US Chess Hall of Fame in Miami, FL. I have links to my site from the wiki Shachcomputer.info research site, etc. Information on dedicated chess computers is extremely scarce on the web and that's why I decided to share the info I researched myself. I thought that was the spirit of Wikipedia.
I respect the community and will not re-edit the article to include the info I had there before, but again, I'm just puzzled and trying to understand the why this info shouldn't be available. As of now, it is only in the possesion of few chess computer collectors around the world. I think it's sad that in the Chronology of computer chess there's no reference to the first commercial chess computer even.
Isn't there anyone here who can verify the info I had? For my own education, how can one get the information on Wikipedia "certified"?
Regards
--Isousa 23:51, 17 May 2006 (UTC)
You publish original research somewhere else first, but it looks like you've done that satisfactorily already. The reason I removed your initial reference to the first chess computer is that it was not well integrated into the flow of the article, which at this point is mainly about the technical aspects of computer chess and the performance of the state-of-the-art machines against professional opponents - the development of low-cost dedicated chess machines for a broad market is largely irrelevant to that; they use fairly unsophisticated hardware and software that is nevertheless quite sufficient to thrash most amateurs. My suggestion is that you should add a section about "commercial chess machines" in which information about the development of this type of chess machine is discussed. --Robert Merkel 00:04, 18 May 2006 (UTC)
Why not create the Dedicated Computer Chess article? I'm sure once you start it up others will help with more information. Dionyseus 15:10, 18 May 2006 (UTC)

Many articles have a history section. You could this chess computer to a short history section, perhaps just before the future section. Stephen B Streater 18:43, 18 May 2006 (UTC)

Thanks for your comments folks. I now understand it better. I usually don't separate the dedicated, commercial chess computers from software based chess computer games but I do see how a separate section makes the whole article more organized. I'll try to put together a brief paragraph there. Please let me know what you think of it when you see it. Thanks again for educating me.
Regards,
--Isousa 23:30, 20 May 2006 (UTC)

--Ferdinanvd 03:52, 15 September 2006 (UTC)fernando villegas03:52, 15 September 2006 (UTC)Ferdinanvd== Dedicated Units ==

Tha article about computer chess lacks a very important chapter, "chess computers" or, as they are called today, "dedicated units". This BIG omision is weird as much the full industry and in fact the field as such begun when commercial little computers that only played chess became commercially available. Today they are not anymore in the technological edge, but at least they were the main incarnation of computer chess in terms of social visibility AND strenght of play at the very least from 1978 to middle the 90's. A definition of a dedicated unit could be: a computer where electronic parts, the processor and the memory unit, are dedicated just to play chess. It is, then, a closed system where a chess program is fully embedded in the components of a system enterily designed to play chess and do nothing else. In the first times of this industry, the brand "Fidelity Electronics" was esential as much it produced some of the first and most sold and popular dedicated units, as Chess Challenger 7, that sold around 700 thousand units. Other companies of the period, some already vanished and some still existent, are Saitek, Novag, Mephisto, etc. The structure of these dedicated units, although variable along time as technology progressed, was constituted esentially by the following elements: a) a processor unit where the chess program was embedded and run the basic rules of the game, the search technique to list the available moves at any times and the rules to evaluate them. b) a memory unit to stock openning moves (ROM) and sometimes also to keep the value of moves already evaluated. c) some kind of contrivance to make possible the input of moves. In the first times this was just an alpha numeric keyboard with which the user could enter the move he wanted to play. d)an output device for the computer to show his moves.

The variations of this basic structure were many, but a the same time very restricted to those elemental principles. Most units came with a flat surface as a chess board, but others came with just a screen to show the alpha numeric identity of the moves and/or also a graphic representation of the board; these were of a reduced size, with the purpose to be used as handheld units. Later and more mature -and expensive- dedicated units came with a sensory surface that made possible to enter the moves just pressing the pieces on the squares, but some - still more expensive- even made possible to play just moving, like in real life, a piece from one square to the destination without exerting pressure over the surface of the board. In his climax, in the middle 90's, the better dedicated units were capable of playing at the level of a high expert or even Fide master, but soon they were overwheelmed by programs run in personal computers whith 100 or 1000 times faster processors. This can run a chess program at equally 100 or 1000 times higher speed, so that the perfomance of those programs were and are, in the main, far superior to even the best dedicated unit. This is so due to the fact that a very important factor to explain different chess strenght is the number of moves analyzed in an interval of time, as much this quantitative factor make possible to examine more deep sequences of moves. Clearly a chess contrivance that in an X time only can examine sequences of about 6 moves (white play, black play, then white play, black play, etc) deep cannot compete with modern chess programs that in current computers can examine very long sequences, sometimes 15-20 deep.

[edit] Chess engine rating lists

I have moved this list to Chess engines where it is more directly relevant. BlueValour 01:19, 18 October 2006 (UTC)

[edit] humans

In the external link I added today, one of the programmers of Deep Blue said that it was not specifically designed to play against Kasparov (although I have heard otherwise). I expect that most programs are not designed for a particular opponent. Bubba73 (talk), 01:33, 11 January 2007 (UTC)

I agree. I would go so far to say that this *never* occurs except in terms of cooking the opening book, which human players do all the time against selected opponents. And even that's more to ensure the program doesn't crash and burn then anything in the opening. As for specificly tuning the program to be anti-kasparov, Programmers don't know enough about chess to even attempt to do such such a thing. To do that you would need to have a special algorithm to analyze and quantity playing style, strengths and weaknesses. It would involve psychological models and all that. I do think that chess programs would be tuned to play differently against human players in general (keep queen on board, open lines as much as possible etc) than against their fellow computer program peers, but that's a far cry from "specifically designed to play against Player X". Aarontay 19:59, 12 January 2007 (UTC)

I see some reasons why computer versus human matches may seem unfair, but I have no reference for this:

  1. Human players are not allowed to use any materials. Computers are allowed to use a huge database of openings, endings, etc.
  2. Humans are not allowed to analyze on another board. You could argue that computer programs are doing that. Bubba73 (talk), 01:33, 11 January 2007 (UTC)

Very old debate , I don't see the point of adding such arguments, since most of this would violate WP:NOR Aarontay 19:59, 12 January 2007 (UTC)

If it is an old debate I would think finding cites is not a problem. So there would be no risk of NOR. Also, especially for old debates it would be interesting to summarize the pro and con positions. Sander123 14:53, 16 January 2007 (UTC)

[edit] Inaccuracies in endgame tablebase section

"All endgames with six or fewer pieces, and some seven-piece endgames, have been analyzed completely."

I thought that Nalimov endgame tablebases does not include 5 vs 1 kind of endgames, so the claim all 6 or fewer is inaccurate? :)

"This results in the tablebase returning results such as "Forced mate in sixty-six moves" in some positions which would actually be drawn because of the fifty move rule. However, a correctly programmed engine does know about the fifty move rule, and in any case if using an endgame tablebase will choose the move that leads to the quickest win (even if it would fall foul of the fifty move rule with perfect play)."

I don't quite agree that the 50 rule move problem can be solved by a correctly programmed engine. Aarontay 13:32, 16 January 2007 (UTC)

You may be right about that 5 versus 1 tablebase, since there isn't much point in doing a king and 4 poieces versus a lone king. The second thing needs to be clarified too. Bubba73 (talk), 14:33, 16 January 2007 (UTC)
This page [1] seems quite comprehensive and doesn't list 5-1 endgames. Presumably because they do not exist. The article claims that some 7 piece positions have been done. Does anybody have a cite for that? Aarontay, what to you mean when you say: "I don't quite agree that the 50 rule move problem can be solved by a correctly programmed engine." ? Sander123 14:52, 16 January 2007 (UTC)
Definitely 7 pieces tablebases has being created (though to my knowledge not sytematically, and not Nalimov format) by Marc Bourzutschky & Yakov etc. What I mean about the second thing is that given the limitations of say Nalimov with regards to 50 moves rule, no (practical) engine modification can compensate for that, without changing the format. That is my understanding anyway Aarontay 16:14, 16 January 2007 (UTC)


As a quick answer to some seven-piece endgames being done, see Endgame#Longest forced win. Bubba73 (talk), 15:26, 16 January 2007 (UTC)
There are probably several othersworking on 7-piece endgames, those came to mind. Bubba73 (talk), 15:39, 16 January 2007 (UTC)
Retrieved from "http://en.wikipedia.org../../../c/o/m/Talk%7EComputer_chess_7352.html"