HW2
Assignment
In this homework you will implement a agent that can classify and hunt ducks. The aim is to get a deep understanding of Hidden Markov Models (HMM). You will practice identifying the number of states, emissions, etc. You will have to learn the HMM model and use it to classify. This is an individual assignment.
Submission
You submit your solution to a system called Kattis. Click on "Courses" and select ai14. Please read the documentation about Kattis to learn more if you have not used it before.
The portal will not show your Kattis result until we run the update. You have to register for the course in Kattis, else your submission will not be recognized and you will fail the assignment.
Voluntary assignments to help with debugging
You are welcome to get started on the voluntary HMM tasks
that are designed to help you debug your HMM implementation so that you know that that part is working before you dive into the actual assignment.
Testing outside Kattis
Note that some of the assignments have sample input data that is too large to fit on the page (too many values) and hence you do not see all of it on the screen and nothing of the sample output. Download the files using the link at the bottom. You can test your java code outside Kattis by running
java MyHMM < hmm4_01.in
and then make sure that the output matches that of hmm4_01.ans in this case. Replace MyHMM with whatever your java program is called. If you are using C++ you would run something like
./myHMM < hmm4_01.in
Duck huntGame Concept
If you have not played the game until now, go here and try your hand at it:
http://www.silvergames.com/duck-hunt
Though this is a one person version of the game, the game was originally meant for 2-6 players and was designed as a Nintendo TV-video game. The controllers were plastic guns with light sensors that could be aimed at the television to "shoot" the ducks on the TV screen.
Our version of ducks hunt is a generalized version of the original game: There is a sky with birds flying. The birds flies around the sky until they are shot down. The player has to observe the flight pattern of the birds and predict the next move in order to shoot them down. If the prediction is correct, the player will hit the bird and gain points. If the prediction is wrong the player will miss the bird and lose points. The game is over when all birds are shot or when the time runs out.
We have also added different species of birds which behaves differently in the air. Most birds give one point when shot, but one of the species is very rare and will hurt your score seriously if you shoot it. The species are identified after each round, in order to prioritize your targets you will need to identify them during flight. You may also get extra points for guessing the correct specie before the truth is revealed.
AI Perspective
The game can be broken down into three main, dependent, topics:
- Predicting the flight trajectory of the birds so that they can be shot down.
- Identifying the bird species to avoid forbidden targets and maximize score.
- Make decisions to shoot or not based on the confidence of prediction of bird species and flight trajectory.
Tip: Focus on predicting the movement of a single bird using a HMM. This is the building block to solve the entire homework.
The Birds
There are 6 species of birds in the game. For the purpose of this game, all species look similar and the player cannot tell the specie of any bird by merely looking at the sky at a single time instant. However, the birds behave differently and can be distinguished by how they move. The birds and their movement patterns are inspired from birds found in Sweden and their descriptions comes mostly from wikipedia.
Figure 1: The Rock Dove (Columba livia). This bird is often simply referred to as the "pigeon".
 |
Pigeon
The Rock Dove (Columba livia) or Rock Pigeon is a member of the bird family Columbidae (doves and pigeons). In common usage, this bird is often simply referred to as the "pigeon".
Wild Rock Doves are pale gray with two black bars on each wing, although domestic and feral pigeons are very variable in color and pattern. There are few visible differences between males and females. The species is generally monogamous, with two squeakers (young) per brood. The species is abundant, with an estimated population of 17 to 28 million feral and wild birds in Europe.
Rock Doves have been domesticated for several thousand years, giving rise to the domestic pigeon (Columba livia domestica). As well as food and pets, domesticated pigeons are used as homing pigeons. They were in the past also used as carrier pigeons, and so-called war pigeons have played significant roles during wartime, with many pigeons having received bravery awards and medals for their services in saving hundreds of human lives. There are numerous breeds of fancy pigeons of all sizes, colors and types.
Figure 2: The Common Raven (Corvus corax).
 |
Raven
The Common Raven (Corvus corax), also known as the Northern Raven, is a large, all-black passerine bird. Found across the northern hemisphere, it is the most widely distributed of all corvids.
The Common Raven averages 63 centimetres (25 inches) in length and 1.2 kilograms (2.6 pounds) in mass. Common Ravens can live up to 21 years in the wild. Young birds may travel in flocks but later mate for life, with each mated pair defending a territory.
Because of its black plumage, croaking call, and diet of carrion, the raven has long been considered a bird of ill omen and of interest to creators of myths and legends. As a carrion bird, ravens are associated with the dead and with lost souls. In Sweden they are known as the ghosts of murdered persons.
Figure 3: The Eurasian Skylark (Alauda arvensis).
 |
Skylark
The Eurasian Skylark (Alauda arvensis) is a small passerine bird species. This lark breeds across most of Europe and Asia and in the mountains of north Africa. When the word "lark" is used without specification, it usually refers to this species.
The Eurasian Skylark is 16 to 18 centimetres long. It is a bird of open farmland and heath, known throughout its range for the song of the male, which is delivered in hovering flight from heights of 50 to 100 m, when the singing bird may appear as just a dot in the sky from the ground. The song generally lasts two to three minutes, but it tends to last longer later in the mating season. The male has broader wings than the female. This adaptation for more efficient hovering flight may have evolved because of female Eurasian Skylarks’ preference for males that sing and hover for longer periods and so demonstrate that they are likely to have good overall fitness.
Larks, commonly consumed with bones intact, have historically been considered wholesome, delicate, and light game. They can be used in a number of dishes, for example, they can be stewed, broiled, or used as filling in a meat pie. Lark tongues were particularly highly valued. In modern times, shrinking habitats made lark meat rare and hard to come by, though it can still be found in restaurants in Italy and elsewhere in Southern Europe.
Figure 4: The Barn Swallow (Hirundo rustica).
 |
Swallow
The Barn Swallow (Hirundo rustica) is the most widespread species of swallow in the world. It is a distinctive passerine bird with blue upperparts, a long, deeply forked tail and curved, pointed wings.
The swallows and martins have an evolutionarily conservative body shape. Swallows have adapted to hunting insects on the wing by developing a slender, streamlined body and long pointed wings, which allow great maneuverability and endurance, as well as frequent periods of gliding. Their body shape allows for very efficient flight. Swallows usually forage at around 30-40 km/h, although they are capable of reaching speeds of between 50-65 km/h when traveling.
The male Barn Swallow returns to the breeding grounds before the females and selects a nest site, which is then advertised to females with a circling flight and song.
Figure 5: The Common Snipe (Gallinago gallinago).
 |
Snipe
The Common Snipe (Gallinago gallinago) is a small, stocky wader native to the Old World. The breeding habitat is marshes, bogs, tundra and wet meadows throughout northern Europe and northern Asia. It is migratory, with European birds wintering in southern and western Europe and Africa (south to the Equator), and Asian migrants moving to tropical southern Asia. Adults are 25-27 cm in length with a 44-47 cm wingspan and a weight of 80-140 g (up to 180 g pre-migration). They have short greenish-grey legs and a very long (5.5-7 cm) straight dark bill. The body is mottled brown with straw-yellow stripes on top and pale underneath.
The male performs "winnowing" display during courtship, flying high in circles and then taking shallow dives to produce a "drumming" sound by vibrating its tail feathers. Medium speed.
It is a well camouflaged bird, it is usually shy and conceals itself close to ground vegetation and flushes only when approached closely. When flushed, they utter a sharp note that sounds like scape, scape and fly off in a series of aerial zig-zags to confuse predators.
Figure 6: The Black Stork, (Ciconia nigra).
 |
Black Stork
The Black Stork (Ciconia nigra) is a large wading bird in the stork family Ciconiidae. It is a widespread, but uncommon, species that breeds in the warmer parts of Europe (predominantly in central and eastern regions), across temperate Asia and Southern Africa. This is a shy and wary species, unlike the closely related White Stork. It is seen in pairs or small flocks in marshy areas, rivers or inland waters.
Slightly smaller than the White Stork, the Black Stork is a large bird, 95 to 100 cm (37-39 in) in length with a 145-155 cm (5 ft) wingspan, and weighing around 3 kilograms (6.6 lb). They can stand as tall as 102 cm (40 in). Like all storks, it has long legs, a long neck, and a long, straight, pointed beak. As a broad-winged soaring bird, the Black Stork is assisted by thermals of hot air for long distance flight.
There is currently only one pair of Black Storks in Sweden. DO NOT SHOOT THEM!
Differentiating birds in flight
The sky is considered flat and the birds can move in the eight basic directions (up, down, left, right, up-left, up-right, down-left, down-right). Some birds can also stop mid-air and hover. They do not have absolute positions as far as you are concerned. Only the direction of the movement is important. Every bird in the sky makes a move for every discrete time step that the game runs. No moves are reported for birds that have been shot.
The birds have different flight-patterns. A particular specie of bird displays only a few flight-patterns and different species may have different variations of them. The patterns may look like this:
MigratingThe bird will fly mostly in one direction. Different species may migrate in different directions but all birds of the same species will migrate in the same direction.CirclingThe bird gains height by flying up-left or up-right.HuntingThe bird dives or flies horizontally back and forth to hunt insects.DrillingTo impress on the opposite sex, the bird makes cool tricks in the air. Different species have different drills.Zig-zagThis is an erratic flight pattern. The bird flies in different directions to avoid predators.Gameplay
The goal of the game is to shoot all birds except black storks. The game is divided into several environments with several rounds of shooting. The different environments contains different distributions of birds and the birds may also behave differenty in each environment. In particular, the birds will behave differently on Kattis compared to your sample data.
There will be up to 10 rounds in each environment. Each round contains 1-20 birds and goes on for 100 time steps. The round will end when all birds are shot or when time runs out. If you hit a black stork, you may not play any more rounds in that environmentand all your points from that environment will be lost. You will still keep your score from the other environments and may continue to the next. The program will be restarted between each environment, so you cannot transfer any information between them.
Shooting
To shoot a bird, the player need to select a bird to shoot and successfully predict the next move of that bird. If the prediction is correct, the bird will be removed from the sky. If not, the player will miss the shot and the bird will stay. Missing a shot reduces the players score by one point. Each bird hit increases the players score with one point (with the exception of black storks). The player can choose to shoot or pass each time step, based on the amount of information available.
Guessing species
The players may bet on the kind of specie of each bird after each round finishes. The players will get one point for each correct guess and lose one point for each incorrect guess. Guessing is optional, you will choose to guess or not for each bird. The score will be unaffected if no guessing is made. You will get to know the correct specie for each bird you make a guess on, regardless if your guess was correct or not. It is possible to get a passing score on this assignment without guessing species, so start with the shooting first.
Other players
There are traces of multi-player functionality in the skeleton but the game does not support true multi-player this year. However, in some of the environments, birds may die as if they were shot by other players.
Provided code
A basic program is provided for you in each of the supported programming languages. The program is fully functional as it is provided, but the program never shoots nor guesses.
The birds and the environments provided for testing are different from the ones that are used in Kattis.
You should modify the player class and you may also create any number of new classes and files. The files included in the skeleton may be modified locally but keep in mind that they will be overwritten on kattis (except for Player.cpp/hpp/java).
Your interface with the judge is the player class. Avoid using stdin and stdout. (Use stderr for debugging.)
Test environments
There are five test environments available to you. Each environment comes in two versions, with and without opponents. The default environment is SouthEmissions.in. You can play other environments by using the "load" option to the server, for example
./duckhunt server load ParadiseEmissions.in < player2server | ./duckhunt verbose > player2server
Grading
You can get up to 35 points for the assignment plus and an additional 2 points for early submissions. NOTE: The score given by Kattis will be mapped to points between 0-35 counting towards the course grade. To pass the assignment you need at least 70 on kattis. This corresponds to a course score of 15. You get course score 35 for anything above 450. When calculating the course score we round down to the closest integer. 
Minimum requirement
The minimum requirement for passing the assignment, 15 course points, corresponds to hitting more often than missing birds (with some margin).