Sunday, December 13, 2009

Frontline story from programming bidding conventions

When working on bidding overcalls last night I had one of those moments where I had to pause and take a look back. I was working on implementing the following from Pavlicek's excellent online beginners lessons (lesson 7):

If your right-hand opponent opens the bidding one of a suit and you have a five-card or longer suit (excluding the enemy suit), you may be able to make a suit overcall.

This plain English text turns out to be very information-dense.  The first part of the sentence, "If your right-hand opponent opens the bidding one of a suit," implies that one of the following bidding scenarios took place:
  • ONE-SUIT
  • PASS, ONE-SUIT
  • PASS, PASS, ONE-SUIT
 When trying to get that in code, I ended up quickly in a tangled web of statements like


if (bidCount==1 &&
    getCalls().get(0).getBid().getTrump().isSuit() &&
    getCalls().get(0).getBid().getValue() == 1
   ) {
     return true;
}


... and that was just the simplest case. Ever since I read in Kerevsky's book a story about Ward Cunningham's writing of a date constructor as november(20, 2005)[1], I have been a lot more careful about writing readable code even in obscure places. I rewrote the above a few times, and finally settled for the following:

public boolean mayOvercall() {
  if (bidCount == 1) {
    if (is1Suit(0)) {
      return true;
    }
  } else if (bidCount == 2) {
    if (isPass(0) && is1Suit(1)) {
      return true;
    }
  } else if (bidCount == 3) {
    if (isPass(0) && isPass(1) && is1Suit(2)) {
      return true;
    }
  }
  return false;
}

private boolean isPass(int i) {
  return PASS.equals(calls.get(i).getBid());
}

This is nothing terribly fancy, no domain specific language, just some appropriately named methods. The whole experience took about half an hour, and if you go back to the original specification, it is much clearer now why Gnubridge is still far from supporting Standard American bidding convention. Human language, especially when spoken by an expert, is incredibly dense. This is just an illustration of what has been a common experience to me in translating from user stories to code.

Another realization I had was how much easier it would have been to just go ahead and code it into a convoluted web of nested IFs and method calls. This was a small piece of a small bidding rule, and my time on the project is limited. I'm sure Gnubridge code is littered with this sort of unreadable garbage, and it was just a lucky call that made me rewrite it somewhat clearer. It seems like combating this sort of unreadable code is an uphill battle. I know we have coding standards, static analysis tools, peer review, etc. at our disposal to maintain code quality. And yet, based on this example, the code seems to naturally tend towards a chaotic mess. The expressive and readable code that comes from proper division of responsibilities is just an ephemeral occurrence, an unstable equilibrium about to roll back into chaos soon after attentive eye of a developer focuses away.


[1] Kerevsky, Refactoring to Patterns, chapter 2

Friday, November 27, 2009

What's NOT a good pruning strategy in Bridge - Part 2

In the previous post I have presented a counter-example to the following heuristic for selecting a move:
Among all cards that are impossible to win the current winning card, only the one with smallest rank is selected. [1]
My counter example only applied to the trick to be taken by partner. Last night I let Gnubridge look for counter examples when the trick was being taken by the opponent, and fairly quickly it came back with the following (Hearts are trump):


If East applies the strategy in question, he will play 5H, and arrive at the following position, after North plays 2H on the next trick:


East will take the next trick with 9H, but the last trick will be captured by South.

The correct play to North's JH in the first example would have been 9H, leading to the last two tricks being captured by East/West. Therefore, the above strategy is flawed, and should not be used in reducing the number of positions to analyze by double-dummy solvers.

As I understand this strategy is often taught to beginning bridge players, and it is still quite relevant in single dummy bridge, it's just that it is not always optimal. If a player possesses knowledge of distribution of all the cards remaining in play, he should avoid this mental shortcut in his analysis.

----
[1] Building a Fast Double-Dummy Bridge Solver – Ming-Sheng Chang, Ming-sheng Chang Phd Student - 1996

Sunday, October 25, 2009

What's NOT a good pruning strategy in Bridge - Part 1

In my spare time I look at academic papers for clues to optimize Gnubridge's double-dummy solver. In a frequently quoted 1996 paper, Chang proposes this pruning strategy:

Among all cards that are impossible to win the current winning card, only the one with smallest rank is selected. [1]
I have seen this strategy advocated in one other paper [2]. While it seems intuitive, it is flawed.

I implemented it in Gnubridge, and the stochastic equivalency checker quickly found counter examples. Take a look at the following position. West is to play and the trump is NT.


 If West follows the pruning strategy's advice, he'll play 4H and the pair will eventually lose the last trick when West plays 2D. If West correctly played 8H, the pair would win all tricks, by simply running the remaining hearts on East's hand.

Now the question remains - can this strategy be amended to only apply to cases when the opponent is winning the current trick and his high card cannot be beaten?



Wednesday, September 30, 2009

Build and Continuous Integration on Small Projects

Continuous Integration (CI) is a concept whose value is usually described in the context of projects of considerable size in terms of modules, environments, number of developers etc. The CI is seen on one hand as a tool to keep efforts of many developers and teams coordinated, and on another, to keep an eye on the complex environment in which code has to live. Yet even on a trivially small project like GNUBridge, consisting of one developer, one module,  and less than 10,000 lines of code, CI has provided considerable value.

First, it forced me to spell out the assumptions and weaknesses of the build process. My manual process involved running junit tests in the IDE, then building a jar and ftping it to the gnubridge.org website. Even in a simple process like this is prone to problems. First, a lot of bad things can happen between the time junit tests are run in the IDE and a jar is built. Key resources could be excluded from the jar. Classes could be compiled by the wrong compiler. Also, the manual FTP step could introduce a problem, like having ascii transfer mode. When I was automating the build in Ant, I made sure the jar was produced first, and then the unit tests were being run against the jar. If the tests pass, the jar gets published by the CI server.

Second, CI forced a separation of the application from my development environment. There are various features in any single environment that are not apparent until the build is attempted on another box in alien environment. In my case, the integration tests were instantiating invisible GUI components, and build was failing on the CI server which did not have X. This forced me to look at the architecture, and put to a test the MVC pattern that GNUBridge was supposed to follow. GNUBridge passed the test - in a couple of hours I had views replaced with mocks, with no significant detriment to code coverage statistics. The CI server also had a limit on the CPU time and memory that was considerably smaller than my box. Out of the window went expensive performance benchmarks. If GNUBridge ever needs them, they can be replaced with lightweight benchmarks. This saved me a couple of minutes in the test suite running time, making it practical once again to run the full suite every 20 minutes or so. Both of these restrictions imposed by the CI server forced discipline that made the architecture and development environment better.

In addition to architectural improvements, the separation between build and the development box had two more advantages. For one, it is now be assured that the tests do not rely on any artifacts that may be laying around. Second, it is easy for anyone else to get started by having everything that's needed available in the source code repository, and only needing the basic tools - subversion client, JDK and Ant to get going.

Along the same lines, any developer wishing to get a quick look at the state of the project, can see the commit frequency and what's being worked on. While I haven't implemented code metrics yet, when they come, it'll be one more axis along which the code can improve.

Another unimplemented feature which will reduce risk of bugs getting by are automatically run stochastic tests. These are exploratory tests with random inputs that discover interesting scenarios and verify that program's behavior is correct in situations that I may not have thought about or found relevant at the time I was writing my developer tests. I will be making a separate post on the importance of stochastic tests in GNUBridge. For stochastic tests to provide the most value, there needs to be a sufficiently large sample, but it's impractical for developer to run them frequently. So CI server is where they belong. 

Finally, while target audience are the developers, the CI server also provides important functionality to end users. They can get the bleeding edge product, tested in a fresh environment, along with an automated "what's new" feature listing pulled from commit comments. When reporting a problem, they can go back to an older version one commit at a time, making it much easier to pinpoint the source of a problem. There's an RSS feed that automatically alerts them of new features being available.

As with most of my software experiences, the full glory of these benefits was not apparent to me when I set out to do CI for GNUBridge. My motivation at the time was the automation of the stochastic tests, which ironically, still remains to be implemented. Based on the insights gained on this project, I think there are valid reasons to consider CI even on small projects.

  • January 10, 2010: CI server just exposed a bug in static initialization that was not a problem when working within the IDE.

  • January 24, 2010: CI server exposed a dependency of a production class on a test class
  •