I have a first version of using a recursive function with Javascript which produces expected results. Below a working version :
// Call the recursive function and get final (a,b) results
var HitTemp = JSON.parse(JSON.stringify(HitCurrent));
var result= recursiveFunction(HitTemp, HitTemp.playerCurrent, maxNodes);
var a = HitTemp.coordPlayable[0];
var b = HitTemp.coordPlayable[1];
// Recursive function
function recursiveFunction(HitCurrent, colorCurrent, depth) {
// Indices
var i, j, k;
// Evaluation
var arrayTemp, eval, e;
// Set current color to HitCurrent
HitCurrent.playerCurrent = colorCurrent;
// Deep copy of arrayCurrent array
arrayTemp = JSON.parse(JSON.stringify(HitCurrent.arrayCurrent));
// If depth equal to 0
if (depth == 0)
return evaluation(HitCurrent);
// Starting evaluation
eval = -infinity;
// Browse all possible hits
for (i = 0; i < 8; i++)
for (j = 0; j < 8; j++) {
if (HitCurrent.arrayPlayable[i][j] == 'playable') {
for (k = 0; k < 8; k++) {
// Explore line started from (i,j) with direction "k"
exploreHitLine(HitCurrent, i, j, k, 'drawing');
}
// Recursive call
e = recursiveFunction(JSON.parse(JSON.stringify(HitCurrent)), ((JSON.stringify(HitCurrent.playerCurrent) == JSON.stringify(playerBlack)) ? playerWhite : playerBlack), depth-1);
if (e > eval) {
HitCurrent.coordPlayable = [i,j];
eval = e;
}
}
// Restore arrayCurrent array
HitCurrent.arrayCurrent = JSON.parse(JSON.stringify(arrayTemp));
}
return eval;
}
From this, I would like to use "inline" WebWorkers to dedicate the recursion to WebWorker and avoid hanging process in browsers.
I tried to follow this link and this other link
I don't know if I have to "postmessage" the object HitCurrent or the value eval to the main thread : by using WebWorker, I make confusions between the return instruction (which returns a value in the terminal case) and the objet HitCurrent argument passed for next recursive call.
If someone could give some clues to reproduce this original algorithm by using inline webworker (or with classical way of using webworker).
Inline webworker example:
As your code, there is no function evaluation, function exploreHitLine.
Before use following code, you must insert them into code.
{
let workerScript = URL.createObjectURL( new Blob( [ `
"use strict";
// Recursive function
function recursiveFunction( HitCurrent, colorCurrent, depth ) {
// Indices
var i, j, k;
// Evaluation
var arrayTemp, eval, e;
// Set current color to HitCurrent
HitCurrent.playerCurrent = colorCurrent;
// Deep copy of arrayCurrent array
arrayTemp = JSON.parse(JSON.stringify(HitCurrent.arrayCurrent));
// If depth equal to 0
if ( depth === 0 ) return evaluation(HitCurrent);
// Starting evaluation
eval = -infinity;
// Browse all possible hits
for (i = 0; i < 8; i++) {
for (j = 0; j < 8; j++) {
if (HitCurrent.arrayPlayable[i][j] === 'playable') {
for (k = 0; k < 8; k++) {
// Explore line started from (i,j) with direction "k"
exploreHitLine(HitCurrent, i, j, k, 'drawing');
}
// Recursive call
e = recursiveFunction(JSON.parse(JSON.stringify(HitCurrent)), ((JSON.stringify(HitCurrent.playerCurrent) == JSON.stringify(playerBlack)) ? playerWhite : playerBlack), depth-1);
if (e > eval) {
HitCurrent.coordPlayable = [i,j];
eval = e;
}
}
// Restore arrayCurrent array
HitCurrent.arrayCurrent = JSON.parse(JSON.stringify(arrayTemp));
}
}
return eval;
}
onmessage = function ( event ) {
let params = event.data;
postMessage( { result: recursiveFunction( ...params ) } );
}
` ], { type: "plain/text" } ) );
// Call the recursive function and get final (a,b) results
new Promise( resolve => {
let HitTemp = JSON.parse(JSON.stringify(HitCurrent));
let firstWorker = new Worker( workerScript );
firstWorker.onmessage = function ( event ) {
resolve( event.data ); //{ result: XXX }
}
firstWorker.postMessage( HitTemp, HitTemp.playerCurrent, maxNodes );
} ).then( ( { result } ) => {
let [ a, b ] = result.coordPlayable;
console.log( result );
} );
}
Additionally following is working inline WebWorker:
{
let workerScript = URL.createObjectURL( new Blob( [ `
"use strict";
onmessage = function ( event ) {
let sum = 0, count = event.data;
for ( let i = 0; i < count**count; i++ ) {
sum += i;
}
postMessage( { result: sum, count } );
}
` ], { type: "plain/text" } ) );
let firstWorker = new Worker( workerScript );
let firstAlive = setTimeout( () => {
firstWorker.terminate();
console.log( "terminated" );
}, 3000 );
firstWorker.onmessage = function ( event ) {
clearTimeout( firstAlive );
console.log( event.data );
}
firstWorker.postMessage( 10 );
let secondWorker = new Worker( workerScript );
let secondAlive = setTimeout( () => {
secondWorker.terminate();
console.log( "terminated" );
}, 3000 );
secondWorker.onmessage = function ( event ) {
clearTimeout( secondAlive );
console.log( event.data );
}
secondWorker.postMessage( 5 );
}
Update 1.
{
// Inline webworker version
let workerScript = URL.createObjectURL( new Blob( [ `
"use strict";
// Recursive function
function recursiveFunction( HitCurrent, colorCurrent, depth ) {
// Indices
var i, j, k;
// Evaluation
var arrayTemp, evaluated, e;
// Set current color to HitCurrent
HitCurrent.playerCurrent = colorCurrent;
// Deep copy of arrayCurrent array
arrayTemp = JSON.parse(JSON.stringify(HitCurrent.arrayCurrent));
// If depth equal to 0
if (depth == 0)
return evaluation(HitCurrent);
// Starting evaluation
evaluated = -infinity;
// Browse all possible hits
for (i = 0; i < 8; i++) {
for (j = 0; j < 8; j++) {
if (HitCurrent.arrayPlayable[i][j] == 'playable') {
for (k = 0; k < 8; k++) {
// Explore line started from (i,j) with direction "k"
exploreHitLine(HitCurrent, i, j, k, 'drawing');
}
// Recursive call
e = recursiveFunction(JSON.parse(JSON.stringify(HitCurrent)), ((JSON.stringify(HitCurrent.playerCurrent) == JSON.stringify(playerBlack)) ? playerWhite : playerBlack), depth-1);
if ( e > evaluated ) {
HitCurrent.coordPlayable = [i,j];
evaluated = e;
}
if (e == -infinity) { HitCurrent.coordPlayable = [ i, j ]; }
// Restore arrayCurrent array
HitCurrent.arrayCurrent = JSON.parse(JSON.stringify(arrayTemp));
}
}
}
return evaluated;
}
onmessage = function ( event ) {
let params = event.data;
//postMessage( { result: recursiveFunction( HitCurrent, HitCurrent.playerCurrent, maxNodes ) } );
postMessage( { result: recursiveFunction( ...params ) } );
};
` ], { type: "plain/text" } ) );
// Call the recursive function and get final (a,b) results
new Promise( resolve => {
let HitTemp = JSON.parse(JSON.stringify(HitCurrent));
let firstWorker = new Worker( workerScript );
firstWorker.onmessage = function ( event ) {
resolve( event.data ); //{ result: XXX }
}
firstWorker.postMessage( [ HitTemp, HitTemp.playerCurrent, maxNodes ] );
} ).then( ( { result } ) => {
let [ a, b ] = result.coordPlayable;
console.log( result );
} );
}
Explanation of my faults:
- It is impossible to use "eval" as the name of a variable when in "strict mode".
=>
from: eval
to: evaluated
Worker.postMessage( aMessage, Transferrable ), in this case, you don't need to use the second parameter.
=>
from: firstWorker.postMessage( HitTemp, HitTemp.playerCurrent, maxNodes );
to: firstWorker.postMessage( [ HitTemp, HitTemp.playerCurrent, maxNodes ] );
(https://developer.mozilla.org/en-US/docs/Web/API/Worker/postMessage)
- Continue to 2, passing parameter to recursiveFunction is fixed.
eval is a keyword; use some other variable name. postMessage only
accepts one argument (it also accepts a transferable, but that is not applicable to your case), and if that argument is not a primitive value, it should
be an object that can be serializable (e.g. you cannot pass functions
or methods directly to the web worker)
I might be misunderstanding what you are trying to do, but you might want to reconsider recursively spawning an unkown number of webworkers! Just spawn one webworker and pass the parameters of your function to it and do your recursive calculations inside that webworker synchronously without spawning a new worker, if you just want to free up your main stack. Spawning too many web workers will consume a lot of a resources and will actually slow down your calculations! FYI, spawning each new web worker takes ~40ms and takes up resources. This is a general observation with regard to utilizing multithreading for calculating recursive functions! This might help:
https://softwareengineering.stackexchange.com/questions/238729/can-recursion-be-done-in-parallel-would-that-make-sense
Concerning all functions called into URL.createObjectURL( new Blob( ... )) block, Have I got to include them in this block or can I write them outside of it (as you say for evaluation and explotHitLine functions) ?
Your webworker is a completely separate JS file and execution context; you will not have access to anything that is not defined within its context or send to it as a message.
Btw, there are a few errors in your code which will prevent it from compiling correctly anyways: infinity should be Infinity, playerBlack and playerWhite are undefined, etc.
