SEARCH
NEW RPMS
DIRECTORIES
ABOUT
FAQ
VARIOUS
BLOG
DONATE


YUM REPOSITORY

 
 

MAN page from openSUSE Tumbleweed perl-HTML-Tree-5.07-1.4.noarch.rpm

HTML::Tree::AboutTrees

Section: User Contributed Perl Documentation (3)
Updated: 2017-09-01
Index 

NAME

HTML::Tree::AboutTrees -- article on tree-shaped data structures in Perl 

SYNOPSIS

  # This an article, not a module.
 

DESCRIPTION

The following article by Sean M. Burke first appeared in The PerlJournal #18 and is copyright 2000 The Perl Journal. It appearscourtesy of Jon Orwant and The Perl Journal. This document may bedistributed under the same terms as Perl itself. 

Trees

-- Sean M. Burke

``AaaAAAaauugh! Watch out for that tree!''
  --- George of the Jungle theme

Perl's facility with references, combined with its automatic management ofmemory allocation, makes it straightforward to write programs that store datain structures of arbitrary form and complexity.

But I've noticed that many programmers, especially those who started outwith more restrictive languages, seem at home with complex but uniformdata structures --- N-dimensional arrays, or more struct-like things likehashes-of-arrays(-of-hashes(-of-hashes), etc.) --- but they're often uneasywith building more freeform, less tabular structures, liketree-shaped data structures.

But trees are easy to build and manage in Perl, as I'll demonstrateby showing off how the HTML::Element class manages elements in an HTMLdocument tree, and by walking you through a from-scratch implementationof game trees. But first we need to nail down what we mean by a ``tree''. 

Socratic Dialogues: What is a Tree?

My first brush with tree-shaped structures was in linguistics classes,where tree diagrams are used to describe the syntax underlying naturallanguage sentences. After learning my way around those trees, Istarted to wonder --- are what I'm used to calling ``trees'' the same as whatprogrammers call ``trees''? So I asked lots of helpful and patientprogrammers how they would define a tree. Many replied with aanswer in jargon that they could not really explain (understandable,since explaining things, especially defining things, is harderthan people think):

-- So what is a ``tree'', a tree-shaped data structure?

-- A tree is a special case of an acyclic directed graph!

-- What's a ``graph''?

-- Um... lines... and... you draw it... with... arcs! nodes! um...

The most helpful were folks who couldn't explain directly, but withwhom I could get into a rather Socratic dialog (where I asked thehalf-dim half-earnest questions), often with much doodling ofillustrations...

Question: so what's a tree?

Answer: A tree is a collection of nodes that are linked together in a,well, tree-like way! Like this [drawing on a napkin]:

     A    / \   B   C     / | \    D  E  F

Q: So what do these letters represent?

A: Each is a different node, a bunch of data. Maybe C is abunch of data that stores a number, maybe a hash table, maybe nothingat all besides the fact that it links to D, E, and F (which are othernodes).

Q: So what're the lines between the nodes?

A: Links. Also called ``arcs''. They just symbolize the fact that eachnode holds a list of nodes it links to.

Q: So what if I draw nodes and links, like this...

     B -- E    / \  / \   A   C        \ /     E

Is that still a tree?

A: No, not at all. There's a lot of un-treelike things about that.First off, E has a link coming off of it going into nowhere. You can't havea link to nothing --- you can only link to another node. Second off, Idon't know what that sideways link between B and E means...

Q: Okay, let's work our way up from something simpler. Is this a tree...?

    A

A: Yes, I suppose. It's a tree of just one node.

Q: And how about...

   A      B

A: No, you can't just have nodes floating there, unattached.

Q: Okay, I'll link A and B. How's this?

   A   |   B

A: Yup, that's a tree. There's a node A, and a node B, and they're linked.

Q: How is that tree any different from this one...?

   B   |   A

A: Well, in both cases A and B are linked. But it's in a differentdirection.

Q: Direction? What does the direction mean?

A: Well, it depends what the tree represents. If it represents acategorization, like this:

          citrus       /    |    \   orange  lemon  kumquat ...

then you mean to say that oranges, lemons, kumquats, etc., are a kind ofcitrus. But if you drew it upside down, you'd be saying, falsely, thatcitrus is a kind of kumquat, a kind of lemon, and a kind of orange.If the tree represented cause-and-effect (or at least what situationscould follow others), or represented what's a part of what, youwouldn't want to get those backwards, either. So with the nodes youdraw together on paper, one has to be over the other, so you can tell whichway the relationship in the tree works.

Q: So are these two trees the same?

     A          A    / \        / \   B   C      B   \                   C

A: Yes, although by convention we often try to line up things in thesame generation, like it is in the diagram on the left.

Q: ``generation''? This is a family tree?

A: No, not unless it's a family tree for just yeast cells or somethingelse that reproduces asexually.But for sake of having lots of terms to use, we just pretend that linksin the tree represent the ``is a child of'' relationship, instead of ``is akind of'' or ``is a part of'', or ``could result from'', or whatever the realrelationship is. So we get to borrow a lot of kinship words fordescribing trees --- B and C are ``children'' (or ``daughters'') of A; A isthe ``parent'' (or ``mother'') of B and C. Node C is a ``sibling'' (or``sister'') of node C; and so on, with terms like ``descendants'' (a node'schildren, children's children, etc.), and ``generation'' (all thenodes at the same ``level'' in the tree, i.e., are either allgrandchildren of the top node, or all great-grand-children, etc.), and``lineage'' or ``ancestors'' (parents, and parent's parents, etc., all theway to the topmost node).

So then we get to express rules in terms like "A node cannot have morethan one parent", which means that this is not a valid tree:

    A   / \  B   C   \ /    E

And: "A node can't be its own parent", which excludes this looped-upconnection:

    /\   A  |    \/

Or, put more generally: "A node can't be its own ancestor", whichexcludes the above loop, as well as the one here:

      /\     Z  |    /   |   A    |  / \   | B   C  |      \/

That tree is excluded because A is a child of Z, and Z is a child of C,and C is a child of A, which means A is its own great-grandparent. Sothis whole network can't be a tree, because it breaks the sort ofmeta-rule: once any node in the supposed tree breaks the rules fortrees, you don't have a tree anymore.

Q: Okay, now, are these two trees the same?

     A         A   / | \     / | \  B  C  D   D  C  B

A: It depends whether you're basing your concept of trees on each nodehaving a set (unordered list) of children, or an (ordered) list ofchildren. It's a question of whether ordering is important for whatyou're doing. With my diagram of citrus types, ordering isn'timportant, so these tree diagrams express the same thing:

          citrus       /    |    \   orange  lemon  kumquat           citrus       /     |    \   kumquat  orange  lemon

because it doesn't make sense to say that oranges are ``before'' or``after'' kumquats in the whole botanical scheme of things. (Unless, ofcourse, you are using ordering to mean something, like a degree ofgenetic similarity.)

But consider a tree that's a diagram of what steps are comprised in anactivity, to some degree of specificity:

           make tea         /    |     \   pour     infuse   serve hot water    / \in cup/pot  /     \           add     let           tea     sit          leaves

This means that making tea consists of putting hot water in a cup orput, infusing it (which itself consists of adding tea leaves and lettingit sit), then serving it --- in that order. If you serve an emptydry pot (sipping from empty cups, etc.), let it sit, add tea leaves,and pour in hot water, then what you're doing is performance art, nottea preparation:

        performance            art        /    |     \   serve   infuse    pour            / \       hot water          /     \      in cup/pot         let     add         sit     tea                leaves

Except for my having renamed the root, this tree is the same asthe making-tea tree as far as what's under what, but it differsin order, and what the tree means makes the order important.

Q: Wait --- ``root''? What's a root?

A: Besides kinship terms like ``mother'' and ``daughter'', the jargon fortree parts also has terms from real-life tree parts: the part thateverything else grows from is called the root; and nodes that don'thave nodes attached to them (i.e., childless nodes) are called``leaves''.

Q: But you've been drawing all your trees with the root at the top andleaves at the bottom.

A: Yes, but for some reason, that's the way everyone seems to think oftrees. They can draw trees as above; or they can draw them sort ofsideways with indenting representing what nodes are children of what:

  * make tea     * pour hot water in cup/pot     * infuse        * add tea leaves        * let sit     * serve

...but folks almost never seem to draw trees with the root at thebottom. So imagine it's based on spider plant in a hanging pot.Unfortunately, spider plants aren't botanically trees, they'replants; but ``spider plant diagram'' is rather a mouthful, so let's justcall them trees. 

Trees Defined Formally

In time, I digested all these assorted facts about programmers' ideas oftrees (which turned out to be just a more general case of linguisticideas of trees) into a single rule:

* A node is an item that contains (``is over'', ``is parent of'', etc.)zero or more other nodes.

From this you can build up formal definitions for useful terms, like so:

* A node's descendants are defined as all its children, and alltheir children, and so on. Or, stated recursively: a node'sdescendants are all its children, and all its children's descendants.(And if it has no children, it has no descendants.)

* A node's ancestors consist of its parent, and its parent'sparent, etc, up to the root. Or, recursively: a node's ancestorsconsist of its parent and its parent's ancestors. (If it has no parent,it has no ancestors.)

* A tree is a root node and all the root's descendants.

And you can add a proviso or two to clarify exactly what I impute to theword ``other'' in ``other nodes'':

* A node cannot contain itself, or contain any node that contains it,etc. Looking at it the other way: a node cannot be its own parent orancestor.

* A node can be root (i.e., no other node contains it) or can becontained by only one parent; no node can be the child of two or moreparents.

Add to this the idea that children are sometimes ordered, and sometimesnot, and that's about all you need to know about defining what a treeis. From there it's a matter of using them. 

Markup Language Trees: HTML-Tree

While not all markup languages are inherently tree-like, thebest-known family of markup languages, HTML, SGML, and XML, are aboutas tree-like as you can get. In these languages, a document consistsof elements and character data in a tree structure wherethere is one root element, and elements can contain either otherelements, or character data.

Footnote:For sake of simplicity, I'm glossing overcomments (<!-- ... -->), processing instructions (<?xmlversion='1.0'>), and declarations (<!ELEMENT ...>, <!DOCTYPE ...>).And I'm not bothering to distinguish entity references(&lt;, &#64;) or CDATA sections (<![CDATA[ ...]]>) from normal text.

For example, consider this HTML document:

  <html lang="en-US">    <head>      <title>        Blank Document!      </title>    </head>    <body bgcolor="#d010ff">      I've got      <em>        something to saaaaay      </em>      !    </body>  </html>

I've indented this to point out what nodes (elements or text items) arechildren of what, with each node on a line of its own.

The HTML::TreeBuilder module (in the CPAN distribution HTML-Tree)does the work of taking HTML source andbuilding in memory the tree that the document source represents.

Footnote: it requires the HTML::Parser module, which tokenizes thesource --- i.e., identifies each tag, bit of text, comment, etc.

The trees structures that it builds represent bits of text withnormal Perl scalar string values; but elements are represented withobjects --- that is, chunks of data that belong to aclass (in this case, HTML::Element), a class that provides methods(routines) for accessing the pieces of data in each element, andotherwise doing things with elements. (See my article in TPJ#17 for aquick explanation of objects, the POD document "perltoot" for a longerexplanation, or Damian Conway's excellent book Object-Oriented Perlfor the full story.)

Each HTML::Element object contains a number of pieces of data:

* its element name (``html'', ``h1'', etc., accessed as $element->tag)

* a list of elements (or text segments) that it contains, if any(accessed as $element->content_list or $element->content, depending onwhether you want a list, or an arrayref)

* what element, if any, contains it (accessed as $element->parent)

* and any SGML attributes that the element has,such as "lang="en-US"", "align="center"", etc. (accessed as$element->attr('lang'), $element->attr('center'), etc.)

So, for example, when HTML::TreeBuilder builds the tree for the aboveHTML document source, the object for the ``body'' element has these pieces ofdata:

 * element name: "body" * nodes it contains:    the string "I've got "    the object for the "em" element    the string "!" * its parent:    the object for the "html" element * bgcolor: "#d010ff"

Now, once you have this tree of objects, almost anything you'd want todo with it starts with searching the tree for some bit of informationin some element.

Accessing a piece of information in, say, a hash of hashes of hashes,is straightforward:

  $password{'sean'}{'sburke1'}{'hpux'}

because you know that all data points in that structure are accessiblewith that syntax, but with just different keys. Now, the ``em'' elementin the above HTML tree does happen to be accessibleas the root's child #1's child #1:

  $root->content->[1]->content->[1]

But with trees, you typically don't know the exact location (viaindexes) of the data you're looking for. Instead, finding what you wantwill typically involve searching through the tree, seeing if every node isthe kind you want. Searching the whole tree is simple enough --- look ata given node, and if it's not what you want, look at its children, andso on. HTML-Tree provides several methods that do this for you, such as"find_by_tag_name", which returns the elements (or the first element, ifcalled in scalar context) under a given node (typically the root) whosetag name is whatever you specify.

For example, that ``em'' node can be found as:

  my $that_em = $root->find_by_tag_name('em');

or as:

  @ems = $root->find_by_tag_name('em');   # will only have one element for this particular tree

Now, given an HTML document of whatever structure and complexity, if youwanted to do something like change every

<em>stuff</em>

to

<em class=``funky''><b>[-</b>stuff<b>-]</b></em>

the first step is to frame this operation in terms of what you're doingto the tree. You're changing this:

      em       |      ...

to this:

      em    /  |  \     b  ...   b   |        |  "[-"     "-]"

In other words, you're finding all elements whose tag name is ``em'', setting its class attribute to ``funky'', and adding one child to the startof its content list --- a new ``b'' elementwhose content is the text string ``[-'' --- and one to the end of itscontent list --- a new ``b'' element whose content is the text string ``-]''.

Once you've got it in these terms, it's just a matter of running to theHTML::Element documentation, and coding this up with calls to theappropriate methods, like so:

  use HTML::Element 1.53;  use HTML::TreeBuilder 2.96;  # Build the tree by parsing the document  my $root = HTML::TreeBuilder->new;  $root->parse_file('whatever.html'); # source file    # Now make new nodes where needed  foreach my $em ($root->find_by_tag_name('em')) {    $em->attr('class', 'funky'); # Set that attribute        # Make the two new B nodes    my $new1 = HTML::Element->new('b');    my $new2 = HTML::Element->new('b');    # Give them content (they have none at first)    $new1->push_content('[-');    $new2->push_content('-]');        # And put 'em in place!    $em->unshift_content($new1);    $em->push_content($new2);  }  print   "<!-- Looky see what I did! -->\n",   $root->as_HTML(), "\n";

The class HTML::Element provides just about every method I can image youneeding, for manipulating trees made of HTML::Element objects. (Andwhat it doesn't directly provide, it will give you the components to buildit with.) 

Building Your Own Trees

Theoretically, any tree is pretty much like any other tree, so you coulduse HTML::Element for anything you'd ever want to do with tree-arrangedobjects. However, as its name implies, HTML::Element is basicallyfor HTML elements; it has lots of features that make sense only forHTML elements (like the idea that every element must have a tag-name).And it lacks some features that might be useful for general applications--- such as any sort of checking to make sure that you're not trying toarrange objects in a non-treelike way. For a general-purpose tree classthat does have such features, you can use Tree::DAG_Node, also availablefrom CPAN.

However, if your task is simple enough, you might find it overkill tobother using Tree::DAG_Node. And, in any case, I find that the bestway to learn how something works is to implement it (or something likeit, but simpler) yourself. So I'll here discuss how you'd implement a treestructure, without using any of the existing classes for tree nodes. 

Implementation: Game Trees for Alak

Suppose that the task at hand is to write a program that can playagainst a human opponent at a strategic board game (as opposed to aboard game where there's an element of chance). For most such games, a``game tree'' is an essential part of the program (as I will argue,below), and this will be our test case for implementing a treestructure from scratch.

For sake of simplicity, our game is not chess or backgammon, but insteada much simpler game called Alak. Alak was invented by the mathematicianA. K. Dewdney, and described in his 1984 book Planiverse. The rulesof Alak are simple:

Footnote: Actually, I'm describing only myinterpretation of the rules Dewdney describes in Planiverse. Manyother interpretations are possible.

* Alak is a two-player game played on a one-dimensional board witheleven slots on it. Each slot can hold at most one piece at a time.There's two kinds of pieces, which I represent here as ``x'' and ``o'' ---x's belong to one player (called X), o's to the other (called O).

* The initial configuration of the board is:

   xxxx___oooo

For sake of the article, the slots are numbered from 1 (on the left) to11 (on the right), and X always has the first move.

* The players take turns moving. At each turn, each player can moveonly one piece, once. (This unlike checkers, where you move one pieceper move but get to keep moving it if you jump an your opponent'spiece.) A player cannot pass up on his turn. A player can move any oneof his pieces to the next unoccupied slot to its right or left, whichmay involve jumping over occupied slots. A player cannot move a pieceoff the side of the board.

* If a move creates a pattern where the opponent's pieces aresurrounded, on both sides, by two pieces of the mover's color (with nointervening unoccupied blank slot), then those surrounded pieces areremoved from the board.

* The goal of the game is to remove all of your opponent's pieces, atwhich point the game ends. Removing all-but-one ends the game aswell, since the opponent can't surround you with one piece, and so willalways lose within a few moves anyway.

Consider, then, this rather short game where X starts:

  xxxx___oooo    ^         Move 1: X moves from 3 (shown with caret) to 5               (Note that any of X's pieces could move, but               that the only place they could move to is 5.)  xx_xx__oooo          ^   Move 2: O moves from 9 to 7.  xx_xx_oo_oo     ^        Move 3: X moves from 4 to 6.  xx__xxoo_oo           ^  Move 4: O (stupidly) moves from 10 to 9.  xx__xxooo_o      ^       Move 5: X moves from 5 to 10, making the board              "xx___xoooxo".  The three o's that X just              surrounded are removed.   xx___x___xo              O has only one piece, so has lost.

Now, move 4 could have gone quite the other way:

  xx__xxoo_oo              Move 4: O moves from 8 to 4, making the board               "xx_oxxo__oo".  The surrounded x's are removed.  xx_o__o__oo  ^           Move 5: X moves from 1 to 2.  _xxo__o__oo        ^     Move 6: O moves from 7 to 6.  _xxo_o___oo   ^          Move 7: X moves from 2 to 5, removing the o at 4.  __x_xo___oo              ...and so on.

To teach a computer program to play Alak (as player X, say), it needs tobe able to look at the configuration of the board, figure out what movesit can make, and weigh the benefit or costs, immediate or eventual, ofthose moves.

So consider the board from just before move 3, and figure all the possiblemoves X could make. X has pieces in slots 1, 2, 4, and 5. The leftmosttwo x's (at 1 and 2) are up against the end of the board, so theycan move only right. The other two x's (at 4 and 5) can move eitherright or left:

  Starting board: xx_xx_oo_oo   moving 1 to 3 gives _xxxx_oo_oo   moving 2 to 3 gives x_xxx_oo_oo   moving 4 to 3 gives xxx_x_oo_oo   moving 5 to 3 gives xxxx__oo_oo   moving 4 to 6 gives xx__xxoo_oo   moving 5 to 6 gives xx_x_xoo_oo

For the computer to decide which of these is the best move to make, itneeds to quantify the benefit of these moves as a number --- call thatthe ``payoff''. The payoff of a move can be figured as just the numberof x pieces removed by the most recent move, minus the number of opieces removed by the most recent move. (It so happens that the rulesof the game mean that no move can delete both o's and x's, but theformula still applies.) Since none of these moves removed any pieces,all these moves have the same immediate payoff: 0.

Now, we could race ahead and write an Alak-playing program that coulduse the immediate payoff to decide which is the best move to make.And when there's more than one best move (as here, where all the movesare equally good), it could choose randomly between the goodalternatives. This strategy is simple to implement; but it makes for avery dumb program. Consider what O's response to each of the potentialmoves (above) could be. Nothing immediately suggests itself for thefirst four possibilities (X having moved something to position 3), buteither of the last two (illustrated below) are pretty perilous,because in either case O has the obvious option (which he would befoolish to pass up) of removing x's from the board:

   xx_xx_oo_oo      ^        X moves 4 to 6.   xx__xxoo_oo          ^    O moves 8 to 4, giving "xx_oxxo__oo".  The two               surrounded x's are removed.   xx_o__o__oo

or

   xx_xx_oo_oo       ^       X moves 5 to 6.   xx_x_xoo_oo          ^    O moves 8 to 5, giving "xx_xoxo__oo".  The one               surrounded x is removed.   xx_xo_o__oo

Both contingencies are quite bad for X --- but this is not capturedby the fact that they start out with X thinking his move will beharmless, having a payoff of zero.

So what's needed is for X to think more than one step ahead --- toconsider not merely what it can do in this move, and what the payoffis, but to consider what O might do in response, and thepayoff of those potential moves, and so on with X's possible responsesto those cases could be. All these possibilities form a game tree --- atree where each node is a board, and its children are successors ofthat node --- i.e., the boards that could result from every movepossible, given the parent's board.

But how to represent the tree, and how to represent the nodes?

Well, consider that a node holds several pieces of data:

1) the configuration of the board, which, being nice and simple andone-dimensional, can be stored as just a string, like ``xx_xx_oo_oo''.

2) whose turn it is, X or O. (Or: who moved last, from which we canfigure whose turn it is).

3) the successors (child nodes).

4) the immediate payoff of having moved to this board position from itspredecessor (parent node).

5) and what move gets us from our predecessor node to here. (Granted,knowing the board configuration before and after the move, it's easy tofigure out the move; but it's easier still to store it as one isfiguring out a node's successors.)

6) whatever else we might want to add later.

These could be stored equally well in an array or in a hash, but it's myexperience that hashes are best for cases where you have more than justtwo or three bits of data, or especially when you might need to add newbits of data. Moreover, hash key names are mnemonic ---$node->{'last_move_payoff'} is plain as day, whereas it's not so easy having toremember with an array that $node->[3] is where you decided to keep thepayoff.

Footnote:Of course, there are ways around that problem: just swear you'll neveruse a real numeric index to access data in the array, and instead useconstants with mnemonic names:

  use strict;  use constant idx_PAYOFF => 3;  ...  $n->[idx_PAYOFF]

Or use a pseudohash. But I prefer to keep it simple, and use a hash.

These are, incidentally, the same arguments thatpeople weigh when trying to decide whether their object-orientedmodules should be based on blessed hashes, blessed arrays, or what.Essentially the only difference here is that we're not blessing ournodes or talking in terms of classes and methods.

[end footnote]

So, we might as well represent nodes like so:

  $node = { # hashref     'board'          => ...board string, e.g., "xx_x_xoo_oo"          'last_move_payoff' => ...payoff of the move                            that got us here.                                 'last_move_from' =>  ...the start...     'last_move_to'   =>  ...and end point of the move                              that got us here.  E.g., 5 and 6,                              representing a move from 5 to 6.     'whose_turn'     => ...whose move it then becomes.                           just an 'x' or 'o'.                                   'successors' => ...the successors  };

Note that we could have a field called something like 'last_move_who' todenote who last moved, but since turns in Alak always alternate (andno-one can pass), storing whose move it is now and who last moved isredundant --- if X last moved, it's O turn now, and vice versa.I chose to have a 'whose_turn' field instead of a 'last_move_who', butit doesn't really matter. Either way, we'll end up inferring one fromthe other at several points in the program.

When we want to store the successors of a node, should we use an arrayor a hash? On the one hand, the successors to $node aren't essentiallyordered, so there's no reason to use an array per se; on the other hand,if we used a hash, with successor nodes as values, we don't haveanything particularly meaningful to use as keys. (And we can't use thesuccessors themselves as keys, since the nodes are referred to byhash references, and you can't use a reference as a hash key.) Given noparticularly compelling reason to do otherwise, I choose to just use anarray to store all a node's successors, although the order is neveractually used for anything:

  $node = {    ...    'successors' => [ ...nodes... ],    ...  };

In any case, now that we've settled on what should be in a node, let's make a little sample tree out of a few nodes and see what we cando with it:

  # Board just before move 3 in above game  my $n0 = {    'board' => 'xx_xx_oo_oo',    'last_move_payoff' => 0,    'last_move_from' =>  9,    'last_move_to'   =>  7,    'whose_turn' => 'x',    'successors' => [],  };  # And, for now, just two of the successors:    # X moves 4 to 6, giving xx__xxoo_oo  my $n1 = {    'board' => 'xx__xxoo_oo',    'last_move_payoff' => 0,    'last_move_from' =>  4,    'last_move_to'   =>  6,    'whose_turn' => 'o',    'successors' => [],  };  # or X moves 5 to 6, giving xx_x_xoo_oo  my $n2 = {    'board' => 'xx_x_xoo_oo',    'last_move_payoff' => 0,    'last_move_from' =>  5,    'last_move_to'   =>  6,    'whose_turn' => 'o',    'successors' => [],  };  # Now connect them...  push @{$n0->{'successors'}}, $n1, $n2;
 

Digression: Links to Parents

In comparing what we store in an Alak game tree node to whatHTML::Element stores in HTML element nodes, you'll note one bigdifference: every HTML::Element node contains a link to its parent,whereas we don't have our Alak nodes keeping a link to theirs.

The reason this can be an important difference is because it can affecthow Perl knows when you're not using pieces of memory anymore.Consider the tree we just built, above:

      node 0     /      \  node 1    node 2

There's two ways Perl knows you're using a piece of memory:1) it's memory that belongs directly to a variable (i.e., is necessaryto hold that variable's value, or values in the case of a hash orarray), or 2) it's a piece of memory that something holds a referenceto. In the above code, Perl knows that the hash for node 0 (for board``xx_xx_oo_oo'') is in use because something (namely, the variable$n0) holds a reference to it. Now, even if you followed the abovecode with this:

  $n1 = $n2 = 'whatever';

to make your variables $n1 and $n2 stop holding references tothe hashes for the two successors of node 0, Perl would still know thatthose hashes are still in use, because node 0's successors array holdsa reference to those hashes. And Perl knows that node 0 is still inuse because something still holds a reference to it. Now, if youadded:

  my $root = $n0;

This would change nothing --- there's just be two things holding areference to the node 0 hash, which in turn holds a reference to thenode 1 and node 2 hashes. And if you then added:

  $n0 = 'stuff';

still nothing would change, because something ($root) still holds areference to the node 0 hash. But once nothing holds a reference tothe node 0 hash, Perl will know it can destroy that hash (and reclaimthe memory for later use, say), and once it does that, nothing will holda reference to the node 1 or the node 2 hashes, and those will bedestroyed too.

But consider if the node 1 and node 2 hashes each had an attribute``parent'' (or ``predecessor'') that held a reference to node 0. If yourprogram stopped holding a reference to the node 0 hash, Perl couldnot then say that nothing holds a reference to node 0 --- becausenode 1 and node 2 still do. So, the memory for nodes 0, 1, and 2 wouldnever get reclaimed (until your program ended, at which point Perldestroys everything). If your program grew and discarded lots ofnodes in the game tree, but didn't let Perl know it could reclaim theirmemory, your program could grow to use immense amounts of memory ---never a nice thing to have happen. There's three ways around this:

1) When you're finished with a node, delete the reference each of itschildren have to it (in this case, deleting $n1->{'parent'}, say).When you're finished with a whole tree, just go through the whole treeerasing links that children have to their children.

2) Reconsider whether you really need to have each node hold a referenceto its parent. Just not having those links will avoid the wholeproblem.

3) use the WeakRef module with Perl 5.6 or later. This allows you to``weaken'' some references (like the references that node 1 and 2 couldhold to their parent) so that they don't count when Perl goes askingwhether anything holds a reference to a given piece of memory. Thiswonderful new module eliminates the headaches that can often crop upwith either of the two previous methods.

It so happens that our Alak program is simple enough that we don't needfor our nodes to have links to their parents, so the second solution isfine. But in a more advanced program, the first or third solutionsmight be unavoidable. 

Recursively Printing the Tree

I don't like working blind --- if I have any kind of a complex datastructure in memory for a program I'm working on, the first thing I dois write something that can dump that structure to the screen so I canmake sure that what I think is in memory really is what's inmemory. Now, I could just use the ``x'' pretty-printer command in Perl'sinteractive debugger, or I could have the program use the"Data::Dumper" module. But in this case, I think the output from thoseis rather too verbose. Once we have trees with dozens of nodes in them,we'll really want a dump of the tree to be as concise as possible,hopefully just one line per node. What I'd like is something that canprint $n0 and its successors (see above) as something like:

  xx_xx_oo_oo  (O moved 9 to 7, 0 payoff)    xx__xxoo_oo  (X moved 4 to 6, 0 payoff)    xx_x_xoo_oo  (X moved 5 to 6, 0 payoff)

A subroutine to print a line for a given node, and then do that again foreach successor, would look something like:

  sub dump_tree {    my $n = $_[0]; # "n" is for node    print      ...something expressing $n'n content...    foreach my $s (@{$n->{'successors'}}) {      # "s for successor      dump($s);    }  }

And we could just start that out with a call to "dump_tree($n0)".

Since this routine...

Footnote:I first wrote this routine starting out with ``sub dump {''. But whenI tried actually calling "dump($n0)", Perl would dump core! Imaginemy shock when I discovered that this is absolutely to be expected ---Perl provides a built-in function called "dump", the purpose of whichis to, yes, make Perl dump core. Calling our routine ``dump_tree''instead of ``dump'' neatly avoids that problem.

...does its work (dumping the subtree at and under thegiven node) by calling itself, it's recursive. However, there's aspecial term for this kind of recursion across a tree: traversal. Totraverse a tree means to do something to a node, and to traverse itschildren. There's two prototypical ways to do this, depending on whathappens when:

  traversing X in pre-order:    * do something to X    * then traverse X's children  traversing X in post-order:    * traverse X's children    * then do something to X

Dumping the tree to the screen the way we want it happens to be a matterof pre-order traversal, since the thing we do (print a description ofthe node) happens before we recurse into the successors.

When we try writing the "print" statement for our above "dump_tree",we can get something like:

  sub dump_tree {    my $n = $_[0];    # "xx_xx_oo_oo  (O moved 9 to 7, 0 payoff)"    print      $n->{'board'}, "  (",      ($n->{'whose_turn'} eq 'o' ? 'X' : 'O'),      # Infer who last moved from whose turn it is now.      " moved ", $n->{'last_move_from'},      " to ",    $n->{'last_move_to'},      ", ",      $n->{'last_move_payoff'},      " payoff)\n",    ;    foreach my $s (@{$n->{'successors'}}) {      dump_tree($s);    }  }

If we run this on $n0 from above, we get this:

  xx_xx_oo_oo  (O moved 9 to 7, 0 payoff)  xx__xxoo_oo  (X moved 4 to 6, 0 payoff)  xx_x_xoo_oo  (X moved 5 to 6, 0 payoff)

Each line on its own is fine, but we forget to allow for indenting, andwithout that we can't tell what's a child of what. (Imagine if thefirst successor had successors of its own --- you wouldn't be able totell if it were a child, or a sibling.) To get indenting, we'll needto have the instances of the "dump_tree" routine know how far down inthe tree they're being called, by passing a depth parameter betweenthem:

  sub dump_tree {    my $n = $_[0];    my $depth = $_[1];    $depth = 0 unless defined $depth;    print      "  " x $depth,      ...stuff...    foreach my $s (@{$n->{'successors'}}) {      dump_tree($s, $depth + 1);    }  }

When we call "dump_tree($n0)", $depth (from $_[1]) is undefined, sogets set to 0, which translates into an indenting of no spaces. But when "dump_tree" invokes itself on $n0's children, those instances see$depth + 1 as their $_[1], giving appropriate indenting.

Footnote:Passing values around between different invocations of a recursiveroutine, as shown, is a decent way to share the data. Another wayto share the data is by keeping it in a global variable, like $Depth,initially set to 0. Each time "dump_tree" is about to recurse, it must"++$Depth", and when it's back, it must "--$Depth".

Or, if the reader is familiar with closures, consider this approach:

  sub dump_tree {    # A wrapper around calls to a recursive closure:    my $start_node = $_[0];    my $depth = 0;     # to be shared across calls to $recursor.    my $recursor;    $recursor = sub {      my $n = $_[0];      print "  " x $depth,        ...stuff...      ++$depth;      foreach my $s (@{$n->{'successors'}}) {        $recursor->($s);      }      --$depth;    }    $recursor->($start_node); # start recursing    undef $recursor;  }

The reader with an advanced understanding of Perl's reference-count-basedgarbage collection is invited to consider why it is currently necessaryto undef $recursor (or otherwise change its value) after all recursionis done.

The reader whose mind is perverse in other ways is invited to considerhow (or when!) passing a depth parameter around is unnecessary becauseof information that Perl's caller(N) function reports!

[end footnote]

 

Growing the Tree

Our "dump_tree" routine works fine for the sample tree we've got, sonow we should get the program working on making its own trees, startingfrom a given board.

In "Games::Alak" (the CPAN-released version of Alak that usesessentially the same code that we're currently discussing thetree-related parts of), there is a routine called "figure_successors"that, given one childless node, will figure out all its possiblesuccessors. That is, it looks at the current board, looks at every piecebelonging to the player whose turn it is, and considers the effect ofmoving each piece every possible way --- notably, it figures out theimmediate payoff, and if that move would end the game, it notes that bysetting an ``endgame'' entry in that node's hash. (That way, we know thatthat's a node that can't have successors.)

In the code for "Games::Alak", "figure_successors" does all these things,in a rather straightforward way. I won't walk you through the detailsof the "figure_successors" code I've written, since the code hasnothing much to do with trees, and is all just implementation of the Alakrules for what can move where, with what result. Especially interestedreaders can puzzle over that part of code in the source listing in thearchive from CPAN, but others can just assume that it works as describedabove.

But consider that "figure_successors", regardless of its innerworkings, does not grow the tree; it only makes one set of successorsfor one node at a time. It has to be up to a different routine to call"figure_successors", and to keep applying it as needed, in order tomake a nice big tree that our game-playing program can base itsdecisions on.

Now, we could do this by just starting from one node, applying"figure_successors" to it, then applying "figure_successors" on allthe resulting children, and so on:

  sub grow {  # Just a first attempt at this!    my $n = $_[0];    figure_successors($n);     unless      @{$n->{'successors'}}        # already has successors.      or $n->{'endgame'}        # can't have successors.    }    foreach my $s (@{$n->{'successors'}}) {      grow($s); # recurse    }  }

If you have a game tree for tic-tac-toe, and you grow it withoutlimitation (as above), you will soon enough have a fully ``solved'' tree,where every node that can have successors does, and all the leavesof the tree are all the possible endgames (where, in each case, theboard is filled). But a game of Alak is different from tic-tac-toe,because it can, in theory, go on forever. For example, the followingsequence of moves is quite possible:

  xxxx___oooo  xxx_x__oooo  xxx_x_o_ooo  xxxx__o_ooo (x moved back)  xxxx___oooo (o moved back)  ...repeat forever...

So if you tried using our above attempt at a "grow" routine, Perl wouldhappily start trying to construct an infinitely deep tree, containingan infinite number of nodes, consuming an infinite amount of memory, andrequiring an infinite amount of time. As the old saying goes: ``Youcan't have everything --- where would you put it?'' So we have to placelimits on how much we'll grow the tree.

There's more than one way to do this:

1. We could grow the tree until we hit some limit on the number ofnodes we'll allow in the tree.

2. We could grow the tree until we hit some limit on the amount of timewe're willing to spend.

3. Or we could grow the tree until it is fully fleshed out to a certaindepth.

Since we already know to track depth (as we did in writing "dump_tree"),we'll do it that way, the third way. The implementation for that thirdapproach is also pretty straightforward:

  $Max_depth = 3;  sub grow {    my $n = $_[0];    my $depth = $_[1] || 0;    figure_successors($n)     unless      $depth >= $Max_depth      or @{$n->{'successors'}}      or $n->{'endgame'}    }    foreach my $s (@{$n->{'successors'}}) {      grow($s, $depth + 1);    }    # If we're at $Max_depth, then figure_successors    #  didn't get called, so there's no successors    #  to recurse under -- that's what stops recursion.  }

If we start from a single node (whether it's a node for the starting board``xxxx___oooo'', or for whatever board the computer is faced with), set$Max_depth to 4, and apply "grow" to it, it will grow the tree toinclude several hundred nodes.

Footnote:If at each move there are four pieces that can move, and they can eachmove right or left, the ``branching factor'' of the tree is eight, givinga tree with 1 (depth 0) + 8 (depth 1) + 8 ** 2 + 8 ** 3 + 8 ** 4 =4681 nodes in it. But, in practice, not all pieces can move in bothdirections (none of the x pieces in ``xxxx___oooo'' can move left, forexample), and there may be fewer than four pieces, if some were lost.For example, there are 801 nodes in a tree of depth four startingfrom ``xxxx___oooo'', suggesting an average branching factor of aboutfive (801 ** (1/4) is about 5.3), not eight.

What we need to derive from that tree is the information about whatare the best moves for X. The simplest way to consider the payoff ofdifferent successors is to just average them --- but what we averageisn't always their immediate payoffs (because that'd leave us usingonly one generation of information), but the average payoff of theirsuccessors, if any. We can formalize this as:

  To figure a node's average payoff:    If the node has successors:      Figure each successor's average payoff.      My average payoff is the average of theirs.    Otherwise:      My average payoff is my immediate payoff.

Since this involves recursing into the successors before doinganything with the current node, this will traverse the treein post-order.

We could work that up as a routine of its own, and apply that to thetree after we've applied "grow" to it. But since we'd nevergrow the tree without also figuring the average benefit, we might as wellmake that figuring part of the "grow" routine itself:

  $Max_depth = 3;  sub grow {    my $n = $_[0];    my $depth = $_[1] || 0;    figure_successors($n);     unless      $depth >= $Max_depth      or @{$n->{'successors'}}      or $n->{'endgame'}    }    if(@{$n->{'successors'}}) {      my $a_payoff_sum = 0;      foreach my $s (@{$n->{'successors'}}) {        grow($s, $depth + 1);  # RECURSE        $a_payoff_sum += $s->{'average_payoff'};      }      $n->{'average_payoff'}       = $a_payoff_sum / @{$n->{'successors'}};    } else {      $n->{'average_payoff'}       = $n->{'last_move_payoff'};    }  }

So, by time "grow" has applied to a node (wherever in the tree it is),it will have figured successors if possible (which, in turn, sets"last_move_payoff" for each node it creates), and will have set"average_benefit".

Beyond this, all that's needed is to start the board out with a rootnote of ``xxxx___oooo'', and have the computer (X) take turns with theuser (O) until someone wins. Whenever it's O's turn, "Games::Alak"presents a prompt to the user, letting him know the state of the currentboard, and asking what move he selects. When it's X's turn, thecomputer grows the game tree as necessary (using just the "grow"routine from above), then selects the move with the highest averagepayoff (or one of the highest, in case of a tie).

In either case, ``selecting'' a move means just setting that move's nodeas the new root of the program's game tree. Its sibling nodes and theirdescendants (the boards that didn't get selected) and its parent nodewill be erased from memory, since they will no longer be in use (as Perlcan tell by the fact that nothing holds references to them anymore).

The interface code in "Games::Alak" (the code that prompts the user forhis move) actually supports quite a few options besides just moving ---including dumping the game tree to a specified depth (using a slightlyfancier version of "dump_tree", above), resetting the game, changing$Max_depth in the middle of the game, and quitting the game. Like"figure_successors", it's a bit too long to print here, but interestedusers are welcome to peruse (and freely modify) the code, as well as toenjoy just playing the game.

Now, in practice, there's more to game trees than this: for games with alarger branching factor than Alak has (which is most!), game trees ofdepth four or larger would contain too many nodes to be manageable, mostof those nodes being strategically quite uninteresting for eitherplayer; dealing with game trees specifically is therefore a matter ofrecognizing uninteresting contingencies and not bothering to grow thetree under them.

Footnote:For example, to choose a straightforward case: if O has a choice betweenmoves that put him in immediate danger of X winning and moves thatdon't, then O won't ever choose the dangerous moves (and if he does, thecomputer will know enough to end the game), so there's no point ingrowing the tree any further beneath those nodes.

But this sample implementation should illustrate the basics ofhow to build and manipulate a simple tree structure in memory.And once you've understood the basics of tree storage here, you shouldbe ready to better understand the complexities and peculiarities of other systems for creating, accessing, and changing trees, includingTree::DAG_Node, HTML::Element, XML::DOM, or related formalismslike XPath and XSL.

[end body of article] 

[Author Credit]

Sean M. Burke ("sburkeAATTcpan.org") is a tree-dwelling hominid. 

References

Dewdney, A[lexander] K[eewatin]. 1984. Planiverse: Computer Contactwith a Two-Dimensional World. Poseidon Press, New York.

Knuth, Donald Ervin. 1997. Art of Computer Programming, Volume 1,Third Edition: Fundamental Algorithms. Addison-Wesley, Reading, MA.

Wirth, Niklaus. 1976. Algorithms + Data Structures = ProgramsPrentice-Hall, Englewood Cliffs, NJ.

Worth, Stan and Allman Sheldon. Circa 1967. George of the Jungletheme. [music by Jay Ward.]

Wirth's classic, currently and lamentably out of print, has a goodsection on trees. I find it clearer than Knuth's (if not quite asencyclopedic), probably because Wirth's example code is in ablock-structured high-level language (basically Pascal), insteadof in assembler (MIX). I believe the book was re-issued in the1980s under the titles Algorithms and Data Structures and, in aGerman edition, Algorithmen und Datenstrukturen. Cheap copiesof these editions should be available through used book servicessuch as "abebooks.com".

Worth's classic, however, is available on thesoundtrack to the 1997 George of the Jungle movie, asperformed by The Presidents of the United States of America. 

BACK

Return to the HTML::Tree docs.


 

Index

NAME
SYNOPSIS
DESCRIPTION
Trees
Socratic Dialogues: What is a Tree?
Trees Defined Formally
Markup Language Trees: HTML-Tree
Building Your Own Trees
Implementation: Game Trees for Alak
Digression: Links to Parents
Recursively Printing the Tree
Growing the Tree
[Author Credit]
References
BACK

This document was created byman2html,using the manual pages.