Re: Implementation of game tree search using TDD

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.




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

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/