Hacker News Reader

Comment by dutchflyboy | Hacker News Reader

Disclaimer: I don't play a lot of Go, I could be completely wrong.

That's probably due to the fact that in Go there are less intermidiary goals. In chess capturing a piece, defending a piece or simply making your position better by putting a bisshop on a diagonal can be seen as a step towards winning. Thus a chess AI doesn't need to go very deep before knowing which strategies are bad. For example, chess AI's written in JS often don't go much deeper than two steps ahead but still play quite decently.

But with Go you need to build chains made of several (often > 10) stones. And that sort of calculation is very heavy for brute-force style AI, which is about all a computer can resort to at this moment.

View on HN

I don't play a lot of chess, but it seems like there are more intermediate goals in go, but they're also more nebulous. Gaining center influence, threatening an opponent's weak group, cutting an opposing group into two groups, defending your own territory, making eyes, and reducing your opponent's territory are all important goals.

The best moves are ones that further two or more of these at the same time; it's very easy to lose if you're only concerned about one at a time.

I don't play a lot of Go either, but I've read some on the topic.

There are a few problems with modeling Go in AI. One of the biggest is that in Chess, you can more easily evaluate intermediary positions by material advantage. Positioning still matters, and there's plenty of times where a sacrifice is worth it, but material advantage is a serviceable enough quantitative measure. Go does not see captures as commonly, and emphasizes positioning more, which makes it harder to quantify.

The other problem is that (if I remember right) Go has more possibilities, so it's harder to look ahead as far. All grid intersections on the board are possible moves, and the board is bigger, while for chess the range of moves is more constrained. But really, this isn't the important part, because the forecast horizon of both games are finite, which means in both games at some point you have to stop looking at possibilities and evaluate board position of leaf nodes. And chess has a less-imperfect method for that.

But really, this isn't the important part, because the forecast horizon of both games are finite, which means in both games at some point you have to stop looking at possibilities and evaluate board position of leaf nodes. And chess has a less-imperfect method for that.

Actually, that makes a big difference. Because you can look ahead farther in chess, the intermediate scoring can be less accurate, as you have a real chance of looking far enough ahead to have turned your positional advantage into a material advantage.

Using the size of the board as a proxy for the number of legal moves, looking ahead N moves in chess requires evaluating approximately 64^N intermediate states, and go requires 361^N. That means that with equivalent computing power, looking ahead N moves in chess will let you look about N^0.177 in go. Thus, a computer that can look ahead 40 moves in chess wouldn't quite be able to look 2 moves ahead in go, without very aggressive pruning of the moves that it considers.

Right idea, wrong execution. If 64^N = 361^M then N log 64 = M log 361, so M = (log 64 / log 361) N ~= 0.71N. So if you could look 12 moves ahead in chess, this estimate would say you could manage 8 or 9 moves in go.

Unfortunately, it's worse than this. In practice, the effective branching factor in a chess tree-search is more like 3 than 64, roughly because lots of moves can quickly be found to be bad. I would be very surprised if the corresponding figure for go were less than, say, 30. So now your factor is log 3 / log 30, or more like 1/3.

On top of that, go games are much longer than chess games, so your search depth in go is a much smaller fraction of the whole game, so the search is a worse proxy for the final result. Slightly related to that: there's no nice simple measurement of how well you're doing that's comparable to measuring material in chess. (Your ultimate goal is to build territory, but it takes quite a while before any sort of quantitative estimate of how much territory each player has is feasible, especially if you want it to be anywhere near as cheap as a material count in chess.)

Reply on news.ycombinator.com