Event driven search

[Maurits Meijer]

Hello,

I'm currently working on a JavaScript based engine but I am having trouble figuring out how to do the search. Since JavaScript is run in a single thread (without interupts available) I would like to do the search in chuncks of about 50 to 100 ms. That way the browser would still be able to respond to user input. The speed of the algorithm isn't that important, but just unraffeling the recursive calls of Negamax creates too much overhead. Has anybody done something like this before or know how to do this?

[MichelG]

Hello,

I'm currently working on a JavaScript based engine but I am having trouble figuring out how to do the search. Since JavaScript is run in a single thread (without interupts available) I would like to do the search in chuncks of about 50 to 100 ms. That way the browser would still be able to respond to user input. The speed of the algorithm isn't that important, but just unraffeling the recursive calls of Negamax creates too much overhead. Has anybody done something like this before or know how to do this?

You can do this by using a non-recursive implementation of alpha-beta. It's a bit more complicated to write, but than you can call it maybe 10000 times, and release the process for user input. It actually might be a tiny bit faster as well.

[Ed Gilbert]

I'm currently working on a JavaScript based engine but I am having trouble figuring out how to do the search. Since JavaScript is run in a single thread (without interupts available) I would like to do the search in chuncks of about 50 to 100 ms. That way the browser would still be able to respond to user input. The speed of the algorithm isn't that important, but just unraffeling the recursive calls of Negamax creates too much overhead. Has anybody done something like this before or know how to do this?

One way to do this is using a test of the search node counter. Every N nodes (entries to negamax), call your function that handles user input. Pick N so that it is often enough for the UI to be responsive, but not so often as to slow down your search. If N is one less than a power of 2, you can simply AND your node counter with it and test for 0.

-- Ed

[Maurits Meijer]

One way to do this is using a test of the search node counter. Every N nodes (entries to negamax), call your function that handles user input. Pick N so that it is often enough for the UI to be responsive, but not so often as to slow down your search. If N is one less than a power of 2, you can simply AND your node counter with it and test for 0.

-- Ed

Thanks for the replys.
The browser itself needs to handle the events that are queued. When a function is executing the browser can't do that and will throw 'this page is not responding' popups at you. So I would need to be able to leave the search and have a timed-event call a function that would continue the search.

I'm gonna try the non-recursive way Michel suggested.

I also found that modern browser have webworkers that would really help out this case, but they are not supported by internet explorer:(

[Maurits Meijer]

Got the non-recursive version negamax working
It doesn't look as bad as I thought it might.