开云体育

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