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
14 Journal #18 and is copyright 2000 The Perl Journal. It appears courtesy
15 of 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
30 uniform 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 building more freeform, less tabular
33 structures, 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,
43 where tree diagrams are used to describe the syntax underlying natural
44 language sentences. After learning my way around those trees, I
45 started to wonder -- are what I'm used to calling "trees" the same as
46 what programmers call "trees"? So I asked lots of helpful and patient
47 programmers how they would define a tree. Many replied with a answer
48 in jargon that they could not really explain (understandable, since
49 explaining things, especially defining things, is harder than people
50 think):
51 -- So what is a "tree", a tree-shaped data structure?
53 -- A tree is a special case of an acyclic directed graph!
55 -- What's a "graph"?
57 -- Um... lines... and... you draw it... with... arcs! nodes! um...
59 The most helpful were folks who couldn't explain directly, but with
61 whom I could get into a rather Socratic dialog (where I asked the half-
62 dim half-earnest questions), often with much doodling of
63 illustrations...
64 Question: so what's a tree?
66 Answer: A tree is a collection of nodes that are linked together in a,
68 well, tree-like way! Like this [drawing on a napkin]:
69 A
71 / \
72 B C
73 / | \
74 D E F
75 Q: So what do these letters represent?
77 A: Each is a different node, a bunch of data. Maybe C is a bunch of
79 data that stores a number, maybe a hash table, maybe nothing at all
80 besides the fact that it links to D, E, and F (which are other nodes).
81 Q: So what're the lines between the nodes?
83 A: Links. Also called "arcs". They just symbolize the fact that each
85 node holds a list of nodes it links to.
86 Q: So what if I draw nodes and links, like this...
88 B -- E
90 / \ / \
91 A C
92 \ /
93 E
94 Is that still a tree?
96 A: No, not at all. There's a lot of un-treelike things about that.
98 First off, E has a link coming off of it going into nowhere. You can't
99 have a link to nothing -- you can only link to another node. Second
100 off, I don't know what that sideways link between B and E means...
101 Q: Okay, let's work our way up from something simpler. Is this a
103 tree...?
104 A
106 A: Yes, I suppose. It's a tree of just one node.
108 Q: And how about...
110 A
112 B
114 A: No, you can't just have nodes floating there, unattached.
116 Q: Okay, I'll link A and B. How's this?
118 A
120 |
121 B
122 A: Yup, that's a tree. There's a node A, and a node B, and they're
124 linked.
125 Q: How is that tree any different from this one...?
127 B
129 |
130 A
131 A: Well, in both cases A and B are linked. But it's in a different
133 direction.
134 Q: Direction? What does the direction mean?
136 A: Well, it depends what the tree represents. If it represents a
138 categorization, like this:
139 citrus
141 / | \
142 orange lemon kumquat ...
143 then you mean to say that oranges, lemons, kumquats, etc., are a kind
145 of citrus. But if you drew it upside down, you'd be saying, falsely,
146 that citrus is a kind of kumquat, a kind of lemon, and a kind of
147 orange. If the tree represented cause-and-effect (or at least what
148 situations could follow others), or represented what's a part of what,
149 you wouldn't want to get those backwards, either. So with the nodes
150 you draw together on paper, one has to be over the other, so you can
151 tell which way the relationship in the tree works.
152 Q: So are these two trees the same?
154 A A
156 / \ / \
157 B C B \
158 C
159 A: Yes, although by convention we often try to line up things in the
161 same generation, like it is in the diagram on the left.
162 Q: "generation"? This is a family tree?
164 A: No, not unless it's a family tree for just yeast cells or something
166 else that reproduces asexually. But for sake of having lots of terms
167 to use, we just pretend that links in the tree represent the "is a
168 child of" relationship, instead of "is a kind of" or "is a part of", or
169 "could result from", or whatever the real relationship is. So we get
170 to borrow a lot of kinship words for describing trees -- B and C are
171 "children" (or "daughters") of A; A is the "parent" (or "mother") of B
172 and C. Node C is a "sibling" (or "sister") of node C; and so on, with
173 terms like "descendants" (a node's children, children's children,
174 etc.), and "generation" (all the nodes at the same "level" in the tree,
175 i.e., are either all grandchildren of the top node, or all great-grand-
176 children, etc.), and "lineage" or "ancestors" (parents, and parent's
177 parents, etc., all the way to the topmost node).
178 So then we get to express rules in terms like "A node cannot have more
180 than one parent", which means that this is not a valid tree:
181 A
183 / \
184 B C
185 \ /
186 E
187 And: "A node can't be its own parent", which excludes this looped-up
189 connection:
190 /\
192 A |
193 \/
194 Or, put more generally: "A node can't be its own ancestor", which
196 excludes the above loop, as well as the one here:
197 /\
199 Z |
200 / |
201 A |
202 / \ |
203 B C |
204 \/
205 That tree is excluded because A is a child of Z, and Z is a child of C,
207 and C is a child of A, which means A is its own great-grandparent. So
208 this whole network can't be a tree, because it breaks the sort of meta-
209 rule: once any node in the supposed tree breaks the rules for trees,
210 you don't have a tree anymore.
211 Q: Okay, now, are these two trees the same?
213 A A
215 / | \ / | \
216 B C D D C B
217 A: It depends whether you're basing your concept of trees on each node
219 having a set (unordered list) of children, or an (ordered) list of
220 children. It's a question of whether ordering is important for what
221 you're doing. With my diagram of citrus types, ordering isn't
222 important, so these tree diagrams express the same thing:
223 citrus
225 / | \
226 orange lemon kumquat
227 citrus
229 / | \
230 kumquat orange lemon
231 because it doesn't make sense to say that oranges are "before" or
233 "after" kumquats in the whole botanical scheme of things. (Unless, of
234 course, you are using ordering to mean something, like a degree of
235 genetic similarity.)
236 But consider a tree that's a diagram of what steps are comprised in an
238 activity, to some degree of specificity:
239 make tea
241 / | \
242 pour infuse serve
243 hot water / \
244 in cup/pot / \
245 add let
246 tea sit
247 leaves
248 This means that making tea consists of putting hot water in a cup or
250 put, infusing it (which itself consists of adding tea leaves and
251 letting it sit), then serving it -- in that order. If you serve an
252 empty dry pot (sipping from empty cups, etc.), let it sit, add tea
253 leaves, and pour in hot water, then what you're doing is performance
254 art, not tea preparation:
255 performance
257 art
258 / | \
259 serve infuse pour
260 / \ hot water
261 / \ in cup/pot
262 let add
263 sit tea
264 leaves
265 Except for my having renamed the root, this tree is the same as the
267 making-tea tree as far as what's under what, but it differs in order,
268 and what the tree means makes the order important.
269 Q: Wait -- "root"? What's a root?
271 A: Besides kinship terms like "mother" and "daughter", the jargon for
273 tree parts also has terms from real-life tree parts: the part that
274 everything else grows from is called the root; and nodes that don't
275 have nodes attached to them (i.e., childless nodes) are called
276 "leaves".
277 Q: But you've been drawing all your trees with the root at the top and
279 leaves at the bottom.
280 A: Yes, but for some reason, that's the way everyone seems to think of
282 trees. They can draw trees as above; or they can draw them sort of
283 sideways with indenting representing what nodes are children of what:
284 * make tea
286 * pour hot water in cup/pot
287 * infuse
288 * add tea leaves
289 * let sit
290 * serve
291 ...but folks almost never seem to draw trees with the root at the
293 bottom. So imagine it's based on spider plant in a hanging pot.
294 Unfortunately, spider plants aren't botanically trees, they're plants;
295 but "spider plant diagram" is rather a mouthful, so let's just call
296 them trees.
297 Trees Defined Formally
299 In time, I digested all these assorted facts about programmers' ideas
300 of trees (which turned out to be just a more general case of linguistic
301 ideas of trees) into a single rule:
302 * A node is an item that contains ("is over", "is parent of", etc.)
304 zero or more other nodes.
305 From this you can build up formal definitions for useful terms, like
307 so:
308 * A node's descendants are defined as all its children, and all their
310 children, and so on. Or, stated recursively: a node's descendants are
311 all its children, and all its children's descendants. (And if it has
312 no children, it has no descendants.)
313 * A node's ancestors consist of its parent, and its parent's parent,
315 etc, up to the root. Or, recursively: a node's ancestors consist of
316 its parent and its parent's ancestors. (If it has no parent, it has no
317 ancestors.)
318 * A tree is a root node and all the root's descendants.
320 And you can add a proviso or two to clarify exactly what I impute to
322 the word "other" in "other nodes":
323 * A node cannot contain itself, or contain any node that contains it,
325 etc. Looking at it the other way: a node cannot be its own parent or
326 ancestor.
327 * A node can be root (i.e., no other node contains it) or can be
329 contained by only one parent; no node can be the child of two or more
330 parents.
331 Add to this the idea that children are sometimes ordered, and sometimes
333 not, and that's about all you need to know about defining what a tree
334 is. From there it's a matter of using them.
335 Markup Language Trees: HTML-Tree
337 While not all markup languages are inherently tree-like, the best-known
338 family of markup languages, HTML, SGML, and XML, are about as tree-like
339 as you can get. In these languages, a document consists of elements
340 and character data in a tree structure where there is one root element,
341 and elements can contain either other elements, or character data.
342 Footnote: For sake of simplicity, I'm glossing over comments (<!--
344 ... -->), processing instructions (<?xml version='1.0'>), and
345 declarations (<!ELEMENT ...>, <!DOCTYPE ...>). And I'm not
346 bothering to distinguish entity references (<, @) or CDATA
347 sections (<![CDATA[ ...]]>) from normal text.
348 For example, consider this HTML document:
350 <html lang="en-US">
352 <head>
353 <title>
354 Blank Document!
355 </title>
356 </head>
357 <body bgcolor="#d010ff">
358 I've got
359 <em>
360 something to saaaaay
361 </em>
362 !
363 </body>
364 </html>
365 I've indented this to point out what nodes (elements or text items) are
367 children of what, with each node on a line of its own.
368 The HTML::TreeBuilder module (in the CPAN distribution HTML-Tree) does
370 the work of taking HTML source and building in memory the tree that the
371 document source represents.
372 Footnote: it requires the HTML::Parser module, which tokenizes the
374 source -- i.e., identifies each tag, bit of text, comment, etc.
375 The trees structures that it builds represent bits of text with normal
377 Perl scalar string values; but elements are represented with objects --
378 that is, chunks of data that belong to a class (in this case,
379 HTML::Element), a class that provides methods (routines) for accessing
380 the pieces of data in each element, and otherwise doing things with
381 elements. (See my article in TPJ#17 for a quick explanation of
382 objects, the POD document "perltoot" for a longer explanation, or
383 Damian Conway's excellent book Object-Oriented Perl for the full
384 story.)
385 Each HTML::Element object contains a number of pieces of data:
387 * its element name ("html", "h1", etc., accessed as $element->tag)
389 * a list of elements (or text segments) that it contains, if any
391 (accessed as $element->content_list or $element->content, depending on
392 whether you want a list, or an arrayref)
393 * what element, if any, contains it (accessed as $element->parent)
395 * and any SGML attributes that the element has, such as "lang="en-US"",
397 "align="center"", etc. (accessed as $element->attr('lang'),
398 $element->attr('center'), etc.)
399 So, for example, when HTML::TreeBuilder builds the tree for the above
401 HTML document source, the object for the "body" element has these
402 pieces of data:
403 * element name: "body"
405 * nodes it contains:
406 the string "I've got "
407 the object for the "em" element
408 the string "!"
409 * its parent:
410 the object for the "html" element
411 * bgcolor: "#d010ff"
412 Now, once you have this tree of objects, almost anything you'd want to
414 do with it starts with searching the tree for some bit of information
415 in some element.
416 Accessing a piece of information in, say, a hash of hashes of hashes,
418 is straightforward:
419 $password{'sean'}{'sburke1'}{'hpux'}
421 because you know that all data points in that structure are accessible
423 with that syntax, but with just different keys. Now, the "em" element
424 in the above HTML tree does happen to be accessible as the root's child
425 #1's child #1:
426 $root->content->[1]->content->[1]
428 But with trees, you typically don't know the exact location (via
430 indexes) of the data you're looking for. Instead, finding what you
431 want will typically involve searching through the tree, seeing if every
432 node is the kind you want. Searching the whole tree is simple enough
433 -- look at a given node, and if it's not what you want, look at its
434 children, and so on. HTML-Tree provides several methods that do this
435 for you, such as "find_by_tag_name", which returns the elements (or the
436 first element, if called in scalar context) under a given node
437 (typically the root) whose tag name is whatever you specify.
438 For example, that "em" node can be found as:
440 my $that_em = $root->find_by_tag_name('em');
442 or as:
444 @ems = $root->find_by_tag_name('em');
446 # will only have one element for this particular tree
447 Now, given an HTML document of whatever structure and complexity, if
449 you wanted to do something like change every
450 <em>stuff</em>
452 to
454 <em class="funky"> <b>[-</b> stuff <b>-]</b> </em>
456 the first step is to frame this operation in terms of what you're doing
458 to the tree. You're changing this:
459 em
461 |
462 ...
463 to this:
465 em
467 / | \
468 b ... b
469 | |
470 "[-" "-]"
471 In other words, you're finding all elements whose tag name is "em",
473 setting its class attribute to "funky", and adding one child to the
474 start of its content list -- a new "b" element whose content is the
475 text string "[-" -- and one to the end of its content list -- a new "b"
476 element whose content is the text string "-]".
477 Once you've got it in these terms, it's just a matter of running to the
479 HTML::Element documentation, and coding this up with calls to the
480 appropriate methods, like so:
481 use HTML::Element 1.53;
483 use HTML::TreeBuilder 2.96;
484 # Build the tree by parsing the document
485 my $root = HTML::TreeBuilder->new;
486 $root->parse_file('whatever.html'); # source file
487 # Now make new nodes where needed
489 foreach my $em ($root->find_by_tag_name('em')) {
490 $em->attr('class', 'funky'); # Set that attribute
491 # Make the two new B nodes
493 my $new1 = HTML::Element->new('b');
494 my $new2 = HTML::Element->new('b');
495 # Give them content (they have none at first)
496 $new1->push_content('[-');
497 $new2->push_content('-]');
498 # And put 'em in place!
500 $em->unshift_content($new1);
501 $em->push_content($new2);
502 }
503 print
504 "<!-- Looky see what I did! -->\n",
505 $root->as_HTML(), "\n";
506 The class HTML::Element provides just about every method I can image
508 you needing, for manipulating trees made of HTML::Element objects.
509 (And what it doesn't directly provide, it will give you the components
510 to build it with.)
511 Building Your Own Trees
513 Theoretically, any tree is pretty much like any other tree, so you
514 could use HTML::Element for anything you'd ever want to do with tree-
515 arranged objects. However, as its name implies, HTML::Element is
516 basically for HTML elements; it has lots of features that make sense
517 only for HTML elements (like the idea that every element must have a
518 tag-name). And it lacks some features that might be useful for general
519 applications -- such as any sort of checking to make sure that you're
520 not trying to arrange objects in a non-treelike way. For a general-
521 purpose tree class that does have such features, you can use
522 Tree::DAG_Node, also available from CPAN.
523 However, if your task is simple enough, you might find it overkill to
525 bother using Tree::DAG_Node. And, in any case, I find that the best
526 way to learn how something works is to implement it (or something like
527 it, but simpler) yourself. So I'll here discuss how you'd implement a
528 tree structure, without using any of the existing classes for tree
529 nodes.
530 Implementation: Game Trees for Alak
532 Suppose that the task at hand is to write a program that can play
533 against a human opponent at a strategic board game (as opposed to a
534 board game where there's an element of chance). For most such games, a
535 "game tree" is an essential part of the program (as I will argue,
536 below), and this will be our test case for implementing a tree
537 structure from scratch.
538 For sake of simplicity, our game is not chess or backgammon, but
540 instead a much simpler game called Alak. Alak was invented by the
541 mathematician A. K. Dewdney, and described in his 1984 book
542 Planiverse. The rules of Alak are simple:
543 Footnote: Actually, I'm describing only my interpretation of the
545 rules Dewdney describes in Planiverse. Many other interpretations
546 are possible.
547 * Alak is a two-player game played on a one-dimensional board with
549 eleven slots on it. Each slot can hold at most one piece at a time.
550 There's two kinds of pieces, which I represent here as "x" and "o" --
551 x's belong to one player (called X), o's to the other (called O).
552 * The initial configuration of the board is:
554 xxxx___oooo
556 For sake of the article, the slots are numbered from 1 (on the left) to
558 11 (on the right), and X always has the first move.
559 * The players take turns moving. At each turn, each player can move
561 only one piece, once. (This unlike checkers, where you move one piece
562 per move but get to keep moving it if you jump an your opponent's
563 piece.) A player cannot pass up on his turn. A player can move any one
564 of his pieces to the next unoccupied slot to its right or left, which
565 may involve jumping over occupied slots. A player cannot move a piece
566 off the side of the board.
567 * If a move creates a pattern where the opponent's pieces are
569 surrounded, on both sides, by two pieces of the mover's color (with no
570 intervening unoccupied blank slot), then those surrounded pieces are
571 removed from the board.
572 * The goal of the game is to remove all of your opponent's pieces, at
574 which point the game ends. Removing all-but-one ends the game as well,
575 since the opponent can't surround you with one piece, and so will
576 always lose within a few moves anyway.
577 Consider, then, this rather short game where X starts:
579 xxxx___oooo
581 ^ Move 1: X moves from 3 (shown with caret) to 5
582 (Note that any of X's pieces could move, but
583 that the only place they could move to is 5.)
584 xx_xx__oooo
585 ^ Move 2: O moves from 9 to 7.
586 xx_xx_oo_oo
587 ^ Move 3: X moves from 4 to 6.
588 xx__xxoo_oo
589 ^ Move 4: O (stupidly) moves from 10 to 9.
590 xx__xxooo_o
591 ^ Move 5: X moves from 5 to 10, making the board
592 "xx___xoooxo". The three o's that X just
593 surrounded are removed.
594 xx___x___xo
595 O has only one piece, so has lost.
596 Now, move 4 could have gone quite the other way:
598 xx__xxoo_oo
600 Move 4: O moves from 8 to 4, making the board
601 "xx_oxxo__oo". The surrounded x's are removed.
602 xx_o__o__oo
603 ^ Move 5: X moves from 1 to 2.
604 _xxo__o__oo
605 ^ Move 6: O moves from 7 to 6.
606 _xxo_o___oo
607 ^ Move 7: X moves from 2 to 5, removing the o at 4.
608 __x_xo___oo
609 ...and so on.
610 To teach a computer program to play Alak (as player X, say), it needs
612 to be able to look at the configuration of the board, figure out what
613 moves it can make, and weigh the benefit or costs, immediate or
614 eventual, of those moves.
615 So consider the board from just before move 3, and figure all the
617 possible moves X could make. X has pieces in slots 1, 2, 4, and 5.
618 The leftmost two x's (at 1 and 2) are up against the end of the board,
619 so they can move only right. The other two x's (at 4 and 5) can move
620 either right or left:
621 Starting board: xx_xx_oo_oo
623 moving 1 to 3 gives _xxxx_oo_oo
624 moving 2 to 3 gives x_xxx_oo_oo
625 moving 4 to 3 gives xxx_x_oo_oo
626 moving 5 to 3 gives xxxx__oo_oo
627 moving 4 to 6 gives xx__xxoo_oo
628 moving 5 to 6 gives xx_x_xoo_oo
629 For the computer to decide which of these is the best move to make, it
631 needs to quantify the benefit of these moves as a number -- call that
632 the "payoff". The payoff of a move can be figured as just the number
633 of x pieces removed by the most recent move, minus the number of o
634 pieces removed by the most recent move. (It so happens that the rules
635 of the game mean that no move can delete both o's and x's, but the
636 formula still applies.) Since none of these moves removed any pieces,
637 all these moves have the same immediate payoff: 0.
638 Now, we could race ahead and write an Alak-playing program that could
640 use the immediate payoff to decide which is the best move to make. And
641 when there's more than one best move (as here, where all the moves are
642 equally good), it could choose randomly between the good alternatives.
643 This strategy is simple to implement; but it makes for a very dumb
644 program. Consider what O's response to each of the potential moves
645 (above) could be. Nothing immediately suggests itself for the first
646 four possibilities (X having moved something to position 3), but either
647 of the last two (illustrated below) are pretty perilous, because in
648 either case O has the obvious option (which he would be foolish to pass
649 up) of removing x's from the board:
650 xx_xx_oo_oo
652 ^ X moves 4 to 6.
653 xx__xxoo_oo
654 ^ O moves 8 to 4, giving "xx_oxxo__oo". The two
655 surrounded x's are removed.
656 xx_o__o__oo
657 or
659 xx_xx_oo_oo
661 ^ X moves 5 to 6.
662 xx_x_xoo_oo
663 ^ O moves 8 to 5, giving "xx_xoxo__oo". The one
664 surrounded x is removed.
665 xx_xo_o__oo
666 Both contingencies are quite bad for X -- but this is not captured by
668 the fact that they start out with X thinking his move will be harmless,
669 having a payoff of zero.
670 So what's needed is for X to think more than one step ahead -- to
672 consider not merely what it can do in this move, and what the payoff
673 is, but to consider what O might do in response, and the payoff of
674 those potential moves, and so on with X's possible responses to those
675 cases could be. All these possibilities form a game tree -- a tree
676 where each node is a board, and its children are successors of that
677 node -- i.e., the boards that could result from every move possible,
678 given the parent's board.
679 But how to represent the tree, and how to represent the nodes?
681 Well, consider that a node holds several pieces of data:
683 1) the configuration of the board, which, being nice and simple and
685 one-dimensional, can be stored as just a string, like "xx_xx_oo_oo".
686 2) whose turn it is, X or O. (Or: who moved last, from which we can
688 figure whose turn it is).
689 3) the successors (child nodes).
691 4) the immediate payoff of having moved to this board position from its
693 predecessor (parent node).
694 5) and what move gets us from our predecessor node to here. (Granted,
696 knowing the board configuration before and after the move, it's easy to
697 figure out the move; but it's easier still to store it as one is
698 figuring out a node's successors.)
699 6) whatever else we might want to add later.
701 These could be stored equally well in an array or in a hash, but it's
703 my experience that hashes are best for cases where you have more than
704 just two or three bits of data, or especially when you might need to
705 add new bits of data. Moreover, hash key names are mnemonic --
706 $node->{'last_move_payoff'} is plain as day, whereas it's not so easy
707 having to remember with an array that $node->[3] is where you decided
708 to keep the payoff.
709 Footnote: Of course, there are ways around that problem: just swear
711 you'll never use a real numeric index to access data in the array,
712 and instead use constants with mnemonic names:
713 use strict;
715 use constant idx_PAYOFF => 3;
716 ...
717 $n->[idx_PAYOFF]
718 Or use a pseudohash. But I prefer to keep it simple, and use a
720 hash.
721 These are, incidentally, the same arguments that people weigh when
723 trying to decide whether their object-oriented modules should be
724 based on blessed hashes, blessed arrays, or what. Essentially the
725 only difference here is that we're not blessing our nodes or
726 talking in terms of classes and methods.
727 [end footnote]
729 So, we might as well represent nodes like so:
731 $node = { # hashref
733 'board' => ...board string, e.g., "xx_x_xoo_oo"
734 'last_move_payoff' => ...payoff of the move
736 that got us here.
737 'last_move_from' => ...the start...
739 'last_move_to' => ...and end point of the move
740 that got us here. E.g., 5 and 6,
741 representing a move from 5 to 6.
742 'whose_turn' => ...whose move it then becomes.
744 just an 'x' or 'o'.
745 'successors' => ...the successors
747 };
748 Note that we could have a field called something like 'last_move_who'
750 to denote who last moved, but since turns in Alak always alternate (and
751 no-one can pass), storing whose move it is now and who last moved is
752 redundant -- if X last moved, it's O turn now, and vice versa. I chose
753 to have a 'whose_turn' field instead of a 'last_move_who', but it
754 doesn't really matter. Either way, we'll end up inferring one from the
755 other at several points in the program.
756 When we want to store the successors of a node, should we use an array
758 or a hash? On the one hand, the successors to $node aren't essentially
759 ordered, so there's no reason to use an array per se; on the other
760 hand, if we used a hash, with successor nodes as values, we don't have
761 anything particularly meaningful to use as keys. (And we can't use the
762 successors themselves as keys, since the nodes are referred to by hash
763 references, and you can't use a reference as a hash key.) Given no
764 particularly compelling reason to do otherwise, I choose to just use an
765 array to store all a node's successors, although the order is never
766 actually used for anything:
767 $node = {
769 ...
770 'successors' => [ ...nodes... ],
771 ...
772 };
773 In any case, now that we've settled on what should be in a node, let's
775 make a little sample tree out of a few nodes and see what we can do
776 with it:
777 # Board just before move 3 in above game
779 my $n0 = {
780 'board' => 'xx_xx_oo_oo',
781 'last_move_payoff' => 0,
782 'last_move_from' => 9,
783 'last_move_to' => 7,
784 'whose_turn' => 'x',
785 'successors' => [],
786 };
787 # And, for now, just two of the successors:
789 # X moves 4 to 6, giving xx__xxoo_oo
791 my $n1 = {
792 'board' => 'xx__xxoo_oo',
793 'last_move_payoff' => 0,
794 'last_move_from' => 4,
795 'last_move_to' => 6,
796 'whose_turn' => 'o',
797 'successors' => [],
798 };
799 # or X moves 5 to 6, giving xx_x_xoo_oo
801 my $n2 = {
802 'board' => 'xx_x_xoo_oo',
803 'last_move_payoff' => 0,
804 'last_move_from' => 5,
805 'last_move_to' => 6,
806 'whose_turn' => 'o',
807 'successors' => [],
808 };
809 # Now connect them...
811 push @{$n0->{'successors'}}, $n1, $n2;
812 Digression: Links to Parents
814 In comparing what we store in an Alak game tree node to what
815 HTML::Element stores in HTML element nodes, you'll note one big
816 difference: every HTML::Element node contains a link to its parent,
817 whereas we don't have our Alak nodes keeping a link to theirs.
818 The reason this can be an important difference is because it can affect
820 how Perl knows when you're not using pieces of memory anymore.
821 Consider the tree we just built, above:
822 node 0
824 / \
825 node 1 node 2
826 There's two ways Perl knows you're using a piece of memory: 1) it's
828 memory that belongs directly to a variable (i.e., is necessary to hold
829 that variable's value, or values in the case of a hash or array), or 2)
830 it's a piece of memory that something holds a reference to. In the
831 above code, Perl knows that the hash for node 0 (for board
832 "xx_xx_oo_oo") is in use because something (namely, the variable $n0)
833 holds a reference to it. Now, even if you followed the above code with
834 this:
835 $n1 = $n2 = 'whatever';
837 to make your variables $n1 and $n2 stop holding references to the
839 hashes for the two successors of node 0, Perl would still know that
840 those hashes are still in use, because node 0's successors array holds
841 a reference to those hashes. And Perl knows that node 0 is still in
842 use because something still holds a reference to it. Now, if you
843 added:
844 my $root = $n0;
846 This would change nothing -- there's just be two things holding a
848 reference to the node 0 hash, which in turn holds a reference to the
849 node 1 and node 2 hashes. And if you then added:
850 $n0 = 'stuff';
852 still nothing would change, because something ($root) still holds a
854 reference to the node 0 hash. But once nothing holds a reference to
855 the node 0 hash, Perl will know it can destroy that hash (and reclaim
856 the memory for later use, say), and once it does that, nothing will
857 hold a reference to the node 1 or the node 2 hashes, and those will be
858 destroyed too.
859 But consider if the node 1 and node 2 hashes each had an attribute
861 "parent" (or "predecessor") that held a reference to node 0. If your
862 program stopped holding a reference to the node 0 hash, Perl could not
863 then say that nothing holds a reference to node 0 -- because node 1 and
864 node 2 still do. So, the memory for nodes 0, 1, and 2 would never get
865 reclaimed (until your program ended, at which point Perl destroys
866 everything). If your program grew and discarded lots of nodes in the
867 game tree, but didn't let Perl know it could reclaim their memory, your
868 program could grow to use immense amounts of memory -- never a nice
869 thing to have happen. There's three ways around this:
870 1) When you're finished with a node, delete the reference each of its
872 children have to it (in this case, deleting $n1->{'parent'}, say).
873 When you're finished with a whole tree, just go through the whole tree
874 erasing links that children have to their children.
875 2) Reconsider whether you really need to have each node hold a
877 reference to its parent. Just not having those links will avoid the
878 whole problem.
879 3) use the WeakRef module with Perl 5.6 or later. This allows you to
881 "weaken" some references (like the references that node 1 and 2 could
882 hold to their parent) so that they don't count when Perl goes asking
883 whether anything holds a reference to a given piece of memory. This
884 wonderful new module eliminates the headaches that can often crop up
885 with either of the two previous methods.
886 It so happens that our Alak program is simple enough that we don't need
888 for our nodes to have links to their parents, so the second solution is
889 fine. But in a more advanced program, the first or third solutions
890 might be unavoidable.
891 Recursively Printing the Tree
893 I don't like working blind -- if I have any kind of a complex data
894 structure in memory for a program I'm working on, the first thing I do
895 is write something that can dump that structure to the screen so I can
896 make sure that what I think is in memory really is what's in memory.
897 Now, I could just use the "x" pretty-printer command in Perl's
898 interactive debugger, or I could have the program use the
899 "Data::Dumper" module. But in this case, I think the output from those
900 is rather too verbose. Once we have trees with dozens of nodes in
901 them, we'll really want a dump of the tree to be as concise as
902 possible, hopefully just one line per node. What I'd like is something
903 that can print $n0 and its successors (see above) as something like:
904 xx_xx_oo_oo (O moved 9 to 7, 0 payoff)
906 xx__xxoo_oo (X moved 4 to 6, 0 payoff)
907 xx_x_xoo_oo (X moved 5 to 6, 0 payoff)
908 A subroutine to print a line for a given node, and then do that again
910 for each successor, would look something like:
911 sub dump_tree {
913 my $n = $_[0]; # "n" is for node
914 print
915 ...something expressing $n'n content...
916 foreach my $s (@{$n->{'successors'}}) {
917 # "s for successor
918 dump($s);
919 }
920 }
921 And we could just start that out with a call to "dump_tree($n0)".
923 Since this routine...
925 Footnote: I first wrote this routine starting out with "sub dump
927 {". But when I tried actually calling "dump($n0)", Perl would dump
928 core! Imagine my shock when I discovered that this is absolutely
929 to be expected -- Perl provides a built-in function called "dump",
930 the purpose of which is to, yes, make Perl dump core. Calling our
931 routine "dump_tree" instead of "dump" neatly avoids that problem.
932 ...does its work (dumping the subtree at and under the given node) by
934 calling itself, it's recursive. However, there's a special term for
935 this kind of recursion across a tree: traversal. To traverse a tree
936 means to do something to a node, and to traverse its children. There's
937 two prototypical ways to do this, depending on what happens when:
938 traversing X in pre-order:
940 * do something to X
941 * then traverse X's children
942 traversing X in post-order:
944 * traverse X's children
945 * then do something to X
946 Dumping the tree to the screen the way we want it happens to be a
948 matter of pre-order traversal, since the thing we do (print a
949 description of the node) happens before we recurse into the successors.
950 When we try writing the "print" statement for our above "dump_tree", we
952 can get something like:
953 sub dump_tree {
955 my $n = $_[0];
956 # "xx_xx_oo_oo (O moved 9 to 7, 0 payoff)"
958 print
959 $n->{'board'}, " (",
960 ($n->{'whose_turn'} eq 'o' ? 'X' : 'O'),
961 # Infer who last moved from whose turn it is now.
962 " moved ", $n->{'last_move_from'},
963 " to ", $n->{'last_move_to'},
964 ", ", $n->{'last_move_payoff'},
965 " payoff)\n",
966 ;
967 foreach my $s (@{$n->{'successors'}}) {
969 dump_tree($s);
970 }
971 }
972 If we run this on $n0 from above, we get this:
974 xx_xx_oo_oo (O moved 9 to 7, 0 payoff)
976 xx__xxoo_oo (X moved 4 to 6, 0 payoff)
977 xx_x_xoo_oo (X moved 5 to 6, 0 payoff)
978 Each line on its own is fine, but we forget to allow for indenting, and
980 without that we can't tell what's a child of what. (Imagine if the
981 first successor had successors of its own -- you wouldn't be able to
982 tell if it were a child, or a sibling.) To get indenting, we'll need
983 to have the instances of the "dump_tree" routine know how far down in
984 the tree they're being called, by passing a depth parameter between
985 them:
986 sub dump_tree {
988 my $n = $_[0];
989 my $depth = $_[1];
990 $depth = 0 unless defined $depth;
991 print
992 " " x $depth,
993 ...stuff...
994 foreach my $s (@{$n->{'successors'}}) {
995 dump_tree($s, $depth + 1);
996 }
997 }
998 When we call "dump_tree($n0)", $depth (from $_[1]) is undefined, so
1000 gets set to 0, which translates into an indenting of no spaces. But
1001 when "dump_tree" invokes itself on $n0's children, those instances see
1002 $depth + 1 as their $_[1], giving appropriate indenting.
1003 Footnote: Passing values around between different invocations of a
1005 recursive routine, as shown, is a decent way to share the data.
1006 Another way to share the data is by keeping it in a global
1007 variable, like $Depth, initially set to 0. Each time "dump_tree"
1008 is about to recurse, it must "++$Depth", and when it's back, it
1009 must "--$Depth".
1010 Or, if the reader is familiar with closures, consider this
1012 approach:
1013 sub dump_tree {
1015 # A wrapper around calls to a recursive closure:
1016 my $start_node = $_[0];
1017 my $depth = 0;
1018 # to be shared across calls to $recursor.
1019 my $recursor;
1020 $recursor = sub {
1021 my $n = $_[0];
1022 print " " x $depth,
1023 ...stuff...
1024 ++$depth;
1025 foreach my $s (@{$n->{'successors'}}) {
1026 $recursor->($s);
1027 }
1028 --$depth;
1029 }
1030 $recursor->($start_node); # start recursing
1031 undef $recursor;
1032 }
1033 The reader with an advanced understanding of Perl's reference-
1035 count-based garbage collection is invited to consider why it is
1036 currently necessary to undef $recursor (or otherwise change its
1037 value) after all recursion is done.
1038 The reader whose mind is perverse in other ways is invited to
1040 consider how (or when!) passing a depth parameter around is
1041 unnecessary because of information that Perl's caller(N) function
1042 reports!
1043 [end footnote]
1045 Growing the Tree
1047 Our "dump_tree" routine works fine for the sample tree we've got, so
1048 now we should get the program working on making its own trees, starting
1049 from a given board.
1050 In "Games::Alak" (the CPAN-released version of Alak that uses
1052 essentially the same code that we're currently discussing the tree-
1053 related parts of), there is a routine called "figure_successors" that,
1054 given one childless node, will figure out all its possible successors.
1055 That is, it looks at the current board, looks at every piece belonging
1056 to the player whose turn it is, and considers the effect of moving each
1057 piece every possible way -- notably, it figures out the immediate
1058 payoff, and if that move would end the game, it notes that by setting
1059 an "endgame" entry in that node's hash. (That way, we know that that's
1060 a node that can't have successors.)
1061 In the code for "Games::Alak", "figure_successors" does all these
1063 things, in a rather straightforward way. I won't walk you through the
1064 details of the "figure_successors" code I've written, since the code
1065 has nothing much to do with trees, and is all just implementation of
1066 the Alak rules for what can move where, with what result. Especially
1067 interested readers can puzzle over that part of code in the source
1068 listing in the archive from CPAN, but others can just assume that it
1069 works as described above.
1070 But consider that "figure_successors", regardless of its inner
1072 workings, does not grow the tree; it only makes one set of successors
1073 for one node at a time. It has to be up to a different routine to call
1074 "figure_successors", and to keep applying it as needed, in order to
1075 make a nice big tree that our game-playing program can base its
1076 decisions on.
1077 Now, we could do this by just starting from one node, applying
1079 "figure_successors" to it, then applying "figure_successors" on all the
1080 resulting children, and so on:
1081 sub grow { # Just a first attempt at this!
1083 my $n = $_[0];
1084 figure_successors($n);
1085 unless
1086 @{$n->{'successors'}}
1087 # already has successors.
1088 or $n->{'endgame'}
1089 # can't have successors.
1090 }
1091 foreach my $s (@{$n->{'successors'}}) {
1092 grow($s); # recurse
1093 }
1094 }
1095 If you have a game tree for tic-tac-toe, and you grow it without
1097 limitation (as above), you will soon enough have a fully "solved" tree,
1098 where every node that can have successors does, and all the leaves of
1099 the tree are all the possible endgames (where, in each case, the board
1100 is filled). But a game of Alak is different from tic-tac-toe, because
1101 it can, in theory, go on forever. For example, the following sequence
1102 of moves is quite possible:
1103 xxxx___oooo
1105 xxx_x__oooo
1106 xxx_x_o_ooo
1107 xxxx__o_ooo (x moved back)
1108 xxxx___oooo (o moved back)
1109 ...repeat forever...
1110 So if you tried using our above attempt at a "grow" routine, Perl would
1112 happily start trying to construct an infinitely deep tree, containing
1113 an infinite number of nodes, consuming an infinite amount of memory,
1114 and requiring an infinite amount of time. As the old saying goes: "You
1115 can't have everything -- where would you put it?" So we have to place
1116 limits on how much we'll grow the tree.
1117 There's more than one way to do this:
1119 1. We could grow the tree until we hit some limit on the number of
1121 nodes we'll allow in the tree.
1122 2. We could grow the tree until we hit some limit on the amount of time
1124 we're willing to spend.
1125 3. Or we could grow the tree until it is fully fleshed out to a certain
1127 depth.
1128 Since we already know to track depth (as we did in writing
1130 "dump_tree"), we'll do it that way, the third way. The implementation
1131 for that third approach is also pretty straightforward:
1132 $Max_depth = 3;
1134 sub grow {
1135 my $n = $_[0];
1136 my $depth = $_[1] || 0;
1137 figure_successors($n)
1138 unless
1139 $depth >= $Max_depth
1140 or @{$n->{'successors'}}
1141 or $n->{'endgame'}
1142 }
1143 foreach my $s (@{$n->{'successors'}}) {
1144 grow($s, $depth + 1);
1145 }
1146 # If we're at $Max_depth, then figure_successors
1147 # didn't get called, so there's no successors
1148 # to recurse under -- that's what stops recursion.
1149 }
1150 If we start from a single node (whether it's a node for the starting
1152 board "xxxx___oooo", or for whatever board the computer is faced with),
1153 set $Max_depth to 4, and apply "grow" to it, it will grow the tree to
1154 include several hundred nodes.
1155 Footnote: If at each move there are four pieces that can move, and
1157 they can each move right or left, the "branching factor" of the
1158 tree is eight, giving a tree with 1 (depth 0) + 8 (depth 1) + 8 **
1159 2 + 8 ** 3 + 8 ** 4 = 4681 nodes in it. But, in practice, not all
1160 pieces can move in both directions (none of the x pieces in
1161 "xxxx___oooo" can move left, for example), and there may be fewer
1162 than four pieces, if some were lost. For example, there are 801
1163 nodes in a tree of depth four starting from "xxxx___oooo",
1164 suggesting an average branching factor of about five (801 ** (1/4)
1165 is about 5.3), not eight.
1166 What we need to derive from that tree is the information about what are
1168 the best moves for X. The simplest way to consider the payoff of
1169 different successors is to just average them -- but what we average
1170 isn't always their immediate payoffs (because that'd leave us using
1171 only one generation of information), but the average payoff of their
1172 successors, if any. We can formalize this as:
1173 To figure a node's average payoff:
1175 If the node has successors:
1176 Figure each successor's average payoff.
1177 My average payoff is the average of theirs.
1178 Otherwise:
1179 My average payoff is my immediate payoff.
1180 Since this involves recursing into the successors before doing anything
1182 with the current node, this will traverse the tree in post-order.
1183 We could work that up as a routine of its own, and apply that to the
1185 tree after we've applied "grow" to it. But since we'd never grow the
1186 tree without also figuring the average benefit, we might as well make
1187 that figuring part of the "grow" routine itself:
1188 $Max_depth = 3;
1190 sub grow {
1191 my $n = $_[0];
1192 my $depth = $_[1] || 0;
1193 figure_successors($n);
1194 unless
1195 $depth >= $Max_depth
1196 or @{$n->{'successors'}}
1197 or $n->{'endgame'}
1198 }
1199 if(@{$n->{'successors'}}) {
1201 my $a_payoff_sum = 0;
1202 foreach my $s (@{$n->{'successors'}}) {
1203 grow($s, $depth + 1); # RECURSE
1204 $a_payoff_sum += $s->{'average_payoff'};
1205 }
1206 $n->{'average_payoff'}
1207 = $a_payoff_sum / @{$n->{'successors'}};
1208 } else {
1209 $n->{'average_payoff'}
1210 = $n->{'last_move_payoff'};
1211 }
1212 }
1213 So, by time "grow" has applied to a node (wherever in the tree it is),
1215 it will have figured successors if possible (which, in turn, sets
1216 "last_move_payoff" for each node it creates), and will have set
1217 "average_benefit".
1218 Beyond this, all that's needed is to start the board out with a root
1220 note of "xxxx___oooo", and have the computer (X) take turns with the
1221 user (O) until someone wins. Whenever it's O's turn, "Games::Alak"
1222 presents a prompt to the user, letting him know the state of the
1223 current board, and asking what move he selects. When it's X's turn,
1224 the computer grows the game tree as necessary (using just the "grow"
1225 routine from above), then selects the move with the highest average
1226 payoff (or one of the highest, in case of a tie).
1227 In either case, "selecting" a move means just setting that move's node
1229 as the new root of the program's game tree. Its sibling nodes and
1230 their descendants (the boards that didn't get selected) and its parent
1231 node will be erased from memory, since they will no longer be in use
1232 (as Perl can tell by the fact that nothing holds references to them
1233 anymore).
1234 The interface code in "Games::Alak" (the code that prompts the user for
1236 his move) actually supports quite a few options besides just moving --
1237 including dumping the game tree to a specified depth (using a slightly
1238 fancier version of "dump_tree", above), resetting the game, changing
1239 $Max_depth in the middle of the game, and quitting the game. Like
1240 "figure_successors", it's a bit too long to print here, but interested
1241 users are welcome to peruse (and freely modify) the code, as well as to
1242 enjoy just playing the game.
1243 Now, in practice, there's more to game trees than this: for games with
1245 a larger branching factor than Alak has (which is most!), game trees of
1246 depth four or larger would contain too many nodes to be manageable,
1247 most of those nodes being strategically quite uninteresting for either
1248 player; dealing with game trees specifically is therefore a matter of
1249 recognizing uninteresting contingencies and not bothering to grow the
1250 tree under them.
1251 Footnote: For example, to choose a straightforward case: if O has a
1253 choice between moves that put him in immediate danger of X winning
1254 and moves that don't, then O won't ever choose the dangerous moves
1255 (and if he does, the computer will know enough to end the game), so
1256 there's no point in growing the tree any further beneath those
1257 nodes.
1258 But this sample implementation should illustrate the basics of how to
1260 build and manipulate a simple tree structure in memory. And once
1261 you've understood the basics of tree storage here, you should be ready
1262 to better understand the complexities and peculiarities of other
1263 systems for creating, accessing, and changing trees, including
1264 Tree::DAG_Node, HTML::Element, XML::DOM, or related formalisms like
1265 XPath and XSL.
1266 [end body of article]
1268 [Author Credit]
1270 Sean M. Burke ("sburke@cpan.org") is a tree-dwelling hominid.
1271 References
1273 Dewdney, A[lexander] K[eewatin]. 1984. Planiverse: Computer Contact
1274 with a Two-Dimensional World. Poseidon Press, New York.
1275 Knuth, Donald Ervin. 1997. Art of Computer Programming, Volume 1,
1277 Third Edition: Fundamental Algorithms. Addison-Wesley, Reading, MA.
1278 Wirth, Niklaus. 1976. Algorithms + Data Structures = Programs
1280 Prentice-Hall, Englewood Cliffs, NJ.
1281 Worth, Stan and Allman Sheldon. Circa 1967. George of the Jungle
1283 theme. [music by Jay Ward.]
1284 Wirth's classic, currently and lamentably out of print, has a good
1286 section on trees. I find it clearer than Knuth's (if not quite as
1287 encyclopedic), probably because Wirth's example code is in a block-
1288 structured high-level language (basically Pascal), instead of in
1289 assembler (MIX). I believe the book was re-issued in the 1980s under
1290 the titles Algorithms and Data Structures and, in a German edition,
1291 Algorithmen und Datenstrukturen. Cheap copies of these editions should
1292 be available through used book services such as "abebooks.com".
1293 Worth's classic, however, is available on the soundtrack to the 1997
1295 George of the Jungle movie, as performed by The Presidents of the
1296 United States of America.
1297
1299 Return to the HTML::Tree docs.
1300perl v5.16.3 2014-06-10 HTML::Tree::AboutTrees(3)