Tuesday, March 15, 2011

Topics for this semester and questions about BIRS 2011

I still have plenty of topics to cover from the BIRS workshop about Combinatorial Games from January, but I want to do each of them justice. At the same time, I'm hoping to get more playable games up and running on my website. With any luck, I'll get some of this accomplished. There is a strong possibility posts will end a bit early this semester, as I'm expecting my first child the first week of May. :)

I haven't gotten to reply to the first comment here yet, so let me do that now.
What did Fan Xie said?
How strong is he?
How did the program worked? (Monte Carlo?)

Can you elaborate on that ? :)
Yes, I certainly can elaborate! I did not get to know Fan Xie terribly well, except to help badger him into joining the NoGo tournament. (He nearly did not play! Luckily, Neil McKay is a persuasive individual!) I didn't pay a great amount of attention to Fan's games, aside from his game against the winning NoGo program. This was a wonderful match, because Fan spent too much time analyzing and explaining whether the computer's moves were good or not (and he did not write that program). Instead of focusing on winning, he was answering everyone else's questions, so the computer came out ahead.

I believe all the computer programs used Monte Carlo (multiple random trial) techniques. From what I understand, they were all modified versions of UAlberta's Go-playing program FueGo. I would like to spend more time talking about this, but the most interesting thing is that these Monte Carlo programs are so easily adaptable from one game to the next. In fact, I believe much of the software is written independent of the different game rules. If you supply the rules, the simulations will run and choose a probable good move.

I am not convinced that this works well for all games, however! I'd like to know how well the algorithm plays Chess, or even Nim! (Maybe impartial games are tough...)


  1. Hi Kyle, there were six programs in the tournament, and only two (mine and Fan's) were based on Fuego. Olivier Teytaud's was based on MoGo (another strong Monte Carlo go-playing program).

    Of the others, Tristan's used alpha beta, and I believe JP's also used alpha beta (at least, I know it wasn't Monte Carlo). The remaining program, by Jean Mehat, may have used Monte Carlo, but I'm not sure.

  2. Bob,

    thanks for the first-hand account! I admit I wasn't really paying attention until the very end.

    Can you comment on how difficult it was to adapt Fuego to NoGo? Which programming language(s) is Fuego written in?

  3. Fuego is written in C++. Actually, it was harder than I expected to adapt it to NoGo. I wouldn't have managed it during the workshop without a lot of help from Martin Müller. It is a very powerful platform for Monte Carlo game playing, though, and if I were going to work in this area I would definitely use it as a starting point.

  4. Bob,

    is Fuego open source?

    Thanks again for your awesome comments! :)

  5. Yep!