Author: Gian-Carlo Pascutto
Date: 07:51:34 09/16/00
Go up one level in this thread
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. >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? Is Dynamic Nullmove pruning allowable too? (I believe that's how it was called...Ernst Heinz has a paper about it) >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? As a more practical example, Hiarcs ply depth and Fritz ply depth are comparable? >>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". >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. >>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... >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). >>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. 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. >>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? >>>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. >>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. (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 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. 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'. -- GCP
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.