Computational Complexity of Games
Kyle (noreply@blogger.com)
At BIRS this year, the game everyone was interested in was Go . I guess it's hard to compete with that! Aside from Go, one of the big features was NoGo . We had the first ever NoGo world tournament, both for humans and computers. After those tournaments were over, Fan Xie, the reigning human champion, battled Bob Hearn's champion NoGo-playing program. When presented with a new game like NoGo, as a computer scientist I'm always interested in the computational complexity: how hard is it to