World of Foo: lisp/AI competition


World of Foo is a coding tournament focused on creating (in lisp) code to control a species of critters. Anyone is welcome to submit entries anytime, but I'll be running the formal competition early in March.

World of Foo is a game in which each competitor, in lisp, designs one species of critters, which will (after the study break) compete against the other class submissions and some species submitted by the instructor (including some of the ones shown in the sample code section below).

You will be writing the code to determine your critters' actions in a series of encounters with other critters. A central controller will run the game, loading the file for each submission, generating a population of critters, and then running the game for a set number of turns (e.g. 250).

Each critter has five permanent stats/skills (attack, endurance, farming, mining, and trading) and three variable stats (food supplies, current health, and wealth). At the start of the game each critter will be given a random number of points (e.g. 21-30) to allocate between their permanent stats.

At the start of the game, the critters will be randomly distributed across an NxN map (map size is determined by the controller).

Each turn, the critters in each map hex will be randomly paired up - one critter from each pair gets to pick an action, the other critter gets to pick how it responds. (Where there are an odd number of critters, the one leftover critter gets to spend its turn with no opponent.) Based on their current stats and chosen actions, the central game controller will adjust each critter's current health, food supplies, and wealth.

The next section of this document provides greater detail on the game rules for critter choices and deciding the results of encounters. The final section details the code specifications that must be followed so your code will interact with the controller correctly.

Game rules

At the start of the game, a number of critters of each species will be generated (e.g. 30).

Each critter is randomly allocated a number of points to be distributed between their permanent stats. Each critter is also told what the upper limit is on points-per-stat, e.g. a critter might be given somewhere between 24 and 30 points, and told they can allocate up to 10 points to any one stat.

Within those limitations, the critter can chose any allocation of points to the following stats: attack, endurance, farming, mining, trading.

Each critter also has three variable stats: food (starts at 0), wealth (starts at 0), and health (starts at the critter's endurance value).

Game play

The game continues for a fixed number of turns (e.g. 250).

Each turn, all the critters from all the species are randomly split into pairs.

One critter from each pair will be randomly chosen, is told what species the other critter is from, which critter within that species (e.g. cow #23) and gets to chose what action they wish to take. (This critter is referred to as the initiator.)

The other critter (the responder) is then told what species the initiator is, and what action they selected, and their id within the species. Based on that information, they get to pick a response.

The initiator actions can be any one of:

The responder actions can be any one of:

Encounter results

The encounter results depend on the actions chosen and the two critters' various stats, and are determined as follows:

If both critters chose to attack, or one attacks and the other flees unsuccessfully (see below) then combat takes place and each critter automatically loses one health.
In the event of combat, each critter's attack value is compared to the other's, the difference is subtracted from the health value for the loser.

Note fleeing/pursuit costs one point of health each, combat costs another, and the attack resolution can cost the loser more on top of that. All this is in addition to the point of health always lost for a turn not spent eating. Combat is costly to health!

If either critter's health is reduced to 0 then they can be robbed of food and wealth by the other critter by up to the robber's farming/mining skill levels. (If both critters' health is reduced to 0 then neither is in any condition to rob the other.)

If one critter flees and the other attacks, they each lose one health for the pursuit. Fleeing critters can drop small amounts of food and/or wealth to distract their opponent. There is a 50/50 chance the critter gets away, modified by 10% for each unit of food/wealth dropped. If the critter gets away then their opponent picks up what was dropped, otherwise combat ensues.
If one or both critters flee when the other isn't attacking then the fleeing critter(s) still lose one health.
Critters who successfully flee move one map hex in a random direction.

If sharing is offered and accepted, then all food and wealth is evenly divided between the two critters. If there is an odd amount then the original owner gets the leftover.

When making a trade offer, the initiator specifies whether they want to trade their food for the other's wealth or vice versa. In a trade, each critter receives an amount equal to their trading skill - it pays to be a good trader.
Trading includes attempts to con critters with lower trading skills - sort of an economic attack. As a responder, the only way to get out of trading is to either flee the hex or try to attack the trader.

The critter can choose to move one map hex north, south, east, or west.

If a critter spends the turn eating (without getting involved in a fight or trade) they gain three health (but never taking them above their endurance rating)

If a critter spends the turn harvesting (without getting involved in a fight or trade) they gain food equal to their farming level.

If a critter spends the turn collecting (without getting involved in a fight or trade) they gain wealth equal to their mining level.

If a critter spends the turn surveying (without getting involved in a fight or trade) they are sent an update clarifying the hex's row and column, farming limit, mining limit, remaining mining capacity, and the number of other critters present in the hex.

The critter sends a text string to the other critter in the encounter (max string length limited by controller, currently up to 960 characters)

The critter chooses to re-allocate all their stats (still within the points/max stats limitations).
This costs the critter 2 food and 2 health, and the changes take effect at the end of the turn.

Health, and helplessness

No critters die in the course of this game, but they can be reduced to helplessness and robbed.

Each turn not spent eating, a critter's health decreases by 1. This is in addition to any health reductions due to combat and/or fleeing.

If a critter's health is 0 then they must attempt to eat. If they have no food then the only actions they can take are offer/accept sharing - they are essentially helpless until someone shares with them. Helpless critters automatically lose (and get robbed) if attacked.

Food and mining limitation

Farming and mining each have some limitations:

The Hall of Knowledge

Each critter is given access to its species Hall of Knowledge, where it can store information for the rest of its species to see, and access information stored there by the other critters in its species.

The map

The World of Foo is played on an NxN map, where the top/bottom edges "wrap around", as do the left/right sides (so I guess Foo is actually a donut-shaped world).

Each square on the map has one value indicating how suitable it is for farming, and another indicating how suitable it is for mining. The various ways for critters to find out how good a hex is for farming/mining include
(i) spend the turn "surveying" to get a precise summary
(ii) give it a try and see how much their assets increase by,
(iii) use the "TELL" command to tell one another what they've learned about specific map squares so far,
(iv) sharing information with other members of the species through its hall of knowledge.

The competition

Winning is mostly just for bragging rights, losing won't impact your mark.

After the submission deadline, all entries will be run together via the game controller.

There will be two runs, one on a map with reasonably distributed resources, the other where most of the map is resource-poor, but with pockets of good resources. The maximum stat value will be set at 12, with an average of about 33 points per critter, and a population of 25 critters per species.

The winner will be the species that possesses the most food+wealth at the end of the game (across all its critters).

In the event of a crash or shutdown, the species that caused the crash will be eliminated from the tournament and the game re-run without them.

Code specifications and restrictions

All code will be run using gcl on otter (or one of the pups).

Entries must be submitted by fork/cloning the wofoo repository and pushing the completed entry by the deadline.

You will be implementing your code in a let-over-lambda style, returning a dispatcher function that allows the game controller to interact with that critter (more detailed discussion below).

Because all competitors will be providing code run by/interacting with the central controller, there are some strict rules around the code. If your code violates any of the rules below you will be immediately eliminated from the competition.

If your code gives an invalid choice/response at any point, the controller will pick a default choice instead.

*Note: you can safely assume the random number generator has already been seeded: do not make your own call(s) to (make-random-state).

Code base: the controller code and a collection of sample critters is available here, and will also be made available as a csci git repository (the repo name will be wofoo).

  • readme: details on how to run the game yourself, and settings that can be easily customized
  • game controller

  • very simple species controllers: bull, cow, redx, robber

  • slightly more advanced:
      - farmer (harvesting food and trading for wealth),
      - foo (hunters/traders who avoid ants),
      - miner (collecting wealth, share surveying results through hall of knowledge)

  • more complex behaviour:
      - trader (always making deals, build up customer ratings through the trader hall of knowledge)
      - ant (ants specialize as workers or soldiers, leaders take over to make decisions for the group, trying to form swarms in good map hexes, attacking any other species that blunder into their hex, strip-mine the hex until it's empty then leave, coordinate everything through Hall of Knowledge)

  • species that change over time:
      - morpher (tries different combinations of stats
      - adapter (tries different combinations of actions for different species) until one performs well, bases current actions on strengths of current stats ... not currently adapting very well)

  • a playable species, prompts player for choices as game proceeds: human
    (requires HumanPlayer set to t in controller, creates just one human)

  • a non-tourney species used to test the controller's error checking: badCritter

  • two sample log files, one from a run on a normal map and one from a run on a sparse map. The results summaries are found right at the bottom of the log files (just the report summaries are shown below).

Turn 1000, MaxStats: 12, Points: ~33, Critters/species 25, SparseMap? no, MapSize: 14x14, Critters/hex 1.4, Resources x 0.83
| ***Species Report: current stat averages ***       num  |           *** Average # encounter types ***            HELP-|
| Species   attk endr farm mine trad food hlth  wlth hlpL | fght trad farm mine shar flee move tell surv mrph eats LESS |
| REDX    :  0    12   12   0    8    170  6    159  4    |  194  74   98   0    41   0    51   0    0    0    269  305 |
| ANT     :  7    10   9    5    0    177  9    1451 0    |  44   7    67   511  0    0    53   0    0    0    269  11  |
| COW     :  9    11   11   0    1    794  9    112  0    |  72   74   371  0    13   11   43   0    0    0    279  30  |
| MINER   :  5    10   4    9    5    104  6    865  4    |  103  66   22   198  37   4    71   0    34   0    222  278 |
| ROBBER  :  11   10   6    5    0    944  8    705  0    |  544  10   53   0    0    0    19   0    0    0    335  0   |
| TRADER  :  4    9    5    5    9    136  6    1358 1    |  77   167  98   314  5    4    51   0    0    0    270  52  |
| FOO     :  10   7    3    4    9    118  5    693  0    |  301  241  49   77   1    3    21   0    0    0    317  16  |
| ADAPTER :  5    10   6    5    5    474  6    48   3    |  151  51   354  19   9    24   51   0    0    0    315  77  |
| FARMER  :  6    11   11   1    5    977  6    22   0    |  141  115  291  0    6    0    50   0    0    0    322  25  |
| BULL    :  11   11   9    1    0    833  9    74   0    |  315  10   51   0    0    0    35   0    0    0    322  11  |
| MORPHER :  6    6    6    6    7    199  4    836  0    |  121  107  92   352  3    4    51   0    0    4    259  107 |

Turn 1000, MaxStats: 12, Points: ~33, Critters/species 25, SparseMap? yes, MapSize: 14x14, Critters/hex 1.4, Resources x 0.83
| ***Species Report: current stat averages ***       num  |           *** Average # encounter types ***            HELP-|
| Species   attk endr farm mine trad food hlth  wlth hlpL | fght trad farm mine shar flee move tell surv mrph eats LESS |
| REDX    :  0    12   12   0    9    12   4    10   14   |  120  33   219  0    186  0    64   0    0    0    168  501 |
| ANT     :  6    10   10   6    0    115  8    1788 0    |  70   3    87   470  16   0    33   0    0    0    264  61  |
| COW     :  10   11   11   0    1    56   8    6    3    |  71   40   274  0    62   12   53   0    0    0    259  86  |
| MINER   :  5    10   4    9    5    19   4    127  13   |  88   32   9    18   288  3    81   0    20   0    97   679 |
| ROBBER  :  11   10   6    5    0    390  9    344  0    |  542  4    77   0    0    0    20   0    0    0    314  0   |
| TRADER  :  4    9    5    5    9    31   4    79   9    |  127  105  81   77   107  4    49   0    0    0    174  435 |
| FOO     :  10   7    3    4    9    101  5    282  1    |  240  198  90   72   31   2    32   0    0    0    274  115 |
| ADAPTER :  5    10   6    7    5    38   4    43   10   |  131  37   288  18   99   15   50   0    0    0    209  359 |
| FARMER  :  6    10   10   1    5    177  5    24   5    |  149  66   185  0    37   0    52   0    0    0    254  276 |
| BULL    :  11   11   9    1    0    311  9    35   1    |  307  7    80   0    9    0    38   0    0    0    303  23  |
| MORPHER :  7    6    6    7    6    35   3    50   10   |  89   39   211  156  119  2    56   0    0    28   200  321 |


Here are a few ideas for new species (I'm sure you can come up with many others!)

Code explanation and discussion

Your dispatcher (implementation discussed below) will have a fixed general structure, and a number of required methods that allow the controller to interact with it.

At the start of the game, your dispatcher will be called once for each critter in your species, at which point it will need to decide on a points allocation, and generate/return a lambda function that allows the controller to interact with it. (The lambda function that will do this is provided as part of the code template below.)

Once all critters for all species have been created, the controller will start the sequence of game turns.

Each turn, the controller will follow the sequence below:

Implementing your dispatcher

This is, of course, the actual coding part of the assignment, and does involve aspects of most of the lisp topics we cover in the course.

The required skeleton of your submission is shown below.

All your code will be added through local functions and variables, in the sections indicated in the comments.

Essentially your function acts something like a constructor in OO languages, setting up this critter's local variables, and declaring some local functions.

At the very bottom, it returns a lambda function to the controller, that the controller will use for the rest of the game to communicate with this critter.

The controller will periodically call that lambda function, sending a command and some options, and that will in turn fire up one of your four local functions:

You can add any additional local functions you wish (within the labels), and any additional critter fields you wish (within the let variables), and you can customize the body of initiate, respond, and update as much as you like (as long as they still return valid results).

Points allocation

Aside from the functions mentioned above, when your critter is first created you need to set up a points allocation based on the points you're given (Points) and the maximum value that can be assigned to any one stat (StatMax).

In the sample template below, this takes place after the end of the local methods section, just before the creation of the final lambda function. You can divy up the points any way you see fit, as long as you stay within the Points and StatMax criteria.

Hall of knowledge

Each species has a shared hash table, its "Hall of Knowledge", that every critter in the species can access. The hash table is initially empty, how you choose to use it (if at all) is totally up to you.

To ensure compatibility with the controller,
sections in bold are where your own code will go.

; WoFoo critter template ; create a critter given parameters specifing ; - an ID for it, ; - the total number of Points available to be spent on permanent stats, ; - the maximum number of points that can be spent on any one stat, ; - the species hall-of-knowledge hash table ; - the starting map row and column for the critter ; return the lambda function that acts as a dispatcher for interaction ; with the central controller (defun youruserid (critID Points StatMax hok row col) (let* ( ; keep track of this critter's stats, ; we're setting them to 0 initially, ; and will allocate the points correctly later (attack 0) (endurance 0) (farming 0) (mining 0) (trading 0) (health 0) (wealth 0) (food 0) (row 0) (column 0) ; 0,0 is upper left corner of map ; make note of the species hall of knowledge (hash table) (hallOfKnow hok) ; keep track of this critter's id (id critID) ; --------------------------------------------- ; YOU CAN ADD ANY OTHER LOCAL VARIABLES HERE, ; these will exist for the entire lifetime ; of this critter ; --------------------------------------------- (scratch 0) ; we use this as temporary storage during some calculations later ) (labels ( ; --------------------------------------------- ; YOU CAN ADD ANY OTHER LOCAL FUNCTIONS HERE ; - they can call each other, and/or you ; can make calls to them from inside allocate, ; initiate, respond, and update ; --------------------------------------------- ; this method is called to ask how you allocated your stats (allocate () ; the permanent stats were initialized earlier (just before the dispatcher) ; so just return them in the order expected (list attack endurance farming mining trading)) (updateMap (coords resources numCritters) ; the results of your survey ; coords is (row col) ; resources is (farmingLimit miningLimit miningCapacity) ; numCritters is the number of critters in the hex ) ; this method is called when the other critter has used tell to send you a message (readmsg (msg) ; the other critter in this encounter sent you a message (a string of up to 256 characters) ; whatever you like with the information ) ; this method is called when your critter has been selected as an initiator (initiate (species id) (cond ; -------------------------------------- ; This is where you pick what action ; your critter should take as initiator. ; The parameter tells you what species the ; other critter is and its id in that species, ; e.g. 'COW 23. ; -------------------------------------- ; right now the critter always just harvests (t '(HARVEST))) ) ; this method is called when your critter has been selected as a responder (respond (species initiatorAction id) (cond ; -------------------------------------- ; this is where you pick what action ; your critter should take as responder, ; (the parameter tells you what species the ; other critter is and what action it chose, ; as well as its id within that species) ; -------------------------------------- ; right now the critter always just harvests (t '(HARVEST))) ) ; this method is called to let you know what your stats are ; at the end of an encounter and what the action/response were (update (turnResults action results) ; here we're just storing them in our local variables ; in case we need them elsewhere (setf attack (nth 0 turnResults)) (setf endurance (nth 1 turnResults)) (setf farming (nth 2 turnResults)) (setf mining (nth 3 turnResults)) (setf trading (nth 4 turnResults)) (setf food (nth 5 turnResults)) (setf health (nth 6 turnResults)) (setf wealth (nth 7 turnResults)) (setf row (nth 8 turnResults)) (setf column (nth 9 turnResults)) ; -------------------------------------- ; if there is any updating you'd like ; to do based on the turn results, ; this is the appropriate spot ; -------------------------------------- ) ; end of local methods ) ; ----------------------------------------------------------------- ; this is the section where we initialize our local variables, ; in particular we need to divy up the points amongst our stats ; this only runs once, when the critter is first created ; ----------------------------------------------------------------- ; in this example we divide the points up more-or-less equally, ; though we have to do some rounding up/down (setf scratch Points) (setf attack (ceiling (/ scratch 5))) (setf scratch (- scratch attack)) (setf endurance (ceiling (/ scratch 4))) (setf scratch (- scratch endurance)) (setf farming (ceiling (/ scratch 3))) (setf scratch (- scratch farming)) (setf mining (ceiling (/ scratch 2))) (setf trading (- scratch mining)) (setf health endurance) (setf wealth 0) (setf food 0) ; this method is being sent back to the controller once the critter ; is first set up ; for the rest of the game, the controller will use it to communicate with ; the critter through the commands ALLOCATE, INITIATE, RESPOND, UPDATE ; begin the dispatcher, responds to requests from the controller (lambda (request &optional (arg1 nil) (arg2 nil) (arg3 nil)) (cond ((equalp 'MESSAGE request) (readmsg arg1)) ; other critter sent you a message ((equalp 'MAPINFO request) (updateMap arg1 arg2 arg3)) ; results of your survey request ((equalp 'ALLOCATE request) (allocate)) ((equalp 'INITIATE request) (initiate arg1 arg2)) ; species, id ((equalp 'RESPOND request) (respond arg1 arg2 arg3)) ; species, action, id ((equalp 'UPDATE request) (update arg1 arg2 arg3)) ; new stats (t (format t "~%***DANGER DANGER: The controller is issuing bad requests! ~A ~A ~A~%~%" request options extra)) )))))