Artificial Intelligence Games 2009

Purpose: A purely recreational competition to battle each others' coding skills. Will promote and share clever Artificial Intelligence tactics for inspiration and use in other Gosu games.

Game:
The attached mini-game involves five hunters chasing and overtaking 100 preys. Once the preys are eaten, the game resimulates. Very simple, allows a very basic knowledge of programming tactics while still leaving plenty of room for clever code.



Procedure:
   1. Download and observe the simple mini-game as provided.

   2. Redefine one or both of the classes "Prey" and "Hunter" (prey.rb, hunter.rb) in the given download and replace their respective files to make the game work with your new classes.

   3. In your own classes, try to either extend or shorten the average lifetime of the preys. Make the Hunters "smarter" or else make the preys "smarter." If you submit a Hunter class, your scoring is based on how quickly the preys are consumed. Likewise, a submitted Prey class is scored on how long the preys can stay alive.

   4. Submit your new class(es) on this forum thread the day of the deadline (TBA).
   (edit) hey, you can just send me a message containing your class(es) too

Description of a Few Shortcomings to Hunter and Prey:
The hunters are fast, but dull. They can chase down the preys easily enough, but sometimes they get caught in a merry-go-round with one prey in the center, which makes them spin in circles until another hunter knocks them away. They only ever accelerate toward the nearest prey at any given moment.

The preys can avoid capture through agility, but they run in an unorganized straight line away from the nearest hunter. Often, they cluster in the corners of the screen allowing the hunters to destroy many of them in one swoop. They only ever accelerate away from the nearest hunter at any given moment. (They do not detect or collide with one another due to optimization necessity).

Special Keys:
The game runs itself through "ruby main.rb" but once the simulation begins, the display can be hidden or shown by pressing "D" and the game can be resimulated at no cost to the average time by pressing the space bar. Press the escape button to quit.

Specs and Restrictions:
  - There is no real reward to the contest. It should not take much time to submit a simple improved class, do it just for fun and to face off with other competitors' classes.
  - Anyone can join, there is no official signup. Just submit however many classes you want on the deadline. Competitors are discouraged from submitting code early to avoid plagiarism (other players might steal your AI ideas and then submit their "own" class before the deadline).
(edit) sending me a private message containing your class solves any cheating problems. I didn't realize this at first. Do that instead xD
  - You are permitted only to change the classes Prey and Hunter (prey.rb, hunter.rb)
  - You cannot adjust the acceleration, radius, or other such set values in either class
  - You cannot "stupefy" or else make "less smart" any class. There simply is no point: any and all classes you send in will be tested separate from each other.
  - Average time is measured in seconds relative to game loops and is unaffected by the performance of your computer.
  - Entities cannot "warp" in any way whatsoever (deliberate setting of x and y position)
  - Let's be honest: The line between clever code and cheap loophole is obvious. Cheating at this competition is about as impressive as playing chess with a broom.
  - Scoring will be based on how well your class stands up against the default counterpart and then against other competitors' classes. All submitted hunter classes will be pitted against the default Prey class and vice versa. At the end, some of the best classes of different competitors will be put against each other.
  - The deadline has not yet been finalized, but is anticipated to be toward the end of December. Plenty of time.

(edit)
Deadline:
Tuesday, December 22, 2009 (no specific time range/zone - all 24 hours of your day to submit)

All entries may be submitted before this deadline, however, this is discouraged to prevent others from receiving ample time to cheat and/or plagiarize other code. It is the expectation that this should not be a problem anyway.

The results will most likely be posted within a week after the deadline. After submitting all entries, a contestant can download other entries to see the results for themselves, but "even_smarter" classes submitted based on these results will not be eligible for the original competition.

Note:
I'm not pretending to be Ludum Dare or anything. I just thought there would be no better way to promote cool code than hosting an AIG. Please post a reply if you wish to join, although it is not required. If it turns out nobody cares, then I'll just shut it down and get out of the way.

If this actually works out, however, there could be more AIG in the future with more elaborate scenarios. Just take a day or two and improve the Prey/Hunter classes. Use my own "smart_prey.rb" as an example - an addition of two or three lines of code increased the preys' lifetime by 30sec. The month-long deadline is just to allow anyone short on time to be able to submit.

Inform me of any errors, if you want fewer restrictions, or if you need help debugging your own classes.

class Entity

Location: entity.rb

--Members--
x, y        read only
vx, vy    read and write, but read only for competition purposes

--Public Class Methods--

new(game)
  game - the Gosu::Window instance being used.

--Public Instance Methods--

move
  Call this function exactly one time in the update method of its subclasses Prey and Hunter. No exceptions. This really should have been called by GameWindow rather than the instances themselves, in fact.

find_closest(targets)
  targets - an array of the counterpart entities, ex: hunters would call "find_closest(array_of_preys)"
  Iterates through targets and returns the instance of the closest Prey/Hunter. Use at your pleasure.

accelerate(dir)
  dir - the angle to accelerated toward.
  Call this function once or not at all in your own code. Do not call it more than once or else the submission is illegitimate.

class Hunter

Location: hunter.rb

--Relevant Instance Methods--

update(preys)
  preys - an array given by GameWindow of all the preys on the screen. Use at you pleasure
  Probably the only method intended to be adjusted in this competition for Hunter. Initialize may be adjusted to accommodate new instance variables, etc. You can find the closest prey in here via find_closest(preys). Note that the code where preys are eaten should not be adjusted to work on more than one prey per cycle and the distance < 5 should not be in any way changed for a larger eating radius.

class Prey

Location: prey.rb

--Members--
eaten      read, boolean for whether or not the prey has been destroyed

--Relevant Instance Methods--

update(hunters)
  hunters - array given by GameWindow containing all the hunter instances. Use at your pleasure.
  The only method that really needs tweaking in this competition. You may consider using find_closest(hunters) and accelerate away. Use "move" exactly one time and "accelerate" at most once or not at all. Always have !@eaten as the last line of this method to tell GameWindow that the prey still exists.

cool :) .. hope I can take time enough from work to submit a really hungry hunter :P

hi,

the included smart_hunter.rb is not ascii text and is unreadable

Okay, I've fixed my smart_hunter.rb and it is now attached here as a .txt file.

Description: The time it took to consume the preys was reduced by about 10 seconds using differential approximation in the angle to accelerate toward. I've included as a convenience the drawing of little white boxes to show the angle of acceleration, not velocity, of the hunters (this is not required in your own games).

This did not take me very long to make, and it does not specialize at all. Some improvements you can make to your own smart hunters would be predicting the path of motion instead of the angle to accelerate toward, specializing behavior at edges and corners, ignoring the "closest" target and focusing only on one until it is destroyed, etc.

Change the name from '.txt' to '.rb', plug and play.

Note: this "smart hunter" did well against the regular prey, but it was terrible when put against the "smart_prey." Keep in mind some tactics don't work in all situations. You may consider submitting multiple smart hunters/preys for the second part of the competition when competitors will face each others' classes.

pretty interesting stuff, thanks, ill have  a play :)

can you explain how your smart hunter works in particular how you used calculus to improve its accuracy?

The calculus is more conceptual than complex. I estimated the rate of change in angle that the hunter must accelerate toward by using the difference between the current calculated angle and the previous calculated angle. This is a kind of differential approximation - quite simple really. I then added this change in angle to the current calculation so that the hunter can essentially "predict" the next angle it must accelerate toward.

Example:
The last angle (in the last frame) from hunter to prey = 36
The current angle = 38
Rate of change in angle in degrees/frame = current - last = 2
accelerate_toward(current angle + rate of change)
# Using a slope differential (the rate of change) to predict
# future values of the angle is very simple calculus

This helped the hunters zone in on the preys and effectively killed the "merry-go-round" effect of hunters orbiting the prey. I ended up multiplying this rate of change by 4 because that improved testing results. The word "calculus" might scare some people away from the competition, but I was not implying that my coding had any true complexity to it. That was just a fancy way of describing a simple modification ;)

Deadline: (I already posted this, but it was destroyed in the server crash)
Tuesday, December 22, 2009 (no specific time range/zone - all 24 hours of your day to submit)

All entries may be submitted before this deadline, however, this is discouraged to prevent others from receiving ample time to cheat and/or plagiarize other code. It is the expectation that this should not be a problem anyway.

The results will most likely be posted within a week after the deadline. After submitting all entries, a contestant can download other entries to see the results for themselves, but "even_smarter" classes submitted based on these results will not be eligible for the original competition.

hey im not sure if this is possible, but im not going to be able to work on this for the next 5 or 6 days, but i would like to take part. is it possible you could extend the due date? :P

The deadline is created for 3 reasons:

1. There has to be a cut-off just so that people will actually get going on their classes
2. There needs to be a 24-hour period for people to submit their classes to help minimize the time window for someone to cheat off of submitted classes. Again, however, I really hope cheating isn't a problem anyway. There's seriously nothing gained from doing so.
3. I am personally going to at last have plenty of free time starting on the 19th to run the competition.

There is, however, no rulebook stating the deadline. Nobody's going to cry or sue if I move it back a few days. Since you are one of the few people who have expressed interest in participating, you are given a large percentage of popular vote over silent participants. I will push the deadline to the 22nd if by tomorrow no objections are raised. Will that be enough time?

All:
Classes still can be submitted before the deadline if you are confident that people will play fair or else if you don't care whether or not anyone does cheat. In fact, there could be a follow-up "cheat" competition where people can submit "even_smarter" classes based on the results of the original competition. The outcome of AIG depends on how many people participate.

The deadline has now been extended to Tuesday, December 22

Hopefully this will allow enough time for more people to submit.

phelps, I seek your help.

I made (am making) a prey class right now, but somehow it glitches the whole app.
The hunters disappear at random times, basically giving me an unlimited score.
While I like that fact; I don't think it's what you (or any other contestant for that matter) want.
But I haven't really deleted anything important, or done something against the rules (as far as I know).

Anybody else get bugs like that?

Can I PM you my prey class so that you, as an impartial person, can try it out to see if you get the same?

Attach the class to a post. I'll delete/change the attachment when I check it out, and hopefully I'll have it back to you in time for necessary adjustments. I really don't think anyone is going to cheat (cheat? Really, people? We're better than that). If it turns out to be some obscure error with your setup and it all works out fine on my end, then the class can still compete -- after all, the competition will officially be held on my end.

Got an email address phelps? .. submitting a hunter and a prey :P

Okay, they won't cheat, but I've put a link in a PM for you anyway, so please check your messages.

I narrowed it down to Gosu::angle_diff (angle1, angle2), which is pretty weird, so it's probably something on my side.
I hope you have enough RAM, and a nice fast CPU :P

Okay guys, I feel really stupid right now because I didn't realize there was a message inbox for forum users xD
I usually don't try to look for extra stuff like that.

Fortunately, this might just solve the cheating possibility that I kept bringing up. If everyone can submit their classes through a private message like AmIMeYet, then all will be well.

Hey, I'll be a little lax on the deadline. I don't want people to think they can't submit classes just because they're a day late; take all the time you need.

ippa, I don't really want to give out my email publicly, so is it possible for you to do that PM thing too?

AmIMeYet, I'm looking at your class right now and getting the same problem. I'll get it to you soon.

I have discovered your problem.

When you declare:

diff = angle_diff(some_angle, @dir)

You leave open the possibility that some_angle = @dir, which would make diff = 0
A couple of lines later, you include this calculation in an expression:

(diff**-1)

Which is the equivalent of saying  1/diff.
1 divided by 0 is infinity.
Turns out, this really jacks things up. I'm actually surprised the ruby interpreter didn't spit out an error.

Solution: after each declaration of diff (one for each cardinal direction) add a line of code so that all four occurances look like this:


diff = angle_diff(cardinal_direction, @dir)
diff = 0.1 if diff.abs < 0.1  # 0.1 is an arbitrary range which I use
                       #simply because it includes 0. Could be 0.01


Did this help you out?  ;)

No way, I did NOT just make the divided by zero mistake!?! :O
Wow.. I did not expect that to just make stuff disappear

Working great now, thanks! I can now make it actually better than the original :)

Okay, entry sent in! :D

hey,

sorry i haven't had access to a computer for more than 1 hour at a time for the last week or so, so i probably can't compete, but it was a nice idea and also it looks like the recent post on showcase (the GA predator/prey simulator) is up a similar alley.

banister:

> hey,
>
> sorry i haven't had access to a computer for more
> than 1 hour at a time for the last week or so, so i
> probably can't compete, but it was a nice idea and
> also it looks like the recent post on showcase (the
> GA predator/prey simulator) is up a similar alley.

1 hour is probably enough to beat the default classes though ... :)

when can we expect some score-tables? :)

Competition Results

(click on image)


All participating classes are attached in .tgz along with game and results image.

Further Results

--AmIMeYet--

-Smart Prey: Avoided clustering by ignoring the position of any hunters and detecting proximity to edges of the screen. Preys regularly shifted acceleration to a calculated "smart" direction (instead of a random direction). Reduced the rate of consumption by requiring hunters to take them one at a time.

This one was interesting to watch, similar to watching a formation pattern of a school of fish. It represents a tactic that does not attempt to avoid the hunters, but rather slow them down.

--Dahrkael--

-Smart Prey: Simplest of tweaks to the original file. Instead of accelerating directly away from the nearest prey, accelerated at a perpendicular trajectory. A simple " + 90." Interestingly effective. Lessened clustering and frequently stalled the hunters in circular chases.

While the simplicity was highly effective, it did not make the prey "smart," nor was it particularly clever for a month-long competition. One hour competition maybe, but I was not impressed by so little effort getting such a high rank. The method did teach a thing or two about simplicity, making us all smack our foreheads, but when one is watching the single remaining prey spinning the hunters in an infinite merry-go-round loop, one isn't thinking "this is genius," but rather "this is boring." I cannot justify counting the lucky rounds that chanced to become infinite loops on the scoreboard; the recorded time is the average of the times when rounds went smoothly, unbiased. If a much more complex class had created infinite loops as frequently, I would happily count it as the winner. But part of the purpose of the competition was to share clever code. Thanks for participating anyway, however. I must commend you for submitting a quick and easy high-scoring class in the face of everyone who didn't participate for "time and schedule" constraints.

--Ippa--

-Smart Prey:  Ignored the hunters and any other obstacles to move in a oscillating pattern either left/right, up/down, or diagonally. Looked similar to AmIMeYet's prey, except this prey wasn't as smart, but the coding was simpler and more clever.

Funny to watch the hunters fail at each swipe to nab the prey that isn't even trying to dodge. Represents the same tactic of distracting the hunters for as long as possible without actually running away. Interesting, but not exactly exciting. Nice job, though.

-Smart Hunter: Gathered to the center of the screen for a few seconds before splitting off to catch the preys in the default hunter mentality. The idea was to cluster the preys as much as possible to increase the rate of consumption. Attempts were made to further improve the hunter's skill, but apparently they didn't work and were commented out before submission.

Showed effective results for the default prey, but the smart prey and dahrkael's prey weren't as easy to cluster, and AmIMeYet's and your own prey did not operate around that mind setting. It was a reasonable approach that did need representation in the competition. Unfortunately, as it turns out, herding the preys is not as rewarding as one might have hoped.

--phelps.db--

-Smart Prey: Used mathematical functions to skew the angle of acceleration. As the nearest hunter grew closer, the prey would accelerate at an increasing angle to the right. Enabled the prey to dodge hunters homing in.

Simple, but clever. I must admit this class is the most interesting one to watch. I enjoyed watching four or five hunters zone in on a single prey, but be impossibly thwarted by its ability to make subtle, seemingly precise movements that keep it alive for several seconds even when completely surrounded. If dahrkael had more time to work, I'm sure something like this would have been the result. Although, I feel a little guilty winning the competition when others of you spend more time and effort on your classes.

-Smart Hunter: Calculated the rate of change in the angle between itself and the prey to predict a more extreme angle of acceleration that would be more likely to make its path intersect with the prey.

Slightly more complex than my smart prey, yet still relatively simple and clever. I cannot say it is an absolute winner because it had only Ippa to compete against, but I think these were some all around smart hunters.

wow, i wouldnt expect a second rank :O
i must admit that my prey looks like a cheat (at least with the default hunters) when they start doing circles (i hoped the other hunters wont do that).
My prey is inspired in those guys:
http://ecodiario.eleconomista.es/imag/efe/2008/07/30/1404234w.jpg

Who make the same, when the bull is coming they run in a rect angle, the prey should make the exactly the same, but the acceleration is too low to be stopped when the hunters are coming.

Congratulations to the others (especially ippa, who known how make a smart hunter), i will be waiting AIG 2010 to make something cool (and no sooo simple :P).

PD: Lets play with the .tgz

Great!
Congratulations, everyone!
Also, a very close 3rd-4th :)

Can't wait for AIG'010! (Let's just hope we get a bit more players then)

w00t.. so I won? .. if we count out the author :)

Nice competition! Some days since I submitted mine now but I thought about some things while coding:

- being able to accelerate less then the max-amount .. I guess this could be achieved my stopping accelerating too  :)
- being able for hunters to see other hunters, and not just preys .. same for the preys (this could be used to prevent swarming)
- hunter.rb and prey.rb could probably be even cleaner .. so they (as far as possible) only contain moving-logic. might be an idea to remove draw() for example, or put it in Entity. Also move() could be called from the outside rather then from update() etc.

But those are details.. i think this was an well thought out competition and well executed. I guess the biggest thing missing was more and better entries :).... and a movie on youtube where Everyone battles on the same arena! :)

> w00t.. so I won? .. if we count out the author :)

Uh, only if you're talking about the hunters, :/ the rank goes 1 = winner, 2 = next best, 3 = third best, etc. It can also be figured from the times that the longest prey total and shortest hunter total are the best.

> - being able for hunters to see other hunters, and not just preys .. same for the preys (this could be used to prevent swarming)

The game engine is a "fake" engine, meaning that a higher intelligence (HI) can see all the objects and handles collisions. The hunters collide with each other, but do not see each other because they do not handle their own collisions. This could easily be remedied by passing in the @hunters array with each update or something of that sort. However, the preys do not detect each other simply for optimization purposes, as stated in my first post. There are 100 preys to begin with, and anyone who can figure out some mathematical algorithm that will keep them scattered while actively avoiding the hunters deserves a gold medal. Meanwhile, 100 preys checking their position against 99 other preys is extremely inefficient and my game engine is too simple for me to care about using grids or quad trees

I made the game mini-engine for something quick and unrelated using etherpad.com with a friend. I considered making your said improvements when I decided to use it in AIG, but I also decided I did not care that much and clearly, given the number of entries, no one else did either.

Thanks for playing.

Regarding your disappointment with the amount of entries.. did you try to get ppl in from other communities/forums then gosu? I think the gosu-community might be a bit small to expect tons of entries...

I also think that ordinary ruby devs / rails devs would find a challenge like this compelling.. with zero game-coding-experience they compete in a game, and they can spend how much or little time they can find outside work on it. Thinking rubyinside, ruby mailinglists, other game-dev forums then libgosu etc.

That would have the added benefit of pushing gosu as well. I'm up for putting a link up on www.rubylicio.us ...