yojo
User
Junior Member
| Posts: 25 |   |
Karma: 0
|
Re:Seeking pruning algorithms - neep help! - 2006/08/15 13:16
If you understand futility pruning, then extended futility pruning and razoring are simple. Basically futility pruning takes place at frontier nodes (leaf nodes), extended futility pruning takes place at pre-frontier nodes (the ply before the leaf nodes), and razoring takes place one ply before that (two plies before leaf nodes).
You can read a little about them here. http://www.ast.cam.ac.uk/~cmf/chess/theory.html
I read an article that stated that razoring and the gamma algorithm "omit moves whose immediate value is worse than the current best of the values from the nodes already searched, since the expectation is that the opponent`s move is only going to make things worse. Generally speaking these forward pruning methods are not reliable and should be avoided." ( http://www.cs.ualberta.ca/~tony/OldPapers/encyc.mac.pdf )
There are plenty of other algorithms that people use, but I doubt you will find much detail about them. For example, Christophe Theron, the author of Chess Tiger, uses a method he refers to as "filtering", in which he uses several pruning techniques. Each one "filters away" a few moves, and it helps him get better move ordering and better branching factor to search quite deep. Of course, that`s about all he`ll say about it.
Basically there are three categories of forward pruning techniques.
1. Null-move 2. Methods that are questionable (razoring, for example) 3. Methods that are used by only a select few that the general public has no knowledge of. (filter, for example)
So basically you can do a lot of looking and searching and you probably won`t find anything too helpful, unless it helps you to understand the idea of forward pruning better. The best method is probably to just try to figure out how you can get rid of moves without searching. In other words, think about what logically makes sense. The null-move pruning method uses the logic that "if I do nothing and my score is still good, then I`m going to have an even better score if I do something." You just have to come up with ideas like that. I`ve come up with a few ideas, but I am not far along enough with my program to even begin testing these ideas.
---------
The difference between genius and stupidity is that genius has its limits.
Popular posts by yojo
Would Fischer have been great at an...
Machines Calulate/Evaluate, Peop...
Simple Chess Program
|
post new topic
