1HTML::Tree::AboutTrees(U3s)er Contributed Perl DocumentatHiToMnL::Tree::AboutTrees(3)
2
6 HTML::Tree::AboutTrees -- article on tree-shaped data structures in
7 Perl
8
10 # This an article, not a module.
11
13 The following article by Sean M. Burke first appeared in The Perl Jour‐
14 nal #18 and is copyright 2000 The Perl Journal. It appears courtesy of
15 Jon Orwant and The Perl Journal. This document may be distributed
16 under the same terms as Perl itself.
17
19 -- Sean M. Burke
20 "AaaAAAaauugh! Watch out for that tree!"
22 -- George of the Jungle theme
23 Perl's facility with references, combined with its automatic management
25 of memory allocation, makes it straightforward to write programs that
26 store data in structures of arbitrary form and complexity.
27 But I've noticed that many programmers, especially those who started
29 out with more restrictive languages, seem at home with complex but uni‐
30 form data structures -- N-dimensional arrays, or more struct-like
31 things like hashes-of-arrays(-of-hashes(-of-hashes), etc.) -- but
32 they're often uneasy with buliding more freeform, less tabular struc‐
33 tures, like tree-shaped data structures.
34 But trees are easy to build and manage in Perl, as I'll demonstrate by
36 showing off how the HTML::Element class manages elements in an HTML
37 document tree, and by walking you through a from-scratch implementation
38 of game trees. But first we need to nail down what we mean by a
39 "tree".
40 Socratic Dialogues: "What is a Tree?"
42 My first brush with tree-shaped structures was in linguistics classes,
44 where tree diagrams are used to describe the syntax underlying natural
45 language sentences. After learning my way around those trees, I
46 started to wonder -- are what I'm used to calling "trees" the same as
47 what programmers call "trees"? So I asked lots of helpful and patient
48 programmers how they would define a tree. Many replied with a answer
49 in jargon that they could not really explain (understandable, since
50 explaining things, especially defining things, is harder than people
51 think):
52 -- So what is a "tree", a tree-shaped data structure?
54 -- A tree is a special case of an acyclic directed graph!
56 -- What's a "graph"?
58 -- Um... lines... and... you draw it... with... arcs! nodes! um...
60 The most helpful were folks who couldn't explain directly, but with
62 whom I could get into a rather Socratic dialog (where I asked the half-
63 dim half-earnest questions), often with much doodling of illustra‐
64 tions...
65 Question: so what's a tree?
67 Answer: A tree is a collection of nodes that are linked together in a,
69 well, tree-like way! Like this [drawing on a napkin]:
70 A
72 / \
73 B C
74 / ⎪ \
75 D E F
76 Q: So what do these letters represent?
78 A: Each is a different node, a bunch of data. Maybe C is a bunch of
80 data that stores a number, maybe a hash table, maybe nothing at all
81 besides the fact that it links to D, E, and F (which are other nodes).
82 Q: So what're the lines between the nodes?
84 A: Links. Also called "arcs". They just symbolize the fact that each
86 node holds a list of nodes it links to.
87 Q: So what if I draw nodes and links, like this...
89 B -- E
91 / \ / \
92 A C
93 \ /
94 E
95 Is that still a tree?
97 A: No, not at all. There's a lot of un-treelike things about that.
99 First off, E has a link coming off of it going into nowhere. You can't
100 have a link to nothing -- you can only link to another node. Second
101 off, I don't know what that sideways link between B and E means...
102 Q: Okay, let's work our way up from something simpler. Is this a
104 tree...?
105 A
107 A: Yes, I suppose. It's a tree of just one node.
109 Q: And how about...
111 A
113 B
115 A: No, you can't just have nodes floating there, unattached.
117 Q: Okay, I'll link A and B. How's this?
119 A
121 ⎪
122 B
123 A: Yup, that's a tree. There's a node A, and a node B, and they're
125 linked.
126 Q: How is that tree any different from this one...?
128 B
130 ⎪
131 A
132 A: Well, in both cases A and B are linked. But it's in a different
134 direction.
135 Q: Direction? What does the direction mean?
137 A: Well, it depends what the tree represents. If it represents a cate‐
139 gorization, like this:
140 citrus
142 / ⎪ \
143 orange lemon kumquat ...
144 then you mean to say that oranges, lemons, kumquats, etc., are a kind
146 of citrus. But if you drew it upside down, you'd be saying, falsely,
147 that citrus is a kind of kumquat, a kind of lemon, and a kind of
148 orange. If the tree represented cause-and-effect (or at least what
149 situations could follow others), or represented what's a part of what,
150 you wouldn't want to get those backwards, either. So with the nodes
151 you draw together on paper, one has to be over the other, so you can
152 tell which way the relationship in the tree works.
153 Q: So are these two trees the same?
155 A A
157 / \ / \
158 B C B \
159 C
160 A: Yes, although by convention we often try to line up things in the
162 same generation, like it is in the diagram on the left.
163 Q: "generation"? This is a family tree?
165 A: No, not unless it's a family tree for just yeast cells or something
167 else that reproduces asexually. But for sake of having lots of terms
168 to use, we just pretend that links in the tree represent the "is a
169 child of" relationship, instead of "is a kind of" or "is a part of", or
170 "could result from", or whatever the real relationship is. So we get
171 to borrow a lot of kinship words for describing trees -- B and C are
172 "children" (or "daughters") of A; A is the "parent" (or "mother") of B
173 and C. Node C is a "sibling" (or "sister") of node C; and so on, with
174 terms like "descedants" (a node's children, children's children, etc.),
175 and "generation" (all the nodes at the same "level" in the tree, i.e.,
176 are either all grandchildren of the top node, or all great-grand-chil‐
177 dren, etc.), and "lineage" or "ancestors" (parents, and parent's par‐
178 ents, etc., all the way to the topmost node).
179 So then we get to express rules in terms like "A node cannot have more
181 than one parent", which means that this is not a valid tree:
182 A
184 / \
185 B C
186 \ /
187 E
188 And: "A node can't be its own parent", which excludes this looped-up
190 connection:
191 /\
193 A ⎪
194 \/
195 Or, put more generally: "A node can't be its own ancestor", which
197 excludes the above loop, as well as the one here:
198 /\
200 Z ⎪
201 / ⎪
202 A ⎪
203 / \ ⎪
204 B C ⎪
205 \/
206 That tree is excluded because A is a child of Z, and Z is a child of C,
208 and C is a child of A, which means A is its own great-grandparent. So
209 this whole network can't be a tree, because it breaks the sort of
210 meta-rule: once any node in the supposed tree breaks the rules for
211 trees, you don't have a tree anymore.
212 Q: Okay, now, are these two trees the same?
214 A A
216 / ⎪ \ / ⎪ \
217 B C D D C B
218 A: It depends whether you're basing your concept of trees on each node
220 having a set (unordered list) of children, or an (ordered) list of
221 children. It's a question of whether ordering is important for what
222 you're doing. With my diagram of citrus types, ordering isn't impor‐
223 tant, so these tree diagrams express the same thing:
224 citrus
226 / ⎪ \
227 orange lemon kumquat
228 citrus
230 / ⎪ \
231 kumquat orange lemon
232 because it doesn't make sense to say that oranges are "before" or
234 "after" kumquats in the whole botanical scheme of things. (Unless, of
235 course, you are using ordering to mean something, like a degree of
236 genetic similarity.)
237 But consider a tree that's a diagram of what steps are comprised in an
239 activity, to some degree of specificity:
240 make tea
242 / ⎪ \
243 pour infuse serve
244 hot water / \
245 in cup/pot / \
246 add let
247 tea sit
248 leaves
249 This means that making tea consists of putting hot water in a cup or
251 put, infusing it (which itself consists of adding tea leaves and let‐
252 ting it sit), then serving it -- in that order. If you serve an empty
253 dry pot (sipping from empty cups, etc.), let it sit, add tea leaves,
254 and pour in hot water, then what you're doing is performance art, not
255 tea preparation:
256 perfomance
258 art
259 / ⎪ \
260 serve infuse pour
261 / \ hot water
262 / \ in cup/pot
263 let add
264 sit tea
265 leaves
266 Except for my having renamed the root, this tree is the same as the
268 making-tea tree as far as what's under what, but it differs in order,
269 and what the tree means makes the order important.
270 Q: Wait -- "root"? What's a root?
272 A: Besides kinship terms like "mother" and "daugher", the jargon for
274 tree parts also has terms from real-life tree parts: the part that
275 everything else grows from is called the root; and nodes that don't
276 have nodes attached to them (i.e., childless nodes) are called
277 "leaves".
278 Q: But you've been drawing all your trees with the root at the top and
280 leaves at the bottom.
281 A: Yes, but for some reason, that's the way everyone seems to think of
283 trees. They can draw trees as above; or they can draw them sort of
284 sideways with indenting representing what nodes are children of what:
285 * make tea
287 * pour hot water in cup/pot
288 * infuse
289 * add tea leaves
290 * let sit
291 * serve
292 ...but folks almost never seem to draw trees with the root at the bot‐
294 tom. So imagine it's based on spider plant in a hanging pot. Unfortu‐
295 nately, spider plants aren't botanically trees, they're plants; but
296 "spider plant diagram" is rather a mouthful, so let's just call them
297 trees.
298 Trees Defined Formally
300 In time, I digested all these assorted facts about programmers' ideas
302 of trees (which turned out to be just a more general case of linguistic
303 ideas of trees) into a single rule:
304 * A node is an item that contains ("is over", "is parent of", etc.)
306 zero or more other nodes.
307 From this you can build up formal definitions for useful terms, like
309 so:
310 * A node's descendants are defined as all its children, and all their
312 children, and so on. Or, stated recursively: a node's descendants are
313 all its children, and all its children's descendants. (And if it has
314 no children, it has no descendants.)
315 * A node's ancestors consist of its parent, and its parent's parent,
317 etc, up to the root. Or, recursively: a node's ancestors consist of
318 its parent and its parent's ancestors. (If it has no parent, it has no
319 ancestors.)
320 * A tree is a root node and all the root's descendants.
322 And you can add a proviso or two to clarify exactly what I impute to
324 the word "other" in "other nodes":
325 * A node cannot contain itself, or contain any node that contains it,
327 etc. Looking at it the other way: a node cannot be its own parent or
328 ancestor.
329 * A node can be root (i.e., no other node contains it) or can be con‐
331 tained by only one parent; no node can be the child of two or more par‐
332 ents.
333 Add to this the idea that children are sometimes ordered, and sometimes
335 not, and that's about all you need to know about defining what a tree
336 is. From there it's a matter of using them.
337 Markup Language Trees: HTML-Tree
339 While not all markup languages are inherently tree-like, the best-known
341 family of markup languages, HTML, SGML, and XML, are about as tree-like
342 as you can get. In these languages, a document consists of elements
343 and character data in a tree structure where there is one root element,
344 and elements can contain either other elements, or character data.
345 Footnote: For sake of simplicity, I'm glossing over comments (<!--
347 ... -->), processing instructions (<?xml version='1.0'>), and dec‐
348 larations (<!ELEMENT ...>, <!DOCTYPE ...>). And I'm not bothering
349 to distinguish entity references (<, @) or CDATA sections
350 (<![CDATA[ ...]]>) from normal text.
351 For example, consider this HTML document:
353 <html lang="en-US">
355 <head>
356 <title>
357 Blank Document!
358 </title>
359 </head>
360 <body bgcolor="#d010ff">
361 I've got
362 <em>
363 something to saaaaay
364 </em>
365 !
366 </body>
367 </html>
368 I've indented this to point out what nodes (elements or text items) are
370 children of what, with each node on a line of its own.
371 The HTML::TreeBuilder module (in the CPAN distribution HTML-Tree) does
373 the work of taking HTML source and building in memory the tree that the
374 document source represents.
375 Footnote: it requires the HTML::Parser module, which tokenizes the
377 source -- i.e., identifies each tag, bit of text, comment, etc.
378 The trees structures that it builds represent bits of text with normal
380 Perl scalar string values; but elements are represented with objects --
381 that is, chunks of data that belong to a class (in this case,
382 HTML::Element), a class that provides methods (routines) for accessing
383 the pieces of data in each element, and otherwise doing things with
384 elements. (See my article in TPJ#17 for a quick explanation of
385 objects, the POD document "perltoot" for a longer explanation, or
386 Damian Conway's excellent book Object-Oriented Perl for the full
387 story.)
388 Each HTML::Element object contains a number of pieces of data:
390 * its element name ("html", "h1", etc., accessed as $element->tag)
392 * a list of elements (or text segments) that it contains, if any
394 (accessed as $element->content_list or $element->content, depending on
395 whether you want a list, or an arrayref)
396 * what element, if any, contains it (accessed as $element->parent)
398 * and any SGML attributes that the element has, such as "lang="en-US"",
400 "align="center"", etc. (accessed as $element->attr('lang'), $ele‐
401 ment->attr('center'), etc.)
402 So, for example, when HTML::TreeBuilder builds the tree for the above
404 HTML document source, the object for the "body" element has these
405 pieces of data:
406 * element name: "body"
408 * nodes it contains:
409 the string "I've got "
410 the object for the "em" element
411 the string "!"
412 * its parent:
413 the object for the "html" element
414 * bgcolor: "#d010ff"
415 Now, once you have this tree of objects, almost anything you'd want to
417 do with it starts with searching the tree for some bit of information
418 in some element.
419 Accessing a piece of information in, say, a hash of hashes of hashes,
421 is straightforward:
422 $password{'sean'}{'sburke1'}{'hpux'}
424 because you know that all data points in that structure are accessible
426 with that syntax, but with just different keys. Now, the "em" element
427 in the above HTML tree does happen to be accessible as the root's child
428 #1's child #1:
429 $root->content->[1]->content->[1]
431 But with trees, you typically don't know the exact location (via
433 indexes) of the data you're looking for. Instead, finding what you
434 want will typically involve searching through the tree, seeing if every
435 node is the kind you want. Searching the whole tree is simple enough
436 -- look at a given node, and if it's not what you want, look at its
437 children, and so on. HTML-Tree provides several methods that do this
438 for you, such as "find_by_tag_name", which returns the elements (or the
439 first element, if called in scalar context) under a given node (typi‐
440 cally the root) whose tag name is whatever you specify.
441 For example, that "em" node can be found as:
443 my $that_em = $root->find_by_tag_name('em');
445 or as:
447 @ems = $root->find_by_tag_name('em');
449 # will only have one element for this particular tree
450 Now, given an HTML document of whatever structure and complexity, if
452 you wanted to do something like change every
453 <em>stuff</em>
455 to
457 <em class="funky"> <b>[-</b> stuff <b>-]</b> </em>
459 the first step is to frame this operation in terms of what you're doing
461 to the tree. You're changing this:
462 em
464 ⎪
465 ...
466 to this:
468 em
470 / ⎪ \
471 b ... b
472 ⎪ ⎪
473 "[-" "-]"
474 In other words, you're finding all elements whose tag name is "em",
476 setting its class attribute to "funky", and adding one child to the
477 start of its content list -- a new "b" element whose content is the
478 text string "[-" -- and one to the end of its content list -- a new "b"
479 element whose content is the text string "-]".
480 Once you've got it in these terms, it's just a matter of running to the
482 HTML::Element documentation, and coding this up with calls to the
483 appropriate methods, like so:
484 use HTML::Element 1.53;
486 use HTML::TreeBuilder 2.96;
487 # Build the tree by parsing the document
488 my $root = HTML::TreeBuilder->new;
489 $root->parse_file('whatever.html'); # source file
490 # Now make new nodes where needed
492 foreach my $em ($root->find_by_tag_name('em')) {
493 $em->attr('class', 'funky'); # Set that attribute
494 # Make the two new B nodes
496 my $new1 = HTML::Element->new('b');
497 my $new2 = HTML::Element->new('b');
498 # Give them content (they have none at first)
499 $new1->push_content('[-');
500 $new2->push_content('-]');
501 # And put 'em in place!
503 $em->unshift_content($new1);
504 $em->push_content($new2);
505 }
506 print
507 "<!-- Looky see what I did! -->\n",
508 $root->as_HTML(), "\n";
509 The class HTML::Element provides just about every method I can image
511 you needing, for manipulating trees made of HTML::Element objects.
512 (And what it doesn't directly provide, it will give you the components
513 to build it with.)
514 Building Your Own Trees
516 Theoretically, any tree is pretty much like any other tree, so you
518 could use HTML::Element for anything you'd ever want to do with tree-
519 arranged objects. However, as its name implies, HTML::Element is basi‐
520 cally for HTML elements; it has lots of features that make sense only
521 for HTML elements (like the idea that every element must have a
522 tag-name). And it lacks some features that might be useful for general
523 applications -- such as any sort of checking to make sure that you're
524 not trying to arrange objects in a non-treelike way. For a general-
525 purpose tree class that does have such features, you can use
526 Tree::DAG_Node, also available from CPAN.
527 However, if your task is simple enough, you might find it overkill to
529 bother using Tree::DAG_Node. And, in any case, I find that the best
530 way to learn how something works is to implement it (or something like
531 it, but simpler) yourself. So I'll here discuss how you'd implement a
532 tree structure, without using any of the existing classes for tree
533 nodes.
534 Implementation: Game Trees for Alak
536 Suppose that the task at hand is to write a program that can play
538 against a human opponent at a strategic board game (as opposed to a
539 board game where there's an element of chance). For most such games, a
540 "game tree" is an essential part of the program (as I will argue,
541 below), and this will be our test case for implementing a tree struc‐
542 ture from stratch.
543 For sake of simplicity, our game is not chess or backgammon, but
545 instead a much simpler game called Alak. Alak was invented by the
546 mathematician A. K. Dewdney, and described in his 1984 book Plani‐
547 verse. The rules of Alak are simple:
548 Footnote: Actually, I'm describing only my interpetation of the
550 rules Dewdney describes in Planiverse. Many other interpretations
551 are possible.
552 * Alak is a two-player game played on a one-dimensional board with
554 eleven slots on it. Each slot can hold at most one piece at a time.
555 There's two kinds of pieces, which I represent here as "x" and "o" --
556 x's belong to one player (called X), o's to the other (called O).
557 * The initial configuration of the board is:
559 xxxx___oooo
561 For sake of the article, the slots are numbered from 1 (on the left) to
563 11 (on the right), and X always has the first move.
564 * The players take turns moving. At each turn, each player can move
566 only one piece, once. (This unlike checkers, where you move one piece
567 per move but get to keep moving it if you jump an your opponent's
568 piece.) A player cannot pass up on his turn. A player can move any one
569 of his pieces to the next unoccupied slot to its right or left, which
570 may involve jumping over occupied slots. A player cannot move a piece
571 off the side of the board.
572 * If a move creates a pattern where the opponent's pieces are sur‐
574 rounded, on both sides, by two pieces of the mover's color (with no
575 intervening unoccupied blank slot), then those surrounded pieces are
576 removed from the board.
577 * The goal of the game is to remove all of your opponent's pieces, at
579 which point the game ends. Removing all-but-one ends the game as well,
580 since the opponent can't surround you with one piece, and so will
581 always lose within a few moves anyway.
582 Consider, then, this rather short game where X starts:
584 xxxx___oooo
586 ^ Move 1: X moves from 3 (shown with caret) to 5
587 (Note that any of X's pieces could move, but
588 that the only place they could move to is 5.)
589 xx_xx__oooo
590 ^ Move 2: O moves from 9 to 7.
591 xx_xx_oo_oo
592 ^ Move 3: X moves from 4 to 6.
593 xx__xxoo_oo
594 ^ Move 4: O (stupidly) moves from 10 to 9.
595 xx__xxooo_o
596 ^ Move 5: X moves from 5 to 10, making the board
597 "xx___xoooxo". The three o's that X just
598 surrounded are removed.
599 xx___x___xo
600 O has only one piece, so has lost.
601 Now, move 4 could have gone quite the other way:
603 xx__xxoo_oo
605 Move 4: O moves from 8 to 4, making the board
606 "xx_oxxo__oo". The surrounded x's are removed.
607 xx_o__o__oo
608 ^ Move 5: X moves from 1 to 2.
609 _xxo__o__oo
610 ^ Move 6: O moves from 7 to 6.
611 _xxo_o___oo
612 ^ Move 7: X moves from 2 to 5, removing the o at 4.
613 __x_xo___oo
614 ...and so on.
615 To teach a computer program to play Alak (as player X, say), it needs
617 to be able to look at the configuration of the board, figure out what
618 moves it can make, and weigh the benefit or costs, immediate or even‐
619 tual, of those moves.
620 So consider the board from just before move 3, and figure all the pos‐
622 sible moves X could make. X has pieces in slots 1, 2, 4, and 5. The
623 leftmost two x's (at 1 and 2) are up against the end of the board, so
624 they can move only right. The other two x's (at 4 and 5) can move
625 either right or left:
626 Starting board: xx_xx_oo_oo
628 moving 1 to 3 gives _xxxx_oo_oo
629 moving 2 to 3 gives x_xxx_oo_oo
630 moving 4 to 3 gives xxx_x_oo_oo
631 moving 5 to 3 gives xxxx__oo_oo
632 moving 4 to 6 gives xx__xxoo_oo
633 moving 5 to 6 gives xx_x_xoo_oo
634 For the computer to decide which of these is the best move to make, it
636 needs to quantify the benefit of these moves as a number -- call that
637 the "payoff". The payoff of a move can be figured as just the number
638 of x pieces removed by the most recent move, minus the nubmer of o
639 pieces removed by the mots recent move. (It so happens that the rules
640 of the game mean that no move can delete both o's and x's, but the for‐
641 mula still applies.) Since none of these moves removed any pieces, all
642 these moves have the same immediate payoff: 0.
643 Now, we could race ahead and write an Alak-playing program that could
645 use the immediate payoff to decide which is the best move to make. And
646 when there's more than one best move (as here, where all the moves are
647 equally good), it could choose randomly between the good alternatives.
648 This strategy is simple to implement; but it makes for a very dumb pro‐
649 gram. Consider what O's response to each of the potential moves
650 (above) could be. Nothing immediately suggests itself for the first
651 four possibilities (X having moved something to position 3), but either
652 of the last two (illustrated below) are pretty perilous, because in
653 either case O has the obvious option (which he would be foolish to pass
654 up) of removing x's from the board:
655 xx_xx_oo_oo
657 ^ X moves 4 to 6.
658 xx__xxoo_oo
659 ^ O moves 8 to 4, giving "xx_oxxo__oo". The two
660 surrounded x's are removed.
661 xx_o__o__oo
662 or
664 xx_xx_oo_oo
666 ^ X moves 5 to 6.
667 xx_x_xoo_oo
668 ^ O moves 8 to 5, giving "xx_xoxo__oo". The one
669 surrounded x is removed.
670 xx_xo_o__oo
671 Both contingencies are quite bad for X -- but this is not captured by
673 the fact that they start out with X thinking his move will be harmless,
674 having a payoff of zero.
675 So what's needed is for X to think more than one step ahead -- to con‐
677 sider not merely what it can do in this move, and what the payoff is,
678 but to consider what O might do in response, and the payoff of those
679 potential moves, and so on with X's possible responses to those cases
680 could be. All these possibilities form a game tree -- a tree where
681 each node is a board, and its children are successors of that node --
682 i.e., the boards that could result from every move possible, given the
683 parent's board.
684 But how to represent the tree, and how to represent the nodes?
686 Well, consider that a node holds several pieces of data:
688 1) the configuration of the board, which, being nice and simple and
690 one-dimensional, can be stored as just a string, like "xx_xx_oo_oo".
691 2) whose turn it is, X or O. (Or: who moved last, from which we can
693 figure whose turn it is).
694 3) the successors (child nodes).
696 4) the immediate payoff of having moved to this board position from its
698 predecessor (parent node).
699 5) and what move gets us from our predecessor node to here. (Granted,
701 knowing the board configuration before and after the move, it's easy to
702 figure out the move; but it's easier still to store it as one is figur‐
703 ing out a node's successors.)
704 6) whatever else we might want to add later.
706 These could be stored equally well in an array or in a hash, but it's
708 my experience that hashes are best for cases where you have more than
709 just two or three bits of data, or especially when you might need to
710 add new bits of data. Moreover, hash key names are mnemonic --
711 $node->{'last_move_payoff'} is plain as day, whereas it's not so easy
712 having to remember with an array that $node->[3] is where you decided
713 to keep the payoff.
714 Footnote: Of course, there are ways around that problem: just swear
716 you'll never use a real numeric index to access data in the array,
717 and instead use constants with mnemonic names:
718 use strict;
720 use constant idx_PAYOFF => 3;
721 ...
722 $n->[idx_PAYOFF]
723 Or use a pseudohash. But I prefer to keep it simple, and use a
725 hash.
726 These are, incidentally, the same arguments that people weigh when
728 trying to decide whether their object-oriented modules should be
729 based on blessed hashes, blessed arrays, or what. Essentially the
730 only difference here is that we're not blessing our nodes or talk‐
731 ing in terms of classes and methods.
732 [end footnote]
734 So, we might as well represent nodes like so:
736 $node = { # hashref
738 'board' => ...board string, e.g., "xx_x_xoo_oo"
739 'last_move_payoff' => ...payoff of the move
741 that got us here.
742 'last_move_from' => ...the start...
744 'last_move_to' => ...and end point of the move
745 that got us here. E.g., 5 and 6,
746 representing a move from 5 to 6.
747 'whose_turn' => ...whose move it then becomes.
749 just an 'x' or 'o'.
750 'successors' => ...the successors
752 };
753 Note that we could have a field called something like 'last_move_who'
755 to denote who last moved, but since turns in Alak always alternate (and
756 no-one can pass), storing whose move it is now and who last moved is
757 redundant -- if X last moved, it's O turn now, and vice versa. I chose
758 to have a 'whose_turn' field instead of a 'last_move_who', but it
759 doesn't really matter. Either way, we'll end up inferring one from the
760 other at several points in the program.
761 When we want to store the successors of a node, should we use an array
763 or a hash? On the one hand, the successors to $node aren't essentially
764 ordered, so there's no reason to use an array per se; on the other
765 hand, if we used a hash, with successor nodes as values, we don't have
766 anything particularly meaningful to use as keys. (And we can't use the
767 successors themselves as keys, since the nodes are referred to by hash
768 references, and you can't use a reference as a hash key.) Given no
769 particularly compelling reason to do otherwise, I choose to just use an
770 array to store all a node's successors, although the order is never
771 actually used for anything:
772 $node = {
774 ...
775 'successors' => [ ...nodes... ],
776 ...
777 };
778 In any case, now that we've settled on what should be in a node, let's
780 make a little sample tree out of a few nodes and see what we can do
781 with it:
782 # Board just before move 3 in above game
784 my $n0 = {
785 'board' => 'xx_xx_oo_oo',
786 'last_move_payoff' => 0,
787 'last_move_from' => 9,
788 'last_move_to' => 7,
789 'whose_turn' => 'x',
790 'successors' => [],
791 };
792 # And, for now, just two of the successors:
794 # X moves 4 to 6, giving xx__xxoo_oo
796 my $n1 = {
797 'board' => 'xx__xxoo_oo',
798 'last_move_payoff' => 0,
799 'last_move_from' => 4,
800 'last_move_to' => 6,
801 'whose_turn' => 'o',
802 'successors' => [],
803 };
804 # or X moves 5 to 6, giving xx_x_xoo_oo
806 my $n2 = {
807 'board' => 'xx_x_xoo_oo',
808 'last_move_payoff' => 0,
809 'last_move_from' => 5,
810 'last_move_to' => 6,
811 'whose_turn' => 'o',
812 'successors' => [],
813 };
814 # Now connect them...
816 push @{$n0->{'successors'}}, $n1, $n2;
817 Digression: Links to Parents
819 In comparing what we store in an Alak game tree node to what HTML::Ele‐
821 ment stores in HTML element nodes, you'll note one big difference:
822 every HTML::Element node contains a link to its parent, whereas we
823 don't have our Alak nodes keeping a link to theirs.
824 The reason this can be an important difference is because it can affect
826 how Perl knows when you're not using pieces of memory anymore. Con‐
827 sider the tree we just built, above:
828 node 0
830 / \
831 node 1 node 2
832 There's two ways Perl knows you're using a piece of memory: 1) it's
834 memory that belongs directly to a variable (i.e., is necessary to hold
835 that variable's value, or values in the case of a hash or array), or 2)
836 it's a piece of memory that something holds a reference to. In the
837 above code, Perl knows that the hash for node 0 (for board
838 "xx_xx_oo_oo") is in use because something (namely, the variable $n0)
839 holds a reference to it. Now, even if you followed the above code with
840 this:
841 $n1 = $n2 = 'whatever';
843 to make your variables $n1 and $n2 stop holding references to the
845 hashes for the two successors of node 0, Perl would still know that
846 those hashes are still in use, because node 0's successors array holds
847 a reference to those hashes. And Perl knows that node 0 is still in
848 use because something still holds a reference to it. Now, if you
849 added:
850 my $root = $n0;
852 This would change nothing -- there's just be two things holding a ref‐
854 erence to the node 0 hash, which in turn holds a reference to the node
855 1 and node 2 hashes. And if you then added:
856 $n0 = 'stuff';
858 still nothing would change, because something ($root) still holds a
860 reference to the node 0 hash. But once nothing holds a reference to
861 the node 0 hash, Perl will know it can destroy that hash (and reclaim
862 the memory for later use, say), and once it does that, nothing will
863 hold a reference to the node 1 or the node 2 hashes, and those will be
864 destroyed too.
865 But consider if the node 1 and node 2 hashes each had an attribute
867 "parent" (or "predecessor") that held a reference to node 0. If your
868 program stopped holding a reference to the node 0 hash, Perl could not
869 then say that nothing holds a reference to node 0 -- because node 1 and
870 node 2 still do. So, the memory for nodes 0, 1, and 2 would never get
871 reclaimed (until your program ended, at which point Perl destroys
872 everything). If your program grew and discarded lots of nodes in the
873 game tree, but didn't let Perl know it could reclaim their memory, your
874 program could grow to use immense amounts of memory -- never a nice
875 thing to have happen. There's three ways around this:
876 1) When you're finished with a node, delete the reference each of its
878 children have to it (in this case, deleting $n1->{'parent'}, say).
879 When you're finished with a whole tree, just go through the whole tree
880 erasing links that children have to their children.
881 2) Reconsider whether you really need to have each node hold a refer‐
883 ence to its parent. Just not having those links will avoid the whole
884 problem.
885 3) use the WeakRef module with Perl 5.6 or later. This allows you to
887 "weaken" some references (like the references that node 1 and 2 could
888 hold to their parent) so that they don't count when Perl goes asking
889 whether anything holds a reference to a given piece of memory. This
890 wonderful new module eliminates the headaches that can often crop up
891 with either of the two previous methods.
892 It so happens that our Alak program is simple enough that we don't need
894 for our nodes to have links to their parents, so the second solution is
895 fine. But in a more advanced program, the first or third solutions
896 might be unavoidable.
897 Recursively Printing the Tree
899 I don't like working blind -- if I have any kind of a complex data
901 structure in memory for a program I'm working on, the first thing I do
902 is write something that can dump that structure to the screen so I can
903 make sure that what I think is in memory really is what's in memory.
904 Now, I could just use the "x" pretty-printer command in Perl's interac‐
905 tive debugger, or I could have the program use the "Data::Dumper" mod‐
906 ule. But in this case, I think the output from those is rather too
907 verbose. Once we have trees with dozens of nodes in them, we'll really
908 want a dump of the tree to be as concise as possible, hopefully just
909 one line per node. What I'd like is something that can print $n0 and
910 its successors (see above) as something like:
911 xx_xx_oo_oo (O moved 9 to 7, 0 payoff)
913 xx__xxoo_oo (X moved 4 to 6, 0 payoff)
914 xx_x_xoo_oo (X moved 5 to 6, 0 payoff)
915 A subroutine to print a line for a given node, and then do that again
917 for each successor, would look something like:
918 sub dump_tree {
920 my $n = $_[0]; # "n" is for node
921 print
922 ...something expressing $n'n content...
923 foreach my $s (@{$n->{'successors'}}) {
924 # "s for successor
925 dump($s);
926 }
927 }
928 And we could just start that out with a call to "dump_tree($n0)".
930 Since this routine...
932 Footnote: I first wrote this routine starting out with "sub dump
934 {". But when I tried actually calling "dump($n0)", Perl would dump
935 core! Imagine my shock when I discovered that this is absolutely
936 to be expected -- Perl provides a built-in function called "dump",
937 the purpose of which is to, yes, make Perl dump core. Calling our
938 routine "dump_tree" instead of "dump" neatly avoids that problem.
939 ...does its work (dumping the subtree at and under the given node) by
941 calling itself, it's recursive. However, there's a special term for
942 this kind of recursion across a tree: traversal. To traverse a tree
943 means to do something to a node, and to traverse its children. There's
944 two prototypical ways to do this, depending on what happens when:
945 traversing X in pre-order:
947 * do something to X
948 * then traverse X's children
949 traversing X in post-order:
951 * traverse X's children
952 * then do something to X
953 Dumping the tree to the screen the way we want it happens to be a mat‐
955 ter of pre-order traversal, since the thing we do (print a description
956 of the node) happens before we recurse into the successors.
957 When we try writing the "print" statement for our above "dump_tree", we
959 can get something like:
960 sub dump_tree {
962 my $n = $_[0];
963 # "xx_xx_oo_oo (O moved 9 to 7, 0 payoff)"
965 print
966 $n->{'board'}, " (",
967 ($n->{'whose_turn'} eq 'o' ? 'X' : 'O'),
968 # Infer who last moved from whose turn it is now.
969 " moved ", $n->{'last_move_from'},
970 " to ", $n->{'last_move_to'},
971 ", ", $n->{'last_move_payoff'},
972 " payoff)\n",
973 ;
974 foreach my $s (@{$n->{'successors'}}) {
976 dump_tree($s);
977 }
978 }
979 If we run this on $n0 from above, we get this:
981 xx_xx_oo_oo (O moved 9 to 7, 0 payoff)
983 xx__xxoo_oo (X moved 4 to 6, 0 payoff)
984 xx_x_xoo_oo (X moved 5 to 6, 0 payoff)
985 Each line on its own is fine, but we forget to allow for indenting, and
987 without that we can't tell what's a child of what. (Imagine if the
988 first successor had successors of its own -- you wouldn't be able to
989 tell if it were a child, or a sibling.) To get indenting, we'll need
990 to have the instances of the "dump_tree" routine know how far down in
991 the tree they're being called, by passing a depth parameter between
992 them:
993 sub dump_tree {
995 my $n = $_[0];
996 my $depth = $_[1];
997 $depth = 0 unless defined $depth;
998 print
999 " " x $depth,
1000 ...stuff...
1001 foreach my $s (@{$n->{'successors'}}) {
1002 dump_tree($s, $depth + 1);
1003 }
1004 }
1005 When we call "dump_tree($n0)", $depth (from $_[1]) is undefined, so
1007 gets set to 0, which translates into an indenting of no spaces. But
1008 when "dump_tree" invokes itself on $n0's children, those instances see
1009 $depth + 1 as their $_[1], giving appropriate indenting.
1010 Footnote: Passing values around between different invocations of a
1012 recursive routine, as shown, is a decent way to share the data.
1013 Another way to share the data is by keeping it in a global vari‐
1014 able, like $Depth, initially set to 0. Each time "dump_tree" is
1015 about to recurse, it must "++$Depth", and when it's back, it must
1016 "--$Depth".
1017 Or, if the reader is familiar with closures, consider this
1019 approach:
1020 sub dump_tree {
1022 # A wrapper around calls to a recursive closure:
1023 my $start_node = $_[0];
1024 my $depth = 0;
1025 # to be shared across calls to $recursor.
1026 my $recursor;
1027 $recursor = sub {
1028 my $n = $_[0];
1029 print " " x $depth,
1030 ...stuff...
1031 ++$depth;
1032 foreach my $s (@{$n->{'successors'}}) {
1033 $recursor->($s);
1034 }
1035 --$depth;
1036 }
1037 $recursor->($start_node); # start recursing
1038 undef $recursor;
1039 }
1040 The reader with an advanced understanding of Perl's reference-
1042 count-based garbage collection is invited to consider why it is
1043 currently necessary to undef $recursor (or otherwise change its
1044 value) after all recursion is done.
1045 The reader whose mind is perverse in other ways is invited to con‐
1047 sider how (or when!) passing a depth parameter around is unneces‐
1048 sary because of information that Perl's caller(N) function reports!
1049 [end footnote]
1051 Growing the Tree
1053 Our "dump_tree" routine works fine for the sample tree we've got, so
1055 now we should get the program working on making its own trees, starting
1056 from a given board.
1057 In "Games::Alak" (the CPAN-released version of Alak that uses essen‐
1059 tially the same code that we're currently discussing the tree-related
1060 parts of), there is a routine called "figure_successors" that, given
1061 one childless node, will figure out all its possible successors. That
1062 is, it looks at the current board, looks at every piece belonging to
1063 the player whose turn it is, and considers the effect of moving each
1064 piece every possible way -- notably, it figures out the immediate pay‐
1065 off, and if that move would end the game, it notes that by setting an
1066 "endgame" entry in that node's hash. (That way, we know that that's a
1067 node that can't have successors.)
1068 In the code for "Games::Alak", "figure_successors" does all these
1070 things, in a rather straightforward way. I won't walk you through the
1071 details of the "figure_successors" code I've written, since the code
1072 has nothing much to do with trees, and is all just implementation of
1073 the Alak rules for what can move where, with what result. Espicially
1074 interested readers can puzzle over that part of code in the source
1075 listing in the archive from CPAN, but others can just assume that it
1076 works as described above.
1077 But consider that "figure_successors", regardless of its inner work‐
1079 ings, does not grow the tree; it only makes one set of successors for
1080 one node at a time. It has to be up to a different routine to call
1081 "figure_successors", and to keep applying it as needed, in order to
1082 make a nice big tree that our game-playing program can base its deci‐
1083 sions on.
1084 Now, we could do this by just starting from one node, applying "fig‐
1086 ure_successors" to it, then applying "figure_successors" on all the
1087 resulting children, and so on:
1088 sub grow { # Just a first attempt at this!
1090 my $n = $_[0];
1091 figure_successors($n);
1092 unless
1093 @{$n->{'successors'}}
1094 # already has successors.
1095 or $n->{'endgame'}
1096 # can't have successors.
1097 }
1098 foreach my $s (@{$n->{'successors'}}) {
1099 grow($s); # recurse
1100 }
1101 }
1102 If you have a game tree for tic-tac-toe, and you grow it without limi‐
1104 tation (as above), you will soon enough have a fully "solved" tree,
1105 where every node that can have successors does, and all the leaves of
1106 the tree are all the possible endgames (where, in each case, the board
1107 is filled). But a game of Alak is different from tic-tac-toe, because
1108 it can, in theory, go on forever. For example, the following sequence
1109 of moves is quite possible:
1110 xxxx___oooo
1112 xxx_x__oooo
1113 xxx_x_o_ooo
1114 xxxx__o_ooo (x moved back)
1115 xxxx___oooo (o moved back)
1116 ...repeat forever...
1117 So if you tried using our above attempt at a "grow" routine, Perl would
1119 happily start trying to construct an infinitely deep tree, containing
1120 an infinite number of nodes, consuming an infinite amount of memory,
1121 and requiring an infinite amount of time. As the old saying goes: "You
1122 can't have everything -- where would you put it?" So we have to place
1123 limits on how much we'll grow the tree.
1124 There's more than one way to do this:
1126 1. We could grow the tree until we hit some limit on the number of
1128 nodes we'll allow in the tree.
1129 2. We could grow the tree until we hit some limit on the amount of time
1131 we're willing to spend.
1132 3. Or we could grow the tree until it is fully fleshed out to a certain
1134 depth.
1135 Since we already know to track depth (as we did in writing
1137 "dump_tree"), we'll do it that way, the third way. The implementation
1138 for that third approach is also pretty straightforward:
1139 $Max_depth = 3;
1141 sub grow {
1142 my $n = $_[0];
1143 my $depth = $_[1] ⎪⎪ 0;
1144 figure_successors($n)
1145 unless
1146 $depth >= $Max_depth
1147 or @{$n->{'successors'}}
1148 or $n->{'endgame'}
1149 }
1150 foreach my $s (@{$n->{'successors'}}) {
1151 grow($s, $depth + 1);
1152 }
1153 # If we're at $Max_depth, then figure_successors
1154 # didn't get called, so there's no successors
1155 # to recurse under -- that's what stops recursion.
1156 }
1157 If we start from a single node (whether it's a node for the starting
1159 board "xxxx___oooo", or for whatever board the computer is faced with),
1160 set $Max_depth to 4, and apply "grow" to it, it will grow the tree to
1161 include several hundred nodes.
1162 Footnote: If at each move there are four pieces that can move, and
1164 they can each move right or left, the "branching factor" of the
1165 tree is eight, giving a tree with 1 (depth 0) + 8 (depth 1) + 8 **
1166 2 + 8 ** 3 + 8 ** 4 = 4681 nodes in it. But, in practice, not all
1167 pieces can move in both directions (none of the x pieces in
1168 "xxxx___oooo" can move left, for example), and there may be fewer
1169 than four pieces, if some were lost. For example, there are 801
1170 nodes in a tree of depth four starting from "xxxx___oooo", suggest‐
1171 ing an average branching factor of about five (801 ** (1/4) is
1172 about 5.3), not eight.
1173 What we need to derive from that tree is the information about what are
1175 the best moves for X. The simplest way to consider the payoff of dif‐
1176 ferent successors is to just average them -- but what we average isn't
1177 always their immediate payoffs (because that'd leave us using only one
1178 generation of information), but the average payoff of their successors,
1179 if any. We can formalize this as:
1180 To figure a node's average payoff:
1182 If the node has successors:
1183 Figure each successor's average payoff.
1184 My average payoff is the average of theirs.
1185 Otherwise:
1186 My average payoff is my immediate payoff.
1187 Since this involves recursing into the successors before doing anything
1189 with the current node, this will traverse the tree in post-order.
1190 We could work that up as a routine of its own, and apply that to the
1192 tree after we've applied "grow" to it. But since we'd never grow the
1193 tree without also figuring the average benefit, we might as well make
1194 that figuring part of the "grow" routine itself:
1195 $Max_depth = 3;
1197 sub grow {
1198 my $n = $_[0];
1199 my $depth = $_[1] ⎪⎪ 0;
1200 figure_successors($n);
1201 unless
1202 $depth >= $Max_depth
1203 or @{$n->{'successors'}}
1204 or $n->{'endgame'}
1205 }
1206 if(@{$n->{'successors'}}) {
1208 my $a_payoff_sum = 0;
1209 foreach my $s (@{$n->{'successors'}}) {
1210 grow($s, $depth + 1); # RECURSE
1211 $a_payoff_sum += $s->{'average_payoff'};
1212 }
1213 $n->{'average_payoff'}
1214 = $a_payoff_sum / @{$n->{'successors'}};
1215 } else {
1216 $n->{'average_payoff'}
1217 = $n->{'last_move_payoff'};
1218 }
1219 }
1220 So, by time "grow" has applied to a node (wherever in the tree it is),
1222 it will have figured successors if possible (which, in turn, sets
1223 "last_move_payoff" for each node it creates), and will have set "aver‐
1224 age_benefit".
1225 Beyond this, all that's needed is to start the board out with a root
1227 note of "xxxx___oooo", and have the computer (X) take turns with the
1228 user (O) until someone wins. Whenever it's O's turn, "Games::Alak"
1229 presents a prompt to the user, letting him know the state of the cur‐
1230 rent board, and asking what move he selects. When it's X's turn, the
1231 computer grows the game tree as necessary (using just the "grow" rou‐
1232 tine from above), then selects the move with the highest average payoff
1233 (or one of the highest, in case of a tie).
1234 In either case, "selecting" a move means just setting that move's node
1236 as the new root of the program's game tree. Its sibling nodes and
1237 their descendants (the boards that didn't get selected) and its parent
1238 node will be erased from memory, since they will no longer be in use
1239 (as Perl can tell by the fact that nothing holds references to them
1240 anymore).
1241 The interface code in "Games::Alak" (the code that prompts the user for
1243 his move) actually supports quite a few options besides just moving --
1244 including dumping the game tree to a specified depth (using a slightly
1245 fancier version of "dump_tree", above), resetting the game, changing
1246 $Max_depth in the middle of the game, and quitting the game. Like
1247 "figure_successors", it's a bit too long to print here, but interested
1248 users are welcome to peruse (and freely modify) the code, as well as to
1249 enjoy just playing the game.
1250 Now, in practice, there's more to game trees than this: for games with
1252 a larger branching factor than Alak has (which is most!), game trees of
1253 depth four or larger would contain too many nodes to be manageable,
1254 most of those nodes being strategically quite uninteresting for either
1255 player; dealing with game trees specifically is therefore a matter of
1256 recognizing uninteresting contingencies and not bothering to grow the
1257 tree under them.
1258 Footnote: For example, to choose a straightforward case: if O has a
1260 choice between moves that put him in immediate danger of X winning
1261 and moves that don't, then O won't ever choose the dangerous moves
1262 (and if he does, the computer will know enough to end the game), so
1263 there's no point in growing the tree any further beneath those
1264 nodes.
1265 But this sample implementation should illustrate the basics of how to
1267 build and manipulate a simple tree structure in memory. And once
1268 you've understood the basics of tree storage here, you should be ready
1269 to better understand the complexities and peculiarities of other sys‐
1270 tems for creating, accessing, and changing trees, including
1271 Tree::DAG_Node, HTML::Element, XML::DOM, or related formalisms like
1272 XPath and XSL.
1273 [end body of article]
1275 [Author Credit]
1277 Sean M. Burke ("sburke@cpan.org") is a tree-dwelling hominid.
1279 References
1281 Dewdney, A[lexander] K[eewatin]. 1984. Planiverse: Computer Contact
1283 with a Two-Dimensional World. Poseidon Press, New York.
1284 Knuth, Donald Ervin. 1997. Art of Computer Programming, Volume 1,
1286 Third Edition: Fundamental Algorithms. Addison-Wesley, Reading, MA.
1287 Wirth, Niklaus. 1976. Algorithms + Data Structures = Programs Pren‐
1289 tice-Hall, Englewood Cliffs, NJ.
1290 Worth, Stan and Allman Sheldon. Circa 1967. George of the Jungle
1292 theme. [music by Jay Ward.]
1293 Wirth's classic, currently and lamentably out of print, has a good sec‐
1295 tion on trees. I find it clearer than Knuth's (if not quite as ency‐
1296 clopedic), probably because Wirth's example code is in a block-struc‐
1297 tured high-level language (basically Pascal), instead of in assembler
1298 (MIX). I believe the book was re-issued in the 1980s under the titles
1299 Algorithms and Data Structures and, in a German edition, Algorithmen
1300 und Datenstrukturen. Cheap copies of these editions should be avail‐
1301 able through used book services such as "abebooks.com".
1302 Worth's classic, however, is available on the soundtrack to the 1997
1304 George of the Jungle movie, as performed by The Presidents of the
1305 United States of America.
1306
1308 Return to the HTML::Tree docs.
1309perl v5.8.8 2006-08-04 HTML::Tree::AboutTrees(3)