Ants AI, language matters

[bearophile]

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