December 4, 2015

Computer Go Game


This post is to gather some information on Go game (wikipedia) for myself and anyone who is interested in Go (Baduk) game.

Go game is a serious challenge for computer scientists as traditional algorithms will not work well for it.  It's because Go has very little rules but vast amount of possible games.  Brute force just will not work.  -- Chess has 10^120 possible games, Go has 10^761.  See above Wikipedia page.

Computer already has won human in Chess in 1997, but not yet for Go (as of Dec 2015).  Google and Facebook are working on this problem and Google's researcher Demis Hassabis hinted that his AI might win. (See [1], [2], [3], [4])

There has been a lot of effort in developing algorithms to play Go better than human, and there are many great Go game programs already that can beat amateur players.  I've been looking into this on and off for a while, and I know it's not a trivial problem.  But just trying and learn it, or just playing Go itself is fun.  I've gathered some information and put on this page for myself and for others who might be interested.

Try It Online

If you are completely new to this game, here is my suggestion:
  1. Read about it -- simple explanation here, more detailed information on Wikipedia.
  2. Learn it online.
  3. Practice playing against computer. (Requires Flash)
  4. Play against other people online. (Registration is not required)

Play Offline On Your Computer

If you want to play offline against computer, GNU Go is pretty good program.  Just like GNU Chess, GNU GO itself is a text based program, using GTP (Go Text Protocol). You will need GUI application to have nice user interface.

For Windows: get this GNU go binary, and GUI (Drago).  I tried a couple of other GUI, and I like this one best.  There are many GUI for Linux, and probably you can get both using package manager.  For OSX, I haven't tried yet -- I'll update it here when I actually try.

There are many Go programs for smart phones -- iOS, Android, and Windows Phone.  It's fun to play it while commuting on public transit.  See bottom of this posting for suggested S/W or you can just search app market for your device.

Go Algorithms

There are many books, web sites and YouTube videos for learning the game play and strategies.  I'm  interested in how Go algorithms are implemented.  There are also a lot of articles on algorithms, game engines, and source codes on the web -- see the links below.

Here is Wikipedia page on computer Go.  It has a wealth of information on algorithms and link to some programs.  These days, almost all late Go programs use Monte Carlo algorithm. (see Monte Carlo method, and this news article.  See also GNU Go's option.)  A recent computer Go winner developer interviewed and commented that Monte Carlo has improved Go AI significantly but unless someone come up with new algorithm, it'd not possible to level up its AI any further.  (May be Demis Hassabis found a breakthrough algorithm.)

To learn more about the algorithms, visit these pages after reading the Wikipedia page:

SGF, UGF

There are records of Go game plays that you can re-play to learn or may be even train your AI.  SGF (Smart Game Format) is one format for this. (See also Wikipedia page) 

There is another format called UGF but SGF seems to be more popular.

Current Computer Go Level

GNU Go or any other programs using GTP would be easier to develop your own algorithm and play against them.  But if you want really strong programs, check below.


[Disclaimer: I am not affiliated with any of the software companies nor I ever purchased/used any of them.]


. . . .


This should be a good starting point to get into Go game and learning the algorithms.  I'm really excited about what Demis Hassabis will announce.



Labels: , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)