Wiki Targeting/Code

Sub-pages:

Wiki Targeting - Dynamic Segmentation - Code - Archived Talk 20090501

---

Schematics

+----------------------------------------------------------------+
| MyRobot ------ Node ------ Leaf ------ Bin                     |
|         \           \           \                              |
|          \           \           ----- Log -----< Observation  |
|           \           \                               |        |
|            \           \                          Situation    |
|             \           \                                      |
|              \           - Splitter ------< Node(recursive)    |
|               \                                                |
|                Recursionlevel                                  |
+----------------------------------------------------------------+

Pseudocode

Class MyRobot
{
	Node root = new Node();
	RecursionLevel level = new Recursionlevel();

	processWave()
	{
		Observation o = new Observation(Situation s, int GuessFactor);
		level.reset();
		root.addObservation(o, level);
	}

	getGuessFactor(Situation s)
	{
		level.reset();
		root.getGuessFactor(s, level);
	}
}

Class Node
{
	Leaf leaf = new Leaf();
	Splitter splitter = null;

	int getGuessFactor(Situation s, RecursionLevel level, double Distance)
	{
		if(leaf==null)
		{
			return Splitter.getGuessFactor(s, level)	//this node is not a leaf. continue recursion.
		}
		else
		{
			return leaf.getGuessFactor(Distance)
		}
		
	}

	addObservation(Observation o, RecursionLevel level)	
	{
		if(leaf==null)
		{
			Splitter.addObservation(o, level)		//this node is not a leaf. continue recursion.
		}
		else
		{
			Leaf.add(o);
			if(leaf.size() >= 40)
			{
				if(splitter == null) splitter = new Splitter();
				if(splitter.split(leaf, level))	//splitter.split returns true if successful
				{
						// this nodes is no longer a leaf node. save memory space by deleting unused objects
					leaf.discard();
					leaf = null;
				}
			}
		}
	}

	getPeakFactor()
	{
		return leaf.getPeakFactor();
	}

	clear()
	{
		leaf.clear();
	}
}

Class RecursionLevel
{
	int level;
	int min[numDimensions]; //inclusive
	int max[numDimensions]; //exclusive

	reset()
	{
		level = o;
		for(i=0;i<numDimensions;i++)
		{
			min[i] = 0;
			max[i] = 127;
		}
	}

	getSplitValue(int SplitDimension)
	{
		return (min[SplitDimension] + max[SplitDimension]) / 2.0D;
	}

	branchLow (int SplitDimension)
	{
		max[SplitDimension] = getSplitValue(SplitDimension);
	}

	branchHigh (int SplitDimension)
	{
		min[SplitDimension] = getSplitValue(SplitDimension);
	}
}

Class Leaf
{
	Log log     = new Log();
	Bin nodeBin = new Bin();
	
	int getGuessFactor(double Distance)
	{
		nodeBin.findBestIndex(Distance);
	}

	add(Observation o)
	{
		log.add(o);
		nodeBin.add(o.getGF());
	}

	getPeakFactor()
	{
		double Distance = log.getAverageDistance();	//assume the distance is the average distance of all observations
		return nodeBin.getPeakFactor(Distance);
	}

	int size()
	{
		return log.size();
	}

	discard()
	{
		log = null;	
		nodeBin = null;
	}

	clear()
	{
		log.clear();
		nodeBin.clear();
	}
}

Class Splitter
{
	Node LChild = new Node();
	Node HChild = new Node();
	int SplitDimension;

	int getGuessFactor(Situation s, Recursionlevel level)	
	{
		if(s.getDimension(SplitDimension) < level.getSplitValue(SplitDimension))
		{
			level.diveLow(SplitDimension);
			LChild.getGuessFactor(s, level);
		}
		else
		{
			level.diveHigh(SplitDimension);
			HChild.getGuessFactor(s, level);
		}
	}

	addObservation(Observation o, Recursionlevel level)
	{
		if(o.getDimension(SplitDimension) < level.getSplitValue(SplitDimension))
		{
			level.diveLow(SplitDimension);
			LChild.addObservation(o, level);
		}
		else
		{
			level.diveHigh(SplitDimension);
			HChild.addObservation(o, level);
		}
	}

	spawnChildren(List Log, int Dimension, int SplitValue, Node LChild, Node HChild)
	{
		for(j=0;j<Log.size();j++)
		{
			Observation o = Log.get(j);
			if(o.getDimension(i) < SplitValue)
			{
				L.addObservation(o);
			}
			else
			{
				H.addObservation(o);
			}
		}
	}


	boolean split(Leaf parent, Recursionlevel level) 			//this function is called by the Node when it has enough Observations to justify splitting the Node up.
	{
		int BestPeakTotal = parent.getPeakFactor(); 			//children need to exceed parent's peak factor
		int BestDim = -1;
		int SplitValue;
		for(i=0; i<numDimensions; i++)					//iterate over all dimensions and remember the most efficient dimension for splitting
		{
			SplitValue = level.getSplitValue(i);
			spawnChildren(parent.Log, i, SplitValue, LChild, HChild);			//temporarily split the parent log into two child nodes
			if((LChild.getPeakFactor() + HChild.getPeakFactor()) > BestPeakTotal)		//check how this split performs
			{
				BestDim = i;
				BestPeakTotal = LChild.getPeakFactor() + HChild.getPeakFactor();
			}
			LChild.clear();
			HChild.clear();
		}
		If(BestDim > -1)									//if a good splitting dimension is found, make it permanent
		{
			SplitDimension = BestDim;
			SplitValue = level.getSplitValue(SplitDimension);
			spawnChildren(parent.Log, SplitDimension, SplitValue, LChild, HChild);		//permanently split the parent log into two child nodes
			return true;
		}
		else
		{
			return false;
		}
	}
}


Class Bin
{
	numBins = 75;

	int bin[numBins];

	add (int GF)
	{
		bin[GF]++;
	}

	clear()
	{
		for(i=0; i<numBins; i++)
		{
			bin[i] = 0;
		}
	}		

	int calcBotwidth()
	{
		//formula see Locke, botwidth is half the bot's width, expressed in GF indices
	}


	getPeakFactor(double Distance)	
	{
			//first find the best index, considering bot width
		int botwidth = calcBotwidth(Distance);
		int index = findBestIndex(botwidth);
			//then, using this index, count the pure visits, considering bot width
		int PeakFactor = 0;
		for(i=(index-botwidth+1);i<(index+botwidth);i++)
		{
			if(i<0) i=0;
			if(i>=numBins) i=numBins;
			PeakFactor += bin[i];
		}
	}

	int findBestIndex(double Distance)
	{
		int botwidth = calcBotwidth(Distance);
		int specialbin[numBins];
		for(index=0; index<numBins; index++)	
		{
			int imin = index-botwidth+1;
			if(imin<0) imin=0;
			int imax = index+botwidth;
			if(imax>=numBins) imax=numBins-1;
			for(i=imin;i<imax;i++)
			{
				specialbin[index] += bin[i];
			}
			
		}
		int bestIndex=0;
		int bestValue=0;
		for(index=0; index<numBins; index++)	
		{
			if(bestValue < specialbin[index]) 
			{
				bestIndex = index;
				bestValue = specialbin[index];
			}
		}
		/*
		TO DO: IN CASE OF "PLATEAU" FIND MIDDLE INDEX. SEE LOCKE FOR CODE.
		*/
		return bestIndex;
	}
}

Class Log
{
	List Log = new List();

	add(Observation o)
	{
		Log.add(o);
	}

	Observation get(int index)
	{
		return (Observation)Log.get(index);
	}

	int size()
	{
		return Log.size();
	}

	double getAverageDistance()
	{	
		int Total, Counter;
		for(i=0; i<size(); i++)
		{
			COunter++;
			Total += (get(i)).getDimension(x); //x = dimension that represents distance
		}
		return (double)Total / (double)Counter;
	}
}

Class Observation
{
	Situation s;
	int GuessFactor;

	getGF()
	{
		return GuessFactor;
	}

	getDimension(int d)
	{
		return s.getDimension(d);
	}
}


Class Situation
{
	int Dimensions[numDimensions];

	getDimension(int d)
	{
		return Dimensions[d];
	}
}