Author: martin fierz
Date: 02:12:12 07/01/03
Go up one level in this thread
On June 30, 2003 at 23:03:02, Christophe Theron wrote: >On June 30, 2003 at 03:36:50, martin fierz wrote: > >>On June 30, 2003 at 03:09:08, Christophe Theron wrote: >> >>>On June 29, 2003 at 10:29:33, martin fierz wrote: >>> >>>>On June 28, 2003 at 11:20:21, Frederic Louguet wrote: >>>> >>>>>I read an interesting paper from Albert Xin Jiang and Michael Buro about >>>>>Multi-ProbCut and its implementation in Crafty. I have always been very >>>>>skeptical about this pruning technique (for chess) but the paper is rather >>>>>optimistic. However, the data presented does not seem very convincing from a >>>>>statistical point of view (too few games, not enough opponents). So could Robert >>>>>Hyatt tell us a little more about the effectiveness of this technique ? Does it >>>>>_really_ work ? >>>> >>>>i can't really tell you anything about chess, but i tried multi-probcut (MPC) in >>>>my checkers program. the general opinion about checkers is that null-move is not >>>>a good idea there, so everybody uses his own hand-crafted pruning algorithm. >>>>therefore, MPC seemed like an interesting candidate for my program. MPC >>>>performed much better than no pruning, but also clearly worse than my (highly >>>>checkers-specific) own pruning. i ran matches with 300 games/match, so the >>>>results were statistically significant (i don't remember the numbers off-head). >>>>i don't see why MPC shouldn't work in chess if it works in other games like >>>>othello and checkers. whether it's better or worse than nullmove i have no idea. >>>>as a general observation, i find it hard to believe that any generic pruning >>>>algorithm (like MPC & nullmove are) could perform better than one which >>>>incorporates game-specific knowledge. >>> >>> >>> >>>The fact that a pruning algorithm works in a certain game tells you that >>>obviously this algorithms incorporates game-specific knowledge. >>> >>>In particular, the fact that null move works well in chess tells you a lot about >>>the essence of this game. At least it gives you an important information about >>>the game. >>> >>>By searching, and finding, good pruning algorithms for a given game we improve >>>our knowledge of that game. The fact that a pruning algorithm works reveals >>>something about the game that maybe you did not know before. >>> >>> Christophe >> >>let me try to reformulate what i meant: a pruning algorithm that knows something >>about the specific game should do better than a generic pruning algorithm, >>always. things like nullmove and MPC are very generic, i.e. you can add them to >>any game-playing program in more or less no time at all, and the program will >>usually improve. don't get me wrong, i like the concept of MPC very much, >>exactly because it's game-independent. >> >>when you say that null move works well in chess, you are talking about "normal" >>positions; in zugzwang situations it fails. AFAIK chess programmers have some >>defenses when not to use null move (or to use some double null move or something >>- i know too little about what you guys are doing...). this is what i meant: >>adding some game-specific knowledge improves the generic pruning algorithm. >> >>with MPC it's similar: although it's generic, it includes some game-specific >>knowledge in the form of the coefficients used, which are the correlation >>between scores at different search depth, which is then game-specific. this >>makes MPC adaptable to any game. in my experience, there are two problems with >>MPC: >>1) it generates horizon effects in the search tree in it's shallow searches, >>which i avoid with my own pruning scheme. >>2) it has no game-specific knowledge on when not to prune included. >> >>cheers >> martin > > > >Null move takes advantage of a fundamental property of chess, that's what we >have learned from it actually, so I consider that it is extremely game specific >in the sense that it helps tremendously in that game and has been shown to be >counter productive in games that share similarities with chess. > >It does not matter if this algorithm can also be used in other games. If you >rule out every pruning algorithm as being non "game specific" just because it >can also be used successfully in other games, you will be left with nothing in >your "game specific" category. Because either what you think is "game specific" >will also work in another game, or it would be possible to create a game in >which it would work. > >I just argue that the fact that some specific family of pruning algorithms works >in a given game reveals a lot about the properties of that game. That's a very >precious information that can be used to invent even better pruning techniques >for that game. > > > > Christophe i feel misunderstood :-) i never said generic algorithms were no good. i said an MPC version of my checkers program was much better than one with no pruning at all. i just say that ADDING some game specific stuff to a generic pruning algorithm is a good idea. with this i mean that the generic null-move algorithm is not the optimal solution for chess, generic null-move being: "search the current position with reduced depth and other side to move; if the score of that search is outside of certain bounds, do not do the full search." you can add this kind of code to any alpha-beta searching game program (just as you could with MPC); therefore i call it generic. whether such a pruning mechanism works or not in different games is a different question, but these algorithms have zero knowledge about the game they are playing, with the exception that you can adjust certain parameters in both algorithms to tune the engine. instead of this, i believe that the good chess programs have something different, specifically, instructions on when NOT to use this pruning. unlike the above version these exceptions are game-specific (possible zugzwang, perhaps identification of a "wild" position, and so on). if your exception reads something like "if not king_is_in_check", then you have something very game-specific for chess, which simply cannot be translated to other games, and which might improve your generic algorithm a lot. are you really telling me that you have no game-specific exceptions to nullmove in chess tiger?! i certainly believe you that you can conclude something about a game if somebody comes and tells you that e.g. generic MPC works with it but generic nullmove does not. BTW, i know some players who use null-move themselves in their decision-making process in chess. not very often, but they do. interestingly, those are usually the strong players :-) which supports your idea that null-move is well-suited to chess. cheers martin
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.