Fabien Letouzey wrote:
I'm not sure it's natural. As a functional programmer, this "Node" class looks like a list of positions to me and is as such not worthy of a name. For the application to graphs, I guess the abstraction is "path". Disclaimer: I haven't had a look at the Python examples.
But in Scan I mostly use it as a position, except for two places that need repetition detection. I didn't find an appropriate (and short!) name for this.
Just so we use the same terminology, the AIMA book has a great section on this.
3.3.1 Infrastructure for search algorithms
Search algorithms require a data structure to keep track of the search tree that is being constructed.
For each node n of the tree, we have a structure that contains four components:
• n.STATE: the state in the state space to which the node corresponds;
• n.PARENT: the node in the search tree that generated this node;
• n.ACTION: the action that was applied to the parent to generate the node;
• n.PATH-COST: the cost, traditionally denoted by g(n), of the path from the initial state
to the node, as indicated by the parent pointers.
The node data structure is depicted in Figure 3.10. Notice how the PARENT pointers
string the nodes together into a tree structure. These pointers also allow the solution path to be
extracted when a goal node is found; we use the SOLUTION function to return the sequence
of actions obtained by following parent pointers back to the root.
Up to now, we have not been very careful to distinguish between nodes and states, but in
writing detailed algorithms it’s important to make that distinction. A node is a bookkeeping
data structure used to represent the search tree. A state corresponds to a configuration of the
world. Thus, nodes are on particular paths, as defined by PARENT pointers, whereas states
are not. Furthermore, two different nodes can contain the same world state if that state is
generated via two different search paths.
Applying this to draughts/chess: what the AIMA book calls State is what most people call Position, and what AIMA calls Action is what most people call Move. Also, PATH-COST is just the ply depth from the root.
The Node class + the PARENT pointers together form the search graph, and tracing the pointers gives your path abstraction. Note that the search graph is an implicit graph, and the edges (i.e. moves/actions) between the vertices a.k.a nodes (containing states/positions) are discovered dynamically through the move generator. I agree that Node is not a fundamental abstraction, but it is a natural building block for the graph abstraction.
In my library, I use the AIMA terminology. My State has several components, the side to move, and the piece placements (bitboard collection, I call this Position).
Chapter 3 in AIMA and the Python repo give a nice infrastructure for analyzing game trees. You can write all algorithm in a game independent way, and just plug in your own State, Action and Successor functions.
