Go, chess, computers

[JustinHorton]

Article in Wired about Go and the continued inability of computer programmers to create a program that will beat the top players (unlike another game we can think of).

Does anybody here possess the knowledge to tell us whether what the article says is accurate, and perhaps to comment further?

[stevencarr]

As far as I know, a Go playing program had been developed which could beat professionals when given a 4-stone handicap.

This is the very rough equivalent of a Knight head start for the computer.

So the article is accurate.


These sorts of Go programs perform very differently from chess playing programs. They play essentially millions of random games from the board position, trying to evaluate the chances.


No, I don't know how that works either.

[Roger de Coverly]

These sorts of Go programs perform very differently from chess playing programs. They play essentially millions of random games from the board position, trying to evaluate the chances.

It sounds like an approach from almost the beginning of numerical computing, sometimes known as the Monte Carlo method. If you don't really have a rule or set of rules that will help you select favourable outcomes, you run all possible outcomes and then select the results. In many chess positions, the Queen =9, Rook =5 approach gives a crude rule for evaluation of moves and positions and you can develop it from there.

Some chess engines will use a Monte Carlo approach in otherwise unfathomable endings to attempt to find the statistical best move.


(edit) Having read the article, it's the Monte Carlo method they are trying to make work. Chess can be relatively simple to program. So you test "I go there, it goes there, I take the Queen". That's easy to compute and is a straightforward way of concentrating on the most promising moves.

There was a reference to local tactical battles. Chess middle-games are full of these, but they aren't deceptive to the overall strategic position as appears the case in Go.

(/edit)

[Nick Thomas]

Backgammon programs use this approach, or at least used to.

[Christopher Kreuzer]

What approach was used in draughts?

[Roger de Coverly]

What approach was used in draughts?

I think it was much the same as chess, although the opening book theory and tablebases eventually met up, so the need for a middle game strategy was mostly avoided.

[MartinCarpenter]

Draughts actually got (essentially) totally solved - the search space was 'small' enough to just chunter through as per chess programs.

The search space in go is probably just about enormous enough to stop that approach ever being really sane there, although you never know.

[MartinCarpenter]

Actually, having thought about this, it occurs to me that if someone like Google really wanted to do this right now they probably could. Resources on the level of those thrown at deep blue say, although it'd take a while too.

The basic problem of using machine learning to decode most of how really strong players play go is incredibly intimidating but probably not that much more so than some of the machine learning problems that they are making a decent attempt at solving/have solved. You'd certainly expect to improve on the existing engines. Can't really see Google doing it of course, maybe some Chinese analogue will have a good go at it at some stage.

[Francis Fields]

The complexity of Go should not be underestimated.

I read (I think in a games programming book) that someone had calculated how complicated games were strategically. They considered the likelihood that one player would be expected to beat his opponent 2 to 1. They then said the better player was in a higher band. In chess (and bridge) there was deemed to be 16 bands, whereas in go the number was 40.


Francis

[Gerard Killoran]

Can I recommend The Master of Go by Yasunari Kawabata...

http://www.amazon.co.uk/Master-Go-Yasun ... 0224078186

...one of the best - if not the best - books about sport. Or anything else.

[stevencarr]

Another article on how purely random moves could be used by a computer to beat world-class players.

http://spectrum.ieee.org/robotics/artif ... go-be-next

[MartinCarpenter]

Fun That's the same sort of way they made progress in Bridge too, although some distinctly non trivial social issues there!

Its the sort of thing I was thinking of when I thought it should be possible to put a big dent in things if they threw as much effort at it as they did in chess.