3 ms·

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 looki

by kd5bjo 17y ago

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.

gjm11 17y ago
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.)

by kd5bjo 17y ago

gjm11 17y ago

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