Re: Implementation of game tree search using TDD

Hi everyone!

Interesting problem!

Just as an alternative, without using mocks, I wrote a solution using C#,
VS2008, MSTests

https://github.com/ajlopez/TddOnTheRocks/tree/master/GameTreeSearch

The history, per test

https://github.com/ajlopez/TddOnTheRocks/commits/master/GameTreeSearch

There are tests that were "additional" in the sense the reached
implementation already solved the cases. I want these test to explicitly
document the expected behavior.

I don't sure if the implementation (class project) needs a tree
create/factory method, so, at the latest steps I refactored the test to
have tree factory methods (at test project). If I needed more test, maybe I
refactored them to use a simple string description

Angel "Java" Lopez
@ajlopez


On Wed, Apr 17, 2013 at 1: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]
>
>  
>


[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/