Recursion doesn't unwind as expected in javascript
I recently wrote a function that takes a board (X and O) as an argument and returns the game status ie (win, lose or draw) and the best move. The algorithm considers each board position as a node in the graph and tries to find the best move by traversing the graph. It is similar to Minimax, but it does not use the scoring function and does not capture depth, instead it tries to use all the possibilities (uses brute force). The implementation works fine in C ++, but then I tried to translate the code to javascript, but I found out that the recursion does not unwind as expected in JS.
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 feature works as expected, you can see the entire program in the ideological link posted below.
I tried to write my 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 turn and 1 if its X 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've been trying to debug it for some time now, but I'm not sure what the problem is. Clearly the javascript function doesn't cover all nodes, but I don't understand why. As a newbie to Javascript, I am not very good at seeing a loop inside a function. It might have something to do with this, since the javascript function doesn't go back to try out nodes with different i values in the for loop.
You can see for the same board configuration the C ++ function visits 935 node http://ideone.com/mgSE5s while the javascript function only visits 7 nodes https://jsfiddle.net/xwo09La9/2/
source to share
On the surface, you seem to be suggesting that you var na = a;
will create a new array (copy). This, however, will just be a link to a
.
Arrays are passed to functions by reference or as a pointer to the original. This means that whatever you do with 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 usually do something like:
var na = a.slice();
More options are available here: Copying an Array by Value in JavaScript
But , since you are dealing with a multidimensional array, you need slice
to do each size / vector:
var na = a.map(function(arr) {
return arr.slice();
});
Inserting this into your script code returns the expected output:
Nodes Visited = 935
minimax returns 0 2
Source: https://jsfiddle.net/xwo09La9/7/
Nice read on JavaScript arrays: http://www.hunlock.com/blogs/Mastering_Javascript_Arrays
source to share