macht jemand beim icfp04 mit?

SideWinder

Physikstudent schrieb:

Nee, da fehlt der Anzreiz.

Ich dachte schon du hättest einen dringenden Termin

MfG SideWinder

volkard

ich sag euch mal meinen plan:
die marker verwende ich wie folgt:
m4: feld ist bewertet
m0-m3: bewertung (interpretiert als binärzahl zwischen 0 und 15)
m5: ameisenstraße

trifft ne ameise auf ein unbewertetes feld, bewertet es diese anhand eines sichbaren nachbarn mit this->wert = nachbar->wert+1

dadurch kann jede amaeise im falle eines futterfundes optimal schnell heimlaufen, sie muß ja nur stets auf ein niederwertigeres als das aktuelle feld tappen. sie wird sicher bei feld 0 ankommen.

ups, alle werte sind modulo 16, aber egal. die funtion < ist halt entsprechend zu bauen.

feld 0 ist in ner "festung", die so aussieht:

+ +
+ 0
 + +

in feld 0 kann nie ne fremde ameise gehen, denn da stirbt sie sofort.
meine ameisen gehen einfach rein, worauf der stopfen (s)

+ +
s 0
 + +

sofort wegrennt. die reingegangene ameise legt auf feld 0 die beute ab und springt zum programmcode von s (sie wird der neue stopfen).

ne ameise, die futter fand, legt auf ihrem rückweg immer Marker 0 5 ab, eine ameisenstraße. findet ne gelangweilte ameise ne straße, geht sie die straße hinauf (entsprechend der bewertungen) und am be futterfund geht sie heim (legt neue strasse dazu). ist aber am ende gar nix, löscht sie den straßenmarker am endfeld. so verschwinden straßen zu inzwischen leeren plätzen allmächlich.

da klappt sogar alles soweit fast. allein mein problem ist, daß sich manchmal ne ameise, die zu feld 0 will, um futter abzuliefern, auf feld s landet und dann den ausgang der festung blockiert.

virtuell Realisticer

Aber sollte das nicht eigentlich _nicht_ passieren, denn du hast doch dieses Feld
belegt solange keine Ameise auf Feld 0 ist?

Merkwuerdiges Verhalten. Bin leider immernoch nicht soweit, meine Simulation fertig
zu uebersetzen. Morgen hab ich die ersten beiden Schulstunden frei, da werd ich
dann auch nochwas daran arbeiten.

Wer weiss, vielleicht werden in diesen beiden Stunden meine Killerameisen geboren

mfg
v R

virtuell Realisticer

Noch ne Frage zu clearMarkerAt():

Was genau wird hier gemacht? Soll hier current_marker-1 gesetzt werden, oder
soll current_marker auf 'no_marker' gesetzt werden?

[Nachtrag]
Lesen sollte gelernt sein und zusaetlich, sollte man selbiges auch mal konzentriert
tun, dann haette ich die frage nicht gestellt
[/Nachtrag]

mfg
v R

virtuell Realisticer

Jetzt muss ich doch nochmal was fragen, koennen Marker von Red und Black zugleich
gesetzt sein?

mfg
v R

volkard

virtuell Realisticer schrieb:

Jetzt muss ich doch nochmal was fragen, koennen Marker von Red und Black zugleich
gesetzt sein?

ja.

volkard

virtuell Realisticer schrieb:

Aber sollte das nicht eigentlich _nicht_ passieren, denn du hast doch dieses Feld
belegt solange keine Ameise auf Feld 0 ist?

ja, aber wenn ne ameise auf feld 0 geht, dann geht die stopfenmeise weg. bevor die ameise von feld 0 auf s gehen kann, huscht von schräg eine dritte ameise auf s und blockiert ab dann dauerhaft, da sie bestrebt ist, auf feld 0 zu kommen.
normalerweise geht wegen des gelände-gefälles keine ameise mit futter einfach so dahin. und nur die mit futter sind so bestrebt, feld 0 zu erreichen, dass sie blockierend wirken.
dass die dritte ameise dahin will, kann zwei gründe haben:
- auf dem heimweg war stau und sie wich aus. ausweichen müssen ameisen auf dem rückweg aber können, da oft die ameisenstraße vom gegenverkehr blockiert ist.
- hinter feld s war ein fein und blockierte... meine ameisen wucherten mit der zeit um das ganze lager und umstellten und killten den feind... und erzeugt beim sterben 3 food!... ne non-food-meise betritt das feld (die dürfen ja, denn non-food-meisen achten nicht auf richtungen (außer wenn sie auf ner straße sind))... sie wird food-meise und strebt gegen 0 und blockiert.

SeriousSam

mein ameisencode hat leider sicher noch einige fehler drin. aber der plan war, dass einige ameisen ein wegnetz bauen, sodass ameisen mit food schnell zurückfinden. dann gabs noch ein paar ameisen, die versuchen food vom gegner aus dessen hügel zu schaffen und ein paar, die den eigenen hügel bewachen sollten. aber irgendwann kommt es auch zu stau, oder die ameisen geraten auf dem rückweg in einen zyklus. mal schauen, ev. verbesser ich den code noch.

hat jemand noch ameisen, gegen die ich antreten kann?

volkard

SeriousSam schrieb:

hat jemand noch ameisen, gegen die ich antreten kann?

wget http://tampe.cc/ant/all_ants.zip
alle einsendungen, die die teilnehmer der liste namens icfp04-discuss@lists.seas.upenn.edu veröffentlicht haben.

ich hole mir gerade humes stricmp.h, weil die leute so oft kleingeschrieben haben und teste dann mal ein paar.

volkard

volkard schrieb:

ich hole mir gerade humes stricmp.h, weil die leute so oft kleingeschrieben haben und teste dann mal ein paar.

ist viel zu viel arbeit, so nen case insensitive string zu bauen. vergleichen geht ja schnell. aber dann vertragen die sich nicht mit istream...

aber dann hab ich die abteilung für fürchterlich riskanten code gefragt und bekam folgende lösung:

//tust du immer machen "string foo;...;if(foo=="hallo)"also string links, 
//dann tut jetzt dein ganzer parser gehen
bool operator==(string const& a,char const* b){
	return stricmp(a.c_str(),b)==0;
}

SeriousSam

Schade...
Ich merk jetzt erst, wie viele Fehler ich gemacht habe.

Hier eine deutlich gründlichere Version: http://www.acid-code.ch/~samuel/seriousant3.ant

volkard

hier meine version, die ich abgegeben habe.
www.volkard.de/volkard.ant

prolog

Hallo,

[OT]
Ausschnit aus Volkards Ameisencode

Drop 0
Drop 0
Turn Left 251
Turn Left 252
Turn Left 253
Sense Ahead 254 253 Friend
Turn Left 255
Turn Left 256
Turn Left 257
Move 400 257

War das beabsichtigt, oder hab ich zu viel Phantasie ?
[/OT]

Sry, für das unqualifizierte Posting.

illuminator

Gibt es eigentlich schon ein offizielles Programm mit dem ich die Ergebnisse/das Verhalten der Ameisen in meinem Program testen kann? Ich find da irgendwie nichts auf der Seite von denen.
Bei mir stimmt glaub ich noch irgendwas mit den Markern nicht, aber die Ameisen ohne Marker machen ihren Job schon einwandfrei.

Vorallem die PersistANT.ant sammelt in dem 100x100 Beispiel-Level bei mir gut 70% - 90% des Futters in 100000 Runden, wenn sie mit der Standard-Random Ameise spielt.

Aber mit einer State-Maschine ein gute Ameise zu schreiben find ich schon recht heftig - mit einer richtigen Scriptsprache wäre das bei den selben Funktionen viel einfacher umzusetzen.

volkard

illuminator schrieb:

Gibt es eigentlich schon ein offizielles Programm mit dem ich die Ergebnisse/das Verhalten der Ameisen in meinem Program testen kann?

nee. aber wenn dein prog exakt die gleiche ausgabe macht, wie dump.all, dann wird es schon ok sein.
zur not kannste meines haben.

Aber mit einer State-Maschine ein gute Ameise zu schreiben find ich schon recht heftig - mit einer richtigen Scriptsprache wäre das bei den selben Funktionen viel einfacher umzusetzen.

das IST ja der task! man mußte sich schnell nen praktikable skriptsprache basteln, um fett zu siegen.

illuminator

das IST ja der task! man mußte sich schnell nen praktikable skriptsprache basteln, um fett zu siegen.

Ich hab mir schon überlegt ob man nicht einen Compiler der State-Maschine ausgibt schreiben könnte. Aber sowas hab ich noch nie gemacht, wäre wohl nicht so einfach...

Na egal, es ging mir ja eh nicht um den Wettbewerb an sich (hab Montag mittag angefangen) sondern ich fand es einfach interessant, KI interessiert mich im allgemeinen sehr stark.

Also dein Programm würde mich interessieren, ich lade mal meines hoch, sobald ich den bug gefunden hab, der bewirkt das z.B. deine Ameise offensichtlich nicht funktioniert (sie bleibt am start stehen).

-> nh-illuminator das_@_zeichen gmx.de

volkard

illuminator schrieb:

Ich hab mir schon überlegt ob man nicht einen Compiler der State-Maschine ausgibt schreiben könnte. Aber sowas hab ich noch nie gemacht, wäre wohl nicht so einfach...

kommt auf die source-sprage an!
meine source-sprache ist der einfachheit halber code für ne state-machine.

0 Sense LeftAhead 2 1 Home             ;start
1 Sense RightAhead 2 100 Home          ;wenn ecke -> bin ecke
2 Drop 3                               ;warte bis ecke erkennbar
3 Drop 4
4 Sense Ahead 200 5 Marker 1           ;wenn sehe ecke -> bin stopfen
5 Drop 6                               ;warte bis stopfen erkennbar
6 Drop 7
7 Drop 8
8 Sense LeftAhead 300 9 Marker 1       ;wenn sehe mauer oder stopfen -> bin mauer
9 Sense RightAhead 300 400 Marker 1    ;sonst -> bin normal

100 Mark 1 101                         ;bin ecke
101 Move 102 101
102 Turn Left 103
103 Turn Left 104
104 Turn Left 105
105 Move 106 105
106 Turn Left 107
107 Turn Left 108
108 Turn Left 109
109 Sense Ahead 110 109 Marker 4
110 Sense LeftAhead 111 109 Marker 4
111 Sense Ahead 112 109 Marker 4
112 Mark 0 113
113 Mark 2 114
114 Mark 4 500

200 Mark 1 201                         ;bin stopfen
201 Move 202 201
202 Turn Left 203
203 Turn Left 204
204 Turn Left 205
205 Move 206 205
206 Unmark 1 207
207 Mark 4 400

250 Turn Left 251                      ;bin austauschstopfen
251 Turn Left 252
252 Turn Left 253
253 Sense Ahead 254 253 Friend
254 Turn Left 255
255 Turn Left 256
256 Turn Left 257
257 Move 400 257

300 Drop 300                        ;bin mauer

400 Sense Here 401 500 Marker 4        ;ohne wert -> bin ohne wert
401 Sense Here 403 402 Home            ;nicht daheim und
402 Sense Here 600 403 Food            ;essen gefunden
403 Sense Here 700 411 Marker 5        ;strasse gefunden
411 Flip 16 412 415
412 Flip 2 413 414
413 Turn Left 415
414 Turn Right 415
415 Move 400 412

500 Sense Ahead 502 501 Marker 4                         ;bin ohne wert
501 Turn Left 500

502 Sense Ahead 503 504 Marker 0
503 Mark 0 504
504 Sense Ahead 505 506 Marker 1
505 Mark 1 506
506 Sense Ahead 507 508 Marker 2
507 Mark 2 508
508 Sense Ahead 509 510 Marker 3
509 Mark 3 510

510 Sense Here 512 511 Marker 0
511 Mark 0 522
512 Unmark 0 513
513 Sense Here 515 514 Marker 1
514 Mark 1 522
515 Unmark 1 516
516 Sense Here 518 517 Marker 2
517 Mark 2 522
518 Unmark 2 519
519 Sense Here 521 520 Marker 3
520 Mark 3 522
521 Unmark 3 522
522 Mark 4 530
530 Flip 30 400 531                     ;suche leeren nachbarn
531 Turn Left 532
532 Sense Ahead 530 400 Marker 4

600 PickUp 601 400                      ;food
601 Sense Here 602 610 Home
602 Sense LeftAhead 610 603 Marker 4
603 Sense RightAhead 610 604 Marker 4
604 Sense Here 610 605 Marker 0
605 Sense Here 610 606 Marker 1
606 Sense Here 610 607 Marker 2
607 Drop 608
608 Move 250 608

610 Mark 5 611
611 Sense Ahead 612 614 Marker 4
612 AheadLesser 613 614
613 Move 601 650

614 Sense LeftAhead 615 618 Marker 4
615 LeftLesser 616 618
616 Turn Left 617
617 Move 601 650

618 Sense RightAhead 619 640 Marker 4
619 RightLesser 620 640
620 Turn Right 621
621 Move 601 650

640 Flip 2 641 642
641 Turn Left 601
642 Turn Right 601

650 Drop 651
651 Turn Left 652
652 Move 400 651

700 Sense Ahead 701 703 Marker 5
701 AheadGreater 702 703
702 Move 700 720
703 Sense LeftAhead 704 706 Marker 5
704 LeftGreater 705 706
705 Turn Left 702
706 Sense RightAhead 708 710 Marker 5
707 RightGreater 708 710
708 Turn Right 702

710 Flip 2 712 713
712 Turn Left 714
713 Turn Right 714
714 Sense Here 700 400 Marker 4

720 Unmark 5 720

die zeilennummern waren sozusagen lebensretend. ohne die, wird man ja sofort krank im kopp.
und nett sind auch die befehle

701 AheadGreater 702 703

und so. die expandieren zu nem dicken entscheidungsbaum, der alle 256 kombinationsmöglichkeiten checkt.

der "compiler":

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
using namespace std;

int lastBit(int x){
	int r=-1;
	while(x){
		++r;
		x/=2;
	}
	return r;
}

bool mlesser(int x){
	int a=x/16;
	int b=x%16;
	if(a-b>8) b+=16;
	if(b-a>8) a+=16;
	return a<b;
}
bool mgreater(int x){
	int b=x/16;
	int a=x%16;
	if(a-b>8) b+=16;
	if(b-a>8) a+=16;
	return a<b;
}

struct Condition{
	char* where;
	char* what;
};

int tab(ostream& out,int pos,Condition conditions[],int conditionsCount,int sttrue,int stfalse,bool(*cond)(int)){
	int inv=(1<<(conditionsCount+1))-2;
	int i=1;
	while(lastBit(i)<conditionsCount){
		int lb=lastBit(i);
		int st1=2*i-1;
		int st2=st1+1;
		if(lb==conditionsCount-1){
			st1=cond(inv-st1)?sttrue:stfalse;
			st2=cond(inv-st2)?sttrue:stfalse;
		}
		else{
			st1+=pos;
			st2+=pos;
		}
		out<<"Sense "<<conditions[lb].where<<' '<<st1<<' '<<st2<<' '<<conditions[lb].what<<endl;
		++i;
	}
	return pos+i-1;
}

int main(){
//	ofstream out("red.txt");
	Condition A0={"Ahead","Marker 0"};
	Condition A1={"Ahead","Marker 1"};
	Condition A2={"Ahead","Marker 2"};
	Condition A3={"Ahead","Marker 3"};
	Condition L0={"LeftAhead","Marker 0"};
	Condition L1={"LeftAhead","Marker 1"};
	Condition L2={"LeftAhead","Marker 2"};
	Condition L3={"LeftAhead","Marker 3"};
	Condition R0={"RightAhead","Marker 0"};
	Condition R1={"RightAhead","Marker 1"};
	Condition R2={"RightAhead","Marker 2"};
	Condition R3={"RightAhead","Marker 3"};
	Condition H0={"Here","Marker 0"};
	Condition H1={"Here","Marker 1"};
	Condition H2={"Here","Marker 2"};
	Condition H3={"Here","Marker 3"};
	Condition aconditions[]={A3,A2,A1,A0,H3,H2,H1,H0};
	Condition lconditions[]={L3,L2,L1,L0,H3,H2,H1,H0};
	Condition rconditions[]={R3,R2,R1,R0,H3,H2,H1,H0};
	int pos=1000;
	ifstream in("D:\\icfp\\ants2\\red.txt");
	ofstream out("D:\\icfp\\ants2\\red.ant",ios::binary);
	ostringstream out2;
	int nextinsno=0;
	int insno=0;
	while(in>>insno){
		while(nextinsno<insno){
			out<<"Drop 0\n";
			++nextinsno;
		}
		string cmd;
		in>>cmd;
		if(cmd=="AheadLesser"){
			int st1,st2;
			in>>st1>>st2;
			string tail;
			getline(in,tail);
			out<<"Flip 2 "<<pos<<' '<<pos<<"\n";
			pos=tab(out2,pos,aconditions,8,st1,st2,&mlesser);
		}else if(cmd=="LeftLesser"){
			int st1,st2;
			in>>st1>>st2;
			string tail;
			getline(in,tail);
			out<<"Flip 2 "<<pos<<' '<<pos<<"\n";
			pos=tab(out2,pos,lconditions,8,st1,st2,&mlesser);
		}else if(cmd=="RightLesser"){
			int st1,st2;
			in>>st1>>st2;
			string tail;
			getline(in,tail);
			out<<"Flip 2 "<<pos<<' '<<pos<<"\n";
			pos=tab(out2,pos,rconditions,8,st1,st2,&mlesser);
		}
		else if(cmd=="AheadGreater"){
			int st1,st2;
			in>>st1>>st2;
			string tail;
			getline(in,tail);
			out<<"Flip 2 "<<pos<<' '<<pos<<"\n";
			pos=tab(out2,pos,aconditions,8,st1,st2,&mgreater);
		}
		else if(cmd=="LeftGreater"){
			int st1,st2;
			in>>st1>>st2;
			string tail;
			getline(in,tail);
			out<<"Flip 2 "<<pos<<' '<<pos<<"\n";
			pos=tab(out2,pos,lconditions,8,st1,st2,&mgreater);
		}
		else if(cmd=="RightGreater"){
			int st1,st2;
			in>>st1>>st2;
			string tail;
			getline(in,tail);
			out<<"Flip 2 "<<pos<<' '<<pos<<"\n";
			pos=tab(out2,pos,rconditions,8,st1,st2,&mgreater);
		}
		else{
			string tail;
			getline(in,tail);
			out<<cmd<<tail<<'\n';
		}
		++nextinsno;
	}
	while(nextinsno<1000){
		out<<"Drop 0 ;dummy\n";
		++nextinsno;
	}
	out<<out2.str();
//	
//	cout<<pos<<endl;
}