Re: Implementation of game tree search using TDD

Sounds like a fun project!

There's several things going on worth teasing out...
* With recursive problems like this, I think it helps to really articulate the rules. In this case, there seem to be two parts:
  + Trees are either leaves or nodes containing children
  + Rules for FindMaxValue
What I'd normally do is define FindMaxValue(tree,depth) for the various combinations of tree (leaf or interior) and depth (0, 1, n). 

(Without doing it I'm not sure, but you may find 0-based works well or doesn't - kind of depends what you say the depth of a tree consisting of just a leaf node is.)

This helps reduce the number of test cases needed. 

* Your mock version doesn't do much for me. (But I'm the sort who doesn't necessarily reach for mocks right away.) It feels very focused on the solution side.

> Don't mock the tree, use a minimal implementation of the tree
> insteadPros: Tree construction will be more readable. Trees can be
> specified as XML or JSON to be more readable.Cons: Not testing in
> isolation

I think this might be a little easier. There'd be nothing wrong with having an interface for the tree (to do things like get the node value and children etc.), where game nodes are more interesting but for testing traversal you can get by with less. XML/JSON feel like heavy ways to do this. I'd either do a set of simple constructors, or some string-based form as someone else suggested. If the latter, I'd probably imitate Lisp expressions as they're pretty minimalist.

* Tree interface
> Redesign the treeCurrently the tree has an internal state / cursor.
> MoveToChild and MoveToParent are used to navigate around the tree. The
> reason for this is that the game trees are very large and creating
> static trees are not feasible. Instead, all the children are calculated
> on demand based on the current state.

There's definitely going to be a difference based on what type tree you use. The basic leaf-node-children type tree is easier to understand for me at least. If you want a sort of cursor-based tree, I'd go back to being very clear about its recursive definition: given a tree and a cursor, what are the operations: move to child n, move to parent, or whatever.

You might find it easier to pass tree and cursor separately. The tree is this abstract thing, not fully elaborated in memory, but you're presumably able to go from any cursor position to a neighboring node. 

You're after an abstract interface, e.g., "given a tree and a cursor node, determine the parent node". An in-memory form (like you might use for testing) can either have a parent pointer or do a search; the "real" one will calculate the new position based on game rules I guess.

* Large trees
> Also, creating larger trees will still need some mechanism for
> constructing them.
> Implement searching as part of the treeStill a problem with the dynamic
> nature of the tree. Mocking won't be simplified unless the tree is
> implemented as static but eventually there will need to be a dynamic
> tree implementation that requires testing and the same issues will
> surface. And probably violates single responsibility pattern.

I think the challenge is mostly about what traversal looks like in the "real" case. If you define an interface that supports the real case (plain or cursor-based), then it would seem like FindMaxValue would be tested. You'd still have to create and test your large-tree items, but that'd be basically independent. 

Can you do some end-to-end approach on a super-simple game? (Maybe something with only trees of depth 1 or 2).

Sometimes you can find ways to share structures - e.g., a board is an empty board, or a board plus a change. (Game trees often have lots of duplicate positions running around.) You might be able to cache these as well. Sometimes you can create very compact representations (e.g., a bit string). 

Good luck!
   Bill 

-- 
   Bill Wake
   Industrial Logic, Inc.  http://industriallogic.com @IndustrialLogic
   Coaching | Training | Assessment | eLearning


--- In [email protected], "haewke" <thinusba@...> wrote:
>
> Hi,
> I am trying to use TDD to implement game tree searching but I am running
> into some issues.Using C#, MS Test  and Rhino Mocks.
> My requirement is to traverse a tree to a specified depth and find the
> maximum value of the nodes at this depth. If a path ends before the
> specified depth then the value of the last node in the path should be
> considered.
> Sample usage looks like this:
> var depth = 5;
> var tree = new GameTree();
> var treeSearch = new TreeSearch();var maxValue =
> treeSearch.FindMaxValue(tree, depth);
> I started with the following tests:
> 
>     * A search to depth zero should return the value of the root node
>     * A search to depth one with no children should return the value of
> the root node
>     * A search to depth one with one child should return the value of the
> child
>     * A search to depth one with two children should return the highest
> value of the two children
>     * A search to depth one of a tree with depth two should return the
> maximum value at depth one
> Up to this point the tests are simple enough and mocking of the tree is
> simple. The last test starts driving towards a depth first tree
> traversal.Now I start on depth 2 tests which should drive the rest of
> the tree traversal algorithm:
>     * A search to depth two should return the maximum value at depth two
> I decided to mock a complete binary tree with depth 2. The test looks
> like this:        public void
> SearchToDepthTwoShouldReturnMaxValueAtDepthTwo()         {            
> _depth = 2;             _returnValue = 6;             _tree.Expect(t =>
> t.GetChildren()).Return(new[] {1, 2}).Repeat.Once();            
> _tree.Expect(t => t.MoveToChild(1)).Repeat.Once();            
> _tree.Expect(t => t.GetChildren()).Return(new[] { 3, 4 }).Repeat.Once();
> _tree.Expect(t => t.MoveToChild(3)).Repeat.Once();            
> _tree.Expect(t => t.Evaluate()).Return(3).Repeat.Once();            
> _tree.Expect(t => t.MoveToParent()).Repeat.Once();            
> _tree.Expect(t => t.MoveToChild(4)).Repeat.Once();            
> _tree.Expect(t => t.Evaluate()).Return(4).Repeat.Once();            
> _tree.Expect(t => t.MoveToParent()).Repeat.Once();            
> _tree.Expect(t => t.MoveToParent()).Repeat.Once();            
> _tree.Expect(t => t.MoveToChild(2)).Repeat.Once();            
> _tree.Expect(t => t.GetChildren()).Return(new[] { 5, 6 }).Repeat.Once();
> _tree.Expect(t => t.MoveToChild(5)).Repeat.Once();            
> _tree.Expect(t => t.Evaluate()).Return(5).Repeat.Once();            
> _tree.Expect(t => t.MoveToParent()).Repeat.Once();            
> _tree.Expect(t => t.MoveToChild(6)).Repeat.Once();            
> _tree.Expect(t => t.Evaluate()).Return(_returnValue).Repeat.Once();
> _tree.Expect(t => t.MoveToParent()).Repeat.Once();            
> _tree.Expect(t => t.MoveToParent()).Repeat.Once();            
> Assert.AreEqual(_returnValue, _treeSearch.Search(_tree, _depth));
> _tree.VerifyAllExpectations();         }Where the interface for the tree
> looks like this:    public interface ITree     {         int Evaluate();
> IEnumerable<int> GetChildren();         void MoveToChild(int node);
> void MoveToParent();     } Not my idea of a good test. I can probably
> clean this up by introducing a tree creator method where I pass in an
> array that defines the structure and an array with the values but even
> that approach has problems as the parsing of the arrays will be complex
> and constructing the array will be complex.
> Also, the mocking is tied to the solution algorithm and expects a depth
> first approach.
> This is also the most trivial of searching algorithms. My next step is a
> minimax / negamax search and then an alpha-beta search where test cases
> for trees of depth 3 and maybe 4 will be required due to the nature of
> the optimizations.
> 
> 
> So I am left scratching my head on how to solve the issue. Some ideas I
> am kicking around:
> Don't mock the tree, use a minimal implementation of the tree
> insteadPros: Tree construction will be more readable. Trees can be
> specified as XML or JSON to be more readable.Cons: Not testing in
> isolation
> 
> Redesign the treeCurrently the tree has an internal state / cursor.
> MoveToChild and MoveToParent are used to navigate around the tree. The
> reason for this is that the game trees are very large and creating
> static trees are not feasible. Instead, all the children are calculated
> on demand based on the current state.
> If this behaviour is ignored and the interface is changed so that a
> context node needs to be specified for each operation then the mocking
> can be changed to return a value based on the parameters and not the
> order of calls to the mocked class.
> Pros: Mocking not tied to implementationCons: If a state tree implements
> the interface then checks will need to be built in to verify that the
> context in the calling methods is always equal to the current state.
> Also, creating larger trees will still need some mechanism for
> constructing them.
> Implement searching as part of the treeStill a problem with the dynamic
> nature of the tree. Mocking won't be simplified unless the tree is
> implemented as static but eventually there will need to be a dynamic
> tree implementation that requires testing and the same issues will
> surface. And probably violates single responsibility pattern.
> 
> Any thoughts?
>



------------------------------------

Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/testdrivendevelopment/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/testdrivendevelopment/join
    (Yahoo! ID required)

<*> To change settings via email:
    [email protected] 
    [email protected]

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/