开云体育

I would highly recommend "refactoring to patterns" by Josh Kerievsky. A
true gem that seems to have fallen out of our memory. It is fantastic,
though.

+1

Possibly the best narrative example of what TDD feels like. Although,
Kent's videos from Pragmatic Programmer are also quite illuminating.
On Apr 29, 2013 11:16 PM, "Joey Samonte" <dyowee23@...> wrote:

**


Test Driven Development by Example (Kent Beck)


________________________________
From: John Carter <john.carter@...>
To: testdrivendevelopment@...
Sent: Tuesday, April 30, 2013 11:12 AM
Subject: [TDD] If you could get your colleagues to read just one book on
TDD, which would it be?



Conversely, which books would you expect a TDD master to have read?

--
John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : mailto:john.carter%40taitradio.com
New Zealand

--

------------------------------
This email, including any attachments, is only for the intended recipient.
It is subject to copyright, is confidential and may be the subject of
legal
or other privilege, none of which is waived or lost by reason of this
transmission.
If you are not an intended recipient, you may not use, disseminate,
distribute or reproduce such email, any attachments, or any part thereof.
If you have received a message in error, please notify the sender
immediately and erase all copies of the message and any attachments.
Unfortunately, we cannot warrant that the email has not been altered or
corrupted during transmission nor can we guarantee that any email or any
attachments are free from computer viruses or other conditions which may
damage or interfere with recipient data, hardware or software. The
recipient relies upon its own procedures and assumes all risk of use and
of
opening any attachments.
------------------------------



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

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

There's about 15 books on TDD (and a few on Refactoring). I would expect a TDD master to have read 6 of them.

--
C. Keith Ray
*
*

On 2013 Apr 29, at 8:12 PM, John Carter <john.carter@...> wrote:

Conversely, which books would you expect a TDD master to have read?

--
John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : john.carter@...
New Zealand

--

------------------------------
This email, including any attachments, is only for the intended recipient.
It is subject to copyright, is confidential and may be the subject of legal
or other privilege, none of which is waived or lost by reason of this
transmission.
If you are not an intended recipient, you may not use, disseminate,
distribute or reproduce such email, any attachments, or any part thereof.
If you have received a message in error, please notify the sender
immediately and erase all copies of the message and any attachments.
Unfortunately, we cannot warrant that the email has not been altered or
corrupted during transmission nor can we guarantee that any email or any
attachments are free from computer viruses or other conditions which may
damage or interfere with recipient data, hardware or software. The
recipient relies upon its own procedures and assumes all risk of use and of
opening any attachments.
------------------------------

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

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

You also can't go wrong with industriallogic.com elearning. Not a book per
se, but a great way to learn with some practice built in (full disclosure:
I used to work for them. I don't anymore, but they still rock.)
On Apr 29, 2013 9:41 PM, "Gishu Pillai" <gishu.pillai@...> wrote:

**


TDD By Example,
Refactoring
GOOS +1
Clean Code

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

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

TDD By Example,
Refactoring
GOOS +1
Clean Code

Depends on the person, but GOOS and the RSpec book come to mind.
On Apr 29, 2013 8:13 PM, "John Carter" <john.carter@...> wrote:

**


Conversely, which books would you expect a TDD master to have read?

--
John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : john.carter@...
New Zealand

--

------------------------------
This email, including any attachments, is only for the intended recipient.
It is subject to copyright, is confidential and may be the subject of
legal
or other privilege, none of which is waived or lost by reason of this
transmission.
If you are not an intended recipient, you may not use, disseminate,
distribute or reproduce such email, any attachments, or any part thereof.
If you have received a message in error, please notify the sender
immediately and erase all copies of the message and any attachments.
Unfortunately, we cannot warrant that the email has not been altered or
corrupted during transmission nor can we guarantee that any email or any
attachments are free from computer viruses or other conditions which may
damage or interfere with recipient data, hardware or software. The
recipient relies upon its own procedures and assumes all risk of use and
of
opening any attachments.
------------------------------

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

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

Test Driven Development by Example (Kent Beck)


________________________________
From: John Carter <john.carter@...>
To: testdrivendevelopment@...
Sent: Tuesday, April 30, 2013 11:12 AM
Subject: [TDD] If you could get your colleagues to read just one book on TDD, which would it be?

?

Conversely, which books would you expect a TDD master to have read?

--
John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : mailto:john.carter%40taitradio.com
New Zealand

--

------------------------------
This email, including any attachments, is only for the intended recipient.
It is subject to copyright, is confidential and may be the subject of legal
or other privilege, none of which is waived or lost by reason of this
transmission.
If you are not an intended recipient, you may not use, disseminate,
distribute or reproduce such email, any attachments, or any part thereof.
If you have received a message in error, please notify the sender
immediately and erase all copies of the message and any attachments.
Unfortunately, we cannot warrant that the email has not been altered or
corrupted during transmission nor can we guarantee that any email or any
attachments are free from computer viruses or other conditions which may
damage or interfere with recipient data, hardware or software. The
recipient relies upon its own procedures and assumes all risk of use and of
opening any attachments.
------------------------------

Conversely, which books would you expect a TDD master to have read?

--
John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : john.carter@...
New Zealand

--

------------------------------
This email, including any attachments, is only for the intended recipient.
It is subject to copyright, is confidential and may be the subject of legal
or other privilege, none of which is waived or lost by reason of this
transmission.
If you are not an intended recipient, you may not use, disseminate,
distribute or reproduce such email, any attachments, or any part thereof.
If you have received a message in error, please notify the sender
immediately and erase all copies of the message and any attachments.
Unfortunately, we cannot warrant that the email has not been altered or
corrupted during transmission nor can we guarantee that any email or any
attachments are free from computer viruses or other conditions which may
damage or interfere with recipient data, hardware or software. The
recipient relies upon its own procedures and assumes all risk of use and of
opening any attachments.
------------------------------

We can only aspire! :-)
On Apr 22, 2013 3:02 AM, "Donaldson, John" <john.m.donaldson@...> wrote:

**


Charlie,

Drawing a parallel to sonnets from TDD - very nice!
But perhaps the even shorter haiku would be an even better analogy?
(Besides, it's hard to think of myself as the Shakespeare of unit-testing
:-))

John D.

-----Original Message-----
From: testdrivendevelopment@... [mailto:
testdrivendevelopment@...] On Behalf Of Charlie Poole
Sent: 20 April 2013 07:41
To: testdrivendevelopment@...
Subject: [TDD] Erroneous Assertion about TDD

Hi All,

Here's an excerpt from a newsletter I got from O'Reilly today...

"For many old-school software engineers, *developing code* has always been
*as much an art as a science*. But as the industry focuses more on
practices such as Test-Driven Development, and Patterns become the lingua
franca of programming, *is there any room left for real creativity in
coding?* Or, has it become an exercise in cookie-cutter production, putting
together components in new ways, but without any real room for individual
style?"

How can such misunderstanding can still exist? Anyway, they asked for
opinions and I sent this:

"I was a bit dismayed at your question "...as the industry focuses more on
practices such as Test-Driven Development, and Patterns become the lingua
franca of programming, is there any room left for real creativity in
coding?"

"I'll address the point as it applies to Test-Driven Development, since
that's closest to my heart. I'm an advocate of TDD as well as the
maintainer of NUnit, a unit-test framework that aims to facilitate TDD.

"To put it baldly, anyone who finds that Test-Driven Development stifles
their creativity simply isn't doing TDD as it's intended to be practiced.
The self-imposed discipline of first discovering tests that will require
the development of the production code we actually want to write is without
a doubt difficult to learn. But once it is learned, it's a source of great
creativity. Just as the strict form of the sonnet allowed Shakespeare to
channel his creativity, the discipline of TDD demands creativity from
developers who adopt it.

"Of course, doing TDD this way doesn't just happen. First and foremost, as
hinted in the preceding paragraph, it's a discipline that must be first
understood and chosen by the programmer - either as an individual or as
part of a team that decides to adopt TDD. Management-imposed TDD - like
most management-imposed technical practices - only succeeds in taking
responsibility away from the programmer.

"Test-Driven Development is a technique discovered and advocated by
programmers for programmers. It's a spark for creativity. When it's
reinterpreted as a set of rules to be imposed on the programmers, it can
easily have the opposite affect. But that's not unique to TDD. We've seen
it before with many other techniques and will likely see it again."

What do you think? Have you heard such complaints? What do you tell people
in response?

Charlie



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

Yahoo! Groups Links

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

Charlie,

Drawing a parallel to sonnets from TDD - very nice!
But perhaps the even shorter haiku would be an even better analogy?
(Besides, it's hard to think of myself as the Shakespeare of unit-testing :-))

John D.

The one that got me every single time is that 'it won't work in the real
world'.

That was before a management imposed 'embrace tdd' phase. Now I hear

* I spend more time writing/fixing my tests than my code.
* Writing tests for this code is impossible.. and I don't have the
authority/time to change the design
* Writing tests is boring, my code works.
* Maybe the test is wrong.. the best one I heard was 'I don't trust
automation'

All deeper systemic issues than deficiencies of TDD. Convincing everyone is
tiring.. There are no winners in verbal arguments.. I feel some teams just
aren't ready for TDD.

Waiting for people to turn around is usually slow enough as to warrant a
management push in most BigCos...but that leads to what I call 'compliance
TDD' or 'just enough to let me check in TDD' leading to tests that resist
change (instead of enabling them).

Maybe that's a source of the 'no creativity in programming anymore' - I
guess some people miss the speed at which they could write code that mostly
works, only they and the compiler could read and chuck it over the wall to
the testers. TDD absolutely chokes that one.

</Rant>

Hi All,

Here's an excerpt from a newsletter I got from O'Reilly today...

"For many old-school software engineers, *developing code* has always been *as
much an art as a science*. But as the industry focuses more on practices
such as Test-Driven Development, and Patterns become the lingua franca of
programming, *is there any room left for real creativity in coding?* Or,
has it become an exercise in cookie-cutter production, putting together
components in new ways, but without any real room for individual style?"

How can such misunderstanding can still exist? Anyway, they asked for
opinions and I sent this:

"I was a bit dismayed at your question "...as the industry focuses more on
practices such as Test-Driven Development, and Patterns become the lingua
franca of programming, is there any room left for real creativity in
coding?"

"I'll address the point as it applies to Test-Driven Development, since
that's closest to my heart. I'm an advocate of TDD as well as the
maintainer of NUnit, a unit-test framework that aims to facilitate TDD.

"To put it baldly, anyone who finds that Test-Driven Development stifles
their creativity simply isn't doing TDD as it's intended to be practiced.
The self-imposed discipline of first discovering tests that will require
the development of the production code we actually want to write is without
a doubt difficult to learn. But once it is learned, it's a source of great
creativity. Just as the strict form of the sonnet allowed Shakespeare to
channel his creativity, the discipline of TDD demands creativity from
developers who adopt it.

"Of course, doing TDD this way doesn't just happen. First and foremost, as
hinted in the preceding paragraph, it's a discipline that must be first
understood and chosen by the programmer - either as an individual or as
part of a team that decides to adopt TDD. Management-imposed TDD - like
most management-imposed technical practices - only succeeds in taking
responsibility away from the programmer.

"Test-Driven Development is a technique discovered and advocated by
programmers for programmers. It's a spark for creativity. When it's
reinterpreted as a set of rules to be imposed on the programmers, it can
easily have the opposite affect. But that's not unique to TDD. We've seen
it before with many other techniques and will likely see it again."

What do you think? Have you heard such complaints? What do you tell people
in response?

Charlie

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

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?

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?

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.

Hi everyone!

Interesting problem!

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



The history, per test



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 <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?

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

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

Adding to Matteo's suggestion, I find it useful in this situation to define
a string representation of the test tree. The implementing class can parse
the string to create trees to pass to the method under test and the string
can be displayed in error messages.

Charlie


On Tue, Apr 16, 2013 at 10:23 PM, Matteo Vaccari <vaccari@...> wrote:

**


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

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

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

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?