Вырваться из рекурсии в Java, когда время истекло - PullRequest
Новая
       18

Вырваться из рекурсии в Java, когда время истекло

1 голос
/ 05 мая 2011

Я реализую ИИ для шахматоподобной игры. Я намерен использовать рекурсию, чтобы попробовать все возможные состояния доски и выбрать «лучший ход».

Из-за ограничения по времени на ход мне нужно иметь какой-то механизм, чтобы выходить из этой рекурсивной процедуры всякий раз, когда достигается ограничение по времени. Конечно, я могу продолжать проверять время, прежде чем делать рекурсивный вызов, и отключиться, если текущее время близко к пределу, но это компромисс с производительностью моей программы.

Было бы замечательно, если бы был выход из этой рекурсивной процедуры всякий раз, когда заканчивался таймер. Однако, поскольку я новичок в Java, я не знаю, есть ли способ сделать это в Java? Можете ли вы привести пример кода? :)

Ответы [ 3 ]

3 голосов
/ 05 мая 2011

Проверка времени, например System.currentTimeMillis () стоит около 200 нс за вызов. Однако, если это слишком много для вас, вы можете попросить другой поток установить флаг для остановки.

Уже есть механизм для этого. 

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();

печать 

Finished task after 1,000,653,574 ns

Примечание: вам не нужно каждый раз запускать / останавливать ExecutorService.

2 голосов
/ 05 мая 2011

Я не думаю, что есть какой-то хороший способ сделать это, не включающий проверку, можете ли вы продолжить.

Даже если вы проверили время ... что произойдет, если у вас есть 8 milliseconds остальной.Можете ли вы гарантировать, что ваш рекурсивный вызов закончится в это время?Проверяете ли вы время после каждого маленького шага (это может добавить много дополнительных затрат)?

Один из способов - это запустить логику выполнения (рекурсии) в одном потоке и таймер в другом потоке.Когда таймер завершает работу, он вызывает interrupt() в вашем потоке выполнения.В рабочем потоке каждый раз, когда вы завершаете рекурсию, вы сохраняете нужное вам состояние.Затем, если оно прервано, верните последнее сохраненное состояние.

Это просто краткое описание одного из способов сделать это .. ни в коем случае не лучший способ

0 голосов
/ 05 мая 2011

Вы можете использовать логический флаг, чтобы установить, когда задача AI должна остановиться.

Создайте поток, который будет запускать задачу AI, этот поток будет проверять логическую переменную перед каждым рекурсивным вызовом.Проверка логической переменной более эффективна, чем вызов метода для получения времени.Родительский поток спит в течение ограниченного времени.После того, как он проснется, установите логический флаг, чтобы остановить дочерний поток.

...