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

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 perfo开发者_高级运维rmance 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? :)

---

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.

---

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

---

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.