开云体育

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?

Thank you for the replies.

Tracking the traversal state in the tree is definitely the complication. I now have an ITreeNode interface that looks like this:

public interface ITreeNode
{
int GetValue();
IEnumerable<ITreeNode> GetChildren();
}

And the test becomes a lot more readable:

[TestMethod]
public void SearchToDepthTwoShouldReturnMaxValueAtDepthTwo()
{
_depth = 2;
_returnValue = 6;
AddChildNodes(_node0, new[] {_node00, _node01}, new[] {0, 0});
AddChildNodes(_node00, new[] {_node000, _node001}, new[] {3, 1});
AddChildNodes(_node01, new[] {_node010, _node011}, new[] {5, _returnValue});
Assert.AreEqual(_returnValue, _negaMax.Search(_node0, _depth));
}


AddChildNodes takes a root node, an array of children and an array of values for the children and it mocks root.GetChildren and child.GetValue calls.

-------

I have a nagging feeling it only shifts the problem somewhere else though.

If the game state is small enough that it can be cloned quickly and not use up too much memory then each node in the tree can be a different game state and the ITreeNode interface can be implemented by the game state directly.

If only one game state is maintained and searching works by transitioning from state to state and back again then how do you implement a solution based on the ITreeNode interface?



I think what I am going to do is keep an interface like:
public interface ITree
{
int GetValue();
IEnumerable<int> GetMoves();
void MakeMove(int move);
void Takeback();
}

Then create an implementation of ITree for testing purposes with methods to ease testing.

Currently it feels like I am changing my design to accommodate mocking which I think is more a problem with mocking data structures rather than a problem with my design.

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. @IndustrialLogic
Coaching | Training | Assessment | eLearning


--- In testdrivendevelopment@..., "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?

Hi Bill,

Even Tic Tac Toe has a large branching factor. 9 moves at the start with each of these 9 moves having 8 possible moves, etc. Yes, there is a lot of transposition (where the same board occurs) and the problem is usually solved by maintaining a transposition table/hash and I'll get to that eventually.

For now I am just focusing on fixed depth searching without worrying about transpositions.

The actual algorithm I am interested in is Negamax with Alpha Beta pruning which looks like this:

int alphaBeta( int alpha, int beta, int depthleft ) {
if( depthleft == 0 ) return quiesce( alpha, beta );
for ( all moves) {
score = -alphaBeta( -beta, -alpha, depthleft - 1 );
if( score >= beta )
return beta; // fail hard beta-cutoff
if( score > alpha )
alpha = score; // alpha acts like max in MiniMax
}
return alpha;
}

Found here:
quiesce in the algorithm is to find a "quiet" position to evaluate.

The problem is getting to that algorithm with small incremental steps. Naming the test cases also becomes a problem. How do you explain the minimax requirement in the name of a test case?

If you consider a tree with depth 2 (0 indexed) in a 2 player game like tic tac toe, at the root level of the tree it is the turn of player 1 and player 1 wants to find the best possible move from the perspective of player 1. At depth 1 it is now player 2's turn and player 2 will pick the best possible move from the perspective of player 2.

So in a complete binary tree of depth 2 with leaf values like this (brackets denotes children):
((8)(45))((65)(23))

The algorithm does the following:
Moves down the left branch to depth 1
Examine all leafs (8, 45) and picks the minimum = 8
Moves back up
Moves down the right branch to depth 1
Picks the minimum = 23
Now it moves back to depth 0
Pick the MAXIMUM of all branches (8, 23) = 23

This is the core of minimax, the alternating minimizing and maximizing. How do you explain that behaviour in a test name?

haewke thinusba@... writes:

The problem is getting to that algorithm with small incremental steps.

Well, I'll distinguish two versions of "getting there". One is "How would I
invent this algorithm in small steps (e.g., from a simple static
evaluator)?" That one is a bit hit-or-miss for me.

The other way would be more "How do I write a series of small tests to
convince myself I've implemented a particular algorithm correctly?" and
that's more doable.

int alphaBeta( int alpha, int beta, int depthleft ) {
if( depthleft == 0 ) return quiesce( alpha, beta );
for ( all moves) {
score = -alphaBeta( -beta, -alpha, depthleft - 1 );
if( score >= beta )
return beta; // fail hard beta-cutoff
if( score > alpha )
alpha = score; // alpha acts like max in MiniMax
}
return alpha;
}

Naming the test cases also becomes a problem.
How do you explain the minimax requirement in the name of a test case?

There are only a few paths through this:
* Zero depth uses the quiesce analysis - test by overriding or mocking the
quiesce function
* Non-zero depth with no moves available returns given alpha - don't know
if this can happen in your structure
* Return beta if any child is lower than beta in a tree of depth 1 - hope I
haven't screwed up my lower and greater!
etc.
but I see I'm re-laying out the tests you started with...

So I guess to jump to the minimax one, maybe something like "The score is
the maximum of minimums in a tree of depth 2".


What normally happens for me in these recursive ones is I write the
"driving" test cases that get me through the various paths. Then I add a
series of tests to convince myself I've really done ok. For this algorithm,
the depth 2 case you mention is probably one of those. I'd probably also
add something to convince myself I did the right thing with all those minus
signs & parameter-flipping on the recursive case.

That is, for those additional test cases, I'd expect them to pass by
default. If I were really feeling paranoid, I'd change the line I was
worried about and make sure the test really could fail. (E.g., write a test
that would break if we don't flip alpha and beta (signs or order), then
mutilate the code to make sure it fails.)

--Bill

--
Bill Wake
Industrial Logic, Inc. @IndustrialLogic
Coaching | Training | Assessment | eLearning