Break out of a recursion in java when the time run out

Question

I'm implementing AI for a chess-like game. I intend to use recursion to try all the possible state of the board and choose out the 'best move'.

Because of the time's limit per move, i need to have some mechanism to break out of those recursive procedure whenever the time limit is reached. Of course i can keep checking the time before making a recursion call and break out if the current time is near the limit, but it is a trade-off with the performance of my program.

It would be great if there is a way to break out of those recursive procedure whenever a timer end. However, since i'm new to Java, i don't know if there are any way to do so in java? Can you give an example code? :)

I'd recommend you to look at this question: http://stackoverflow.com/questions/856124/breaking-out-of-a-recursion-in-java and this question: http://stackoverflow.com/questions/4570960/count-recursion-steps-in-java — brandizzi, May 05 '11 at 16:04
Why not pass the time as an argument to your recursive calls? Then have a base case check if time is running out and return the best solution at that point. — Cooper, May 05 '11 at 16:08
In my opinion checking the value of a variable (the time) will have a negligible affect on the overall performance. — yurib, May 05 '11 at 16:08

Peter Lawrey · Accepted Answer · 2011-05-05T16:23:17.193

3

Checking the time, e.g. System.currentTimeMillis() costs about 200 ns per call. However if this is to much for you, you can have another thread set a flag to stop.

There is a mechanism to do this already.

ExecutorService es = Executors.newSingleThreadExecutor();
Future f = es.submit(new Runnable() {
    @Override
    public void run() {
        long start = System.nanoTime();
        while(!Thread.interrupted()) {
            // busy wait.
        }
        long time = System.nanoTime() - start;
        System.out.printf("Finished task after %,d ns%n", time);
    }
});
try {
    f.get(1, TimeUnit.SECONDS); // stops if the task completes.
} catch (TimeoutException e) {
    f.cancel(true);
}
es.shutdown();

prints

Finished task after 1,000,653,574 ns

Note: you don't need to start/stop the ExecutorService every time.

edited May 05 '11 at 16:23

answered May 05 '11 at 16:10

Peter Lawrey

525,659
79
751
1,130

Ah this looks like a great way to do it... I've not used `Future`s much, looks like there is a nice mechanism for interruption. – Java Drinker May 05 '11 at 16:17
The ExecutorService can do much more such as; return a value, run/queue multiple tasks across multiple threads. If you can split your search, you may be able to use all the cores in your machine. ;) – Peter Lawrey May 05 '11 at 16:22

score 2 · Answer 2 · answered May 05 '11 at 16:15

I don't think there is any nice way of doing this that doesn't involve checking if you can continue.

Even if you did check the time... what happens if you have 8 milliseconds remaining. Can you guarantee that your recursive call will finish in that time? Do you check the time after every little step (this may add a lot of extra overhead)?

One way is to have your execution(recursion) logic running in one thread, and a timer in another thread. When the timer completes, it invokes an interrupt() on your execution thread. In your worker thread, everytime you complete a recursion, you save the state that you need. Then if it gets interrupted, return the last saved state.

That's just a brief description of one way to do it.. by no means the best way

score 0 · Answer 3 · answered May 05 '11 at 16:23

You can use a boolean flag to set when the AI task have to stop.

Create a thread that will run the AI task, this thread will check a boolean variable before each recursive call. To check boolean variable is more efficient than to call a method to get time. Do the parent thread sleep for the limited time. After it wake up, set the boolean flag to stop the child thread.

Break out of a recursion in java when the time run out

3 Answers3