javascript - 递归未按预期在 javascript 中展开

Question

我最近写了一个函数，它将棋盘(X 和 O)作为参数并返回游戏状态，即(赢、输或平)和最佳着法。该算法将每个棋盘位置视为图形的节点，并尝试通过图形遍历找到最佳着法。它类似于 Minimax 但它不使用评分函数并且不固定深度，而是尝试所有可能性(使用蛮力)。该实现在 C++ 中运行良好，但后来我尝试用 javascript 翻译代码，但我发现递归没有像 JS 中预期的那样展开。

C++中的findmove函数:-

///1 for win, 0 for draw, -1 for loss
int nodes;

pair<int,int> findmove(int a[3][3], int tomove){
    nodes++;
    if (winning(a,-1)){
        return make_pair(1,-1);
    }
    if (losing(a,-1)){
        return make_pair(-1,-1);
    }
    if (draw(a,-1)){
        return make_pair(0,-1);
    }

    int best = -1;
    int nbest = -1;
    int gstat = -1;
    if (tomove==1){
        gstat = 1;
    }
    for (int i=0; i<9; i++){
        int na[3][3];
        int flag = getnew(a,na,tomove,i);
        if (flag==0){continue;}
        pair<int,int> getstatus = findmove(na, nex[tomove]);
        int status = getstatus.first;

        if (status==1){
            if (tomove==-1){
                best = i;
                gstat = 1;
            }
            continue;
        }
        if (status==0){
            if (tomove==-1){
                if (nbest==-1){
                    nbest = i;
                }
                if (gstat<0){
                    gstat = 0;
                }
            }
            if (tomove==1){
                if (gstat>0){
                    gstat = 0;
                }
            }
            continue;
        }
        if (status==-1){
            if (tomove==1){
                gstat = -1;
            }
            continue;
        }
    }
    if (gstat==1){
        return make_pair(1,best);
    }
    if (gstat==0){
        if (best!=-1){
            nbest = best;
        }
        return make_pair(0,nbest);
    }
    return make_pair(-1,-1);
}

此功能按预期工作，您可以在下面发布的 ideone 链接中看到整个程序。

我尝试编写其等效的 javascript 代码，但它没有按预期工作。

Javascript 中的函数:-

function findMove(a,tomove){
    //a is a 3*3 int matrix, with 0 representing empty, 
    //1 representing X and -1 representing O
    //tomove = -1 if its O's turn and 1 if its X's turn 
    nodesvis++;   //global variable that counts the number of times function is called
    if (winning(a,-1)){
        return new Vector(1,-1);
    }
    if (losing(a,-1)){
        return new Vector(-1,-1);
    }
    if (draw(a,-1)){
        return new Vector(0,-1);
    }

    var best = -1;
    var nbest = -1;
    var gstat = -1;
    if (tomove==1){
        gstat = 1;
    }
    for (var i=0; i<9; i++){
        //console.log("Nodesvisited, i " + nodesvis +" "+ i);   
        var na = a;
        var xi = Math.floor(i/3);
        var yj = i%3;
        if (na[xi][yj]!=0){continue;}
        na[xi][yj] = tomove;

        var nexttomove = tomove*(-1);
        var getstatus = findMove(na, nexttomove);
        var status = getstatus.x;

        if (status==1){
            if (tomove==-1){
                best = i;
                gstat = 1;
            }
            continue;
        }
        if (status==0){
            if (tomove==-1){
                if (nbest==-1){
                    nbest = i;
                }
                if (gstat<0){
                    gstat = 0;
                }
            }
            if (tomove==1){
                if (gstat>0){
                    gstat = 0;
                }
            }
            continue;
        }
        if (status==-1){
            if (tomove==1){
                gstat = -1;
            }
            continue;
        }
    }

    if (gstat==1){
        return new Vector(1,best);
    }
    if (gstat==0){
        if (best!=-1){
            nbest = best;
        }
        return new Vector(0,nbest);
    }
    return new Vector(-1,-1);
}

我已经尝试调试了一段时间，但我不确定问题出在哪里。很明显javascript函数没有覆盖所有节点，但我不明白为什么。作为 Javascript 的新手，我不太了解函数内部的循环范围。可能与此有关，因为 javascript 函数不会返回以在 for 循环中尝试具有不同 i 值的节点。

您可以看到，对于相同的电路板配置，C++ 函数访问了 935 个节点 http://ideone.com/mgSE5s而 javascript 函数只访问 7 个节点 https://jsfiddle.net/xwo09La9/2/

Answer 1

从外观上看，您似乎假设 var na = a; 将创建一个新数组(副本)。然而，这只是对 a 的引用。

Arrays are passed to functions by reference, or as a pointer to the original. This means anything you do to the Array inside the function affects the original. Assigning an Array to a new variable creates a pointer to the original Array.

要创建一个新的副本来使用，你通常会做这样的事情:

var na = a.slice();

此处提供其他选项:Copying array by value in JavaScript

但是，由于您处理的是多维数组，因此您必须切片每个维度/向量:

var na = a.map(function(arr) {
   return arr.slice();
});

将此插入您的 fiddle 代码中，返回您预期的结果:

Nodes visited = 935
minimax returns 0 2

来源:https://jsfiddle.net/xwo09La9/7/

关于 JavaScript 数组的好读物:http://www.hunlock.com/blogs/Mastering_Javascript_Arrays