www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Ants AI, language matters

reply bearophile <bearophileHUGS lycos.com> writes:
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
Dec 25 2011
next sibling parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Sunday, 25 December 2011 at 17:07:46 UTC, bearophile wrote:
 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--];


I agree that one should *generally* avoid this kind of code, but this example here is a very common C/C++ idiom, it should be fairly recognizable to anyone.
Dec 25 2011
prev sibling parent "Marco Leise" <Marco.Leise gmx.de> writes:
I posted about this contest in D.learn, so it was expectable that people  
try out D there without a good feel for the language and its shortcuts.  
Rank 439 is respectable, but I hoped for a higher ranked D entry.

I don't know if there should to be an optimized boolean matrix in Phobos.  
Is this a construct that is often needed? Is bool[][] just good enough?  
All together I think this source code isn't very informative, but it is an  
example of someone who misses some of the rather obvious features of D,  
like vector operations and foreach. This is all documented somewhere,  
probably not easy to stumble over, yet I think chatting with helpful  
people is the best way to learn by example. Sometimes programming topics  
were discussed on #aichallenge, but then again mostly about  
C++/Java/Python, the most used languages in the contest.

In the list of D2 users (showing those who submitted a program in D as  
their last upload)  
(http://aichallenge.org/language_profile.php?language=D) there are many  
who did only upload one or two programs in D in the whole two months.  
Usually that means they just uploaded the starter bot or a slightly  
modified version. So from the 24 people only 8 active participants remain.  
This is not much different from other languages though.

When I proposed D in the chat, I found that it was generally well received  
now, with many of the legendary issues fixed. What kept some people from  
trying D were:
- a small standard library (the upcoming curl wrapper is one good addition)
- a GC (when they were used to manual memory management)
- C++11

People from interpreted languages that wanted to improve the performance,  
looked more into C/C++, and frankly I know that you have to profile your D  
code now and then. foreach vs. array slice assignments, BigInt and other  
features can be slower than in Java, Perl or other, older languages. In  
this situation I can't tell them to use D, although it is a compiled  
language. Another point is that C++ users usually don't miss the D  
features that they don't know about and C++11 seems good enough to them. I  
don't know how to present contract programming in a chat without going to  
lengths and looking like a fan boy. D's arrays and associative arrays are  
usually a good starting point though. Note that the contest so far didn't  
allow multi-threading (except for runtime threads).

When "modern convenience" and "native performance" meet, I think more  
people will see D as the alternative to Java and C++. This will take some  
time with the GC, the code gen and Phobos.
Dec 25 2011