Author: Russell Reagan
Date: 16:52:57 11/13/02
Go up one level in this thread
On November 13, 2002 at 16:05:37, Dann Corbit wrote: >There are huge differences in alpha-beta algorithms, depending on different >pruning techniques, mostly. PVS and NegaScout are two major variations, but >that does not tell the whole story. There are many variants on null move >techniques (such as double null move and variable depth reduction). There are >various move ordering techniques in use. This may sound trivial and unimportant >but it can double the search depth. > >What about new algorithms that nobody has thought of yet? There may be some >surprises in store. There are still lots of choices to make for algorithms. > >If all engines were using the same algorithms, they would be at about the same >strenght. Why then, do chess engines vary in playing strength by many orders of >magnitude? > >I don't think you have a good handle on it. Sure, everyone uses *some* form of >alpha-beta. But that is like saying that all cars run on tires and gas and are >therefore of the same speed. But still chess programs mostly use the same algorithms, at least, the same in principle. I think the difference is that top chess programs are all different by evolution rather than revolution. For example, a program that uses min-max would be revolutionarily different from a program using alpha-beta. Contrast that with an engine that uses alpha-beta being evolutionarily different from a program that uses PVS. It's like the car commercial that says, "With the release of our car, every other car on the road suddenly becomes a previous generation automobile" (from Inifinity I think, even though it's not true). A program that uses min-max would be a previous generation chess program. A program that does no forward pruning is previous generation chess program. Using alpha-beta does not make a chess program a previous generation chess program, because PVS is not a revolutionary improvement that leaves alpha-beta in the dust. I'm not sure how your car analogy fits in here. On the one hand, I think that saying "cars have wheels" is like saying "chess programs do a search", so comparing a statement like Bob D.'s to a statement like "cars all have wheels so they're basically the same" isn't really comparing apples to apples. Specifying that a car has an engine is a different level of detail than specifying that a chess program uses alpha-beta. Saying a car has an engine is on the same level of detail as saying that a chess program has a search algorithm, even though you don't know what kind it is. Specifying that a program uses alpha-beta is on the same detail level as saying that a car has a V6 engine. You say that it's not fair to say that "all cars have wheels and an engine so they're all basically the same", but it is, because the detail level you're working with makes it so. It's not fair to compare a 4-cylinder Honda with a V8 Camero (different level of detail here), just like it's not fair to compare min-max with alpha-beta. They're not in the same class. A V8 Camero would beat a 4-cyliner Honda every time, just like alpha-beta would beat min-max every time. The same can not be said when comparing V8's against V8's, just like the same can't be said when comparing alpha-beta with PVS. Compare an improved V8 with a straight V8, and other factors will still be very important, such as the talent of the driver. Compare an alpha-beta engine with a PVS engine and other factors will still be important, such as forward pruning and move ordering. The same can not be said if you compared min-max with alpha-beta. If the min-max program has null-move and a better evaluation function, and the alpha-beta program doesn't have null-move, the min-max program still has very little chance. In other words, alpha-beta and PVS are within an arms reach of each other, so other factors are important. Min-max and alpha-beta aren't within a stone's throw of each other, so other factors are not even an issue. Are chess programs different? By many magnitudes in some cases? Yes, but are they revolutionarily different? I don't think so. I think all of the top programs are in the same generation. I don't think any top program has made any breakthrough of the significance that every other chess program suddenly becomes a previous generation chess program (I think this is what Bob D. meant by saying all chess programs use basically the same algorithms). What do you think? Russell
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.