Saturday, 8 November 2014
Friday, 19 April 2013
ClojureScript & WebGL
A week ago I went to Hack the Tower, a JVM language hackathon (mostly Java/Scala/Clojure). Working with David, our agenda was to try to get a simple WebGL hello-world to work from ClojureScript.
For this I had previously found some example code written by Vishvajit Singh of the Los Angeles Clojure Users Group. We managed to make the code compile and work with modern versions of Leiningen etc. You can find the code on my GitHub and see it in action here.
Looking at the code, what I'd like to do next is to simplify things a bit and see how much of a hassle it would be to get rid of PhiloGL and instead implement that stuff in ClojureScript myself. (No offence to PhiloGL - it's great, but I'm not sure that using JavaScript libraries from ClojureScript is the most elegant way of doing things.)
Another simple thing would be to add a textbox that takes a URL pointing to an image file and then uses that image file as the texture. Or why not even take a URL pointing to a 3D object file, say a .3DS or a Blender file, and then render that. The possibilities are endless. And while I'm dreaming, how about adding sound - how would one go about doing that?
WebGL is awesome, need to explore it a bit more when I have time.
For this I had previously found some example code written by Vishvajit Singh of the Los Angeles Clojure Users Group. We managed to make the code compile and work with modern versions of Leiningen etc. You can find the code on my GitHub and see it in action here.
Looking at the code, what I'd like to do next is to simplify things a bit and see how much of a hassle it would be to get rid of PhiloGL and instead implement that stuff in ClojureScript myself. (No offence to PhiloGL - it's great, but I'm not sure that using JavaScript libraries from ClojureScript is the most elegant way of doing things.)
Another simple thing would be to add a textbox that takes a URL pointing to an image file and then uses that image file as the texture. Or why not even take a URL pointing to a 3D object file, say a .3DS or a Blender file, and then render that. The possibilities are endless. And while I'm dreaming, how about adding sound - how would one go about doing that?
WebGL is awesome, need to explore it a bit more when I have time.
Monday, 4 March 2013
A fun little function
Working through the backlog of potentially interesting bits I've been meaning to post about, I came across this one. Suppose you're given an unknown function, call it
Question 1: what does the function
The input ints are interpreted as the edges of a puzzle piece, which is then printed out. Viewing the ints in their binary form, it's easy to see that the orientation of the edges is clockwise, north-east-south-west:
Question 2: how would you implement the function
A simple scanline algorithm should be good for this. First convert the given ints, interpreted as 5-bit numbers, into a 5x5 boolean matrix for simplicity. (Note that the center 3x3 of each puzzle piece is always filled, so it's just the given 4 edges that make this interesting.) After this start at, say, the upper left corner, and going through each row in the matrix left to right, check the values for this cell and the relevant neighbours and draw accordingly. (Define the cells outside the matrix to have the value 0.)
Now since you're processing the cells in order, top-to-bottom and left-to-right, it's sufficient at each cell to just consider the upper, upper-left and left neighbours. This gives you in theory 16 different cases. Sketching them out you'll find 5 distinct cases (or 4, depending on how you look at it); or you could just notice that there are 4 main cases depending on whether you've just crossed a horizontal edge, vertical edge, both or neither, and then one more case depending on whether you've just ended or started a both-horizontal-and-vertical cross point.
Instead of going through the algorithm in more detail, here's the link to an implementation on Github. I wrote the refactored version in slightly scruffy C for some reason, after noticing that the first implementation I had done a while back was amusingly bad. To test it out, simply say "make" and for some examples, see the "test" script. (No unit tests this time, sorry.)
foo, and asked to figure out what it does. The function takes as parameters four ints and returns a string. Experimenting a bit, you figure out that if the ints are small and non-negative, the function returns nice ASCII art:
> print(foo(4, 12, 4, 10)) +---+ | | +-------+ +-------+ | | +---+ | | | +---+ +---+ | | +-------+ +---+ | | +---+ > print(foo(24, 5, 24, 11)) +-------+ | | | +-------+ | | +---+ +---+ | | +---+ +---+ | | +-----------+ +---+ | | +-------+
Question 1: what does the function
foo do?
The input ints are interpreted as the edges of a puzzle piece, which is then printed out. Viewing the ints in their binary form, it's easy to see that the orientation of the edges is clockwise, north-east-south-west:
--> +-------+ | 1 1 | 0 0 0 | +-------+ | | 1 1 1 1 | 0 | +---+ +---+ v ^ 0 | 1 1 1 1 | | +---+ +---+ | | 1 1 1 1 | 0 +-----------+ +---+ 0 0 0 | 1 1 | +-------+ <--Here of course 24 = 11000, 5 = 00101, 24 = 11000 again and 11 = 01011. The ordering is a bit arbitrary and there's an overlap between the first and last bits of each int, but that's all fine.
Question 2: how would you implement the function
foo?
A simple scanline algorithm should be good for this. First convert the given ints, interpreted as 5-bit numbers, into a 5x5 boolean matrix for simplicity. (Note that the center 3x3 of each puzzle piece is always filled, so it's just the given 4 edges that make this interesting.) After this start at, say, the upper left corner, and going through each row in the matrix left to right, check the values for this cell and the relevant neighbours and draw accordingly. (Define the cells outside the matrix to have the value 0.)
Now since you're processing the cells in order, top-to-bottom and left-to-right, it's sufficient at each cell to just consider the upper, upper-left and left neighbours. This gives you in theory 16 different cases. Sketching them out you'll find 5 distinct cases (or 4, depending on how you look at it); or you could just notice that there are 4 main cases depending on whether you've just crossed a horizontal edge, vertical edge, both or neither, and then one more case depending on whether you've just ended or started a both-horizontal-and-vertical cross point.
Instead of going through the algorithm in more detail, here's the link to an implementation on Github. I wrote the refactored version in slightly scruffy C for some reason, after noticing that the first implementation I had done a while back was amusingly bad. To test it out, simply say "make" and for some examples, see the "test" script. (No unit tests this time, sorry.)
Friday, 27 April 2012
Carmack: Functional Programming in C++
Here's John Carmack with a solid blog post on the benefits of a (more) functional style.
Functional programming seems to be trending up lately. Interesting stuff.
The further reading links on the bottom are also worth checking out.
Functional programming seems to be trending up lately. Interesting stuff.
The further reading links on the bottom are also worth checking out.
Tuesday, 10 April 2012
On objects and state
"State is inherently complex, since it complects value and time". - Rich Hickey
At work one part of our multi-tier architecture, written in Java, is a system sitting between the data source (usually a database) and the front end. An important task of this service tier is to unify the data from different data sources into a single common format for display to the end user, and also to enable easy caching of data. The connection between the service tier and the front end is REST and the connection between the service tier and the data source is either JDBC or REST.
One main thing the service tier does then is receive data from a data source, validate it, and digest it into a common, easily serialisable format for the front end. For this purpose we have a bunch of different Model classes, one for each different type of chart we support (line chart, bar chart etc).
The life cycle of a Model object is straightforward: the Model is created; data is given to it for validation; and if the data was valid, eventually the
toDto() method is called to produce the digested version of the data. (DTO stands for Data Transfer Object, which is just a pretentious way of saying "struct". That's design patterns for you, heh.)Our system is pretty sensible and works well in practice. However, when I was recently tasked with creating a new Model for our system, I spent some time thinking whether this way of doing things is really the best possible. Specifically, I wanted to figure out how best to manage the life cycle of my Model object, that is, to manage its state over time.
The question I eventually came across was simple: why would I want my Model to have state?
In fact, since the whole point of an object is that it encapsulates state, why would I want to use an object at all?
This may seem like a silly question; and in this case the obvious answer "of course you need to use objects and state - it's Java, duh" happens to be correct. But it is worthwhile to think of just how essential object-orientedness and state is in general. So bear with me here.
In my currently favourite language, Clojure, it seems that the recommended way to do this kind of thing is to use a multimethod. A multimethod consist of (at least) two things: the method name and a dispatch function. When you call the method, the arguments you give are first passed to the dispatch function, whose return value is then used to determine which actual implementation function is called. This sounds a bit weird, but is rather cool in practice. Let's look at a hello-world example of a multimethod:
(defmulti validate :chart-type) (defmethod validate :line-chart [{:keys [data] :as data-map}] (merge {:valid-data data} data-map)) (defmethod validate :default [d] nil)
Here the first line defines a multimethod called validate and defines its dispatch function to be the keyword
:chart-type. In Clojure, using a keyword as a function just returns the corresponding value from the given map:multim.core> (def data {:chart-type :line-chart, :data [[1 2] [3 4]]}) #'multim.core/data multi.core> (:chart-type data) :line-chart
The second and third lines of the multimethod bit define the function that is run whenever the dispatch function returns the value
:line-chart. This function simply constructs a map with the key :valid-data associated with the given map's :data, merges that with the given map and returns the result. Next the default-case method is defined to just return nil for any dispatch function value not covered by other methods. (The default default is to throw an exception, which you might like better.)Let's test this multimethod:
multim.core> (validate data) {:data [[1 2] [3 4]], :chart-type :line-chart, :valid-data [[1 2] [3 4]]} multim.core> (def data2 {:chart-type :bar-chart, :data [[5 6] [7 8]]}) #'multim.core/data2 multim.core> (validate data2) nil
The multimethod recognises the line chart and calls the correct method for it. Other
:chart-type values are not bound to any method, so the default method is called for those, as expected.Here's another simple multimethod to munch valid data into a DTO:
(defn munch [data-matrix] (for [col (range (count (first data-matrix)))] (map #(nth % col) data-matrix))) (defmulti make-dto :chart-type) (defmethod make-dto :line-chart [{:keys [valid-data] :as data-map}] (merge {:dto (munch valid-data)} data-map)) (defmethod make-dto :default [d] nil)
So with this, we can turn valid data (but not unvalidated data) into a DTO:
multim.core> (make-dto data) {:data [[1 2] [3 4]], :chart-type :line-chart, :dto ()} multim.core> (make-dto (validate data)) {:valid-data [[1 2] [3 4]], :chart-type :line-chart, :data [[1 2] [3 4]], :dto ((1 3) (2 4))}
And data that cannot be validated cannot be DTOified either:
multim.core> (make-dto data2) nil multim.core> (make-dto (validate data2)) nil
Now this might all seem pretty trivial. But that's sort of the point. The system I just described is very simple, consisting of two things: functions and data. Even though the functions are called multimethods in Clojure terminology, they're not methods in the Java sense of the word - they stand alone, not contained in any object; and they also happen to be pure functions, free of side effects such as state.
The question I asked previously now becomes: Why would I want to add state to this system?
The management of state can get much more complicated than it would be in this example. Let's look at one of the old Model implementations in our system to illustrate this. We actually have three different
toDto()-like methods: one to construct the actual DTO; one to convert that into comma-separated values (CSV); and one to convert it to another simple representation we use internally. For instance, here's the pseudocode for toCsv() in one of the old implementations:public String toCsv() { if(this.data == null) throw new IllegalStateException("data is not set"); if(!this.validateData()) throw new IllegalStateException("data is invalid"); if(this.dto == null) this.toDto(); // actual computation, using this.dto }
So in every method one has to check what the current state of the object is, and if the state is wrong, to either throw an exception or to try to fix the situation. It's easy to forget to check one of the many conditions in one of the many methods, which can lead to subtle bugs when (not if) someone at some point calls the methods "out of order".
The problem here is that it's impossible to enforce the correct calling order. The data is set into the object, then validated, and then the DTO computed from it, in completely separate operations: the programmer who calls these methods may do so in any order s/he wishes. We then have to manually check the situation in each method to figure out what the calling order was this time.
The solution seems simple: don't store any state in the object. Instead, just require that each relevant datum is passed to each method as a parameter. This way, it's physically impossible for the caller to call the methods out of order; in Java, you wouldn't get past the compiler.
One problem that may still remain is that one can pass invalid data to a method. One way to get around that is to make two classes, say
Data and ValidData, to represent raw data and already-validated data, and to have methods only accept one or the other. Or, if using a language such as Clojure, just add a field into the data to indicate it's been validated like in the multimethod example above.Given all that, if I were designing this data-to-DTO system from the ground up (and if I had to use Java), I would emulate the multimethod solution with something like this:
public interface Munchable { public ValidData validate(Data data); public DTO makeDto(ValidData validData); public String makeCsv(ValidData validData); public InternalThing makeInternalThing(ValidData validData); }
And then simply leave out any class variables in the implementing classes. This way, the objects become just dummy things which can be constructed whenever and discarded, if you wish, after each method call; you no longer need to worry about managing their internal state, since they don't have any.
(One could also have the
makeCsv() and makeInternalThing() methods take a DTO object as a parameter instead, or add DTO-taking versions of them; but this doesn't affect the point.)This brings me to the following criticism of Java. Cleanly implementing something like the multimethod in Java is impossible, since Java doesn't have functions - everything has to be wrapped in an object, which then provides methods. There are static methods, but those cannot be overridden in a subclass. One could write a separate static method for each different type to be handled, but there's no good place to put all these static methods. This means that in Java, you pretty much have to always use objects, even if you're not really doing anything at all with them - in the Munchable example, all the objects do is hold functions.
Java, of course, was designed to very strongly encourage you to always use objects; it is quite literally the only paradigm the language offers. Because of this it is, often implicitly, assumed that when you use Java, you'll write all of your code in the objects-and-state manner, such as the old
toCsv() example above. Since you have all these object-oriented constructs and it's so easy to use them to "manage" state, why not do that?I must point out that the examples given here are fairly benign, and it might be difficult to see from them why this would be a big deal. In fact our system, even the old code, works quite well; it is very much possible to take all the possible states into account and to write proper unit tests that verify all the different state transitions. But the point is that when you can do the exact same thing in a much simpler way, why wouldn't you? Given two systems that do the same thing, isn't the simpler one preferable?
The criticism of using state when you don't have to becomes more relevant as the system and therefore the number of its possible states grows. (Obviously the number of state transitions grows exponentially with the number of states.) For instance, one issue I haven't mentioned at all, but which will be both more important and more difficult to solve in larger stateful systems, is concurrency. I won't go into that in more detail here; perhaps later.
I began to ponder all this more seriously recently, after witnessing Rich Hickey's presentation Simple Made Easy. This presentation is the best "how to code" lecture I've ever seen, and I encourage everyone to watch it. The issue of state vs. no state is but one of the things Hickey discusses in his speech. For a more Java-specific critique, see Steve Yegge's awesome rant.
Somebody once quipped that it's still possible to write good code in Java, but that code will be very non-idiomatic. Indeed. But I am glad that other idioms exist; even if in practice I end up using Java, it's good to expand one's mind by considering the alternatives.
Monday, 30 January 2012
Online courses
Last autumn Stanford university offered three programming courses online: machine learning, artificial intelligence and database basics. I took the machine learning one. The course recently ended, with I and over 12000 fellow students receiving a nice statement of accomplishment.
The lectures by Andrew Ng - which you can watch online for free, or download if you register (for free) - were awesome. Having previously taken a few courses on the subject (introduction to machine learning; basic statistics courses; independent component analysis) I knew most of the stuff already, but watching the lectures was still absolutely worth it as a rehearsal, for the excellent clarity of the presentation. The programming exercises were somewhat milder, being sometimes too brief, but still good.
I haven't yet checked out the other courses' lecture videos, but if they're at the same level as the machine learning stuff, this is going to be world-changing stuff. The Stanfordians aren't done with just three courses, and it's not just the Stanfordians. One of the Stanford lecturers is starting his own online education company. Other Stanforders are offering 12 new online courses starting soon - see e.g. the course on probabilistic graphical models, which has links at the bottom to the other ones. MIT has had their Open CourseWare thing for a while now, and they're just launching MITx, a competitor to the Stanford online stuff. And of course Khan Academy has also been around for a while, although it's a different level of education. Probably I'm forgetting some as well.
Based on all this, I predict that online education is going to be pretty big pretty soon. We live in interesting times.
The lectures by Andrew Ng - which you can watch online for free, or download if you register (for free) - were awesome. Having previously taken a few courses on the subject (introduction to machine learning; basic statistics courses; independent component analysis) I knew most of the stuff already, but watching the lectures was still absolutely worth it as a rehearsal, for the excellent clarity of the presentation. The programming exercises were somewhat milder, being sometimes too brief, but still good.
I haven't yet checked out the other courses' lecture videos, but if they're at the same level as the machine learning stuff, this is going to be world-changing stuff. The Stanfordians aren't done with just three courses, and it's not just the Stanfordians. One of the Stanford lecturers is starting his own online education company. Other Stanforders are offering 12 new online courses starting soon - see e.g. the course on probabilistic graphical models, which has links at the bottom to the other ones. MIT has had their Open CourseWare thing for a while now, and they're just launching MITx, a competitor to the Stanford online stuff. And of course Khan Academy has also been around for a while, although it's a different level of education. Probably I'm forgetting some as well.
Based on all this, I predict that online education is going to be pretty big pretty soon. We live in interesting times.
Saturday, 24 December 2011
AI Challenge: Ants - afterthoughts
Update: here are some links to interesting write-ups etc:
Memetix, 10th place
FlagCapper, 8th place
Xathis, contest winner
MBCook, another Clojure bot, rather different from mine
Official strategy forum for all the rest
---
So the AI challenge is over. Sadly I didn't really have enough time to properly participate; I started in earnest with less than a week remaining, so I guess mine was a last-minute entry. It turned out suprisingly well except for one large detail: completely unoptimised, the code runs fast enough on my machine with the official settings, but times out on the official game servers almost every game. This was due to a bug in the timeout code that I didn't notice until after the deadline. Oh well.
The code is immature enough that it's not worth publishing, but the general ideas are pretty interesting, so I'll say a few words about those.
The best writeup I've seen so far is the one by Memetix, the UK champion. My ideas, most of which were scavenged from the excellent forums, were similar to some extent, except of course for the whole UK champion bit.
As I see it, the two major parts of a successful ant bot are the general path finding and target assignment algorithm, and the combat engine. These are basically the macro and the micro.
Macro: path-finding routines
Starting with path finding, the one that appealed to me the most was the rubber surface attraction thing, some version or variation of which seemed to be used by everyone and their cat on this competition.
The attraction algorithm is basically just breadth-first search, with some optional tweaks. One important idea is to begin the search at each source, such as food or an unexplored tile, instead of from each of the player's ants; this way the algorithm scales fairly well when the number of visible things grows, because the time requirement doesn't depend on how many ants you have. (It might still depend on the number of food, the number of enemy ants etc, depending on exactly how you tweak it, but initialising the search from the sources is a good start.)
Collaborative diffusion, which I guess can be described as a further variation of attraction, has also been used a lot in this competition. The scents used in diffusion are explicitly averaged for each square based on the neighbouring scents, instead of just taking the maximum attractiveness like in basic attraction. Of course, you can use this idea with attraction too. An important consequence of this averaging is that an area with, say, a lot of food gives off a stronger combined scent than an area with just one food. I'm not certain however how much of a benefit this gives (see below).
In the collaborative part of diffusion, friendly ants block some or most of the scent from proceeding further, depending on the type of scent. E.g. a food scent would be mostly blocked by an ant, since one or two ants are usually enough to harvest all the food in an area; but an enemy hill's scent would go through ants more or less intact, since we want as many ants as possible to help in razing enemy hills. Such collaboration seems like a pretty useful idea. Notably though some very highly ranked bots such as Memetix's didn't use it at all. I didn't have time myself to implement anything like this, so I can't really say.
Another thing with diffusion, that you can also do with attraction, is to a non-linear distance function. E.g. exponential falloff is often used with diffusion, and Memetix used weight over distance squared (as in gravity). Sadly, I didn't have time to properly experiment with this either. It seems to me that neither the collaboration part nor the non-linear distance function is truly necessary for a very well performing algorithm, but this is mere speculation - hopefully some of the other top contenders will do a writeup soon so we can learn how they dealt with this.
One final note about diffusion: for some reason, some people implemented it by doing multiple sequential passes over the entire map and hoping that they can do enough passes to propagate the scents to every square - which takes one pass for each square traveled. Instead, the standard BFS method is of course to use a queue for the squares yet to be processed and a hash set or similar for the squares already visited. In this case one can easily replace the hash set with a double array of booleans since the maximum map size is only 200 by 200. The standard queue-and-visiteds version should perform much better than the multiple-pass version, since it skips over a zillion uninteresting squares, so it's not entirely clear to me why anyone would opt for the latter.
Tweaking it
Once you have your attraction or diffusion or whatever, the endless and endlessly fun tweaking can begin. As described above, there are many of variations of the basic algorithm. But there are also lots of parameters to tweak: which weight should I give to a food compared to an unseen tile? What about tiles that I've seen at some point, but not recently (and what is "recently")? Should I assign some of my ants to be food gatherers and some to be soldiers, or should I just rely on the different weights? Should I change the weights, or the assignments, as the game progresses, or as I gain or lose area or ants? Countless questions - and after all this, there's still combat to worry about!
It turns out that early exploration and food gathering is extremely important, which is why my bot was doing surprisingly well against my coworkers' bots on our private TCP server. I implemented a good food finding routine first, then a good exploration routine; then I was nearly out of time, so my combat code is hilariously primitive, and of course everything times out when ran on a machine slower than my own.
To assign food gatherers, I do a simple BFS (linear distance function, no blocking of "scent" by friendly ants; just the basic vanilla thing) separately from each visible food until I either find a friendly ant or I hit a distance cutoff. The BFS doesn't consider non-visible squares. I set the cutoff at twice the sight radius (which might be too small though); the idea is that each food is obviously within the sight radius of a friendly ant, but a food is only worth going after if there are not too many obstacles on the way. After finding the closest ant for each food, I then find the closest food for each ant. This way when there's a cluster of food only one ant will get assigned to it, which seems good. A few obvious improvements to this routine would be remembering where food was last seen (at least for a few turns after seeing it) and ignoring food when an enemy ant is closer to it than we are.
For the ants that weren't assigned as food gatherers, I do another BFS, starting at each interesting non-food square simultaneously. Such interesting squares are enemy hills, enemy ants, and the squares just off the edge of visible space. I assign a very large weight (that is, a very small "distance") to the enemy hills, a medium weight to enemy ants and a small weight proportional to last-seen time to the non-visible squares.
The exploration part here seems to work quite nicely. When there are no enemies around, my ants will explore in all directions, and will try to bring and keep the whole map under their control. At first every non-visible edge square has the same score, so the deciding factor is the distance: after the first ant goes, say, north, the new northern edge is now farther away from the hill than the other edges, which causes the ants to spread out naturally. As the game progresses, ants that don't have anything better to do than explore will tend to run around in their own small area, chasing the edge that they've least recently seen, which maximises the visibility and map control. And of course, when new food spawns, gathering it takes priority for the ant nearest to it.
For combat targeting this doesn't work quite as well (all the combat stuff was a last-minute addition). Even though the attraction of enemy hills is very large (and my code remembers the location of currently unseen hills, and forgets hills once they're razed), the BFS doesn't have an option of going through unseen squares, so my ants are only drawn towards enemy hills in those turns when the hill is seen by at least one of my ants. In addition, when searching a path to enemy hills the search cutoff is the same as for exploration, which is probably suboptimal. Well, still better than nothing.
It seems to me that on the exploration and macro side, a few relatively simple BFS routines, when properly tweaked, would be enough for even a top ten bot. I refer again to Memetix, whose code is remarkably simple yet performs very well. A shame that I didn't have more time to polish my own routines.
Micro: combat routines
I had no time to really get into the intricacies of combat, which are many and detailed. Apparently however there are simply too many possibilities to evaluate them all: five possible moves per ant for each of n ants leads to 5^n different moves on every turn. Even if you can cull most of these, you can't always cull enough.
An interesting approach then is a1k0n's random sampling, which attempts to iteratively figure out a plausible probability distribution corresponding to the best moves. Of simpler heuristic approaches, I refer again to Memetix. His experiences in general seem to show that non-complicated approaches, both to path-finding and to combat, can be sufficient to do very well on this challenge. Update: Xathis uses a traditional min-max algorithm with heavy heuristic pruning, highly polished, which obviously works very well.
My combat code is ran after I've figured out the general moves with the path finding routine. The combat routine then checks these moves and, if necessary, replaces them with hopefully safer moves. For each ant I add up the number of enemy and friendly ants within potential combat range (well, actually within the square root of (combat range squared + 12), which in some cases might be almost the same). If there are as many enemy ants as friendly ants, or more, I arbitrarily choose the "first" enemy, figure out where it is, and tell my ant to go in the opposite direction. This works surprisingly well: if there's just one enemy ant, my ant will run away from it; if there are several enemies and they're surrounding my ant, it doesn't really matter where my ant will move. (Well, it does, but figuring out the best move would have taken me too long.)
Other stuff
In addition to the micro management of individual combat moves, there's also base defence (see e.g. Memetix - apparently static defence is a bad idea, and dynamic defence can be good enough), zone control and blockading enemy ants (see contest winner Xathis for a good example), symmetry detection etc etc. I don't have enough time to go through all of these in detail, so I recommend checking out the strategy forum for lots of good discussion on this stuff.
In summary, if only I had had more time to polish and optimise my code and implement better routines, this would have been the most awesome programming project ever. Really looking forward to the next AI challenge - hopefully I'll do better then!
Memetix, 10th place
FlagCapper, 8th place
Xathis, contest winner
MBCook, another Clojure bot, rather different from mine
Official strategy forum for all the rest
---
So the AI challenge is over. Sadly I didn't really have enough time to properly participate; I started in earnest with less than a week remaining, so I guess mine was a last-minute entry. It turned out suprisingly well except for one large detail: completely unoptimised, the code runs fast enough on my machine with the official settings, but times out on the official game servers almost every game. This was due to a bug in the timeout code that I didn't notice until after the deadline. Oh well.
The code is immature enough that it's not worth publishing, but the general ideas are pretty interesting, so I'll say a few words about those.
The best writeup I've seen so far is the one by Memetix, the UK champion. My ideas, most of which were scavenged from the excellent forums, were similar to some extent, except of course for the whole UK champion bit.
As I see it, the two major parts of a successful ant bot are the general path finding and target assignment algorithm, and the combat engine. These are basically the macro and the micro.
Macro: path-finding routines
Starting with path finding, the one that appealed to me the most was the rubber surface attraction thing, some version or variation of which seemed to be used by everyone and their cat on this competition.
The attraction algorithm is basically just breadth-first search, with some optional tweaks. One important idea is to begin the search at each source, such as food or an unexplored tile, instead of from each of the player's ants; this way the algorithm scales fairly well when the number of visible things grows, because the time requirement doesn't depend on how many ants you have. (It might still depend on the number of food, the number of enemy ants etc, depending on exactly how you tweak it, but initialising the search from the sources is a good start.)
Collaborative diffusion, which I guess can be described as a further variation of attraction, has also been used a lot in this competition. The scents used in diffusion are explicitly averaged for each square based on the neighbouring scents, instead of just taking the maximum attractiveness like in basic attraction. Of course, you can use this idea with attraction too. An important consequence of this averaging is that an area with, say, a lot of food gives off a stronger combined scent than an area with just one food. I'm not certain however how much of a benefit this gives (see below).
In the collaborative part of diffusion, friendly ants block some or most of the scent from proceeding further, depending on the type of scent. E.g. a food scent would be mostly blocked by an ant, since one or two ants are usually enough to harvest all the food in an area; but an enemy hill's scent would go through ants more or less intact, since we want as many ants as possible to help in razing enemy hills. Such collaboration seems like a pretty useful idea. Notably though some very highly ranked bots such as Memetix's didn't use it at all. I didn't have time myself to implement anything like this, so I can't really say.
Another thing with diffusion, that you can also do with attraction, is to a non-linear distance function. E.g. exponential falloff is often used with diffusion, and Memetix used weight over distance squared (as in gravity). Sadly, I didn't have time to properly experiment with this either. It seems to me that neither the collaboration part nor the non-linear distance function is truly necessary for a very well performing algorithm, but this is mere speculation - hopefully some of the other top contenders will do a writeup soon so we can learn how they dealt with this.
One final note about diffusion: for some reason, some people implemented it by doing multiple sequential passes over the entire map and hoping that they can do enough passes to propagate the scents to every square - which takes one pass for each square traveled. Instead, the standard BFS method is of course to use a queue for the squares yet to be processed and a hash set or similar for the squares already visited. In this case one can easily replace the hash set with a double array of booleans since the maximum map size is only 200 by 200. The standard queue-and-visiteds version should perform much better than the multiple-pass version, since it skips over a zillion uninteresting squares, so it's not entirely clear to me why anyone would opt for the latter.
Tweaking it
Once you have your attraction or diffusion or whatever, the endless and endlessly fun tweaking can begin. As described above, there are many of variations of the basic algorithm. But there are also lots of parameters to tweak: which weight should I give to a food compared to an unseen tile? What about tiles that I've seen at some point, but not recently (and what is "recently")? Should I assign some of my ants to be food gatherers and some to be soldiers, or should I just rely on the different weights? Should I change the weights, or the assignments, as the game progresses, or as I gain or lose area or ants? Countless questions - and after all this, there's still combat to worry about!
It turns out that early exploration and food gathering is extremely important, which is why my bot was doing surprisingly well against my coworkers' bots on our private TCP server. I implemented a good food finding routine first, then a good exploration routine; then I was nearly out of time, so my combat code is hilariously primitive, and of course everything times out when ran on a machine slower than my own.
To assign food gatherers, I do a simple BFS (linear distance function, no blocking of "scent" by friendly ants; just the basic vanilla thing) separately from each visible food until I either find a friendly ant or I hit a distance cutoff. The BFS doesn't consider non-visible squares. I set the cutoff at twice the sight radius (which might be too small though); the idea is that each food is obviously within the sight radius of a friendly ant, but a food is only worth going after if there are not too many obstacles on the way. After finding the closest ant for each food, I then find the closest food for each ant. This way when there's a cluster of food only one ant will get assigned to it, which seems good. A few obvious improvements to this routine would be remembering where food was last seen (at least for a few turns after seeing it) and ignoring food when an enemy ant is closer to it than we are.
For the ants that weren't assigned as food gatherers, I do another BFS, starting at each interesting non-food square simultaneously. Such interesting squares are enemy hills, enemy ants, and the squares just off the edge of visible space. I assign a very large weight (that is, a very small "distance") to the enemy hills, a medium weight to enemy ants and a small weight proportional to last-seen time to the non-visible squares.
The exploration part here seems to work quite nicely. When there are no enemies around, my ants will explore in all directions, and will try to bring and keep the whole map under their control. At first every non-visible edge square has the same score, so the deciding factor is the distance: after the first ant goes, say, north, the new northern edge is now farther away from the hill than the other edges, which causes the ants to spread out naturally. As the game progresses, ants that don't have anything better to do than explore will tend to run around in their own small area, chasing the edge that they've least recently seen, which maximises the visibility and map control. And of course, when new food spawns, gathering it takes priority for the ant nearest to it.
For combat targeting this doesn't work quite as well (all the combat stuff was a last-minute addition). Even though the attraction of enemy hills is very large (and my code remembers the location of currently unseen hills, and forgets hills once they're razed), the BFS doesn't have an option of going through unseen squares, so my ants are only drawn towards enemy hills in those turns when the hill is seen by at least one of my ants. In addition, when searching a path to enemy hills the search cutoff is the same as for exploration, which is probably suboptimal. Well, still better than nothing.
It seems to me that on the exploration and macro side, a few relatively simple BFS routines, when properly tweaked, would be enough for even a top ten bot. I refer again to Memetix, whose code is remarkably simple yet performs very well. A shame that I didn't have more time to polish my own routines.
Micro: combat routines
I had no time to really get into the intricacies of combat, which are many and detailed. Apparently however there are simply too many possibilities to evaluate them all: five possible moves per ant for each of n ants leads to 5^n different moves on every turn. Even if you can cull most of these, you can't always cull enough.
An interesting approach then is a1k0n's random sampling, which attempts to iteratively figure out a plausible probability distribution corresponding to the best moves. Of simpler heuristic approaches, I refer again to Memetix. His experiences in general seem to show that non-complicated approaches, both to path-finding and to combat, can be sufficient to do very well on this challenge. Update: Xathis uses a traditional min-max algorithm with heavy heuristic pruning, highly polished, which obviously works very well.
My combat code is ran after I've figured out the general moves with the path finding routine. The combat routine then checks these moves and, if necessary, replaces them with hopefully safer moves. For each ant I add up the number of enemy and friendly ants within potential combat range (well, actually within the square root of (combat range squared + 12), which in some cases might be almost the same). If there are as many enemy ants as friendly ants, or more, I arbitrarily choose the "first" enemy, figure out where it is, and tell my ant to go in the opposite direction. This works surprisingly well: if there's just one enemy ant, my ant will run away from it; if there are several enemies and they're surrounding my ant, it doesn't really matter where my ant will move. (Well, it does, but figuring out the best move would have taken me too long.)
Other stuff
In addition to the micro management of individual combat moves, there's also base defence (see e.g. Memetix - apparently static defence is a bad idea, and dynamic defence can be good enough), zone control and blockading enemy ants (see contest winner Xathis for a good example), symmetry detection etc etc. I don't have enough time to go through all of these in detail, so I recommend checking out the strategy forum for lots of good discussion on this stuff.
In summary, if only I had had more time to polish and optimise my code and implement better routines, this would have been the most awesome programming project ever. Really looking forward to the next AI challenge - hopefully I'll do better then!
Subscribe to:
Comments (Atom)