The Pacwar project

Agent design: PacWar

The context

This problem is about designing killer species that live in an imaginary world called PacWorld, created by Donald Knuth of Stanford University. PacWorld is inhabited by several species of tiny creatures called PacMites, all of which are engaged in a constant struggle for survival with every other species. Each individual mite lives out its short lifetime by following a small set of deterministic rules and interacting only with its immediate surroundings. However, in large numbers, the PacMites of a species combine to form complex patterns of behavior, which enable them to compete with PacMites of other species. Your goal is to design a species that will annihilate every other species in this world in a one-on-one duel.

screenshot of Pacworld

Pac World and PacMites

PAC-world consists of a grid of discrete cells, measuring 21 cells horizontally by 11 cells vertically. The world is completely surrounded by insurmountable barriers that occupy the outermost cells. Therefore, the actual world measures 19 cells by 9 cells. In the simulator, the barriers are not displayed, so only the 19x9 region is visible.
Each cell may be occupied by a blob (i.e. an empty cell) or a PAC-mite. The PAC-mites are represented by pacman-like symbols. PAC-mites can be facing any of the cardinal directions (right and left, up and down). Direction 0 is used to indicate a right-facing mite, 1 to indicate an upward-facing mite, 2 to indicate a left-facing mite, and 3 to indicate a downward-facing mite.
Pacmites have a life span of 4 rounds. Their age (0,1,2,3) is represented by the number of rings at their centers, and they are colored according to the species to which they belong. The number of rings a PAC-mite has corresponds to the age of the mite and its power. A ringless mite has just been born, while a mite with three rings has been around for the past three rounds. Since a mite dies after four time rounds, no mite has more than three rings. In the world depicted above there are four blue pacmites of age 3 and seven newborn mites (age 0).
Since age and the direction a pacmite faces are independent, there are sixteen possible configurations for a PAC-mite of any given species.

The Dynamics of PacWorld

The contents of PacWorld change deterministically in discrete steps of time (rounds). This transition function is completely local -- that is, the contents of a cell at time t+1 depend only upon the contents of that cell and its four neighboring cells at time t. In this transition, which is described below, each mite
- ages,
- possibly changes direction,
- possibly causes a baby mite to be born in the cell that it was facing,
- possibly dies,
- or is replaced by a mite of the opposing species.
The transition function is as follows:
- A cell containing a blob at time t also contains a blob at time t+1, unless there is a birth into that cell (see U below).
- A cell containing a k-ringed PACmite at time t will normally contain a k+1 ringed PacMite of the same species at time t+1. There are two exceptions to this rule:
  1. If the PacMite already has 3 rings at time t, it dies of old age and will normally revert to a blob at time t+1.
  2. If the cell which the PacMite inhabits is being attacked by hostile PacMites, the normal aging process may be overridden as explained below. If neither of the above conditions hold, the k+1-ringed mite will turn (see W, X, Y, and Z below).
- If a cell containing a PacMite is being attacked by one or more PacMites of a different species at time t, then one of these rules applies.
  - If all of the most powerful attackers are friendly, the PacMite in the cell ages normally, as described above.
  - If there is a unique most powerful attacker which is of a different species, the mite is replaced by a baby enemy mite (see V below).
  - Otherwise, the cell is being attacked by at least two different equally powerful PacMites, at least one of which is hostile. In this case, the competition for the cell is so intense that the PacMite is destroyed, leaving only a blob behind.

All PacMites of a given species have a common genetic code. The PacMite genetic code has 50 components, we will call genes. Each gene takes on one of four values: 0, 1, 2 or 3. Thus there are 4⁵⁰ possible species of PacMites. We need a small amount of notation to describe the function of the genes. A turn is a rotation of 90 degrees counter-clockwise. We use l to represent an age (0..3), e represents the difference between directions of mites A and B (in the number of turns it takes A to face B's direction) (0..3), and k is an age (0..2). The genes and their general functions are:

[U] If an empty cell has exactly 1 oldest mite facing it, a new baby of that species is born there, Ul turns from the direction its "mother" is facing, where l is the age of the mother.
[V] If a mite (``she'') is facing an enemy mite (``he'') and is the single, strongest mite facing him, he is replaced with a baby of her species, Vel turns from the direction she is facing, where e is the difference between his and her directions, and her age is l.
[W] If a mite survives this round and is facing a barrier (i.e., is at the edge of PacWorld), it turns Wk times, where k is the age of the mite.
[X] If a mite survives this round and is facing a blob, it turns Xk times, where k is the age of the mite.
[Y] If a mite survives this round and is facing a friendly mite, it turns Yek times, where e is the difference between the mite's and his friend's directions and k is this mite's age.
[Z] If a mite survives this round and is facing an enemy mite, it turns Zek times, where e is the difference between the mite's and his enemy's directions and k is this mite's age.

Examples

Here are a few examples to aid in the understanding of the laws of PAC-world.

Two PacMites A and B both face a certain cell, but A has more rings than B does. If the cell contains another mite of A's species, this mite will age normally. If instead it contains a blob or mite of some other species, it will now contain baby mite of A's species. Simultaneously A and B change direction and age, or they are consumed by some other mite attacking them.
Four PacMites, A, B, C and D all aim at a certain cell. A and B both have three rings, while C and D have two or fewer rings. If both A and B are of the same species, and the cell also contains a mite of this species, the mite will be allowed to age normally. Otherwise, the cell will contain a blob at the next time step.
Two adjacent PacMites A and B of different species face each other. Assuming they are isolated from other attacking mites, they will cause baby mites b and a to occupy the previous sites of A and B respectively. These newborn mites might possibly be attacking each other as well.

How duels between species are evaluated

Duels are held only between pairs of species. Duels will continue until one species has been completely eliminated, or until 500 time units have passed. If neither species has won after 500 time units, the relative populations of the two species will be used to determine the score of the duel. Each duel is worth a total of 20 points. These 20 points will be divided between the two species as follows:

Points for a duel	Outcome of a duel
20-0	Destroying the opposing species in under 100 rounds
19-1	Destroying the opposing species in 100-199 rounds
18-2	Destroying the opposing species in 200-299 rounds
17-3	Destroying the opposing species in 300-500 rounds
13-7	Outnumbering the opponent by at least 10:1 after 500 rounds
12-8	Outnumbering the opponent by between 3:1 and 10:1 after 500 rounds
11-9	Outnumbering the opponent by between 1.5:1 and 3:1 after 500 rounds
10-10	If neither species outnumbers the other by more than 1.5:1 after 500 rounds

Observe that this scoring system gives significant advantage to species that actually destroy the opposing species rather than just outnumbering them. The reason for this complicated scoring system is that the set of all PacMite species is probably not a totally ordered set. Thus, it is possible that no clear winner would emerge from the competition if we simply considered the number of wins/losses/draws. The scoring system makes it unlikely that this will occur.

Your task

Your mission is to find a PacMite species that will annihilate the PacMites submitted by your classmates in a round-robin duel. All the primary code resources for the project are in the code/pac subdirectory on owlnet in the comp440 account.

What to hand in

A PacMite for the competition: Each team will submit their best entry into a round-robin duel on December 4, 2007, in class. We will set up projection equipment to watch duels on a big screen on December 4, 2007 in McMurtry Auditorium at 7 pm. Pizza will be served.
The report: Prepare the final report containing information about your experiments to date, variations on search algorithms you tried, your current knowledge of the search space topology, and your final strategy for devising a killer gene. The report is due on December 4, 2007. You have the option of turning in a near final draft to me by November 29 and I will give you feedback in two days. December 4, 2007 is the last day to submit your final report.
Interim progress reports and draft of final report: Interim progress reports (with due dates indicated in the course schedule) are an important deliverable for this project. They should be 2-3 pages in length and they should provide a description of your results to date as well as your analysis and interpretation, clearly indicating the progress you have made since the previous report. I expect to see discussion of your overall strategy to find the killer gene, what hypotheses you had about the search space, how it influenced your design of the exploration algorithm, what heuristics you used to guide your search, what you thought were more profitable regions, how well they worked, how you revised your hypotheses, your algorithms, etc. These interim progress reports will be returned to you with comments. You are encouraged to use this feedback facility to help with writing your final report and also to get technical suggestions from me on how to best direct your search efforts. Interim reports are due as indicated in the course schedule. You have the option of turning in a near final draft of your report to me on November 30 and get feedbackto help you with fine tuning your final report, which is due on December 4 in class.