Re: Implementation of game tree search using TDD

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: http://chessprogramming.wikispaces.com/Alpha-Beta
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?

--- In [email protected], "wwake2" <bill@...> wrote:
>
> 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.  http://industriallogic.com @IndustrialLogic
>    Coaching | Training | Assessment | eLearning



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

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/