Recursion not uncoiling as expected in javascript

Question

I recently wrote a function that takes a board of (X and O) as an argument and returns the game status i.e (win, loss, or draw) and the best move. The algorithm treats each board position as a node of a graph and tries to find the best move by doing a graph traversal. Its similar to Minimax but it doesn't use a score function and doesn't fix the depth, instead it tries out all possibilities(uses brute force). The implementation works fine in C++, but then I tried to translate the code in javascript but I found out that the recursion is not unwinding as expected in JS.

The findmove function in C++:-

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

This function works as expected, you can see the entire program in the ideone link posted below.

I tried writing its equivalent javascript code, but it doesn't work as expected.

Function in 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);
}

I have been trying to debug it for some time now, but I am not sure what the problem is. Its clear that the javascript function doesn't cover all the nodes, but I don't understand why. Being new to Javascript I am not well aware of for loop scoping inside a function. Maybe it has something to do with that, as javascript function doesn't return back to try out nodes with different value of i in the for loop.

You can see that for the same board configuration the C++ function visits 935 node http://ideone.com/mgSE5s while javascript function visits only 7 nodes https://jsfiddle.net/xwo09La9/2/

Answer 1

By the looks you seem to assume that var na = a; will create a new array (a copy). This will however just be a reference to 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.

To create a new copy to work with, you'd normally do something like:

var na = a.slice();

Other options are available here: Copying array by value in JavaScript

But, since you're dealing with a multi-dimensional array you'll have to slice every dimension/vector:

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

Inserting this in your fiddle code, your expected result is returned:

Nodes visited = 935
minimax returns 0 2

Source: https://jsfiddle.net/xwo09La9/7/

A good read on JavaScript arrays: http://www.hunlock.com/blogs/Mastering_Javascript_Arrays