public void FindBestSolution()
{
// Set best solution to null.
_bestSolution = null;
HerbertProgram bestProgram = null;
int bestProgramScore = 0;
HerbertInterpreter interp = new HerbertInterpreter(this.Level);
int maxDepth = this.Level.ProgramMaxByteLength * 2;
int depth = 1;
List<HSearchState> searchStates;
List<HSearchState> nextSearchStates = new List<HSearchState>();
int numTotalPrograms = 0;
int numBadPrograms = 0;
HerbertProgram curProgram;
int curProgramScore;
int reportStatusTrackerCount = 8000;
int reportStatusTracker = 0;
// Write to trace.
Trace.WriteLine(DateTime.Now.ToShortDateString() + " " + DateTime.Now.ToLongTimeString());
Trace.WriteLine("");
Trace.WriteLine(string.Format("Maximum depth of search: {0}", maxDepth));
Trace.WriteLine("");
// Write information about search.
Console.WriteLine("Max program length: {0}", maxDepth);
// Add initial search state to list.
HSearchState initialState = new HSearchState();
initialState.State = HProgramState.PrototypingProcedures;
initialState.HistoryState = HProgramState.Initialized;
initialState.Program = new HerbertProgram(maxDepth * 2);
initialState.CurAddress = 0;
initialState.Procedures = new HProcedurePrototype[4];
initialState.ProcCount = 0;
initialState.ProcIndex = 0;
initialState.ArgCount = 0;
initialState.ArgIndex = 0;
initialState.DefineNewProcedure = false;
initialState.ProcedureIsEmpty = true;
initialState.CommandIndex = 0;
initialState.CallProcIndex = 0;
nextSearchStates.Add(initialState);
initialState = initialState.Clone();
initialState.State = HProgramState.MainProgram;
nextSearchStates.Add(initialState);
// Loop until depth of search is maximum depth.
while (depth <= maxDepth)
{
// Insure that status is reported on first iteration.
reportStatusTracker = reportStatusTrackerCount;
// Write to trace.
Trace.WriteLine(string.Format("Start of search at depth: {0}", depth));
Trace.WriteLine("");
// Set current search states to next search states.
searchStates = nextSearchStates;
// Create list of next search states.
nextSearchStates = new List<HSearchState>();
// Get each search state in current list.
HSearchState curState;
for (int i = 0; i < searchStates.Count; i++)
{
// Get current search state.
curState = searchStates[i];
// Check whether to report status now.
if (reportStatusTracker == reportStatusTrackerCount)
{
// Reset tracker.
reportStatusTracker = 0;
// Report status.
Console.CursorLeft = 0;
Console.Write("{0:#0%}", (float)i / (float)searchStates.Count);
}
else
reportStatusTracker++;
// Increment number of total programs.
numTotalPrograms++;
// Create all possible programs based on current one.
bool programFinished;
do
{
_allChildProgramsCreated = false;
try
{
//HSearchState oldState = curState.Clone();
// Create new program from current search state.
programFinished = CreateProgram(ref curState);
curProgram = curState.Program;
//if (curState.Program.Code[0] != HInstruction.NoOp)
//{
// Console.WriteLine();
// Console.WriteLine("<program>");
// Console.WriteLine(curProgram.ToString());
// Console.WriteLine("</program>");
// Console.ReadKey(true);
//}
// Check if in Main Program state.
if (curState.State == HProgramState.MainProgram)
{
// Compile and run program.
curProgram.Compile();
curProgramScore = interp.Run(curProgram);
#if TRACE
// Write program code to trace.
Trace.WriteLine(curProgram.ToString());
Trace.WriteLine("");
#endif
// Check if current program has higher score than previous best program.
if (curProgramScore > bestProgramScore)
{
bestProgram = curProgram;
bestProgramScore = curProgramScore;
// Set best solution.
_bestSolution = new HerbertSolutionInfo(bestProgram, bestProgram.GetByteLength(),
bestProgramScore);
}
}
// Check whether to add clone of search state to list of next states.
if (!programFinished)
{
HSearchState nextState = curState.Clone();
// Check if Procedure Call state has just been entered.
if (nextState.State == HProgramState.ProcedureCall
&& curState.State != HProgramState.ProcedureCall)
{
// Set number of arguments and reset index of current argument.
nextState.ArgCount = nextState.Procedures[nextState.CallProcIndex].ArgCount;
nextState.ArgIndex = -1;
// Enter Procedure Call state.
nextState.HistoryState = nextState.State;
nextState.State = HProgramState.ProcedureCall;
}
if (nextState.State == HProgramState.NumericalArgument)
{
// Check if previous instruction was number/parameter.
HInstruction prevInstruction = nextState.Program.Code[
nextState.CurAddress - 1];
if ((prevInstruction & HInstruction.NumberBase) != 0
|| (prevInstruction & HInstruction.ParameterNameBase) != 0)
// Set that last instruction was number.
nextState.LastInstructionWasNumber = true;
else
// Set that last instruction was not number.
nextState.LastInstructionWasNumber = false;
}
// Add state to list of next states.
nextSearchStates.Add(nextState);
}
}
catch (Exception)
{
// Increment number of bad programs.
numBadPrograms++;
continue;
}
} while (!_allChildProgramsCreated);
}
// Write to trace.
Trace.WriteLine(string.Format("End of search at depth: {0}", depth));
Trace.WriteLine("");
// Report status.
Console.CursorLeft = 0;
Console.WriteLine("Done.\tTarget program length: {0}\tBest score: {1}",
depth, bestProgramScore);
// Increment length of programs.
depth++;
}
// Report statistics of search.
Console.WriteLine("Percentage of bad programs: {0:#0%}",
(float)numBadPrograms / (float)numTotalPrograms);
}