public class ParallelSearcher<M extends Move<M>, B extends Board<M, B>> extends AbstractSearcher<M, B> {

	public static final ForkJoinPool POOL = new ForkJoinPool();
	private static int DIVIDE_CUTOFF = 3;

	public M getBestMove(B board, int myTime, int opTime) {
		List<M> moves = board.generateMoves();
		SearchTask task = new SearchTask(this.evaluator, board, moves, this.ply, 0,
				moves.size());
		return POOL.invoke(task).move;
	}

	public class SearchTask extends RecursiveTask<BestMove<M>> {

		public Evaluator<B> evaluator;
		public B board;
		public int depth, lo, hi;
		private static final long serialVersionUID = -4025688100707858050L;
		private List<M> moves;

		public SearchTask(Evaluator<B> evaluator, B board, List<M> moves, int depth, int lo, int hi) {
		    /* if (hi == lo) {
		        throw new IllegalArgumentException("hi: " + hi + " lo: " + lo + " depth: " + depth + " moves: " + moves.size());
		    }
		    if (moves.size() == 0) {
		        throw new IllegalArgumentException("moves.size() == " + moves.size());
		    } */
			this.evaluator = evaluator;
			this.board = board;
			this.depth = depth;
			this.lo = lo;
			this.hi = hi;
			this.moves = moves;
		}

		@Override
		protected BestMove<M> compute() {
			if (depth <= cutoff || moves.isEmpty()) {
				return SimpleSearcher.minimax(evaluator, board, depth);
			} else {
				// if we're done splitting the moves on this level
				if (hi - lo <= DIVIDE_CUTOFF) {
					// B boardCopy = board.copy();

					SearchTask[] tasks = (SearchTask[]) new ParallelSearcher<?, ?>.SearchTask[hi - lo - 1];
					for (int i = lo; i < hi - 1; i++) {

	                    /* boardCopy.applyMove(moves.get(i));
                        List<M> newMoves = boardCopy.generateMoves();
                        SearchTask taskAfterMove = new SearchTask(evaluator, boardCopy, newMoves, depth - 1, 0, newMoves.size());
                        BestMove<M> ret = taskAfterMove.compute().negate();
                        boardCopy.undoMove(); */

					    B boardCopy = board.copy();
					    boardCopy.applyMove(moves.get(i));
					    List<M> newMoves = boardCopy.generateMoves();

					    SearchTask taskAfterMove = new SearchTask(evaluator, boardCopy, newMoves, depth - 1, 0, newMoves.size());
						tasks[i - lo] = taskAfterMove;
						taskAfterMove.fork();

						/* if (ret.value > best.value) {
							best.value = ret.value;
							best.move = moves.get(i);
						} */
					}
					/* return best; */

					// compute the last move
					B boardCopy = board.copy();
					boardCopy.applyMove(moves.get(hi - 1));
                    List<M> newMoves = boardCopy.generateMoves();
					SearchTask taskAfterMove = new SearchTask(evaluator, boardCopy, newMoves, depth - 1, 0, newMoves.size());
	                BestMove<M> best = taskAfterMove.compute().negate();
	                best.move = moves.get(hi - 1);

					for (int i = lo; i < hi - 1; i++) {
					    BestMove<M> ret = tasks[i - lo].join().negate();
					    if (ret.value > best.value) {
                            best.value = ret.value;
                            best.move = moves.get(i);
                        }
					}
					return best;
				}
				// divide the moves
				if (hi - 1 == lo) {
				    throw new IllegalArgumentException("hi and lo are one apart");
				}
				int mid = lo + (hi - lo) / 2;

				SearchTask left = new SearchTask(evaluator, board, moves, depth, lo, mid);
				SearchTask right = new SearchTask(evaluator, board, moves, depth, mid, hi);

				right.fork();
				BestMove<M> leftRet = left.compute();
				BestMove<M> rightRet = right.join();

				// return the best
				return rightRet.value > leftRet.value ? rightRet : leftRet;
			}
		}
	}
}