radupana
asked on
Duck Hunt AI
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)
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)
ASKER
Thank you for your answer Tommy.
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.
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.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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.
Hopefully I will get enough data to make an accurate model.
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.
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.
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.