Gongo: Go in Go
201 views
Skip to first unread message
Brian Slesinsky
Nov 30, 2009, 5:26:09 AM11/30/09
to golan...@googlegroups.com
As my first real program in Go, I wrote a program that plays Go (the
traditional board game). More details and source code here:
http://github.com/skybrian/Gongo
traditional board game). More details and source code here:
http://github.com/skybrian/Gongo
John Asmuth
Nov 30, 2009, 11:12:26 AM11/30/09
to golang-nuts
So, I didn't browse your source so maybe you are doing this, but
cutting-edge go (the game) algorithms seem very appropriate for
implementation in go (the language). In short, the go (the game) agent
will simultaneously play many games against a semi-heuristic/semi-
learning opponent. Being able to spawn off these roll-outs, as they're
called, with the very low code overhead in go (the language) might be
kind of fun.
(roll-outs as opposed to branching searches, such as minimax. a roll-
out will play a single game to completion, choosing exactly one branch
to take all the waydown)
- John
cutting-edge go (the game) algorithms seem very appropriate for
implementation in go (the language). In short, the go (the game) agent
will simultaneously play many games against a semi-heuristic/semi-
learning opponent. Being able to spawn off these roll-outs, as they're
called, with the very low code overhead in go (the language) might be
kind of fun.
(roll-outs as opposed to branching searches, such as minimax. a roll-
out will play a single game to completion, choosing exactly one branch
to take all the waydown)
- John
John Asmuth
Nov 30, 2009, 11:17:03 AM11/30/09
to golang-nuts
Upon scanning the code, it appears that this is *exactly* what you're
doing ;)
doing ;)
gorgo...@online.de
Nov 30, 2009, 3:03:02 PM11/30/09
to golan...@googlegroups.com
http://go-lang.cat-v.org/
this is a bit of an early freshmeat for go code. registering gongo
would help others finding it, i think? it also helps me remembering
it ;)
--
GorgonZola <gorgo...@online.de>
Brian Slesinsky
Nov 30, 2009, 4:00:58 PM11/30/09
to golang-nuts
Looks like someone already did?
> Brian Slesinsky <bslesin...@gmail.com> wrote:
> > As my first real program in Go, I wrote a program that plays Go (the
> > traditional board game). More details and source code here:
>
> >http://github.com/skybrian/Gongo
>
> could you please register gongo at:
>
> http://go-lang.cat-v.org/
>
> this is a bit of an early freshmeat for go code. registering gongo
> would help others finding it, i think? it also helps me remembering
> it ;)
>
> --
> GorgonZola <gorgonz...@online.de>
> > As my first real program in Go, I wrote a program that plays Go (the
> > traditional board game). More details and source code here:
>
> >http://github.com/skybrian/Gongo
>
> could you please register gongo at:
>
> http://go-lang.cat-v.org/
>
> this is a bit of an early freshmeat for go code. registering gongo
> would help others finding it, i think? it also helps me remembering
> it ;)
>
> --
Brian Slesinsky
Nov 30, 2009, 4:13:09 PM11/30/09
to golang-nuts
The "standard" way of writing a Go bot these days combines UCT (a kind
of probabilistic tree search) with a Monte Carlo method using random
games. This bot only does the Monte Carlo part without any tree, so
it's fairly dumb. The reason for doing it this way is to have a
standard algorithm that's relatively easy to implement so we can
compare varying approaches to the implementation - for example, using
different languages.
Currently Gongo is much slower than the Java reference bot when using
the gc compiler. I've written it with gccgo in mind (avoiding creating
any garbage in a loop) but haven't tried it yet. I also haven't done
any profiling yet; I suspect the random number generator might be slow
but that's a wild guess.
It's also single-threaded; fixing that is another feature.
- Brian
of probabilistic tree search) with a Monte Carlo method using random
games. This bot only does the Monte Carlo part without any tree, so
it's fairly dumb. The reason for doing it this way is to have a
standard algorithm that's relatively easy to implement so we can
compare varying approaches to the implementation - for example, using
different languages.
Currently Gongo is much slower than the Java reference bot when using
the gc compiler. I've written it with gccgo in mind (avoiding creating
any garbage in a loop) but haven't tried it yet. I also haven't done
any profiling yet; I suspect the random number generator might be slow
but that's a wild guess.
It's also single-threaded; fixing that is another feature.
- Brian
Don Dailey
Nov 30, 2009, 4:22:11 PM11/30/09
to golang-nuts
I have also done these same types of monte carlo go programs but not
in the go language.
But I'm considering the possibility of trying to write a world class
parallel chess program in Go! It's not going to be possible unless
Go gets reasonably close to the speed of C, but I think it will in
time. Even if it's half speed compared to C I am confident that it
can still be one of the better chess programs but it really needs to
be close to C speed for this particular thing where 30 or 40% would be
a major handicap.
It's ironic to me that Ken Thompson, one of the go creators is famous
for building a chess computer that dominated computer chess for a few
years. So it would be rather cool to honor him with a very strong
chess program in a language he created!
- Don
in the go language.
But I'm considering the possibility of trying to write a world class
parallel chess program in Go! It's not going to be possible unless
Go gets reasonably close to the speed of C, but I think it will in
time. Even if it's half speed compared to C I am confident that it
can still be one of the better chess programs but it really needs to
be close to C speed for this particular thing where 30 or 40% would be
a major handicap.
It's ironic to me that Ken Thompson, one of the go creators is famous
for building a chess computer that dominated computer chess for a few
years. So it would be rather cool to honor him with a very strong
chess program in a language he created!
- Don
Brian Slesinsky
Dec 1, 2009, 1:15:50 AM12/1/09
to golang-nuts
I timed self-play of a complete game, using Gogui on 9x9 board:
java -server -jar javabot/jrefgo.jar - 3 seconds per side
Gongo compiled with gogcc - 13 seconds per side.
I'm probably doing something silly. Time to get out the profiler.
java -server -jar javabot/jrefgo.jar - 3 seconds per side
Gongo compiled with gogcc - 13 seconds per side.
I'm probably doing something silly. Time to get out the profiler.
Jim Rueschhoff
Dec 1, 2009, 7:34:02 AM12/1/09
to Don Dailey, golang-nuts
Most chess programs are brute force affairs where speed and multi-processing rules. Go is probably not going to be a competitive language for chess soon.
The game go however defies brute force methods because of the huge move tree. The Go language will be efficient enough and offers many good features to be able to implement a skill based Go playing program. The game Go is an excellent problem where innovative skill based programing can offer great results without a supercomputer.
--
Jim Rueschhoff
Glendale Arizona
jrues...@gmail.com
jru...@rueschhoff.com
The game go however defies brute force methods because of the huge move tree. The Go language will be efficient enough and offers many good features to be able to implement a skill based Go playing program. The game Go is an excellent problem where innovative skill based programing can offer great results without a supercomputer.
Jim Rueschhoff
Glendale Arizona
jrues...@gmail.com
jru...@rueschhoff.com
Don Dailey
Dec 1, 2009, 10:27:53 AM12/1/09
to Jim Rueschhoff, golang-nuts
The game go does not, nor ever has defied brute force methods. It is now required to come to tournaments with the best hardware possible in order to be competitive, just like in chess. For instance in a recent competition we saw an 8-core 16 thread Xeon PC. In some exhibition matches programs are running on monster machines with 32 or 64 cores or more in order to play better.
Since Go programs are now tree based, like chess, it's all about the speed. But that would be true even if it were not tree based - the only reason it has not seemed so in the past was because go program authors did not know how to implement knowledge in a scalable way. The common wisdom on this seems to be that the more sophisticated the game, the less CPU power is needed to play it well, but that is one of those many silly computer myths floating around. Part of the problem lies in the phrase "brute force" which implies that you should do something as stupidly as possible so that you can do it fast. But this is nonsense. You should do it as smart as possible and do it fast too (so that you can do more.) BOTH require CPU power.
But that is off topic. The reason I am considering using Go for chess is that it might facilitate more experimentation and it would be superbly cool. If I came up with something impressive I could always recode it in C, just using go as my vehicle to get there, but it's difficult, time consuming and disruptive to do many kinds of experiments in C, so you take shortcuts or you just don't bother trying.
One this is clear to me though. A huge percentage of my chess development time is testing and I'm running test matches 24/7 and if go is say 2x slower than C, it's probably not viable as I cannot get enough testing horsepower as it is. Having only 1 quad core computer to test on is by far the biggest bottleneck I have and doing this in go (might be) like throwing away half of my testing resources. However I don't really have a sense for what the difference is but I would find out quickly if I started such a project.
Since Go programs are now tree based, like chess, it's all about the speed. But that would be true even if it were not tree based - the only reason it has not seemed so in the past was because go program authors did not know how to implement knowledge in a scalable way. The common wisdom on this seems to be that the more sophisticated the game, the less CPU power is needed to play it well, but that is one of those many silly computer myths floating around. Part of the problem lies in the phrase "brute force" which implies that you should do something as stupidly as possible so that you can do it fast. But this is nonsense. You should do it as smart as possible and do it fast too (so that you can do more.) BOTH require CPU power.
But that is off topic. The reason I am considering using Go for chess is that it might facilitate more experimentation and it would be superbly cool. If I came up with something impressive I could always recode it in C, just using go as my vehicle to get there, but it's difficult, time consuming and disruptive to do many kinds of experiments in C, so you take shortcuts or you just don't bother trying.
One this is clear to me though. A huge percentage of my chess development time is testing and I'm running test matches 24/7 and if go is say 2x slower than C, it's probably not viable as I cannot get enough testing horsepower as it is. Having only 1 quad core computer to test on is by far the biggest bottleneck I have and doing this in go (might be) like throwing away half of my testing resources. However I don't really have a sense for what the difference is but I would find out quickly if I started such a project.
Horace Blegg
Dec 3, 2009, 5:59:51 AM12/3/09
to golang-nuts
Hello Don Dailey,
I'm curious if you would be willing to share some introductory information on writing AI's for Go and Chess? Perhaps writing AI's in general? I have an idea for a project that would involve an AI (or something like an AI, basically an algorithm making decisions based on input and past experience) and don't really know how to approach it. I'm mainly interested in general knowledge on the subject (of which there is a lot), and I'm interested in finding out what you found/find useful in terms of resources?
Slightly off-topic, sorry.
I'm curious if you would be willing to share some introductory information on writing AI's for Go and Chess? Perhaps writing AI's in general? I have an idea for a project that would involve an AI (or something like an AI, basically an algorithm making decisions based on input and past experience) and don't really know how to approach it. I'm mainly interested in general knowledge on the subject (of which there is a lot), and I'm interested in finding out what you found/find useful in terms of resources?
Slightly off-topic, sorry.
Dan Andersson
Dec 3, 2009, 11:57:19 AM12/3/09
to golang-nuts
Chess:
http://chessprogramming.wikispaces.com/
Go:
http://senseis.xmp.net/?ComputerGoProgrammingPapers
http://www.citeulike.org/group/5884/library
Communities with massive amounts of experience:
Talkchess
Winboard Forum
Computer Go Mailing List
/Dan
> >> jrue...@rueschhoff.com
http://chessprogramming.wikispaces.com/
Go:
http://senseis.xmp.net/?ComputerGoProgrammingPapers
http://www.citeulike.org/group/5884/library
Communities with massive amounts of experience:
Talkchess
Winboard Forum
Computer Go Mailing List
/Dan
> > On Tue, Dec 1, 2009 at 7:34 AM, Jim Rueschhoff <jrueschh...@gmail.com>wrote:
>
> >> Most chess programs are brute force affairs where speed and
> >> multi-processing rules. Go is probably not going to be a competitive
> >> language for chess soon.
>
> >> The game go however defies brute force methods because of the huge move
> >> tree. The Go language will be efficient enough and offers many good
> >> features to be able to implement a skill based Go playing program. The
> >> game Go is an excellent problem where innovative skill based programing can
> >> offer great results without a supercomputer.
>
>
> >> Most chess programs are brute force affairs where speed and
> >> multi-processing rules. Go is probably not going to be a competitive
> >> language for chess soon.
>
> >> The game go however defies brute force methods because of the huge move
> >> tree. The Go language will be efficient enough and offers many good
> >> features to be able to implement a skill based Go playing program. The
> >> game Go is an excellent problem where innovative skill based programing can
> >> offer great results without a supercomputer.
>
> >> On Mon, Nov 30, 2009 at 2:22 PM, Don Dailey <dailey....@gmail.com> wrote:
>
> >>> I have also done these same types of monte carlo go programs but not
> >>> in the go language.
>
> >>> But I'm considering the possibility of trying to write a world class
> >>> parallel chess program in Go! It's not going to be possible unless
> >>> Go gets reasonably close to the speed of C, but I think it will in
> >>> time. Even if it's half speed compared to C I am confident that it
> >>> can still be one of the better chess programs but it really needs to
> >>> be close to C speed for this particular thing where 30 or 40% would be
> >>> a major handicap.
>
> >>> It's ironic to me that Ken Thompson, one of the go creators is famous
> >>> for building a chess computer that dominated computer chess for a few
> >>> years. So it would be rather cool to honor him with a very strong
> >>> chess program in a language he created!
>
> >>> - Don
>
> >>> On Nov 30, 5:26 am, Brian Slesinsky <bslesin...@gmail.com> wrote:
> >>> > As my first real program in Go, I wrote a program that plays Go (the
> >>> > traditional board game). More details and source code here:
>
> >>> >http://github.com/skybrian/Gongo
>
> >> --
> >> Jim Rueschhoff
> >> Glendale Arizona
> >> jrueschh...@gmail.com
>
> >>> I have also done these same types of monte carlo go programs but not
> >>> in the go language.
>
> >>> But I'm considering the possibility of trying to write a world class
> >>> parallel chess program in Go! It's not going to be possible unless
> >>> Go gets reasonably close to the speed of C, but I think it will in
> >>> time. Even if it's half speed compared to C I am confident that it
> >>> can still be one of the better chess programs but it really needs to
> >>> be close to C speed for this particular thing where 30 or 40% would be
> >>> a major handicap.
>
> >>> It's ironic to me that Ken Thompson, one of the go creators is famous
> >>> for building a chess computer that dominated computer chess for a few
> >>> years. So it would be rather cool to honor him with a very strong
> >>> chess program in a language he created!
>
> >>> - Don
>
> >>> On Nov 30, 5:26 am, Brian Slesinsky <bslesin...@gmail.com> wrote:
> >>> > As my first real program in Go, I wrote a program that plays Go (the
> >>> > traditional board game). More details and source code here:
>
> >>> >http://github.com/skybrian/Gongo
>
> >> --
> >> Jim Rueschhoff
> >> Glendale Arizona
> >> jrue...@rueschhoff.com
Brian Slesinsky
Dec 5, 2009, 9:47:36 PM12/5/09
to golang-nuts
Spent some time with the profiler. It turned out most of the time was
spent in markSurroundedChain(), which contained a loop on each
cardinal direction (up, down, left, right) that could be profitably
unrolled. After a few more microoptimizations, I was able to improve
Gongo's performance a bit:
Before: 5.0k to 5.3k playouts/second
After: 6.3k to 6.6k playouts/second
Versus: 6.2k to 6.8k for the Java reference bot (without the same
optimizations applied)
Looking at the assembly, it looks like there's a lot that an optimizer
could do, such as getting rid of jumps to jumps and avoiding array
index checks. I'll try it out on gccgo next week.
Profiler output (after):
77 samples (avg 1 threads)
28.57% gongo·*board·markSurroundedChain
12.99% gongo·*board·playRandomGame
11.69% gongo·*board·wouldFillEye
9.09% dodiv
6.49% gongo·*robot·findWins
5.19% rand·*Rand·Int63
3.90% _div64by32
3.90% gongo·*board·makeMove
3.90% rand·*Rand·Intn
2.60% _modv
2.60% rand·*rngSource·Int63
1.30% etext
1.30% gongo·*board·capture
1.30% gongo·*board·copyFrom
1.30% gongo·*board·getEasyScore
1.30% rand·*Rand·Int63n
1.30% runtime·uint64mod
Notes:
http://github.com/skybrian/Gongo/blob/master/optimize_notes.txt
spent in markSurroundedChain(), which contained a loop on each
cardinal direction (up, down, left, right) that could be profitably
unrolled. After a few more microoptimizations, I was able to improve
Gongo's performance a bit:
Before: 5.0k to 5.3k playouts/second
After: 6.3k to 6.6k playouts/second
Versus: 6.2k to 6.8k for the Java reference bot (without the same
optimizations applied)
Looking at the assembly, it looks like there's a lot that an optimizer
could do, such as getting rid of jumps to jumps and avoiding array
index checks. I'll try it out on gccgo next week.
Profiler output (after):
77 samples (avg 1 threads)
28.57% gongo·*board·markSurroundedChain
12.99% gongo·*board·playRandomGame
11.69% gongo·*board·wouldFillEye
9.09% dodiv
6.49% gongo·*robot·findWins
5.19% rand·*Rand·Int63
3.90% _div64by32
3.90% gongo·*board·makeMove
3.90% rand·*Rand·Intn
2.60% _modv
2.60% rand·*rngSource·Int63
1.30% etext
1.30% gongo·*board·capture
1.30% gongo·*board·copyFrom
1.30% gongo·*board·getEasyScore
1.30% rand·*Rand·Int63n
1.30% runtime·uint64mod
Notes:
http://github.com/skybrian/Gongo/blob/master/optimize_notes.txt
Ben Bullock
Dec 5, 2009, 9:55:36 PM12/5/09
to golang-nuts
On Dec 6, 11:47 am, Brian Slesinsky <bslesin...@gmail.com> wrote:
> Looking at the assembly, it looks like there's a lot that an optimizer
> could do, such as getting rid of jumps to jumps and avoiding array
> index checks.
For the "jumps to jumps", please see the following thread:
> Looking at the assembly, it looks like there's a lot that an optimizer
> could do, such as getting rid of jumps to jumps and avoiding array
> index checks.
http://groups.google.com/group/golang-nuts/browse_frm/thread/ecfac150c472bf23/f7298b4033b8dc46
Brian Slesinsky
Dec 6, 2009, 11:40:00 PM12/6/09
to golang-nuts
Spent a big more time optimizing Gongo and now it's quite a bit faster
than the Java reference bot.
Current standings:
Gongo: 9.5 -10.2k playouts/second
Java refbot: 6.2 - 6.8k
Orego 6.10: 16.5 - 17.2k
Orego is another Go bot written in Java. It's an apples-to-oranges
comparison because it's a different (and smarter) algorithm, but I
figured it's time to set my sights higher.
Gongo is no longer a straight port of the refbot; there's an
additional array to track the number of liberties for each point,
which helps cut down on array accesses of neighbor points. However,
the biggest win was when I ran the profiler with the -hs option and
discovered that 40% of the time was being spent in the random number
generator. (The core generator itself is fast, but doing a 64 bit
divide on a 32 bit CPU is slow.)
Filed a bug for this: http://code.google.com/p/go/issues/detail?id=390
Current profile:
147 samples (avg 1 threads)
29.93% 29.93% gongo·*board·markSurroundedChain
21.77% 52.38% gongo·*board·makeMove
15.65% 88.44% gongo·*board·playRandomGame
8.84% 12.24% gongo·*randomness·Intn
8.84% 8.84% gongo·*board·wouldFillEye
8.16% 96.60% gongo·*robot·findWins
3.40% 3.40% rand·*rngSource·Int63
1.36% 1.36% gongo·*board·getEasyScore
0.68% 8.16% gongo·*board·hasLiberties
0.00% 96.60% goexit
0.00% 96.60% gongo·*robot·GenMove
0.00% 96.60% mainstart
0.00% 96.60% main·main
0.00% 22.45% gongo·*board·capture
0.00% 0.68% MHeap_LookupMaybe
0.00% 0.68% etext
0.00% 0.68% os·*File·Write
- Brian
than the Java reference bot.
Current standings:
Gongo: 9.5 -10.2k playouts/second
Java refbot: 6.2 - 6.8k
Orego 6.10: 16.5 - 17.2k
Orego is another Go bot written in Java. It's an apples-to-oranges
comparison because it's a different (and smarter) algorithm, but I
figured it's time to set my sights higher.
Gongo is no longer a straight port of the refbot; there's an
additional array to track the number of liberties for each point,
which helps cut down on array accesses of neighbor points. However,
the biggest win was when I ran the profiler with the -hs option and
discovered that 40% of the time was being spent in the random number
generator. (The core generator itself is fast, but doing a 64 bit
divide on a 32 bit CPU is slow.)
Filed a bug for this: http://code.google.com/p/go/issues/detail?id=390
Current profile:
147 samples (avg 1 threads)
29.93% 29.93% gongo·*board·markSurroundedChain
21.77% 52.38% gongo·*board·makeMove
15.65% 88.44% gongo·*board·playRandomGame
8.84% 12.24% gongo·*randomness·Intn
8.84% 8.84% gongo·*board·wouldFillEye
8.16% 96.60% gongo·*robot·findWins
3.40% 3.40% rand·*rngSource·Int63
1.36% 1.36% gongo·*board·getEasyScore
0.68% 8.16% gongo·*board·hasLiberties
0.00% 96.60% goexit
0.00% 96.60% gongo·*robot·GenMove
0.00% 96.60% mainstart
0.00% 96.60% main·main
0.00% 22.45% gongo·*board·capture
0.00% 0.68% MHeap_LookupMaybe
0.00% 0.68% etext
0.00% 0.68% os·*File·Write
- Brian
Ben Bullock
Dec 7, 2009, 12:39:59 AM12/7/09
to golang-nuts
On Dec 7, 1:40 pm, Brian Slesinsky <bslesin...@gmail.com> wrote:
> Spent a big more time optimizing Gongo and now it's quite a bit faster
> than the Java reference bot.
>
> Current standings:
> Gongo: 9.5 -10.2k playouts/second
> Java refbot: 6.2 - 6.8k
> Orego 6.10: 16.5 - 17.2k
But who is winning the game?
> Spent a big more time optimizing Gongo and now it's quite a bit faster
> than the Java reference bot.
>
> Current standings:
> Gongo: 9.5 -10.2k playouts/second
> Java refbot: 6.2 - 6.8k
> Orego 6.10: 16.5 - 17.2k
Brian Slesinsky
Dec 7, 2009, 3:36:27 AM12/7/09
to golang-nuts
The other two use an algorithm that's useful as a benchmark but isn't
competitive.
Perhaps I'll try fixing that.
- Brian
Reply all
Reply to author
Forward
0 new messages