codecentric challenge 2014

Man vs. Machine

This fall will see a first in the realm of computer go – a match between a go program and a top European go player on even terms, i.e. without a handicap. And codecentric will be the sponsor of this event. So this will not be your typical codecentric blog post – no hints or strategy around java, agile development, software quality or similar topics. Instead I want to speak about the game of go and computer go – the one topic about as ancient as it gets for games, the other one from the forefront of technology.

Go, the Last Fortress

You may have heard of the east asian board game go being something like the last frontier in computer gaming, the one classic game where humans still outplay even the strongest computer programs. In a certain sense this is true. Chess was conquered in 1997 by the epochal win of IBM’s Deep Blue against then world champion Garry Kasparov. Today, a standard chess program on a typical notebook can probably beat the human world champion. In checkers and backgammon humans are hopeless contenders, too.

For go it is another matter. The game mechanics are extremely simple, as a look at the rules reveals (www.usgo.org ). But if you have never played go before and just read the rules, you are probably baffled at the question when the game ends and how to discern the winner. This gives a first hint about the complexity of go: It is quite hard to come up with a good, heuristic algorithm to evaluate a go position – who is ahead and by how much? Another reason why it is so difficult to apply the traditional game tree search algorithms to go that work so well for chess is the sheer size of the go board with its 19×19 intersections. On average, there are 25 different possible moves in a given chess position. In go, you start with 361 and drop slowly down to say 100 or 50. A game of chess lasts for something like 80 (half) moves on average, a game of go for 200 to 300. All this means that there are a lot more numbers to crunch in go than in chess. Accordingly, go programs could look ahead far less than their chess relatives, and up to a few years ago the average go player could easily defeat any go program.

Monte Carlo Algorithms

Enter Monte Carlo methods. One other possible way to come to grips with the vast game tree of go is to replace the knowledge-based classical game-tree search with chance, using random moves to play out certain positions multiple times and determine this way which move might be most promising. As this is completely contrary to the way we humans play and think about go, this approach was largely neglected for a long time. But in the last couple of years, go programming has made enormous progress using Monte Carlo methods. The best programs begin to approach top amateur level.

Challenging Top Human Players

Since 2007 the University of Electro-Communications in Japan hosts the “UEC Cup Computer Go”, something like an inofficial world championship of go programs. Until the recent advances with Monte Carlo methods, computer go was not taken very seriously in the go world. But since 2013, the Nihon Ki-in, the most prominent Japanese professional go players association, agreed that professional go players will play against the strongest contenders of the UEC Cup. For the last few years, the two strongest go programs have consistently been the Japanese program “Zen” and French programmer Rémi Coulom’s “Crazy Stone”. In the play-offs against professional go players in 2013 and 2014, the programs were given a four stone handicap. To offer some perspective: Only an already really strong amateur could hope to beat a professional go player with such a handicap. While Zen was defeated both years, Crazy Stone managed to eke out wins against the professionals, leaving open the question how big the gap in strength between the best go programs and the professional level really is.

codecentric challenge 2014

In a few weeks, the “codecentric challenge 2014” will pit Crazy Stone against Franz-Josef Dickhut in a five game match, played online on the KGS go server. Dickhut is an amateur 6 dan and eleven times German go champion. In the realm of amateur go, it doesn’t get much stronger than this. No stronger player has ever before agreed to play a serious competition against a go program on even terms, without a handicap. That the winner will not be decided in a single game but in a best-of-five match, gives the challenge additional weight. The first game will be played on Saturday, October 4th, with the other games following on a weekly schedule until one side has registered three wins.

The match was proposed and organized by Prof. Ingo Althöfer of the University of Jena, Germany, who is active in researching the mathematics of games and game programming for some decades now. codecentric on the other hand has agreed to sponsor the event and host the website of the competition. The link to the website will be published here in time before the match begins.

I hope I have been able to awaken your interest in this fascinating game and the oncoming human-computer duel. Stay tuned!