C# minmax graph search

Question

EDIT 3: Okay, so i got my code to work, but i'm facing a huge memory consumption problem if i'm using let's say 16 nodes and a search depth above 11.

an soemone check the code and tell me how can i correct that memory leak?

Here's the full code:

public void searchTSP(
    int depth,
    RouterPoint startpoint,
    bool isRound,
    IRouter<RouterPoint> router)
{
  #region TSP_startpointCheck
  if (!routepoints[0].Location.Equals(startpoint.Location))
  {
    int index = Array
      .FindIndex(routepoints, x => x.Location == startpoint.Location);

    if (index != -1 && index != 0) //it's somewhere in the array
    {
      RouterPoint temprp = routepoints[0];
      routepoints[0] = routepoints[index]; //put it to index 0
      routepoints[index] = temprp;
    }
    else //it's not in the array
    {
      //we add it...
      RouterPoint[] ta = new RouterPoint[routepoints.Length + 1];
      routepoints.CopyTo(ta, 0);
      ta[routepoints.Length] = startpoint;
      ta.CopyTo(routepoints, 0);
    }
  }
  #endregion

  selectedRouter = router;
  if (pathDictionary == null)
  {
    pathDictionary = new Dictionary<int[], double>(new IntArrayComparer());
    fillDictionary();
  }            

  DecisionPath bestPath = new DecisionPath();
  //DecisionPath currentPath = new DecisionPath();
  //List<DecisionPath> listOfPaths = new List<DecisionPath>();
  //List<int> visited = new List<int>();
  //List<RouterPoint> waypoints = routepoints.ToList();

  DateTime start = DateTime.Now;
  RouteNode root = new RouteNode();
  root.parent = null;
  root.curr = 0;
  root.weight = 0.0f;
  root.isTerminal = false;
  root.memory = new List<short>();
  root.memory.Add(root.curr);
  calculateChildren(root);

  double bestval=double.MaxValue;
  while (bestPath.list.Count < routepoints.GetLength(0))
  {
    bestval = double.MaxValue;
    int bestIndex = 0;
    for (int i = 0; i < root.children.Count; i++)
    {
      RouteNode child = root.children[i];
      double t = minimax(child, depth);
      if (t < bestval)
      {
        bestval = t;
        bestIndex = i;
        bestPath.cost = bestval;
        bestPath.list = child.memory;
      }
    }

    RouteNode temp = root.children[bestIndex];
    root.children.Clear();
    root.children.Add(temp);
    root = root.children[0];
  }

  //My result is in the bestPath class 
  // which has two properties: a list of indexes
  // representing my found result node sequence
  // and a double containing the total cost of the path
}

class RouteNode
{
  public RouteNode parent { get; set; }
  public short curr { get; set; }
  public bool isTerminal { get; set; }
  public float weight { get; set; }
  public List<RouteNode> children { get; set; }
  public List<short> memory { get; set; }
}

/// <summary>
/// List of all children of a node that should be removed
/// </summary>
private List<RouteNode> killList;

/// <summary>
/// MiniMax recursive search for deciding witch ode to go to
/// </summary>
/// <param name="point">Input node</param>
/// <param name="depth">How deep will we search</param>
/// <returns>Weight value</returns>
private double minimax(RouteNode point, int depth)
{
  if (point.isTerminal || depth <= 0)
  {
    //if (point.isTerminal)
    if (point.weight < bestyVal)
    {
      bestyVal = point.weight;
      //Console.WriteLine(
      //    "{0} - {1}",
      //    string.Join(", ", point.memory.ToArray()),
      //    point.weight.ToString());
    }

    return point.weight;
  }

  double alpha = double.PositiveInfinity;
  if (point.children == null || point.children.Count == 0 )
    calculateChildren(point);

  killList = new List<RouteNode>();
  for (int i=0; i< point.children.Count; i++)
  {
    RouteNode child = point.children[i];
    if (child != null)
    {
      if (!child.isTerminal && child.weight > bestyVal)
      {
        child = null;
        continue;
      }

      alpha = Math.Min(alpha, minimax(child, depth - 1));
    }
    else
      continue;
  }

  point.children.RemoveAll( e => killList.Contains(e));
  //killList = null;
    return alpha;
}

/// <summary>
/// Calculates possible children for a node
/// </summary>
/// <param name="node">Input node</param>
private void calculateChildren(RouteNode node)
{
  int c = node.curr;
  List<int> possibleIndexes = Enumerable
      .Range(0, routepoints.GetLength(0))
      .ToList();

  RouteNode curNod = node;

  if (node.children == null)
    node.children = new List<RouteNode>();

  while (curNod != null)
  {
    possibleIndexes.Remove(curNod.curr);
    curNod = curNod.parent;
  }
  //imamo še neobiskane potomce...
  foreach (int i in possibleIndexes)
  {
    RouteNode cc = new RouteNode();
    cc.curr = (short)i;
    cc.parent = node;
    double temp=0.0;
    if (!pathDictionary.TryGetValue(new int[] { node.curr, i }, out temp))
    {
      //preracunajPoti(node.curr, i, selectedRouter);
      throw new Exception(
          String.Format(
              "Missed a path? {0} - {1}",
              node.curr,
              i));
    }

    cc.weight = cc.parent.weight + (float)temp;
    cc.memory = node.memory.ToList();
    cc.memory.Add(cc.curr);

    if (possibleIndexes.Count == 1)
      cc.isTerminal = true;
    else
      cc.isTerminal = false;

    node.children.Add(cc);
  }
  //jih dodamo
  possibleIndexes = null;    
}

Answer 1

Just throwing in my two cents on this, @mao47 is dead on, in that there is not a memory leak just a massive amount of memory needed.

I came across this thread when looking for reading on MinMax searching and it is worth adding there is a fair bit of work out there on optimizing MinMax and other algorithms. I found this paper useful reading for example (language was reasonably understandable given my personal rate of academic decay and time t since I finished school).