x
Solved

# Duck Hunt AI

Posted on 2011-09-23
Medium Priority
1,616 Views
Good day everyone. I have a bit of a longer question.

First I should tell you the context of the problem briefly. I have to implement an intelligent agent that shoots "ducks" in the sky (using Java). The sky is just a 2D matrix and the birds can move NORTH, SOUTH, WEST,EAST or STOP. Also, they can change their speeds in any of these directions. For example, at a give time step, a bird could STOP horizontally and accelerate vertically. There are hundreds of birds of 6 different colors (species). The WHITE are the most common (exactly half of all birds) and worth the fewest points, there is only one BLACK that is endangered and if I shoot it i lose the game and there can be other colors as well, or not, depends on the initial random layout. I cannot see the birds' species, I can only observe their movement patters. I also know that birds have habits: MIGRATING means that a bird will fly in the same direction (EAST,WEST, NORTH, SOUTH) more or less along the same line, QUACKING means that a bird will move slowly and erratically and so on, you get the gist. I know that the habits are tied somehow to the species, but I can't see the species, I can only observe the movements, i.e the habits, so this leads me to believe that HMMs would be a solution.

What I have: I have  Duck, State and Action classes which basically tell me everything about the past of every duck. I can ask "What was the i-th movement of this duck?", I can ask how many ducks there are, if a duck is dead and anything else I'd need to know.

What I have to do: I need to write a function that says "At t+1 bird X will be doing this: MOVEMENT, VerticalSPEED, HorizontalSPEED", based on what that bird did in the prior turns.. If i get it right, that bird dies and I find out the species. In 240 turns I have to kill as many ducks (EXCEPT the black one) and get as many points as possible. Each time the game starts fresh the patterns change and the habits belong to different birds, so I have to learn by hunting what habit belongs to each bird.

What would be a good place to start? A pseudocode suggestion would be appreciated.

Thank you.
(No ducks will be harmed in the making of this program)

0
• 3
• 2

LVL 37

Expert Comment

ID: 36586517
I would start by looking for migrating birds since they will be easy to hit.
Note the speed at which they are travelling and the species so you can get an idea of the average speed of each species (if you are lucky, this will be very useful info).
Another thing to keep track of is the percentage of time the bird is doing each of the actions.
0

Author Comment

ID: 36586956

I was looking for something more general though, seeing that the ducks can change their movement patterns, so if a duck is migrating now, it can just as well stop at the next time step. I need to use probabilities somehow to determine what the duck is doing and what it will do based on the past. It's a learning algorithm. Also, I'm pretty sure I should use hidden Markov models but I can't figure out how.

A more extended explanation of the problem:

At any time, the bird will follow one out of four movement patterns:
migrating: a bird that is migrating will always y in the same direction (east or west), and its height will be more or less stable. Different species may migrate in different directions, but all birds of the same species will always migrate in the same direction.

quacking: a bird that is quacking will tend to make erratic, slow moves, both in the horizontal and vertical direction

panicking: a bird that is panicking will tend to fly fast, both in the horizontal and vertical direction

feigning death: a bird that is feigning death will tend to fall (go down vertically), and move very little horizontally.

Different species combine these patterns in different ways: there might be methodical species which rarely change their movement pattern and species which change often; some might frequently quack after migrating for a while, while others might panic instead. Unfortunately each hunting occurs in a different region, so you don 't know anything about the species movement behavior at the beginning of each new round of hunting. You will have to learn (fast!) about it while hunting.

At a time step, a bird can accelerate, keep speed or stop, in any direction. The probability of the bird performing each of these actions will depend on what the bird is doing (migrating, quacking, panicking or feigning death) and the species of the bird.
0

LVL 37

Accepted Solution

TommySzalapski earned 2000 total points
ID: 36587331
"but all birds of the same species will always migrate in the same direction."
That's probably one of the most useful parts of the whole thing. That could certainly help you avoid the black bird.

How slow can your algorithm be? If you are doing HMMs on all the birds, then it's going to take a while.

I would start with a simple approach and look for birds that just changed their movement pattern. Whether they change frequently or not, if they just started migrating or feigning death, you should have a very good idea of where they will be the next step.

Then as you get more data, you can start looking at average times and directions to get an idea of which birds are worth more points. I really don't see much utility in fancy modelling.
0

Author Comment

ID: 36587374
Thanks for the answers, I'll try the simpler approach then, since I have to return a shot in under 1s.
Hopefully I will get enough data to make an accurate model.
0

LVL 37

Expert Comment

ID: 36587418
The good thing about averages is that you can keep them on the fly, you don't need to recompute the sum every time.

new_avg = old_avg*(count-1)/count + value/count
If you want a standard deviation, you can do it in the same way if you remember that
stdev = sqrt(E(X^2) - (E(X))^2) and keep the average of the square of the values in the same way as above.
0

## Featured Post

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.