Ants AI, language matters
bearophile
bearophileHUGS at lycos.com
Sun Dec 25 09:07:46 PST 2011
Ants AI Challenge sponsored by Google is now finished, 24 people have played this contest using D2:
http://aichallenge.org/language_profile.php?language=D
The best D entry, by Minthos, with rank 439 (over about 8000 entries!):
http://aichallenge.org/profile.php?user=4823
Minthos D2 code:
http://files.minthos.com/code/minthos.dbot.dm02.tgz
Some low-level comments on Minthos code, about D, and not about game strategy or other high level things.
His code is:
> ...
> ...
My code is the one without those >.
-------------------------------
pqueue.d module: sometimes more collections are needed.
-------------------------------
Missed !in
> assert(!(hill in myAnts));
-------------------------------
Missed foreach() and maybe more:
> struct pfNode{
> Loc pos;
> pfNode* prev;
> float cost;
> bool visited;
> bool water;
> }
>
> ...
>
> pfNode[][] nodes = new pfNode[][](map.rows, map.cols);
> pfNode*[] openList;
> // initialize data structure
> for(int y = 0; y < map.rows; y++){
> for(int x = 0; x < map.cols; x++){
> nodes[y][x].water = map.water[y][x];
> nodes[y][x].visited = false;
> nodes[y][x].pos = Loc(y, x);
> nodes[y][x].prev = null;
> }
> }
This is a bit sad because of no named arguments yet in D (add braces as desired):
foreach (y; row; map)
foreach (x, ref el; row)
el = PfNode(/*pos*/ Loc(y, x),
/*prev*/ null,
/*cost*/ el.cost,
/*visited*/ false,
/*water*/ map.water[y][x]);
-------------------------------
It's usually better to think of pre/post increments as returning void, and avoid code like this (but there is _far_ worse C/D code around):
> lokeLars = path[index--];
-------------------------------
Sad need(?) to use GC.disable:
> void main(string[] args) {
> version(unittest) {
> // We don't run the bot or wait for input in this case
> } else {
> GC.disable();
> MyBot b = new MyBot();
> b.name = args[0];
> Ants.run(b);
> }
> }
-------------------------------
Missed AA.byKey(), and required care to use "ref" to avoid bad bugs here:
> foreach(ref hill; map.myHills.keys){
> if(engine.manhattan(ant.pos, hill) < 5){
> goto ignore;
> }
> }
Often a return or a named break/continue are better in D than that goto.
-------------------------------
Improving switch to make it work on structs avoids such not nice code (http://d.puremagic.com/issues/show_bug.cgi?id=596 ):
> struct Direction {
> char key;
> int row;
> int col;
> }
>
> immutable Direction[4] AIM = [
> {'n', -1, 0},
> {'e', 0, 1},
> {'s', 1, 0},
> {'w', 0, -1}
> ];
>
> ...
>
> Direction directionLeft(Direction d){
> for(int i = 0; i < 4; i++){
> if(d == AIM[i]){
> return AIM[(i + 1) % 4];
> }
> }
> assert(0);
> }
>
> Direction oppositeDirection(Direction d){
> if(d == AIM[0]) return AIM[2];
> if(d == AIM[1]) return AIM[3];
> if(d == AIM[2]) return AIM[0];
> if(d == AIM[3]) return AIM[1];
> assert(0);
> }
I am thinking about something like:
Direction oppositeDirection(in Direction d) pure nothrow {
final switch (d) {
case AIM0: return AIM2;
case AIM1: return AIM3;
case AIM2: return AIM0;
case AIM3: return AIM1;
}
}
Hopefully the "final switch" too becomes usable here if AIM array becomes an enum of 4 items.
But I can't even create an enum of structs, maybe I am doing something wrong:
import std.typecons;
// Error: need member function opCmp() for struct Foo to compare
struct Foo { int x, y; }
// Error: template std.typecons.Tuple!(int,"x",int,"y").Tuple.opCmp(R) if (isTuple!(R)) does not match any function template declaration
alias Tuple!(int,"x", int,"y") Foo;
// Error: Integer constant expression expected instead of Foo(1,1)
const struct Foo {
int x, y;
int opCmp(const ref Foo other) const pure nothrow {
return 1;
}
}
enum MyE : Foo { A = Foo(1, 1),
B = Foo(2, 2),
C = Foo(3, 3) }
void main() {}
-------------------------------
There's a bit of need of std.random.choice, as in Python:
> Direction randomDirection(){
> return AIM[uniform(0, 3)];
> }
Using $ it becomes a bit better (and maybe removes a bug, because AIM length is 4, while uniform on default doesn't return the right extrema):
Direction randomDirection() {
return AIM[uniform(0, $)];
}
But with a choice() it becomes less bug-prone and more clear:
Direction randomDirection() nothrow {
return choice(AIM);
}
-------------------------------
> void clearArray(ref bool[][] a)
> {
> for(int x = 0; x < cols; x++){
> for(int y = 0; y < rows; y++){
> a[y][x] = false;
> }
> }
> }
Seems better:
void clearArray(bool[][] a) pure nothrow {
foreach (row; a)
a[] = false;
}
a is a headconst array, its size must not change inside clearArray().
-------------------------------
There's some need for a fast boolean matrix data structure in Phobos:
http://d.puremagic.com/issues/show_bug.cgi?id=6697
> // unpermanent stuff
> bool[][] explored;
> bool[][] vision;
> bool[][] water;
> bool[][] land;
> float[][] threat;
> float[][] crowd;
> int[Loc] waypoints;
> int[Loc] staleWaypoints;
> Loc[] bestGuesses;
-------------------------------
Bye,
bearophile
More information about the Digitalmars-d
mailing list