4

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.

Olivier Dulac
  • 3,695
  • 16
  • 31
Łukasz Lew
  • 48,526
  • 41
  • 139
  • 208
  • You want to write an AI that plays GO? Did you search CiteSeer or the ACM archives? – Ian Aug 29 '10 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. – Matthieu M. Aug 29 '10 at 11:48

4 Answers4

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.

tsiki
  • 1,638
  • 21
  • 34
  • 1
    In particular, Monte Carlo Tree Search might be the best starting term for Googling. See, for instance, http://sander.landofsand.com/publications/Monte-Carlo_Tree_Search_-_A_New_Framework_for_Game_AI.pdf – Larry OBrien Feb 15 '13 at 17:16
3

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

rano
  • 5,616
  • 4
  • 40
  • 66
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).

Daniel
  • 1,994
  • 15
  • 36
-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.

Jack
  • 131,802
  • 30
  • 241
  • 343
  • 2
    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. – Cerin Aug 29 '10 at 15:23
  • 3
    That taken together with the fact that there is no simple heuristic. Even deciding who has won a finished game is far from trivial. – ziggystar Aug 30 '10 at 07:38
  • 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. – Douglas Zare Oct 01 '14 at 07:53