Author: Christophe Theron
Date: 11:09:08 07/01/03
Go up one level in this thread
On July 01, 2003 at 05:12:12, martin fierz wrote:
>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
I wouldn't say that we disagree. We are not talking about the same thing.
Christophe
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.