Re: Implementation of game tree search using TDD

> haewke [email protected] 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.  http://industriallogic.com @IndustrialLogic
   Coaching | Training | Assessment | eLearning


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