Algorithms to play Game of Go?

Question

What is the state of the art of algorithms to play the game of Go ?
Which articles (describing algorithms) are best to read ?

There is a StackExachge site devoted to Go, but not enough people commited to ask the question there.

Answer 1

The Amirim project tried to use a minimax approach combining ab-pruning and partition search methods to get a Go AI working. They seemed to have some success but I don't remember them proving their AI by playing it against human opponents.

I suggest you lookup partition search.

Unfortunately the link I had to the Amirim project is now dead (here).

Answer 2

I implemented something similar it in Prolog by using alpha-beta pruning.. This kind of approach can be used easily with Go since it is a perfect information game in which

• every possible move is known
• the state of the game is completely known

You could start from Minimax trees and then dig deeper which clever approaches like AB-pruning, negmax and so on.

The cool thing is that you can first develop the engine that works out the best move and then try to find the best heuristic (also by letting your AIs play one against the other to see which one is smarter) that decides how much good is a move.

Of course finding a good heuristic is the part of the implementation in which you have to study the rules of the game and that requires to think about various strategies.. so it is the more complex one but also the funniest.

Answer 3

All the current top bots use Monte Carlo -based algorithms. They're usually heavily adapted to Go and have many additional layers to support the MC algorithm in predicting the outcome of each move. You can look at an open source bot such as Fuego for an example.

Answer 4

This is the most basic resource start, but it is quite complete I dare to say