Fear not, this weekend I reentered the ring, with a plan. First, I isolated the AlpaBeta pruning logic from the main search class, DoubleDummySolver. Then I attacked the AlphaBeta pruning itself, only to realize that it was a mess as well. Which brings me to the subject of today's post: working out a Domain Specific Language (DSL) for tree manipulation.
In the pruning tests, there's a need to create scenarios, where a tree of many nodes represents choices at any given point in play. To get a better idea, take a look at the following ASCII diagram for a simple case:
/* root W * / \ * (max:1) 0 1 S * / \ * (max:0) 1_0 1_1 E */
At the root, we have West to move, with two choices of cards to play, represented by nodes, 0 and 1. When choice 0 is made (and perhaps following full evaluation of node 0), we find out that West has scored 1 trick (that's the value of the max function at node 0, from standard computer science terminology). If, on the other hand, West makes choice represented by node 1, the next move belongs to his opponent, South. South, in turn also has two choices, and for ease of navigation, I chose to name them node 1_0, and node 1_1. This is to represent node's location in the tree from root: first take choice 1, then 0, arriving at node 1_0. It's probably not relevant, that at 1_0 and 1_1 East is to move, but what's important, is that after fully evaluating node 1_0, we find out that West has scored 0 tricks (value of max function is 0). It's at this stage that we have enough information to make a decision to forego the evaluation of node 1_1, which is the core idea behind Alpha Beta pruning.
As you can see, this diagram is very rich in information, which makes it difficult to represent in code, which in turn makes it hard to write and debug test cases. We need more than a dozen of these examples to describe AlphaBeta, and the diagrams get more complicated for the "deep" pruning scenarios, which is what I was hoping to implement. To get an idea of what the test cases looked like, see the straightforward representation in code of the above diagram:
public void testOneLevelAlphaPrune() {
Node root = new Node(null, WEST.getValue());
Node node_00 = new Node(root, WEST.getValue());
Node node_0 = new Node(node_00, SOUTH.getValue());
node_0.setTricksTaken(Player.WEST_EAST, 1);
Node node_1 = new Node(node_00, SOUTH.getValue());
Node node_1_0 = new Node(node_1, EAST.getValue());
@SuppressWarnings("unused")
Node node_1_1 = new Node(node_1, EAST.getValue());
node_1_0.setTricksTaken(Player.WEST_EAST, 0);
AlphaBeta ab = new AlphaBeta();
ab.prune(node_1_0);
assertTrue(node_1_0.isAlphaPruned());
assertTrue(node_1.isAlphaPruned());
}
Isn't it perfectly clear that this code builds a tree as per diagram? Ouch... This suffers from the same problem as the example in the previous post, where the solution was to abstract the test code into Beharior Driven style of GIVEN... WHEN... THEN. Alas, it's not so simple in this case, because we need to construct a tree and populate it with information while at the same time exposing all the relevant details in the test.
So after a day of experimenting with various approaches, I settled for the following abstraction:
public void testOneLevelAlphaPrune1() {
givenMax(WEST);
nodeWithPath("0").withTricksForMax(1).withNextTurn(SOUTH);
nodeWithPath("1").withNextTurn(SOUTH);
nodeWithPath("1", "0").withNextTurn(EAST).withTricksForMax(0);
nodeWithPath("1", "1").withNextTurn(EAST);
whenPruning(nodeWithPath("1", "0"));
assertTrue(nodeWithPath("1", "0").isAlphaPruned());
assertTrue(nodeWithPath("1").isAlphaPruned());
}
I hope that's readable to developers that come after me, and certainly to me a year from now.
The complete code is in the AlphaBetaTest class for now, but it will probably be pulled into some reusable test class eventually.
Posts
