Team name: Frictionless Bananas
Team members: Jeremy Sawicki (jeremy at sawicki dot us)
Lightning submission:
lightning.tar.gz
(lightning.gcc,
lightning.man)
Final submission:
final.tar.gz
(final.gcc,
final.man,
final.ghc)
The Frictionless Bananas had only one team member again this year. This page describes my 2014 ICFP Programming Contest entry.
For lambda man, I implemented a compiler in C++ for a simple Scheme-like language. The compiler parses S-expressions and produces lambda man machine code.
The language supports pretty much what you would expect and little more:
My lambda man implementation uses a graph of nodes representing all non-wall map locations in order to search for locations reachable by lambda man and the ghosts. A list of lists is used for slow lookup of nodes by their coordinates, for example to look up the node for lambda man's current location, and each node has links to its four neighbor nodes for constant time traversal from one node to the next.
Because the node graph contains cycles, the links between nodes must be mutable in order to build the graph. The ST instruction can only modify variables, not cons cells, so I implemented a mutable cell as follows (note that in my language set! returns the new value):
(make-mutable (lambda (val)
(let ((x val))
(lambda (f) (set! x (f x))))))
(mutable-get (lambda (m) (m (lambda (x) x))))
(mutable-set (lambda (m val) (m (lambda (x) val))))
Each node contains the following:
My lightning round AI performs a breadth first search from lambda man's current location to find the pill that can be reached in the fewest steps, and moves in the appropriate direction to reach that pill. It entirely ignores ghosts. If time permitted, I would have treated ghost locations as walls in the search.
My final AI performs two breadth first searches. The first search starts from all ghost locations. It takes into consideration the restriction on reversing direction, making the assumption that no power pills will be eaten. Each node stores four bits indicating whether the search has already visited that node for ghosts traveling in each of the four directions, as well as the minimum number of steps for a ghost to reach the node.
The second search starts from lambda man's location. In addition to avoiding walls, it avoids any location that can be reached by a ghost in the same number of steps or fewer than it would take lambda man to reach the location. Each location reached in the search is assigned a score, and lambda man moves in the appropriate direction to reach the highest scoring node.
The scoring is a heuristic that tries to score points while also trying to stay as far away from ghosts for as long as possible.
The "ghost distance" of a location is defined roughly as follows:
The score of a location is roughly the sum of the following:
The last rule is designed to make lambda man prefer directions where he can walk for as long as possible before encountering a ghost, but also to keep the distance from the nearest ghost as high as possible. He is willing to decrease the ghost distance in order to increase the number of steps he can walk, but only if the increase in the number of steps is at least as large as the reduction in the ghost distance (more if the ghost distance is reduced to 1).
I'm not sure how good those rules are, but they try to strike a balance between earning points and avoiding ghosts. If lambda man can score points before running into a ghost, he tries to do so in a way that maximizes the distance from ghosts. Otherwise, he tries to stay away from ghosts for as long as possible in hopes that an escape route will open up. In practice, he tends to go for power pills early because they both earn points and are considered to increase the ghost distance (if it is currently below 20).
My simulation of the game is not very accurate—the search assumes that lambda man and the ghosts move at exactly the same speed, and other things like the ability to reach the fruit or a ghost in fright mode are approximated. I didn't even begin to consider simulating ghost programs.
I implemented my ghosts using some simple code generation tools in C++. The tools include a representation of ghost instructions, some helper macros and functions to make it easier to construct a series of instructions, and a routine to format instructions as text.
My ghost AI is rather simple. It enumerates the legal moves and chooses a move that decreases the distance to lambda man if possible. In fright mode (but not invisible mode) it tries to increase the distance instead.
If there is more than one best move, each ghost uses its own direction preferences to break the tie, with some ghosts preferring horizontal moves and other preferring vertical moves. In hindsight, it would have been better to choose pseudo-randomly, because for example in the classic map a horizontal-preferring ghost can get stuck in the starting area.
By always moving towards lambda man, it is possible for all of the ghosts to get stuck in a map like this one (stuck.txt):
#################### # # # # ############.# # # # #........#.... # # # #.###.##...#.# # # # #..o#...##%..# # # # #.#.#.#..##.## # # # #.#.#.##..#..# # # # .......#..#.# # # # # #####.##.#.# # # \#......# # # ####### #.####.# # # # = # #...o#.# # # # ### # #.##.#.# # # #=# #=# ......# # # # ### # # ###### # # = # # # # ##### ######## # # # ####################
I had an idea to get around obstacles by remembering lambda man's location and following along a wall edge until the distance to the remembered location is smaller than when the ghost got stuck, at which point the usual algorithm is resumed, but I never implemented it. Aside from time constraints, I was also worried about the possibility of following an outer wall edge and unnecessarily circling the entire maze.
In my submission archive, the src directory contains C++ code and a Makefile. The code can be compiled by running "make" on Ubuntu 12.04 with g++ 4.6.3.
A lambda man can be compiled by running compileman [<filename.man> [<filename.gcc>]]. If either argument is missing or "-", stdin/stdout are used. If stdout is used, the output includes comments showing the source corresponding to each compiled section of code.
My ghost program can be generated by running mkghost [<filename.ghc>]. If the argument is missing or "-", stdout is used.