| 66 | } |
| 67 | |
| 68 | public OutCome alphaBeta(final Board board, final int depth, double alpha, double beta, final int printAt) { |
| 69 | final List<Move> legalMoves = board.getLegalMoves(); |
| 70 | nodesEvaluated++; |
| 71 | if (legalMoves.isEmpty() || depth == 0) { |
| 72 | final double score; |
| 73 | if (transpositionTable.containsKey(board.zobristHash)) { |
| 74 | score = transpositionTable.get(board.zobristHash).eval; |
| 75 | } else { |
| 76 | score = board.evaluation(legalMoves.size()); |
| 77 | transpositionTable.put(board.zobristHash, new Result(score, 0)); |
| 78 | } |
| 79 | return new OutCome(board, null, -score); |
| 80 | } |
| 81 | final List<OutCome> outComes = legalMoves.stream().map(move -> { |
| 82 | final Board changedBoard = board.copy(); |
| 83 | changedBoard.makeMove(move); |
| 84 | final double score; |
| 85 | if (transpositionTable.containsKey(changedBoard.zobristHash)) { |
| 86 | score = transpositionTable.get(changedBoard.zobristHash).eval; |
| 87 | } else { |
| 88 | score = changedBoard.evaluation(changedBoard.getLegalMoves().size()); |
| 89 | transpositionTable.put(changedBoard.zobristHash, new Result(score, 0)); |
| 90 | } |
| 91 | return new OutCome(changedBoard, move, score); |
| 92 | }).sorted(Comparator.comparingDouble(OutCome::getScore)).collect(Collectors.toList()); |
| 93 | OutCome bestOutCome = null; |
| 94 | for (final OutCome outCome : outComes) { |
| 95 | final OutCome eval = alphaBeta(outCome.getBoard(), depth - 1, alpha, beta, printAt); |
| 96 | if (depth == printAt) { |
| 97 | System.out.println(getString(outCome.getMove()) + ": " + eval.getScore() + " " + outCome + |
| 98 | " " + outCome.getBoard().fenRepresentation()); |
| 99 | } |
| 100 | if (bestOutCome == null || bestOutCome.getScore() > -eval.getScore()) { |
| 101 | bestOutCome = new OutCome(board, outCome.getMove(), -eval.getScore()); |
| 102 | if (bestOutCome.getScore() < 0 && bestOutCome.getScore() + Integer.MAX_VALUE < 0.0001) { |
| 103 | return bestOutCome; |
| 104 | } |
| 105 | } |
| 106 | if (board.playerToMove.equals(Color.WHITE)) { |
| 107 | if (alpha < -bestOutCome.getScore()) { |
| 108 | alpha = -bestOutCome.getScore(); |
| 109 | } |
| 110 | } else { |
| 111 | if (beta > bestOutCome.getScore()) { |
| 112 | beta = bestOutCome.getScore(); |
| 113 | } |
| 114 | } |
| 115 | if (alpha >= beta) { |
| 116 | break; |
| 117 | } |
| 118 | } |
| 119 | if (!transpositionTable.containsKey(board.zobristHash) || transpositionTable.get(board.zobristHash).depth < depth) { |
| 120 | transpositionTable.put(board.zobristHash, new Result(-bestOutCome.getScore(), depth)); |
| 121 | } |
| 122 | return bestOutCome; |
| 123 | } |
| 124 | |
| 125 | public OutCome iterativeDeepening(final Board board, final long time) { |