BobNoGo started as a collaboration betwen Bob Hearn and Martin Müller at the 2011 BIRS workshop. Bob developed, tested (and rejected!) most of the NoGo-specific parts, while Martin helped with all technical aspects of Fuego to make the program run as smoothly as possible, and to disable Go-specific components of the program which do not make sense in NoGo. BobNoGo won all its "official" games in 2011-2012: it won the first ever computer NoGo competition at BIRS, the exhibition game against human champion Fan Xie, also at BIRS, the 2011 computer Olympiad and the 2012 TCGA championship. It finally met its match at the 2013 Olympiad where HappyNoGo won convincingly. See the History of NoGo and competitions for details. As of November 29, 2011, the version 0.1 of BobNoGo that won the Computer Olympiad has been available as open source.
Update Sep 18, 2014 Released a new version 0.2 of BobNoGo for the current Fuego svn revision 1937. Fixed a bug with the simulation move generator - some legal moves were not generated.
BobNoGo is implemented as a relatively simple patch to Fuego. The patch file that changes Fuego into BobNoGo is about 25K of text. The patch changes the rules of the game, and removes many Go-specific enhancements. The playouts are uniformly random on two levels: first, among points that both players can play. Second, if there are no such points, then choose uniformly randomly among the program's legal moves.
The program has a way to back up proven wins and losses. This is part of the UCT tree search that comes with Fuego. No game-specific NoGo code was used. The method is very simple and has been described in papers such as the Winands and Bjornsson paper in TCIAIG on Lines of Action. It is just the usual minimax rule. If one child in an OR node is a win, the node is a win. For an AND node all children must be wins. Similar for losses.
BobNoGo does not have a separate win/loss solver, it just solves the game when the UCT search backs up the result. Bob writes:
About my NoGo program -- actually, it's not especially interesting. Because Fuego is open source, I thought it made the most sense to start with that, and modify it to play NoGo instead of Go. It took a bit more effort than I expected to do this, but fortunately Martin Müller, one of the main authors, was also at the workshop, and helped me quite a bit.
Beyond a basic MCTS NoGo player, which is what I then had, there are basically two places in the Fuego architecture that one can add game-specific knowledge: playout heuristics, and prior knowledge used in node expansion.
If you have played NoGo, you know that the main goal is to accumulate spots that you can play, that your opponent cannot. It turns out that it's essentially never a good idea to play in such a spot unless you have to. So, the first thing I did is add that heuristic to the playouts, and that made the program much stronger.
After that I tried adding various kinds of prior knowledge to the node-expansion code. What I wanted to do was keep track of how many places I could play that my opponent could not, and vice-versa, using that to determine the node's prior knowledge. But there is an important technical problem that if I have, say, 5 places only I can play, that doesn't mean I can actually play all 5 of them. Maybe I can only play 3 or 4. I wrote some code that was reasonably efficient at computing the actual number I could play, and used that. However, it reduced the playouts / seconds by a factor of 3 or 4, and the gain in prior knowledge did not seem to make up for this -- the "smarter" version lost most games against the "dumber" version.
So, the program that I entered in the tournament was just the basic Fuego-based MCTS program, with the simple playout heuristic I described.
At the olympiad, BobNoGo used an opening book containing a total of 16 moves. These moves were pulled from test games played under olympiad tournament conditions. Their main effect is to save some thinking time. BobNoGo usually plays its first one or two moves from book.
patch -p0 < nogo1937.patch
patch -p0 < bobnogo-1523+nolimit.patch
<nogo>/fuego/build/dbg/fuegomain/fuego
<nogo>/fuego/build/dbg/fuegomain/fuegoOptionally, you can use a config file as follows:
<full path>/fuego --config myConfigFile.gtp
<nogo>/fuego/build/dbg/fuegotest/fuego_test --player random
Martin Müller