Go questions

[Laskos]

I couldn't find clear answers to my stupid questions on other forums, I hope Remi or Don, or someone else can answer here.

1) Is the distributed df-UCT implemented in some current Go programs? It is claimed that df-UCT move selection doesn't hurt compared to UCT, but its speedup (with the number of cores) is dramatically better (almost linear as compared to UCT(TDS) pretty logarithmic speedup).

2) What is now the value of an effective factor of 2 speedup in Go? I remember something like 50 Elo points, but I don't really know where to find data on current programs which use MCTS UCT sorts.

3) What is the computer score 6d against 5d? Or 5d against 4d? I knew of something like 80% for lower dan (2d vs 1d), but this could be off for recent bots. I mean in current rankings on KGS, not separated in time, the ranking there seems to drift in time. What are the scores of the current engines self-playing with handicaps, 1 stone, 2 stones?

Thanks,

Kai

[Rémi Coulom]

I couldn't find clear answers to my stupid questions on other forums, I hope Remi or Don, or someone else can answer here.

1) Is the distributed df-UCT implemented in some current Go programs? It is claimed that df-UCT move selection doesn't hurt compared to UCT, but its speedup (with the number of cores) is dramatically better (almost linear as compared to UCT(TDS) pretty logarithmic speedup).

Yes, many programs have a distributed search. They scale rather well. You can take a look at pachi:
http://pachi.or.cz/
It was made to run efficiently on a 64*20-core cluster.

I don't have a distributed version of Crazy Stone. I found that on a single machine, it scales almost linearly up to 24 cores on 19x19. The Fuego team ran some experiments on some special IBM hardware, and found that scaling becomes difficult beyond 100 cores, IIRC.

2) What is now the value of an effective factor of 2 speedup in Go? I remember something like 50 Elo points, but I don't really know where to find data on current programs which use MCTS UCT sorts.

Against programs, I would say about 70 Elo on 9x9, about 100 Elo on 19x19. Probably less against humans.

3) What is the computer score 6d against 5d? Or 5d against 4d? I knew of something like 80% for lower dan (2d vs 1d), but this could be off for recent bots. I mean in current rankings on KGS, not separated in time, the ranking there seems to drift in time. What are the scores of the current engines self-playing with handicaps, 1 stone, 2 stones?

Thanks,

Kai

On KGS, a one-stone difference is about 230 Elo points around 5d.
http://senseis.xmp.net/?KGSRatingMath

It is important to understand that the Elo model is really very wrong when mixing humans and machines.

Rémi

[Daniel Shawul]

Yes, many programs have a distributed search. They scale rather well. You can take a look at pachi:
http://pachi.or.cz/
It was made to run efficiently on a 64*20-core cluster.

I don't have a distributed version of Crazy Stone. I found that on a single machine, it scales almost linearly up to 24 cores on 19x19. The Fuego team ran some experiments on some special IBM hardware, and found that scaling becomes difficult beyond 100 cores, IIRC.

Just to be clear, what algorithms are used and how is the speed up number computed ? With a simple "start from a different seed" approach that I have, the scaling is linear for any number of processors. But I don't share any nodes at the top, so separate tree is grown for each processor (probably too redundant though). And some papers I read also mention this kind of root splitting gives comparable performance (interms of elo gain) with other more complicated methods, so I didn't bother to implement them.

[Rémi Coulom]

Yes, many programs have a distributed search. They scale rather well. You can take a look at pachi:
http://pachi.or.cz/
It was made to run efficiently on a 64*20-core cluster.

I don't have a distributed version of Crazy Stone. I found that on a single machine, it scales almost linearly up to 24 cores on 19x19. The Fuego team ran some experiments on some special IBM hardware, and found that scaling becomes difficult beyond 100 cores, IIRC.

Just to be clear, what algorithms are used and how is the speed up number computed ? With a simple "start from a different seed" approach that I have, the scaling is linear for any number of processors. But I don't share any nodes at the top, so separate tree is grown for each processor (probably too redundant though). And some papers I read also mention this kind of root splitting gives comparable performance (interms of elo gain) with other more complicated methods, so I didn't bother to implement them.

I share the whole tree among all processors. I made a lockless data structure. You can find more info in those past emails to computer-go:
http://www.mail-archive.com/computer-go ... 07611.html

Edit: note that my playouts are now twice slower than what they were then, so scaling improved.

Rémi

[Daniel Shawul]

I share the whole tree among all processors. I made a lockless data structure. You can find more info in those past emails to computer-go:
http://www.mail-archive.com/computer-go ... 07611.html

Edit: note that my playouts are now twice slower than what they were then, so scaling improved.

Rémi

I think your method can give the best results on shared memory systems since it shares everything and avoids locking. The comparisons that I read about were mostly distributed algorithms that exchanges some of the nodes to coordinate simulations. As you mentioned in that post, you can extend it to a distributed hash table algorithm, but I prefer to use it as the algorithm to be used exclusively on "fat-nodes" (node with many processors). My distributed chess tree search actually works like that, and I haven't seen anyone does similar implement. It gets a bit complex with mixed SMP / distributed algorithm and probably not worth doing since MPI can do some optimization by itself on nodes with shared memory. But it will not be as good due to a poor distributed algorithm being used even on SMP systems.

[Laskos]

I couldn't find clear answers to my stupid questions on other forums, I hope Remi or Don, or someone else can answer here.

1) Is the distributed df-UCT implemented in some current Go programs? It is claimed that df-UCT move selection doesn't hurt compared to UCT, but its speedup (with the number of cores) is dramatically better (almost linear as compared to UCT(TDS) pretty logarithmic speedup).

Yes, many programs have a distributed search. They scale rather well. You can take a look at pachi:
http://pachi.or.cz/
It was made to run efficiently on a 64*20-core cluster.

I don't have a distributed version of Crazy Stone. I found that on a single machine, it scales almost linearly up to 24 cores on 19x19. The Fuego team ran some experiments on some special IBM hardware, and found that scaling becomes difficult beyond 100 cores, IIRC.

Thanks, I followed a bit your links in your later reply about the "lockless data structure", things are too technical to me, I cannot follow the papers.

2) What is now the value of an effective factor of 2 speedup in Go? I remember something like 50 Elo points, but I don't really know where to find data on current programs which use MCTS UCT sorts.

Against programs, I would say about 70 Elo on 9x9, about 100 Elo on 19x19. Probably less against humans.

3) What is the computer score 6d against 5d? Or 5d against 4d? I knew of something like 80% for lower dan (2d vs 1d), but this could be off for recent bots. I mean in current rankings on KGS, not separated in time, the ranking there seems to drift in time. What are the scores of the current engines self-playing with handicaps, 1 stone, 2 stones?

Thanks,

Kai

On KGS, a one-stone difference is about 230 Elo points around 5d.
http://senseis.xmp.net/?KGSRatingMath

It is important to understand that the Elo model is really very wrong when mixing humans and machines.

Rémi

I am referring to Elo here as percentage only, not a shape of the curve. Is it set by definition on KGS that 5d vs 4d performance is equal to 5d vs 5d handicap 1? Can one measure the "fair" computer (bot-bot) komi (maybe as a function of ranking)?

Thanks,

Kai

[Uri Blass]

I am surprised that the rating improvement from doubling is so high in go 19*19(100 elo in comp-comp games)

I thought that this game is hard for computers and it means less advantage for doubling the speed.

Some questions

1)Is there a game that is really hard for computers?(meaning that they do not get more than 10 elo per doubling and not because they play perfect or almost perfect).

2)Is there a diminishing returns in go?(meaning that the rating difference between 2 minutes and 1 minute is smaller than the rating difference between 2 seconds and 1 second or maybe people did not test it)

3)What is the rating difference between the best 19*19 go program and the best human and at what time control.

4)How much rating advantage do humans get from doubling their time?

[Laskos]

I am surprised that the rating improvement from doubling is so high in go 19*19(100 elo in comp-comp games)

I thought that this game is hard for computers and it means less advantage for doubling the speed.

Some questions

1)Is there a game that is really hard for computers?(meaning that they do not get more than 10 elo per doubling and not because they play perfect or almost perfect).

2)Is there a diminishing returns in go?(meaning that the rating difference between 2 minutes and 1 minute is smaller than the rating difference between 2 seconds and 1 second or maybe people did not test it)

3)What is the rating difference between the best 19*19 go program and the best human and at what time control.

4)How much rating advantage do humans get from doubling their time?

Until Remi answers, I will give a Wiki link to "Go ranks and rankings":
http://en.wikipedia.org/wiki/Go_ranks_and_ratings

The EGF ranking seems weird: some 340 (human) points between strongest humans and strongest bots (at short TC?). If (incorrectly) assuming human difference of points as equal to computer difference, means only ~10 times more computing power necessary for computers. I guess even 1,000 won't be enough.

I hope Remi or someone else will answer your questions.

Kai

[zamar]

I thought that this game is hard for computers and it means less advantage for doubling the speed.

That used to be the case until they found the way out...

1)Is there a game that is really hard for computers?(meaning that they do not get more than 10 elo per doubling and not because they play perfect or almost perfect).

Go used to be such a game until Monte Carlo techniques were invented.

"Being difficult for computer" = "nobody has put enough effort to invent better algorithms"

[Rémi Coulom]

I am surprised that the rating improvement from doubling is so high in go 19*19(100 elo in comp-comp games)

I thought that this game is hard for computers and it means less advantage for doubling the speed.

Some questions

1)Is there a game that is really hard for computers?(meaning that they do not get more than 10 elo per doubling and not because they play perfect or almost perfect).

2)Is there a diminishing returns in go?(meaning that the rating difference between 2 minutes and 1 minute is smaller than the rating difference between 2 seconds and 1 second or maybe people did not test it)

3)What is the rating difference between the best 19*19 go program and the best human and at what time control.

4)How much rating advantage do humans get from doubling their time?

Until Remi answers, I will give a Wiki link to "Go ranks and rankings":
http://en.wikipedia.org/wiki/Go_ranks_and_ratings

The EGF ranking seems weird: some 340 (human) points between strongest humans and strongest bots (at short TC?). If (incorrectly) assuming human difference of points as equal to computer difference, means only ~10 times more computing power necessary for computers. I guess even 1,000 won't be enough.

I hope Remi or someone else will answer your questions.

Kai

340 is obviously very wrong.

In handicap games vs pros, the current handicap is about 5 stones. That is more than 1000 Elo. Top programs have really no chance at all without handicap.

Also, there are diminishing returns. Here is an old 9x9 scalability study:
http://cgos.boardspace.net/study/index.html

But that study was computer vs computer. I guess that computer vs human has even bigger diminishing returns, although I have very little data. My experience is that I sometimes measure a 100 Elo improvement in Crazy Stone in comp vs comp, but get almost no improvement when connecting the new version to KGS.

An interesting aspect of computer go is that we have programs based on completely different algorithms. I found that a N-point Elo improvement against another Monte-Carlo program is usually worth N/2 points against a classical program such as GNU Go, and maybe even less against humans. So Elo ratings are a bit meaningless. It is important to understand how wrong the Elo model is.

I expect that if I could make Crazy Stone 1 million times faster, it would still not be enough to beat pros. We need better algorithms.

Rémi