AI Challenge Current Rankings

[Jan Mercl]

From: Uriel É. (the original G+ post has no public link available to point from here)

In the AI Challenge over >80% of all bots seem to depressingly be written in Java or C++. 

But two out of the top three bots are written in Go.

#golang #aichallenge

Current Rankings | AI Challenge

[Andrew Gerrand]

Very cool - but who are the contestants who are using Go? Are they readers of golang-nuts? Say hi!

Andrew

[Johann Höchtl]

Wow, that's realy impressive. I am not talking about the current #1 but the amount of contestants using Go for beeing such a young language!

[Rodrigo Moraes]

Pretty sweet that Go is currently #1.

But... not a single Brazilian. Hmpf.

-- rodrigo

[Archos]

But if I'm not wrong pguillory[1], the number 1 by now, has written 26
versions for the Go code. In change, xathis[2], the actual number 2 in
Java, only has written one version for its code and he follows in the
second number.

Of course, I'm very happy that Go is in the top 10.

[1]: http://aichallenge.org/profile.php?user=589
[2]: http://aichallenge.org/profile.php?user=4513

[Andre Santos]

How often does this competition takes place? Im interested in participating but this edition is finishing in less then a week.

2011/12/11 Jan Mercl <jan....@nic.cz>

[Rodrigo Moraes]

On Dec 12, 11:38 am, Archos wrote:
> But if I'm not wrong pguillory[1], the number 1 by now, has written 26
> versions for the Go code. In change, xathis[2], the actual number 2 in
> Java, only has written one version for its code and he follows in the
> second number.

I've heard that the Java guy has been preparing a new version since
October, while the Go guy iterated a few versions.

Hah. I'm so funny.

-- rodrigo

[Jan Mercl]

On Monday, December 12, 2011 2:51:59 PM UTC+1, Andre Santos wrote:

How often does this competition takes place? Im interested in participating but this edition is finishing in less then a week.

Since 2009 it's a fourth such event: http://en.wikipedia.org/wiki/AI_Challenge

[Jeff Davis]

I am one of the participants using Go. It was my learn Go project and
it's been a lot of fun...I am bugnuts on
the website if you want to see how I am doing. The code is in a
private repo on github now but I plan to open it up
after the submission deadline (as embarrassing as that might be).

[Archos]

At the end, xathis has won [1] and its strategy is very
interesting[2].
It's nice to see to 3 Go bots inner of the 100 first ones.

[1]: http://aichallenge.org/rankings.php
[2]: http://xathis.com/posts/ai-challenge-2011-ants.html

[ChrisH]

Hi. I wrote the entry that finished #7 in the finals and was the top Go entry, although I think that pguillory's entry is just as good as mine. I just got a little luckier about the last few games.

Here is a link to the description of my entry. I also did well in the prior contest, but I wrote that entry in Java. After the Fall 2010 competition I decided to write my next entry in Go for two main reasons. First: I tend to solve these problems by doing a lot of integer array manipulation and Go's slices seemed a much more elegant and efficient tool than what Java provided. Second: I think Go is a cool language and this contest was a good opportunity to learn by doing.

I learned a few things that may be worth sharing here on golang-nuts. First a little context. The contest froze Go at release 60.1 for consistency during the course of the competition. Our code ran on 64 bit Ubuntu 11.10 with one core dedicated to our program and we were not allowed to have more than one CPU bound OS thread active. Go entries were compiled with 6g. Each entry had 500ms per turn to submit its moves, and thus, the most sophisticated entries were typically very concerned about performance.

I had to avoid interface values in performance critical loops. My code mostly manipulated slices of integers in various ways. One of the most important pieces of the program was a highly optimized implementation of Dijkstra's algorithm that used a priority queue of ints. Initially I used container/heap directly with the obvious implementations for the heap.Interface methods. But analysis of the code using gopprof showed that my program was spending a high percentage of its time doing interface value conversions and method calls into the heap.Interface methods. Writing a heap implementation with type specific inlined comparison and swapping code provided a big performance gain. Another portion of my program benefited from a similarly custom version of functions from the sort package for sorting int slices.

I learned the hard way that CPU bound goroutines don't play nice. My program consisted of five explicit goroutines. In addition to the main program, there was a goroutine each for a game state lexer, and parser, and one for computing non-combat moves and combat-moves respectively. On each turn the main goroutine receives the game state from the parser, updates some data structures, and partitions the problem into the combat and non-combat categories. It then launches a goroutine to process each category and waits for them to send their move orders via a channel. Each of the move computing goroutines is entirely CPU bound and also needs to stop when the time limit is near so that the program can reply to the game server with its moves before time has expired.

Initially I tried using a time.Timer to send a message on a channel when it was time to stop computing moves, but the goroutine used by the time package to sleep for the Timer was starved of CPU cycles by the CPU bound goroutines. Luckily I was able to find some discussion of this phenomenon here on golang-nuts that helped me realize it was an expected behavior rather than something I was doing wrong. I tried different hacks to make this architecture work, but the only approach that worked reliably was to call time.Nanoseconds() at manually tuned loop counts and exit when a threshold was exceeded.

As a side note, it seems that (at least on my development machine) gopprof statistics are biased in a way that causes them to over-represent system calls. When I changed the timeout code to make frequent calls to time.Nanoseconds(), gopprof reported that my program was spending a huge percentage of its time (25-35%) getting the system time, yet a run of the program on the same input and performing the same amount of real work but without calls to time.Nanoseconds() took only slightly less time to run, indicating that time.Nanoseconds() calls were not actually consuming anywhere close to the amount of time reported by gopprof. Had I known of this discrepancy earlier I would probably would not have tried using time.Timer. The big numbers for time.Nanoseconds() reported by gopprof in my early efforts were the reason I tried other approaches in the first place. I lost a lot of time dealing with this issue.

I will use Go again. I enjoyed writing my entry in Go, and I will use it again if I compete in future competitions. I will also consider using Go on other projects if I think it is a good fit.

[⚛]

On Jan 1, 9:57 am, ChrisH <chris.cs....@gmail.com> wrote:
> *I learned the hard way that CPU bound goroutines don't play nice.* My

> program consisted of five explicit goroutines. In addition to the main
> program, there was a goroutine each for a game state lexer, and parser, and
> one for computing non-combat moves and combat-moves respectively. On each
> turn the main goroutine receives the game state from the parser, updates
> some data structures, and partitions the problem into the combat and
> non-combat categories. It then launches a goroutine to process each
> category and waits for them to send their move orders via a channel. Each
> of the move computing goroutines is entirely CPU bound and also needs to
> stop when the time limit is near so that the program can reply to the game
> server with its moves before time has expired.

I would be interested in learning whether (in your opinion) converting
this goroutine-based implementation of your algorithm into sequential
call-return implementation would increase the amount of code that
needed to be written.

Next, I would like to know whether the outcome of your algorithm (that
is: the strength of the solution found by the algorithm) depends on
the global order of messages sent via Go channels. My question
actually is: whether you were able to map the optimization process to
some of the concurrency features offered by the Go language.

[Chris Hines]

On Sunday, January 1, 2012 7:49:04 AM UTC-5, ⚛ wrote:

I would be interested in learning whether (in your opinion) converting
this goroutine-based implementation of your algorithm into sequential
call-return implementation would increase the amount of code that
needed to be written.

The non-combat goroutine could probably be converted to a structure to store intermediate state and a method to compute and return a single move order relatively easily. On the other hand, this part of the program was the first code I wrote and early on it was the main loop run by the main goroutine. It was trivial and natural to convert it to a goroutine when I added the combat evaluation code. Converting it to a goroutine only required replacing a slice return value with channel sends. Converting it to a struct and method would require moving all the local variables into the struct and splitting the preamble code before the main loop into a separate initialization method.

The combat goroutine would not be as easy to convert to an incremental call-return style because the main loop could vary in complexity by several orders of magnitude but I wanted each time slice used by the CPU bound routines to use a relatively constant amount of time. Using a goroutine made it trivial (once I got it working) to yield the CPU to the other CPU bound goroutine even from within deeply nested loops and pick up where it left off when it got the CPU back without having to invert the flow of control.
 

Next, I would like to know whether the outcome of your algorithm (that
is: the strength of the solution found by the algorithm) depends on
the global order of messages sent via Go channels. My question
actually is: whether you were able to map the optimization process to
some of the concurrency features offered by the Go language.

I'm not sure I completely understand your question, but I don't think that the strength of my solution depended on the order of messages sent via Go channels. I chose to use goroutines because I had two completely independent computations to perform in a hard time constraint and the time to perform those two computations was difficult to predict. I therefore structured each of them to do the easiest computations first so that they could complete the most total tasks before time expired, and I ran them in parallel because I deemed it more important to finish some of each set of tasks rather than as many as possible of one and a much smaller number (maybe zero) of the other. This architecture made my program take full advantage of the time available and degrade relatively gracefully when the time constraint could not be met.

I left out a detail in my post above because it was getting too long, but I did use another goroutine and set of channels as an intermediary between the CPU bound goroutines and the time checks. The intermediary goroutine also used a token passing scheme to enforce a rule that only one of the CPU bound goroutines was allowed to run at any given moment, the other being blocked on a channel operation waiting to get the run token. So in essence I built my own simple cooperative multi-tasking scheduler. There is probably a better way to accomplish this goal, but once I got it working I went back to making my AI code better since that was my primary goal, rather than finding the most elegant way to use goroutines.

Does that answer your questions?

[Alexey Borzenkov]

On Mon, Jan 2, 2012 at 1:22 AM, Chris Hines <chris....@gmail.com> wrote:
> I left out a detail in my post above because it was getting too long, but I
> did use another goroutine and set of channels as an intermediary between the
> CPU bound goroutines and the time checks. The intermediary goroutine also
> used a token passing scheme to enforce a rule that only one of the CPU bound
> goroutines was allowed to run at any given moment, the other being blocked
> on a channel operation waiting to get the run token. So in essence I built
> my own simple cooperative multi-tasking scheduler. There is probably a
> better way to accomplish this goal, but once I got it working I went back to
> making my AI code better since that was my primary goal, rather than finding
> the most elegant way to use goroutines.

Why did you need to make your own multi-tasking scheduler? Wouldn't it
be better to call runtime.Gosched() periodically in your computation
loops (so computations are more evenly distributed and don't starve
communication), or was the cost of the call too high? (I just measured
and on my Macbook Pro I can do ~2.5 million runtime.Gosched calls in
500ms, which is surprisingly small)

[Kyle Lemons]

Here is a link to the description of my entry

Thanks for the write-up! 

I learned the hard way that CPU bound goroutines don't play nice. My program consisted of five explicit goroutines. In addition to the main program, there was a goroutine each for a game state lexer, and parser, and one for computing non-combat moves and combat-moves respectively. On each turn the main goroutine receives the game state from the parser, updates some data structures, and partitions the problem into the combat and non-combat categories. It then launches a goroutine to process each category and waits for them to send their move orders via a channel. Each of the move computing goroutines is entirely CPU bound and also needs to stop when the time limit is near so that the program can reply to the game server with its moves before time has expired.

Initially I tried using a time.Timer to send a message on a channel when it was time to stop computing moves, but the goroutine used by the time package to sleep for the Timer was starved of CPU cycles by the CPU bound goroutines. Luckily I was able to find some discussion of this phenomenon here on golang-nuts that helped me realize it was an expected behavior rather than something I was doing wrong. I tried different hacks to make this architecture work, but the only approach that worked reliably was to call time.Nanoseconds() at manually tuned loop counts and exit when a threshold was exceeded.

Yeah, I had a similar experience.  I really, really liked the idea of doing go func(){ time.Sleep(threshold); close(cancel) } and having periodic selects seeing if cancel had been closed, but it turned out that the sleep/close goroutine was getting shoved off by the compute intensive goroutines, and even adding in Gosched's didn't help out enough to prevent timing out.

 

I will use Go again. I enjoyed writing my entry in Go, and I will use it again if I compete in future competitions. I will also consider using Go on other projects if I think it is a good fit.

I also had the same experience.  Mine didn't do really well, but it was really fun to see how well even an unoptimized Go AI stacked up against other languages.

[Chris Hines]

Why did you need to make your own multi-tasking scheduler? Wouldn't it
be better to call runtime.Gosched() periodically in your computation
loops (so computations are more evenly distributed and don't starve
communication), or was the cost of the call too high? (I just measured
and on my Macbook Pro I can do ~2.5 million runtime.Gosched calls in
500ms, which is surprisingly small)

Using runtime.Gosched was one of the first things I tried. My experience was that a CPU bound goroutine that calls Gosched will often (usually?) just return to processing without another goroutine being scheduled, at least not at the granularity that I wanted (< 5ms). Certainly a goroutine blocked on a call to sleep that should have expired was not getting scheduled in time for it to wake up reliably within a specific time window. I tried adjusting that time window to as much as 100ms, but was still experiencing timeouts, and I really didn't like the idea of throwing away 20% of my time allotment.

Eventually I settled on a 40ms window to shutdown computation and submit moves (the server had a 10ms polling loop for each 100 orders). Using the technique I described my program would send moves somewhere in the 460ms - 465ms mark once computation was heavy enough to use that much time. Since the granularity of my time checks would often decrease as the game progressed and there are more ants to control I increased the time window to maintain a 460ms target whenever I overran that mark and this worked well in practice.

[⚛]

On Jan 1, 10:22 pm, Chris Hines <chris.cs....@gmail.com> wrote:
> Does that answer your questions?

Yes (mostly). Thanks.

[Alexey Borzenkov]

On Mon, Jan 2, 2012 at 4:17 AM, Chris Hines <chris....@gmail.com> wrote:
>> Why did you need to make your own multi-tasking scheduler? Wouldn't it
>> be better to call runtime.Gosched() periodically in your computation
>> loops (so computations are more evenly distributed and don't starve
>> communication), or was the cost of the call too high? (I just measured
>> and on my Macbook Pro I can do ~2.5 million runtime.Gosched calls in
>> 500ms, which is surprisingly small)
> Using runtime.Gosched was one of the first things I tried. My experience was
> that a CPU bound goroutine that calls Gosched will often (usually?) just
> return to processing without another goroutine being scheduled, at least not
> at the granularity that I wanted (< 5ms).

I think I found why this happens. The problem is that go scheduler has
a list of runnable goroutines, so runtime.Gosched puts current
goroutine to the end of that list and jumps to scheduler. The problem
is that when using timers (e.g. <-time.After(delay)) there are two
things going on. First there's an underlying sleep syscall that works
with timers, when syscall it returns needs goroutine to resume which
it schedules to the end of the list. The timer goroutine then does a
send on a channel, which finally schedules the receiving goroutine to
wake up, and again it adds it to the end of the list.

This basically means that at least *two* cycles of each computing
goroutines will pass before you receive anything from the timer
channel. I played with it and came up with something like this (I'm
using current tip though, not 60.1) that shows what's going on:

package main

import (
"fmt"
"time"
"runtime"
)

func calc() {
d, _ := time.ParseDuration("100ms")
t0 := time.Now()
for {
t1 := time.Now()
if t1.Sub(t0) >= d {
runtime.Gosched()
t0 = time.Now()
}
}
}

func main() {
d, _ := time.ParseDuration("10ms")
t0 := time.Now()
timer := time.After(d)
go calc()
go calc()
<-timer
t1 := time.Now()
fmt.Println(t1.Sub(t0))
}

The goroutines are not strictly computing, but calling time.Now, but
luckily time.Now is lightweight, handled by runtime and doesn't cause
entering/leaving syscall. What it shows is that for runtime.Gosched
every 100ms for small enough timer values at least 400ms will pass for
2 goroutines (2 cycles x 2 goroutines), 600ms for 3, 800ms for 4, etc.
So when planning how often you need to call Gosched you need to keep
this latency in mind (for 10ms latency with 2 computing goroutines you
would need to call Gosched every 2.5ms).

It turned out to be an interesting side effect of the current
scheduler design, hope this helps you in the future.

[Chris Hines]

On Monday, January 2, 2012 9:09:52 AM UTC-5, Alexey Borzenkov wrote:

So when planning how often you need to call Gosched you need to keep
this latency in mind (for 10ms latency with 2 computing goroutines you
would need to call Gosched every 2.5ms).

It turned out to be an interesting side effect of the current
scheduler design, hope this helps you in the future.

Thanks, that's interesting. The fact that the number of computing goroutines is a multiplier in that equation is unfortunate because that means the more of them you have the stronger the starvation effect becomes, to the point where you could conceivably need to call Gosched at a rather high rate. It also means that it might be difficult to know the proper rate to call Gosched in a program with a variable number of computing goroutines.

Hopefully the Go scheduler will handle this better in the future.

[Henrik Johansson]

What is the status if the scheduler regarding this? I seem to remember this coming up every now and then in the mailing list.

Having to control the scheduling of goroutines is not an appealing trait. Being able to control them may have its uses but being forced is not good.

Congrats on the nice result in the competition!

/ Henrik

[Kyle Lemons]

Good sleuthing!  Did you try to see if calling time.Sleep directly (not <-time.After) allows it to work in one gosched?