1

我正在编写一个在游戏状态下执行 alhpa-beta 搜索的游戏引擎，并且我正在尝试并行化它。到目前为止，我一开始是在工作，然后似乎慢慢停止了。我怀疑这是因为我没有正确处理我的线程。

与计算机对战时，游戏调用 MultiThreadedComputerPlayer 对象的 getMove() 函数。这是该方法的代码：

public void getMove(){
    int n = board.legalMoves.size();
    threadList = new ArrayList<WeightedMultiThread>();
    moveEvals = new HashMap<Tuple, Integer>();

    // Whenever a thread finishes its work at a given depth, it awaits() the other threads
    // When all threads are finished, the move evaluations are updated and the threads continue their work.
    CyclicBarrier barrier = new CyclicBarrier(n, new Runnable(){
        public void run() {
            for(WeightedMultiThread t : threadList){
                moveEvals.put(t.move, t.eval);
            }
        }
    });

    // Prepare and start the threads
    for (Tuple move : board.legalMoves) {
        MCBoard nextBoard = board.clone();
        nextBoard.move(move);
        threadList.add(new WeightedMultiThread(nextBoard, weights, barrier));
        moveEvals.put(move, 0);
    }
    for (WeightedMultiThread t : threadList) {t.start();}

    // Let the threads run for the maximum amount of time per move
    try {
        Thread.sleep(timePerMove);
    } catch (InterruptedException e) {System.out.println(e);}
    for (WeightedMultiThread t : threadList) {
        t.stop();
    }

    // Play the best move
    Integer best = infHolder.MIN;
    Tuple nextMove = board.legalMoves.get(0);
    for (Tuple m : board.legalMoves) {
        if (moveEvals.get(m) > best) {
            best = moveEvals.get(m);
            nextMove = m;
        }
    }
    System.out.println(nextMove + " is the choice of " + name + " given evals:");
    for (WeightedMultiThread t : threadList) {
        System.out.println(t);
    }
    board.move(nextMove);
}

这里有问题线程的 run() 方法：

public void run() {
    startTime = System.currentTimeMillis();
    while(true) {
        int nextEval = alphabeta(0, infHolder.MIN, infHolder.MAX);
        try{barrier.await();} catch (Exception e) {}
        eval = nextEval;
        depth += 1;
    }
}

我需要能够在时间到时中断所有线程——我应该如何实现这个？截至目前，我一直在捕捉（并忽略）InterruptedExceptions。

4

3 回答 3

7

Thread.stop 被弃用是有原因的。当您在中间中断一个线程时，该线程没有机会正确释放它正在使用的资源，并且不会通知其他线程它的完成......这在多线程应用程序中非常重要。我对你的性能坦克并不感到惊讶；我愿意打赌你的内存使用量会飙升。您也不会回收线程，您可以在不创建新对象的情况下启动和停止它们，这意味着变量留在的任何损坏状态可能仍在困扰它们。

更好的方法是设置一个标志，告诉线程它应该返回。因此，在您的 WeightedMultiThread 类中包含一个名为 shouldQuit 的布尔值，并在每次调用 start() 时将其设置为 false。然后，使用 t.shouldQuit = true 代替 while (true) 执行 while (!shouldQuit)，而不是 t.stop()。在对每个线程执行此操作后，再创建一个循环来检查每个线程的 t.isAlive()，一旦每个线程都返回，就可以开始您的业务了。这样你应该会有更好的结果。

于 2012-11-27T07:02:45.957 回答
4

这看起来是使用ExecutorService. 您可以创建Callable实现并行任务的实例，将它们提交给ExecutorService，然后用于awaitTermination强制超时。

例如：

public void getMove() {
    ExecutorService service = Executors.newFixedThreadPool(board.legalMoves.size());
    List<Future<Something>> futures = new ArrayList<Future<Something>>(board.legalMoves.size());
    for (Tuple move : board.legalMoves) {
        futures.add(service.submit(new WeightedMultiThread(...)));
    }
    service.awaitTermination(timePerMove, TimeUnit.MILLISECONDS);
    service.shutdownNow(); // Terminate all still-running jobs
    for (Future<Something> future : futures) {
        if (future.isDone()) {
            Something something = future.get();
            // Add best move logic here
        }
    }
    ...
}

替换Something为封装有关已评估移动的信息的内容。我建议Something成为一个拥有Tuple及其相关分数的类。你的WeightedMultiThread班级可以做这样的事情：

class WeightedMultiThread implements Callable<Something> {
    public Something call() {
        // Compute score
        ...
        // Return an appropriate data structure
        return new Something(tuple, score);
    }
}

更好的是创建ExecutorService一次并在每次调用时重新使用它getMove。创建线程很昂贵，所以如果可以的话，最好只做一次。如果您采用这种方法，那么您不应该调用shutdownNow，而是使用该Future.cancel方法来终止未及时完成的​​作业。确保您的WeightedMultiThread实现检查线程中断并抛出InterruptedException. 这通常是编写需要可中断的长时间运行任务的好方法。

编辑：

由于您正在对游戏空间进行逐级探索，因此我建议您将其编码在getMove函数中而不是Tuple评估代码中，例如

public Tuple getMove() {
    ExecutorService service = ...
    Tuple best = null;
    long timeRemaining = MAX_TIME;
    for (int depth = 0; depth < MAX_DEPTH && timeRemaining > 0; ++depth) {
        long start = System.currentTimeMillis();
        best = evaluateMoves(depth, service, timeRemaining);
        long end = System.currentTimeMillis();
        timeRemaining -= (end - start);
    }
    return best;
}

private Tuple evaluateMoves(int depth, ExecutorService service, long timeRemaining) {
    List<Future<Whatever>> futures = service.submit(...); // Create all jobs at this depth
    service.awaitTermination(timeRemaining, TimeUnit.MILLISECONDS);
    // Find best move
    ...
    return best;
}

那可能更干净，但你明白了。

于 2012-11-27T07:19:09.020 回答
0

最敏感的方式是使用中断机制。Thread.interrupt()和Thread.isInterrupted()方法。这确保您的消息将被传递到线程，即使它位于阻塞调用中（还记得某些方法声明 throwingInterruptedException吗？）

PS 阅读 Brian Goetz 的“Java 并发实践”第 7 章：取消和关闭会很有用。

于 2012-11-27T13:32:04.027 回答