PHP 树构建函数在深度 = 4 时中断，但在深度 <4 时工作，为什么？

发布于 2024-08-08 23:26:37 字数 2892 浏览 4 评论 0 原文

坦率地说，这是我大学作业的一部分，但我已经做了很多了……所以请放心并继续阅读，因为我不要求备忘单等:) 该项目现已部署在我的网站

好吧，我可能几分钟前就找到了原因： array_push() 在推送数组中的许多项目后失败。数组容量小得离谱？？？

当初始深度设置为 3 时，它可以工作，因为 77 行不会炸毁数组；但初始深度为 4 会生成超出 PHP 数组容量的更多行（很奇怪，以前从未考虑过这一点）。

注释掉 array_push() 部分后，这个树构建函数将起作用，初始深度为 6 需要 10 多秒的时间...所以我想修复方法是在 PHP 中找到另一种可以容纳那么多的集合类型元素...

测试表明，在我当前的递归树构建功能下，数组存储中允许的最大行数大约为 950...超出此范围将导致“不可见”的允许内存大小耗尽错误，从而简单地终止 PHP 脚本从进一步执行。我可以简单地通过引入更多的数组存储对象来解决这个问题。

所以请忽略下面的话，因为现在问题已经改变，焦点不再存在。

猴子关卡和菜鸟关卡已经完成，没有任何错误（至少我希望如此）。在老手级别实现极小极大搜索算法时，我遇到了一个奇怪的问题，特别是在尝试构建深度为 N 的树时。

我的 buildTree 函数仅在初始深度设置不大于 3 时才起作用。当初始深度设置为 2 时，它生成 16 个树节点；当设置为 3 时，它生成 77 个树节点。我认为这个逻辑是有效的，因为您可以使用 Fire Bug Console 进行检查。

该函数的目的是模拟人工智能/玩家的 n 步移动。每一步都会改变游戏板上的单元格状态。请访问上述网站并玩一个菜鸟游戏，以便您了解其用途。

比如说，这个功能是用于AI的。 AI采取A行动，然后玩家根据AI的行动采取B行动，依此类推......采取行动后，棋盘上的某些单元格需要翻转。评分功能是根据当前游戏板的状态来评估分数。当函数完成时，我可以获得一个完整的列表，其中每一行实际上代表树中的一个节点，如下所示：

<前><代码>人工智能 | |------------| 玩家玩家 | | |--------|------------| |--------|---------| 人工智能人工智能人工智能人工智能人工智能人工智能 ......................

下面是有 bug 的函数，花了几个小时查看它，但找不到原因：

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;
}

因为我使用 PHP + AJAX，所以我在 PHP 中调试的常规方法（回显函数中的某些内容）将不起作用。另外，当初始深度不大于 3 时它确实起作用时，我仍然对这意味着什么感到困惑...... 有人可以帮我吗？非常感谢任何建议，并提前致谢！

原文

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!

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

不及他 2024-08-15 23:26:37

出于调试目的，我有这个函数：

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>";
}

使用它非常简单，可以将任意多个变量传递给 debug_array()

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

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,...)

回复收藏 0 原文

虚拟世界 2024-08-15 23:26:37

您可以尝试通过回显 console.logs() 来调试 javascript，甚至可以在 ajax 请求的 json 输出中添加注释（如果您正在评估它们），或者使用类似 http://www.firephp.org/。
这样你就可以使用 javascript 回调来调试它。
自发的错误是最难发现和修复的。看起来现在对我来说工作得很好。