PHP Tree building function breaks when depth = 4 but works when depth <4, why?

Question

Hi all. Frankly this is part of my uni assignment, BUT I have already done quite a bit... so please feel comfortable and keep reading since I am not asking for a cheat sheet or so :) The project is now deployed on my website

Okay, I might have found the reason just minutes ago: array_push() fails after pushing many items in an array. Ridiculously small array capacity???

It works when initial depth is set to 3, since 77 rows will not BLOW UP the array; but an initial depth of 4 will generate more rows beyond the PHP array's capacity(weird, never thought about this before).

After commenting out the array_push() part, this Tree building function will work, 10+ seconds cost for an initial depth of 6... So I guess the fix would be finding another collection type in PHP that can hold that many elements...

a test shows that under my current recursive tree building function, the largest number of rows allowed in an array storage is roughly 950... Beyond this would cause an "invisible" Allowed Memory size exhausted error which simply kills the PHP script from further execution. I can fix this problem simply by introducing more array storage objects.

So Please ignore the words below, since now the question has been changed and the focus is no longer there.

The monkey level and rookie level are finished with no bugs(at least I hope so). I encountered a weird problem when implementing the minimax search algorithm in the Veteran level, particularly when trying to build a tree up to N-th depth.

my buildTree function will only work when initial depth is set no greater than 3. It generates 16 tree nodes when initial depth is set to 2, and 77 when set to 3. I reckon the logic works, as you can check that using Fire Bug Console.

The purpose of this function is to simulate ai/player moves for n steps. Each move changes the cells status on the gameboard. Please go to the aforementioned website and play a rookie game so you understand what this is for.

Say, this function is used for AI. AI takes a move A, then player shall take his/her move B according to AI's move, then so forth... After making a move, certain cells on board need to be flipped. The score function is to evaluate a score based on current gameboard status. When the function finishes, I can get a full list where each row actually represent a node in a Tree, like this :

                                 AI 
                                 |
                           |-----------|
                         PLAYER       PLAYER
                           |           |
            |--------|-----------|  |-------|---------|
           AI       AI          AI AI      AI         AI
                        ......................

Below is the function that is buggy, spent hours looking at it but cannot find the cause:

function buildTree($gamecells, $depth, $side, $parent)
{ 
 //make copies of the arguments passed.
 $currentCells  = $gamecells;
 $currentDepth  = $depth;
 $currentSide   = $side;
 $currentParent = $parent;

 $nextMoves = $this->checkForValidMoves($currentCells, $currentSide);

 if(count($nextMoves) != 0 ) //can still move on.
 {
  foreach($nextMoves as $nextMove)
  {
   $flippedCells = $this->flipCells($currentCells, $nextMove, $side);
   $result = $this->getScore($flippedCells, $this->Session->read('aiside'));
   $score  = $result['score'] - $result['libertyPenalty'];
   $parentsTrace = $currentParent.'_'.$nextMove;

   if($currentDepth > 1) //currentDepth == 1 means this is a leaf node.
    $this->buildTree($this->getGamecellMap($flippedCells), $currentDepth-1,
           $this->swapSides($currentSide), $parentsTrace);

   array_push($this->movesTree, array
    ('depth'=>$currentDepth,
      'parentTrace'=>$parentsTrace,
      'move'=>$nextMove,
      'score'=>$score));
  }
 }
 if($currentDepth == 1) //we have traversed all leaf nodes, time to quit.
  return;
}

Because I am using PHP + AJAX, my normal way of debugging in PHP (echo some stuff in function) will not work. Plus I am still confusing about what this means when it does work when initial depth is no greater than 3... Can anyone help me out? Any suggestion is much appreciated and thanks a lot in advance!

Answer 1

You can try to debug the javascript by echoing out console.logs(), or even comments in the json output from the ajax requests (if you are evaluating them), or use something like http://www.firephp.org/. That way you can debug it with javascript callbacks. Spontaneous bugs are the hardest to find and fix. It looks like it's working fine now for me though.

Answer 2

for debug purposes i have this function:

function debug_array(){

        echo "<pre>";

        foreach(func_get_args() as $v){
         $v = Filter::htmlspecialchars($v, ENT_QUOTES, 'UTF-8');
        is_array($v) || is_object($v) ? print_r($v) : var_dump($v); 
        }
        echo "</pre>";
}

it is very simple to use it pass as many variables you like to debug_array()

debug_array($var1, $array, object, (bool)$test,...)