3

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.

Improve this question
2
  • You want to write an AI that plays GO? Did you search CiteSeer or the ACM archives? Commented Aug 29, 2010 at 11:10
  • 2
    I must admit I find it amazing that a game with such simple rules could be one of the "last one standing" game where top players still beat computers hands down... of course the board size certainly helps here. Commented Aug 29, 2010 at 11:48

4 Answers 4

Reset to default
7

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

In particular, Monte Carlo Tree Search might be the best starting term for Googling. See, for instance, sander.landofsand.com/publications/…
3

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

Improve this answer

Comments

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).

Improve this answer

Comments

-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.

Improve this answer

3 Comments

Although minimax with AB pruning can technically be used, the immense state space of Go makes it impractical, if not entirely useless. It's estimated there are more Go states than atoms in the universe. You could parse a minimax tree to the end of time and still not play better than a human.
That taken together with the fact that there is no simple heuristic. Even deciding who has won a finished game is far from trivial.
The difficulty in evaluating positions is far more important than the size of the search space. In chess, there is a simple linear heuristic that bishops are worth 3 times as much as a pawn, etc. There is nothing similar that you can compute to evaluate a go position, even one that isn't close. If you move chess to a larger board, so that there are more possible positions, the piece evaluations may need to be modified but there is probably still a simple linear evaluator that you can use to identify lopsided positions. Without that, AIs can't bootstrap toward reasonable play.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.