Author: Tom Likens
Date: 14:17:46 02/21/03
Go up one level in this thread
On February 21, 2003 at 13:26:34, Alvaro Jose Povoa Cardoso wrote: >Could someone please define what "ALL node" is and axplain how do we process >these type of nodes? > >Best regards, >Alvaro Cardoso Alvaro, The node types were first defined by Knuth. They basically refer to the nature of the nodes in a perfectly ordered tree that is searched with the alpha-beta algorithm. He defined the nodes into three types (called appropriately enough type 1, 2, and 3 ;) Type 1 ------ 1. The principal variation consists of Type 1 nodes. 2. All the moves at type 1 nodes have to be searched, and move ordering is *very* important. 3. The first child of a type 1 node is also a type 1 node 4. All other children of a type 1 node are type 2 nodes Type 2 ------ 1. Only the first child of a type 2 node needs to be search since it will (again, remember this is a "perfectly" ordered tree) cause a beta cutoff and return. 2. All children of a type 2 node are type 3 nodes Type 3 ------ 1. All children of type 3 nodes are type 2 nodes 2. All children of type 3 nodes must be searched and move ordering is *irrelevant*. 3. This is an ALL node, since all the moves need to be searched and the order will not help in achieving a quick cutoff. Knuth's original paper has just been recently re-released in the new book "Selected Papers on the Analysis of Algorithms". A quick search on Amazon.com will locate it for you. regards, --tom
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.