Team: I don't need to stinkin' team
Language: Prolog
It's Friday afternoon. I'm reading /. and see this pointer to a programming
contest. What better way to waste -- er, spend -- my weekend? I check with the
family and they don't mind not seeing me for a few days, so I'm off...
I've been programming in Prolog lately for some AI projects, and it seemed a
good match for the contest, so that's what I used. Which is a good place to say
something about this "best language" thing. There is no best language. There are
only programmers who can't see things from all the perspectives. So if my entry
should win (however unlikely that may be), I hope it won't be used by some
Prolog fanatic to beat up some other flavor of language fanatic. In fact, as I'm
fairly new to Prolog, I'll bet "real" Prolog programmers will look at my code
and cringe...
My algorithm is low on strategy, a bit better on tactics, and (hopefully)
very solid on implementation. Three days just isn't enough to develop complex
strategy. It would be very interesting to see what people came up with given,
say, three weeks, or given a series of competitions where programs could be
refined in between.
My strategy is simply to choose one of the following in this order of
priority:
- If the bot has a package and is at the package destination, drop it.
- If the bot is standing on a package and has room for it, pick it up.
- If the bot has a package, go to the package destination.
- If the bot knows where a package or base is, go there.
- If the bot doesn't know anything, go to every space on the board (who
knows, it might have missed something).
- Do nothing (it should never come down to this; just in case something
above breaks).
Tactics cover a variety of local situations, in no order of priority:
- When picking places to go, pick the closest ones first.
- When going places, take the shortest route (the program first figures out
the optimum route (which takes a bit of CPU), then goes there without further
thinking (or taking any more CPU)).
- When going somewhere, if the bot gets pushed, it re-evaluates the current
strategy, since things may have changed. (This would have been more useful if
I'd gotten more done at the strategy level.)
- Try to detect dead-lock situations with other bots (cases where
simple-minded algorithms can get into a rut), and avoid them. The avoidance
scheme involves some randomization, which should eventually clear the
dead-lock, even if the other guy does something similar. As with any
good-neighbor algorithm, this can be taken advantage of, and it helps the
other player as well as us, but the flip side is getting dead-locked for the
rest of the game.
- If the bot gets pushed while picking up a package, it's possible two
bots are trying to get the same package and keep picking, getting pushed,
and dropping over and over. Make a couple random moves before continuing.
- If the bot gets pushed under other conditions, it could be doing
something like butting heads trying to move through the same square. Again,
make some random moves, though not as many as the case above.
- Generally bid low. I don't know any good algorithm for deciding on larger
bidding strategies.
- But try to make the chosen move happen. If there's a bot one move away
(imminent push potential), bid 3. If there's a bot two moves away (potential
push after move), bid -2. (In retrospect, and having looked at some other
entry descriptions, I perhaps should have bid even more when near water. Also,
this approach can waste lots of money if another bot is following one space
behind (we bid 3 every time).)
Implementation-wise, I think it was important to use a language like Prolog,
not one like C, to leverage the development time and to avoid several classes of
potential crashes -- there just wasn't enough time to fully test things. But I
did run the bot against as many boards and with other bots as much and as long
as I could, including every one of the single-bot test boards. I've seen
contests like this in past where someone had an absolutely brilliant algorithm,
but the code crashed two seconds after starting because the program ran into a
situation that wasn't anticipated. Sometimes the implementation quality is more
important than the algorithm.
Anyway, I hope everyone else had as much fun as I did.
P.S. The Prolog source code (for SWI Prolog) is available
here. The full submission is
here.
