Author: Dann Corbit
Date: 17:05:01 09/16/00
Go up one level in this thread
On September 16, 2000 at 10:51:34, Gian-Carlo Pascutto wrote: >On September 15, 2000 at 21:04:53, Dann Corbit wrote: > >>On September 15, 2000 at 17:57:47, Gian-Carlo Pascutto wrote: > >>>The ply depths listed are totally uncomparable to alpha-beta >>>ply depths. >>> >>>If you think this is cheating, consider that that measuring >>>ply depth, via any algorithm at all, is a bogus measure. >> >>So! I've been bamboozled. I think that pruning that leads to the same >>solutions is valid. > >>Every sort of pruning will throw away some correct solutions. > >False. Normal futility pruning for example will never give incorrect >solutions. Alpha-beta pruning doesn't either. Depends on how you define it, I suppose. Alpha-Beta isn't really pruning, since it always gives the identical solution, at some point. Any sort of extension might give the same solution also. Consider quiescence. If I go forward for 10 1-ply exchanges at the end of a search, I see far into the future. I don't look at all the possibilities, but only a microscopic fraction of them. But I would not add 10 plies to the search depth. >>But NULL move is only very rarely going to lead to problems. > >You really think so? But what depth of nullmove pruning? Recursive or >non-recursive? At the depth which does not cause statisical harm to the solution. Whether recursive or not, or iterative to a given depth in plies is not terribly important. >Is Dynamic Nullmove pruning allowable too? (I believe that's how >it was called...Ernst Heinz has a paper about it) I have the paper. I don't see why not. As long as it does not harm play, it should be acceptable. But if null move is too vigorous or used in the endgame when only a few pieces are on the board, it clearly is not advantageous. Hence, variable nullmove pruning is an obvious and very good idea. >>As for extensions like quiescense and things of that nature -- they lead >>to better solutions but I don't think the added depth should be used to >>increase the ply estimate. > >Hmmm...so two programs, one with quiescense and without quiescense >are comparable in your opionion? Yes. The one with quiescense will probably play better most of the time. But a solution that exists at ply n will be seen by both programs at ply n. The program with quiescence might possibly see a *better* solution, but it will have considered the one seen by both programs. >As a more practical example, Hiarcs ply depth and Fritz ply depth >are comparable? Yes. They clearly are comparable. A linear function would probably provide an exact equation to fit them within a very close tolerance. >>>The only thing that might qualify is a fixed-depth, not pruned >>>except by alpha-beta, search. Those won't reach 16 ply within >>>the next few years I guess ;) >> >>Which was exactly my point. However, for NULL-move pruned searches, it appears >>that two of the difficult problems I posed were solved. A third would have >been solved, but Dieter felt mercy. I think the nature of my request was >>fairly obvious. > >>The notion that "ply depth means nothing" is bogus because >>everyone obviously knows exactly what I mean. > >Gee...I don't think I'm the only one trying to explain you that >you are wrong. Even one of the world's best chessprogrammers tried >to explain you were wrong and your refutation consisted of false >arguments. Doesn't look to me that "everybody obviously knows what >you mean". Whether you know it or not is unimportant, I suppose. To search to a given depth, through whatever means, is necessary to find a good move. All programs search in a very similar way and have the same exponential algorithm behavior. That's because the problem is an exponential problem. At some point in the search it will have considered all the important moves out to a certain depth in plies. The algorithm may not be able to determine what that depth is, but that search will have happened. This can plainly be seen from first principles. >>But let me temper it. >> >>If a pruning extension that leads to an examination of fewer leaves proves to >be superior in providing correct answers after a thorough statistical test for >>the same estimated depth in plies, that extension would be accepted. > >Nullmove thus fails. It IS NOT superior in providing answers for the same >estimated depth in plies. Even common sense should tell you why. Actually, I must agree, because nullmove will (on very rare occasions) cause serious problems because of zugzwang positions. They seem to be fairly rare in practice except in the endgame. Be that as it may, null move programs obviously play better than non-nullmove programs because they ignore bad choices and hence search much faster. The loss of correct solutions (however rare) should be acceptable in this case because most engines are designed this way and such losses are obviously outweighed by the benefits. >>>Every more or less standard chessprogram uses some kind of >>>extensions or pruning, which make the ply depth figure _meaningless_. >>>As meaningless as NPS is as an indicator of program strength. >> >>I disagree. Let's call ply the number of half-moves that a program is >examining on a minimum (ignoring NULL-move pruning). That is a completely >unambiguous term that anyone can understand. Now, if a program uses >extensions to see farther along certain special tracks, that is not a ply >depth but a speculation to improve the guess at the current ply. > >This sounds acceptable, but the choice of NULL-move pruning as an >exception is completely arbitrary. Also explain why using extensions >doesn't contribute to a programs strength, even if it is speculation. >Some programs are better speculators than others... Obviously, extensions greatly improve a program's strength (if done properly). I think Phalanx is a model that many people might want to consider in this regard. It consitently finds a correct solution at an earlier ply because of the extensions employed. But a ply is not completed until the search at the stated ply has finished. If someone does some sort of extreme pruning, it might be clever enough to almost always find the right answer (or 100% always like alpha-beta). In such a case, the program will win more games. >>On the next iteration, we will have moved to the next ply. > >Urgh. Define iteration. How does fractional iterative deepening >figure into this? (And it's not a theoretical question because >both Robert and Georg Zimmerman use/used it) > >>>Even worse, there exist very good algorithms that don't have >>>any notion of ply depth at all. >> >>What algorithms are those that do not consider half moves from the origin? > >Read Angrims answer. If you are interested in those algorithms, the soon-to >-be-released Sjeng 7.4 has a full implementation of proof number and >proof-number-squared search. > >I will be implementing Conspiracy Numbers as soon as I have time to do so. > >Allessandro Damiano (sp?) already has them for the next version of >Fortress...he is now reaching ply depth's of the form of 1.73 plies >(or something like that...CN ply depths are fractional). I don't have a problem with fractional plies. As long as we are talking about possible moves and possible responses to that move it seems a better method than integral plies. After all, ply completions are jumps and starts, but chess search progress is fairly smooth. Many programs report plies as: Ply NN: xx/yy Where NN is the level of move-countermove-countermove... reached and xx/yy is the number of moves completely considered and yy is the number possible. In a sense, that is a fractional ply too. In fact, I see no reason why ply depth should not be real valued. I could even imagine that plies could be imaginary numbers under some creative algorithm (though I might have a tough time picturing it). >>>Besides, the basic task you gave us was very badly worded too: >>>SOLVE these positions. >> >>Solve in the following manner: >>A program which has exhaustively searched 16 plies will have a material and >>positional value computation. The value of that computation is calculated in >>centipawns according to the PGN standard. You will find that after reaching a >>certain depth, good programs generally agree on the evaluation (certainly >within a pawn or so). > >Generally...within a pawn...I consider a solution to be something >that is mathematically certain. But it's indeed just dependent on >how you define things. Well, we won't ever have certainty in chess without some incredible breakthrough in algorithms. Doesn't your program report a depth in plies? Is it just to placate the masses, or what is the purpose of that number that you report? >Also...remember Steve Ham's games. What did he note about the programs >evaluation? I'm not saying that is _proof_ that you are wrong, but it's >a good indication. I don't think the way humans play chess and computers play chess are very comparable. I could be wrong, of course, but first we'll have to have someone discover how humans do it. Nobody knows yet. >>>A real solution would only consist of one thing: 1, 0, or -1. >>>Now, ironically, the one solution you didn't accept was the only >>>one I was able to solve... (to a 1) >> >>That's an interesting real solution, but it isn't the one that I asked for. > >Agreed, you asked for a proof if a mate was found. >What do you consider valid proof? Chest gives a certificate of proof, and will even expand it to prove the solution if you ask. Someone did offer a chest certificate for the position in question, and I have accepted that solution. >>>>Instead you ask for a value (centipawn evaluation) that is >>>also meaningless. Centipawn = 1/100 of a pawn ? But the >>>value of a pawn is NO constant! >> >>I made no such claim. However, centipawns is a measure approved of in the PGN >>standard. An unblocked pawn on the 7th rank is worth far more than 100 >>centipawns, obviously. > >I never said you did. I just demonstrated the approved measure of the >PGN standard is shaky. And yet you use it. You berate me for my lack of mathematical rigor, and yet you use each and every measure you chide me for in your program. Why doesn't your program just return a -1, 0, or +1? That's the only certain mathematical result. But it is totally impractical except for rare situations (when a mate has been found). >>>The only thing that matters >>>is whether the position is WON or LOST (or drawn). >> >>Is that what your evaluation function returns? I doubt it. > >It does. Not for the alpha-beta searcher though. It doesn't >matter to me what my evaluation function returns for the >a/b searcher. It's just an estimate anyway, used to guide >the search. The only thing that matters is that the correct >move is played. I agree with that, of course. But how do you decide about "the correct move is played?" You certainly don't find the mate/loss/draw 99.9% of the time in a search (except at the end of the game). You (rather) use a statistical estimate of material and position to decide a value. Whatever you decide to use, if your search is consistently successful, there will be an approximate mapping from your search to some other successful program's search. Is it pure chance that the WAC epd test suite will get approximately the same answers from top programs at similar time controls? Most of the positions are not checkmates, so they are finding "the same solutions" without any pure mathematical rigor of true solutions. But somehow they get the correct solution anyway. >(correct = leading to the same gametheoretic value as the position >has) > >[personal opionion without supporting figures or facts snipped] > >>I realize that programs do prune differently. However, at whatever the author >>really believes are the strongest play settings they do have some idea of what >>half move they are processing, I am sure, for any algorithm. If not, where is >>the algorithm so that I can read about it? > >Louis Victor Allis, Searching for solutions in games and artificial >intelligence, PhD thesis Is this used in Chess? >Anything about conspiracy numbers (Ulf Lorez's and Schaeffer's work >recommended) > >Probability Based B* (Hans Berliner) > >Probably STC too (the one I used for the analysis), but I don't think >there are any papers about that on the web. For each of these, they search a depth in plies in some way. They may not have the information to display it, but the same information must be considered in some way. Now, they may not search "sperically" but rather "elliptically" or even in some tortured shape. But at some point, they will have considered the same sphere of important moves or they won't be successful strategies. If the information is not available for display, then it can't be used in my challenge. >Actually...I think most ANYTHING except alpha-beta. > > >>>PS. >>>My own program Sjeng reached over 12 ply in 30mins on 5 of >>>those positions on my Cyrix120, so it's likely that a fast PentiumII >>>can solve them. Also, the matefinder was on to something in at >>>least one other position (not the mate above though!). I will >>>try to get a full 16 ply search tomorrow. But again I ask you >>>to realize that '16 ply' is meaningless. The only reason why Sjeng >>>is able to get to those depths faster than e.g. Crafty (on the positions >>>I tested this was the case) is that Sjeng is very light on extensions, >>>but heavy on pruning. A 16 ply Crafty search is totally uncomparable >>>to a 16 ply Sjeng search. You can replace Crafty and Sjeng by any >>>random chessprogram in that last sentence. >> >>When Christophe Theron said that we were close to being able to search 16 plies >>in a game, what do you think he meant? > >That ChessTiger is able to search the game to an arbitrary depth measure >he calls plies because that sounds familiar. > >>Were his words meaningless? > >No, keeping in mind above statement. > >>I don't think so. Each ply (in my definition) is a half-move carefully >examined by the program [in such a way that the optimal chances of winning >from performing the analysis in that manner are performed]. > >Now it gets even better. I can show you Sjeng is able to search to >depths of 100 000 000+ plies. I even let it go to 300 000 000 once. > >This definition is equal to what most people call a 'node'. Then your program wasn't playing chess. There are less than 300 million moves and responses allowed in a game (see Steve Pribut's Chess FAQ). If I call a node a truck, can I drive it home? Well, I can call my car a test tube. Then I am driving a test tube to work? (Shakespeare, roses, and all that). Maybe that is one more reason computer chess programs are hard to understand. Everyone uses any term they like to mean anything they want. A ply is the legal moves possible from a node. The next ply is the set of responses to the choices made. The next ply are the responses to the responses, etc. At some point, I *must* search through the current possibities to make a choice. A deeper search means I must search through the next set of possibilities. Now, extensions do muddle up the meaning of ply some, I will admit. But until you have considered all the possibilities (excluding null move or other equally sensible moves to safely ignore) you have not _completed_ the ply. And if you search very quickly and very deeply down a certain trajectory [e.g. quiescence], you will have more information for the choice of the best move, but you will not have completed the ply yet.
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.