Author: Christophe Theron
Date: 20:03:02 06/30/03
Go up one level in this thread
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
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.