WPC13

[Jester]

Jo, kann ich machen

aber ist das wirklich sooo wichtig?

[phlox81]

Jester schrieb:

Jo, kann ich machen

aber ist das wirklich sooo wichtig?

wollte nur damit wissen, welches nun die Anforderungen sind,
und ob sich was dran geändert hat.

Devil

[Ponto]

Da die Zeit abgelaufen ist, hier mal der Bot, den ich geschrieben habe:

http://www.pontohonk.de/wpc13/PontoAgent.tgz

Die Arbeitsweise ist einfach:

1. Wenn ein neues Feld betreten wurde, sammle alle verfügbaren Informationen zusammen

2. Analysiere die Situation
2a) Falls es ein definitiv freies Feld gibt, gehe dort hin.
2b) Falls es kein freies Feld gibt, aber ein Feld, das frei wird, wenn man das Monster tötet. gehe zum ersten solchen Feld.
2c) Falls keiner der beiden oberen Fälle zutrifft, checke ob das Feld eine der gespeicherten Formen hat, gehe dann das Risiko ein auf eine Falle zu treten. Die gespeicherten Fälle sind alle Situationen, in denen es auf lange Sicht besser ist ein Risiko einzugehen.
2d) Falls nichts zutrifft, gebe auf.

3. Wird ein Weg gesucht, so läuft ein einfacher Dijkstra, der die kürzeste Zugfolge sucht, bis ein Prädikat erfüllt ist. Für die Fälle 2a) 2b) und 2c) gibt es jeweils ein eigenes Prädikat.

4. Führe die Zugfolge aus, bis das Zielfeld erreicht wurde.

Die wesentlichen Methoden sind:

update_info() für 1.
analyse() für 2.
search_path() für 3.
move() für 4.

Die riskanten Fälle sind in der riskmap kodiert. Dabei sind die Felder wie folgt benannt:

DHLP
CGKO
BFJN
AEIM

Nach jedem Feld steht die Information, wie oft für das Feld eine Falle in einem benachbarten Feld gemeldet wurde. Eine G2 bedeutet also, auf zwei Nachbarfeldern von G wurde ein Luftzug gespürt. Zu jeder Situation gibt es die Information, auf welches Feld man treten kann.

Insgesamt hat der Bot einen Erwartungswert von 348.791945988877 Punkten pro Runde.

[volkard]

Ponto schrieb:

2c) Falls keiner der beiden oberen Fälle zutrifft, checke ob das Feld eine der gespeicherten Formen hat, gehe dann das Risiko ein auf eine Falle zu treten. Die gespeicherten Fälle sind alle Situationen, in denen es auf lange Sicht besser ist ein Risiko einzugehen.
Insgesamt hat der Bot einen Erwartungswert von 348.791945988877 Punkten pro Runde.

damit haste mich um längen geschlagen.
342,280

[Ponto]

volkard schrieb:

Ponto schrieb:

2c) Falls keiner der beiden oberen Fälle zutrifft, checke ob das Feld eine der gespeicherten Formen hat, gehe dann das Risiko ein auf eine Falle zu treten. Die gespeicherten Fälle sind alle Situationen, in denen es auf lange Sicht besser ist ein Risiko einzugehen.
Insgesamt hat der Bot einen Erwartungswert von 348.791945988877 Punkten pro Runde.

damit haste mich um längen geschlagen.
342,280

Je nachdem, welche Instanzen Jester testet, kann das auch in die Hose gehen. Hängt halt von der Anzahl und der Verteilung ab.

[volkard]

Ponto schrieb:

Je nachdem, welche Instanzen Jester testet, kann das auch in die Hose gehen. Hängt halt von der Anzahl und der Verteilung ab.

ich hoffe, es gibt keine einsendungen, die rand() benutzen. dann kann der volltest genommen werden.
oder, falls nicht, hoffe ich, die, die rand() benutzen, sind deutlich schlechter, und erlauben, daß die nicht-rand()-benutzer in einer anderen liga sind und getrennt einen volltest machen können.
mal sehen, wie es wird.

edit: aber dein code wird meinen auch bei sagen wir mal ab 100000 tests sicher plattmachen. der unterschied ist einfach zu groß.

[Ponto]

Wann kann man die Auswertung erwarten?

[Jester]

hallo

ich denke die Ergebnisse gibt es heute abend.

MfG Jester

[Jester]

So, die Auswertung ist fertig: http://wpc.schornboeck.net/viewtopic.php?p=351#351

Hier nur nochmal die Plazierung:

1. Ponto
2. OnlyFoo
3. TGGC
4. cd9000

[volkard]

Jester schrieb:

So, die Auswertung ist fertig: http://wpc.schornboeck.net/viewtopic.php?p=351#351

du hast meine einsendung also nicht mehr genommen. schade.

falls es jemanden interessiert. er hat 342.803 punkte.
weil mein internet-provider einen server-umzug nicht hinkriegt, konnte ich am freitag abend keine mail verschicken. hab's erst samstag bemerkt und erst um um 13:44 es geschafft, jester eine mail zu schicken. der isp hat an jester auch eine mail geschickt, in der er sagt, daß der server nicht geht und deswegen ich keine mail absetzen konnte.

#include "Agent.h" // inheriting class's header file

#include <cstddef>

class Volkard:public Agent{
private:
	template<class T,size_t SIZE>
	class RingBuffer{
	private:
		size_t write;
		size_t read;
		T data[SIZE];
	public:
		RingBuffer(){
			read=0;
			write=0;
		}
		bool empty(){
			return write==read;
		}
		void push(T const& t){
			data[write]=t;
			++write;
			write%=SIZE;
		}
		T& front(){
			return data[read];
		}
		void pop(){
			++read;
			read%=SIZE;
		}
	};
	typedef unsigned int u32;
	typedef u32 Map;
	//W: wall
	//x: datenfeld
	//WWWWWWWWxxxxWxxxxWxxxxWxxxxWWWWW
	//10987654321098765432109876543210
	//links oben ist 5
	//rechts oben ist 8
	static const Map WALL=0xFF08421F;
	//11111111000010000100001000011111
	//WWWWWWWWxxxxWxxxxWxxxxWxxxxWWWWW
	static const Map START=1<<20;
	typedef u32 Position;
	static Position moveLeft(Position pos){
		return pos>>=1;
	}
	static Position moveRight(Position pos){
		return pos<<=1;
	}
	static Position moveUp(Position pos){
		return pos>>=5;
	}
	static Position moveDown(Position pos){
		return pos<<=5;
	}
	typedef u32 Direction;
	static Direction turnLeft(Direction dir){
		return (dir+1)%4;
	}
	static Direction turnRight(Direction dir){
		return (dir+3)%4;
	}
	static Position move(Position pos,Direction dir){
		switch(dir){
		case 0: return moveRight(pos);
		case 1: return moveUp(pos);
		case 2: return moveLeft(pos);
		case 3: return moveDown(pos);
		}
		return 0;//only to make the compiler happy
	}
	struct PosDir{
		Position position;
		Direction direction;
		PosDir(){
		};
		PosDir(Position pos,Direction dir):
		position(pos),
		direction(dir){
		}
		static int findFirstBitTrue(Position x){
			int result=0;
			while((x&1)==0){
				x>>=1;
				++result;
			}
			return result;
		}
		int pack() const{
			//WWWWWWWWxxxxWxxxxWxxxxWxxxxWWWWW
			return findFirstBitTrue(position>>5)*4+direction;
		}
	};
	Position position;
	Direction direction;
	Map visited;
	Map pit;
	Map monster;
	Map unknown;//ich war noch nie in der nachbarschaft
	bool gold;
	bool shot;
	static Map getNeighbours(Position pos){
		Map neighbours=moveLeft(pos)|moveUp(pos);
		neighbours|=moveRight(moveDown(neighbours));
		return neighbours;
	}
	static Map removeNear(Map map,Position pos){
		return map&~getNeighbours(pos);
	}
	static Map removeNotNear(Map map,Position pos){
		return map&getNeighbours(pos);
	}
	static int population(Map x){
		int result=0;
		while(x){
			x&=(x-1);
			++result;
		}
		return result;
	}
	static int value(Position position,Map val1,Map val2){
		//zielfeld bewerten, falls wegsuche mehrere gleich weit entfernte ziele findet
		//kleine ergebnisse sind gut
		return 55-10*population(getNeighbours(position)&val1)-population(getNeighbours(position)&val2);
	}
	static int calcDistance(Position position,Direction direction,Map interest,Map blocked,Map val1,Map val2){
		if(position&blocked) return 1000000;
		if(position&interest) return (100*1)+value(position,val1,val2);
		//einfachste breitensuche
		char dist[19*4]={0};
		dist[PosDir(position,direction).pack()]=1;
		RingBuffer<PosDir,32> toDo;
		toDo.push(PosDir(position,direction));
		while(!toDo.empty()){
			PosDir here=toDo.front();
			toDo.pop();
			PosDir next[3]={
				PosDir(here.position,turnLeft(here.direction)),
				PosDir(move(here.position,here.direction),here.direction),
				PosDir(here.position,turnRight(here.direction))
			};
			for(int i=0;i<3;++i){
				PosDir const& there=next[i];
				if(there.position&blocked) continue;
				if(there.position&interest) return 100*(dist[here.pack()]+1)+value(there.position,val1,val2);
				int thereid=there.pack();
				if(dist[thereid]) continue;
				dist[thereid]=dist[here.pack()]+1;
				toDo.push(there);
			}
		}
		return 1000000;
	}
	Action think(Sense const& sense){
		//sofort-aktionen
		if(gold) return FINISH;
		if(sense.glitter) return GRAB;
		//keine sofort-aktionen gefunden, also erstmal sensor-daten einspeisen
		if(sense.scream) monster=0;
		if(!(position&visited)){
			visited|=position;
			unknown=removeNear(unknown,position);
			if(!sense.breeze)
				pit=removeNear(pit,position);
			if(!sense.stench)
				monster=removeNear(monster,position);
			else
				monster=removeNotNear(monster,position);
		}
		//unbesuchtes ungefõhrliches feld suchen
		if(Map interest=~visited&~pit&~monster&~WALL){
			Map blocked=pit|monster|WALL;
			Map val1=~visited&~pit&~monster&~WALL;
			Map val2=unknown&~WALL;
			int dl=calcDistance(position,turnLeft(direction),interest,blocked,val1,val2);
			int dm=calcDistance(move(position,direction),direction,interest,blocked,val1,val2);
			int dr=calcDistance(position,turnRight(direction),interest,blocked,val1,val2);
			if(dl<dm && dl<dr) return TURN_LEFT;
			if(dr<dm && dr<dl) return TURN_RIGHT;
			if(dl<dm && dr<dm) return TURN_RIGHT;
			return MOVE;
		}
		//nix ungefõhrliches mehr da. 
		//dann ballere ich mal das monster ab
		if(Map interest=monster&~pit&~WALL){
			if(shot) return FINISH;//ups, zwecklos
			if(move(position,direction)&monster) return SHOOT;//haha, ich hab dich!
			Map blocked=pit|WALL;
			Map val1=~visited&~pit&~monster&~WALL;
			Map val2=unknown&~WALL;
			int dl=calcDistance(position,turnLeft(direction),interest,blocked,val1,val2);
			int dm=calcDistance(move(position,direction),direction,interest,blocked,val1,val2);
			int dr=calcDistance(position,turnRight(direction),interest,blocked,val1,val2);
			if(dl<dm && dl<dr) return TURN_LEFT;
			if(dr<dm && dr<dl) return TURN_RIGHT;
			if(dl<dm && dr<dm) return TURN_RIGHT;
			return MOVE;
		}
		//schade, nix mehr zu holen
		return FINISH;
	}
public:
	Volkard():
		position(START),
		direction(0),
		visited(0),
		pit(~WALL&~START),
		monster(~WALL&~START),
		unknown(~WALL&~START),
		gold(false),
		shot(false){
	}
	virtual ~Volkard(){
	}
	virtual Action decideNextAction(Sense sense){ 
		Action action=think(sense); 
		switch(action){ 
		case TURN_LEFT: 
			direction=turnLeft(direction);
			break; 
		case TURN_RIGHT: 
			direction=turnRight(direction);
			break; 
		case MOVE:
			position=move(position,direction);
			break;
		case GRAB: 
			gold=true;
			break;
		case SHOOT:
			//ich schie▀e nur, wenn es stinkt
			monster&=~move(position,direction);
			shot=true;
			break;
		case FINISH: 
			break; 
		} 
		return action; 
	} 
	static char const* getName(){
		return "volkard";
	}
	static char const* getMail(){
		return "volkard@normannia.de";
	}
	static Agent* createAgent(){
		return new Volkard;
	}
	static void destroyAgent(Agent* agent){
		delete agent;
	}
};