Re: Implementation of game tree search using TDD

Hi,

my thoughts:

   - Building a minimal implementation of the tree need not mean that
   you're not testing in isolation.  Define an AbstractTree class with an
   abstract children() method.  It's much easier to reason on "what should the
   search algorithm find when it's given this particular tree" than what you
   are doing now.
   - It seems you're implementing the state of traversal inside the tree.
    This means that you're loading it with an extra responsibility.  I would
   rather keep the state of the search inside the SearchAlgorithm.
   - If your tree type is abstract, the search algorithm doesn't need to
   know if the actual tree it's working on is computed lazily or it is a
   static data structure.

Hope this helps,

Matteo

On Wed, Apr 17, 2013 at 6:38 AM, haewke <[email protected]> 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?
>
>
> [Non-text portions of this message have been removed]
>
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>
>


[Non-text portions of this message have been removed]



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

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/