Team name: Frictionless Bananas
Team members: Jeremy Sawicki (jeremy at sawicki dot us)
Lightning submission:
lightning.tar.gz
Final submission:
submission.tar.gz
The Frictionless Bananas had only one team member this year. This page describes my 2017 ICFP Programming Contest entry.
My first attempt at a strategy was to choose moves greedily: on every turn, make the move that gains the largest number of points on that turn alone.
Computing the greedy move efficiently is not entirely straightforward. It requires some data structures that proved useful for later strategies as well. I first partition the sites into connected components, where by "connected" I mean connected by my own rivers. I also identify those components that contain mines, which I will call mine components. I then build a table that stores for each (mine component, component) pair the number of points that would be gained by connecting each mine in the mine component with each site in the other component. The table is filled by performing a breadth-first search from each mine. For each site reached in the search, the square of the distance is added to the appropriate entry in the table. Once the table is built, it is easy to determine the number of points gained by each move by looking up in the table the two components that the move connects. Up to two lookups are required, one for each of the components that is a mine component. All of this should require time and space roughly proportional to the number of mines times the size of the map, perhaps with a log factor thrown in somewhere.
My lightning round submission uses the greedy strategy, with an additional rule to break ties by favoring rivers that have the most neighboring unclaimed rivers (to maximize options for future moves). My final submission keeps the greedy strategy as a fallback in case of time pressure.
To do better than the greedy strategy, one must look further ahead. Starting from a mine, it is desirable to build a path in a direction that will lead to higher scoring moves in the future -- typically either because the path reaches sites that are far from the original mine, gaining points for distance, or because the path reaches another mine, gaining points by using the same rivers to serve multiple mines -- ideally both.
To generate a set of candidate paths, I use breadth-first search from each mine component. The search takes place in the graph of connected components, not the graph of sites, so the resulting path may not be a contiguous sequence of rivers if it enters and leaves a component at different sites.
To choose among multiple candidate paths, I use a metric of the total number of points gained by a path divided by the number of moves in the path. The idea is to maximize the average number of points gained per turn. In theory, it seems that the points gained in later moves should be discounted to account for the possibility that the entire path may not be successfully completed. I briefly experimented with a simple exponential decay like 0.99^turns, but I did not enable it in my submission. After the contest I determined that such a rule does appear to help on a selection of maps.
To determine the number of points gained by each path, I use the same table as in the greedy strategy. Initially, I implemented an approximation that includes points gained by connecting the initial mine component with later components in the path, but excludes points gained by connecting later components with each other. Computing the approximation requires up to two table lookups per component. Later I implemented the accurate computation, but surprisingly I found it to generate worse moves in practice. The main issue was that it would try to connect two mines by building from both ends simultaneously, while it is more desirable to build from one end in case the path cannot be completed. I think the approximate calculation was in effect discounting the points gained by later moves. Perhaps the best approach would be to use the accurate computation combined with an appropriate discounting rule.
My final submission generates a new best path on every turn, and makes the first move of the path. By generating a new path on every turn, it is able to respond to changing conditions resulting from other players' moves. It is also able to follow paths that are outside the limited set of candidate paths generated by the breadth-first search. For example, I sometimes observed my program proceed towards a distant mine for a while, then take a brief detour to visit a nearby mine before continuing in the original direction. The most desirable path may be one that visits both mines, but the breadth-first search will not generate such a path if the second mine can be reached in fewer turns by bypassing the first mine.
Three extensions were made to the problem specification during the course of the contest. While it was necessary to implement basic support for the new protocol messages, actually using the extensions was optional. I only found one of them to be an important part of a winning strategy.
I am skeptical that using futures is a good strategy. At first, it seems that they should be quite important: Using n moves to reach a destination earns n^3 points using futures, but only n^2 points under ordinary scoring rules. On the other hand, points are earned for every site along the way to the final destination, so the actual number of points earned under ordinary scoring rules is closer to 1/3 * n^3, and more if multiple mines are visited. Furthermore, futures carry a risk of losing points for failure to reach a destination. In games with many players, I found that the possible destinations are significantly constrained by the actions of other players. It seems better to adapt to changing conditions and gain as many points as possible by visiting the best destinations that happen to be accessible. Then again, I did not seriously attempt to use futures so I may be mistaken. The options extension makes them less risky and potentially more valuable.
My lightning and final submissions both make one trivial use of futures: If I am the first player, I buy a future for my first move for a guaranteed gain of one point. On the large maps that will be used in the final round of judging, one point is not worth the time spent implementing the feature or the resulting complexity and risk of bugs. I mainly did it as a test of my infrastructure.
I am also skeptical about the value of splurges. Deferring turns does not gain any truly valuable benefit, like a larger number of turns later. The only theoretical benefit seems to be that you don't have to risk making moves towards a destination until you can be sure that you will reach it. On the other hand, deferring moves means that you may not be able to reach a destination that you could have reached by moving as soon as possible because some of the necessary rivers may have been claimed by another player in the meantime, which seems like the more important consideration in practice.
I implemented a version of my main strategy that skips turns until the chosen path (or a contiguous part of it) can be claimed all at once, but I found it to perform worse.
Options seem to be clearly beneficial in at least some circumstances, for example if they allow a path to connect to a mine that cannot otherwise be reached. The main question is how to decide when to use them for the greatest benefit.
My main strategy evaluates candidate paths based on how many points are gained per turn. With the introduction of options, there are two scarce resources: turns and options. It is not clear how to compare two paths when one requires more turns and fewer options than the other to gain the same number of points. Some kind of exchange rate between turns and options may be needed. Also, my main strategy generates a limited set of candidate paths using breadth-first search, and it must be modified somehow to generate paths that use options when necessary, but to avoid using them too much.
I settled on a rule that I will only generate a path using n options if the destination cannot be reached using n-1 options. To implement that rule, I first perform a breadth-first search using no options, then restart the search from all those destinations using a single option, and so on.
Initially I ignored the cost of options and only evaluated candidate paths in terms of points per turn as before, which worked fairly well. After some testing, I found that treating an option as equal to one turn worked a bit better on a selection of maps. It seems like an option should be worth many more turns, but that kind of rule did not work as well in practice. I suspect that the choice of candidate paths already was sufficiently biased against using options.
My program is written in C++ and uses the Jansson library for JSON manipulation, as well as some homegrown libraries and utilities that I have developed over the years with the contest in mind.
During the contest I wrote a graphical visualizer that allows watching a game as it progresses. I have learned in past contests the importance of a visualizer to gain valuable insights into how a program is behaving.
About three hours before the end of the contest I wrote a tool that runs a large number of games between two versions of my program. I can run 1000 games on a selection of 12 maps with varying extensions and turn order in under 10 minutes on 6 cores. Just in the final hours of the contest it provided some valuable insights, and I wish I had it sooner. I will have to add that to my list of tools to remember to write in future contests.
This contest was a lot of fun, and I thought the organizers did a great job.
I am sometimes skeptical of game playing contests, because in addition to the uncertainty of what kinds of maps will be used for judging there is the added uncertainty of what strategies will be used by other competitors. Both things mean that there is not necessarily an objectively best program -- it depends on the circumstances. But games are also fun, and I definitely had a lot of fun with this task. I could also nitpick about various details of the spec or little glitches along the way, but I don't want to detract from what was overall a great contest.
Thanks to the organizers for all the hard work putting the contest together!