<commit_before>package de.tilosp.chess.lib;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class ChessEngine {

    private static Random random = new Random();

    public static Chessboard compute(Chessboard chessboard) {
        long time = System.currentTimeMillis();

        List<CThread> threads = new ArrayList<>();
        for (List<Chessboard> partPossibleMoves : splitList(getPossibleMoves(chessboard), Runtime.getRuntime().availableProcessors())) {
            CThread thread = new CThread(chessboard.endGame, partPossibleMoves);
            threads.add(thread);
            thread.start();
        }

        int bestValue = Integer.MIN_VALUE;
        ArrayList<Chessboard> bestMoves = new ArrayList<>();
        for (CThread thread : threads) {
            CThread.Result result = thread.getResult();
            if (result.bestValue > bestValue) {
                bestValue = result.bestValue;
                bestMoves = result.bestMoves;
            } else if (result.bestValue == bestValue) {
                bestMoves.addAll(result.bestMoves);
            }
        }

        System.out.println("compute took " + (System.currentTimeMillis() - time)+ " ms, " + bestMoves.size() + " move(s) with score " + bestValue);
        return bestMoves.get(random.nextInt(bestMoves.size()));
    }

    private static <T> ArrayList<List<T>> splitList(ArrayList<T> list, int parts) {
        parts = Math.min(parts, list.size());
        ArrayList<List<T>> lists = new ArrayList<>(parts);

        int partSize = list.size() / parts;

        for (int i = 0; i < parts; i++)
            lists.add(list.subList(i * partSize, i + 1 == parts ? list.size() : (i + 1) * partSize));

        return lists;
    }

    private static ArrayList<Chessboard> getPossibleMoves(Chessboard chessboard){
        ArrayList<Chessboard> possibleMoves = new ArrayList<>();

        for (int i1 = 0; i1 < 8; i1++) {
            for (int i2 = 0; i2 < 8; i2++) {
                ChessPiece chessPiece = chessboard.getChessPiece(i1, i2);
                if (chessPiece != null && chessPiece.playerColor == chessboard.playerColor) {
                    for (int[] m : chessboard.getPossibleMoves(i1, i2)) {
                        Chessboard move = chessboard.move(new int[] { i1, i2 }, m);
                        if (move.promotion)
                            for (ChessPieceType type : ChessPieceType.POSITIONS_PROMOTION)
                                possibleMoves.add(move.promotion(type));
                        else
                            possibleMoves.add(move);
                    }
                }
            }
        }

        return possibleMoves;
    }

    // negamax algorithm with alpha beta pruning https://en.wikipedia.org/wiki/Negamax
    private static int negamax(Chessboard chessboard, int depth, int alpha, int beta) {
        if (chessboard.isDraw())
            return chessboard.playerColor.sign * computeValue(chessboard) / 2;
        if (chessboard.isWin(PlayerColor.WHITE))
            return chessboard.playerColor.sign * 10000;
        if (chessboard.isWin(PlayerColor.BLACK))
            return chessboard.playerColor.sign * -10000;
        if (depth == 0)
            return chessboard.playerColor.sign * computeValue(chessboard);

        int bestValue = Integer.MIN_VALUE;

        for (Chessboard c : getPossibleMoves(chessboard)) {
            int value = -negamax(c, depth - 1, -beta, -alpha);
            bestValue = Math.max(bestValue, value);

            alpha = Math.max(alpha, value);
            if (alpha >= beta)
                break;
        }

        return bestValue;
    }


    // https://chessprogramming.wikispaces.com/Simplified+evaluation+function
    public static int computeValue(Chessboard chessboard) {
        int value = 0;
        for (int i1 = 0; i1 < 8; i1++) {
            for (int i2 = 0; i2 < 8; i2++) {
                ChessPiece chessPiece = chessboard.getChessPiece(i1, i2);
                if (chessPiece != null) {
                    value += (chessPiece.chessPieceType.value
                            + chessPiece.chessPieceType.getSquareValues(chessboard.endGame)[i1][chessPiece.playerColor == PlayerColor.WHITE ? i2 : 7 - i2])
                            * chessPiece.playerColor.sign;
                }
            }
        }

        return value;
    }

    private static int[][] computeThreatenedMatrix(Chessboard chessboard) {
        int[][] threatenedMatrix = new int[8][8];
        for (int i1 = 0; i1 < 8; i1++) {
            for (int i2 = 0; i2 < 8; i2++) {
                ChessPiece chessPiece = chessboard.getChessPiece(i1, i2);
                if (chessPiece != null) {
                    for (int[] a : chessboard.getThreatenedFields(i1, i2)) {
                        if (chessPiece.playerColor == chessboard.playerColor)
                            threatenedMatrix[a[0]][a[1]] += chessPiece.chessPieceType.value;
                        else
                            threatenedMatrix[a[0]][a[1]] -= chessPiece.chessPieceType.value;
                    }
                }
            }
        }
        return threatenedMatrix;
    }

    private static final class CThread extends Thread {

        private final boolean endGame;
        private final List<Chessboard> moves;
        private ArrayList<Chessboard> bestMoves = new ArrayList<>();
        private int bestValue = Integer.MIN_VALUE;

        private CThread(boolean endGame, List<Chessboard> moves) {
            this.endGame = endGame;
            this.moves = moves;
        }

        private Result getResult() {
            try {
                join();
            } catch (InterruptedException ignored) {}
            return new Result(bestValue, bestMoves);
        }

        @Override
        public void run() {
            for (Chessboard c : moves) {
                int value = -negamax(c, endGame ? 6 : 3, Integer.MIN_VALUE + 1, Integer.MAX_VALUE);
                if (value > bestValue) {
                    bestValue = value;
                    bestMoves = new ArrayList<>();
                    bestMoves.add(c);<commit_msg>Optimized chess engine<commit_after>package de.tilosp.chess.lib;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class ChessEngine {

    private static Random random = new Random();

    public static Chessboard compute(Chessboard chessboard) {
        long time = System.currentTimeMillis();

        List<CThread> threads = new ArrayList<>();
        for (List<Chessboard> partPossibleMoves : splitList(getPossibleMoves(chessboard), Runtime.getRuntime().availableProcessors())) {
            CThread thread = new CThread(chessboard.endGame, partPossibleMoves);
            threads.add(thread);
            thread.start();
        }

        int bestValue = Integer.MIN_VALUE;
        ArrayList<Chessboard> bestMoves = new ArrayList<>();
        for (CThread thread : threads) {
            CThread.Result result = thread.getResult();
            if (result.bestValue > bestValue) {
                bestValue = result.bestValue;
                bestMoves = result.bestMoves;
            } else if (result.bestValue == bestValue) {
                bestMoves.addAll(result.bestMoves);
            }
        }

        System.out.println("compute took " + (System.currentTimeMillis() - time)+ " ms, " + bestMoves.size() + " move(s) with score " + bestValue);
        return bestMoves.get(random.nextInt(bestMoves.size()));
    }

    private static <T> ArrayList<List<T>> splitList(ArrayList<T> list, int parts) {
        parts = Math.min(parts, list.size());
        ArrayList<List<T>> lists = new ArrayList<>(parts);

        int partSize = list.size() / parts;

        for (int i = 0; i < parts; i++)
            lists.add(list.subList(i * partSize, i + 1 == parts ? list.size() : (i + 1) * partSize));

        return lists;
    }

    private static ArrayList<Chessboard> getPossibleMoves(Chessboard chessboard){
        ArrayList<Chessboard> possibleMoves = new ArrayList<>();

        for (int i1 = 0; i1 < 8; i1++) {
            for (int i2 = 0; i2 < 8; i2++) {
                ChessPiece chessPiece = chessboard.getChessPiece(i1, i2);
                if (chessPiece != null && chessPiece.playerColor == chessboard.playerColor) {
                    for (int[] m : chessboard.getPossibleMoves(i1, i2)) {
                        Chessboard move = chessboard.move(new int[] { i1, i2 }, m);
                        if (move.promotion)
                            for (ChessPieceType type : ChessPieceType.POSITIONS_PROMOTION)
                                possibleMoves.add(move.promotion(type));
                        else
                            possibleMoves.add(move);
                    }
                }
            }
        }

        return possibleMoves;
    }

    // negamax algorithm with alpha beta pruning https://en.wikipedia.org/wiki/Negamax
    private static int negamax(Chessboard chessboard, int depth, int alpha, int beta) {
        if (chessboard.isDraw())
            return chessboard.playerColor.sign * computeValue(chessboard) / 2;
        if (chessboard.isWin(PlayerColor.WHITE))
            return chessboard.playerColor.sign * (computeValue(chessboard) + 1000);
        if (chessboard.isWin(PlayerColor.BLACK))
            return chessboard.playerColor.sign * (computeValue(chessboard) - 1000);
        if (depth == 0)
            return chessboard.playerColor.sign * computeValue(chessboard);

        int bestValue = Integer.MIN_VALUE;

        for (Chessboard c : getPossibleMoves(chessboard)) {
            int value = -negamax(c, depth - 1, -beta, -alpha);
            bestValue = Math.max(bestValue, value);

            alpha = Math.max(alpha, value);
            if (alpha >= beta)
                break;
        }

        return bestValue;
    }


    // https://chessprogramming.wikispaces.com/Simplified+evaluation+function
    public static int computeValue(Chessboard chessboard) {
        int value = 0;
        for (int i1 = 0; i1 < 8; i1++) {
            for (int i2 = 0; i2 < 8; i2++) {
                ChessPiece chessPiece = chessboard.getChessPiece(i1, i2);
                if (chessPiece != null) {
                    value += (chessPiece.chessPieceType.value
                            + chessPiece.chessPieceType.getSquareValues(chessboard.endGame)[i1][chessPiece.playerColor == PlayerColor.WHITE ? i2 : 7 - i2])
                            * chessPiece.playerColor.sign;
                }
            }
        }

        return value;
    }

    private static int[][] computeThreatenedMatrix(Chessboard chessboard) {
        int[][] threatenedMatrix = new int[8][8];
        for (int i1 = 0; i1 < 8; i1++) {
            for (int i2 = 0; i2 < 8; i2++) {
                ChessPiece chessPiece = chessboard.getChessPiece(i1, i2);
                if (chessPiece != null) {
                    for (int[] a : chessboard.getThreatenedFields(i1, i2)) {
                        if (chessPiece.playerColor == chessboard.playerColor)
                            threatenedMatrix[a[0]][a[1]] += chessPiece.chessPieceType.value;
                        else
                            threatenedMatrix[a[0]][a[1]] -= chessPiece.chessPieceType.value;
                    }
                }
            }
        }
        return threatenedMatrix;
    }

    private static final class CThread extends Thread {

        private final boolean endGame;
        private final List<Chessboard> moves;
        private ArrayList<Chessboard> bestMoves = new ArrayList<>();
        private int bestValue = Integer.MIN_VALUE;

        private CThread(boolean endGame, List<Chessboard> moves) {
            this.endGame = endGame;
            this.moves = moves;
        }

        private Result getResult() {
            try {
                join();
            } catch (InterruptedException ignored) {}
            return new Result(bestValue, bestMoves);
        }

        @Override
        public void run() {
            for (Chessboard c : moves) {
                int value = -negamax(c, endGame ? 3 : 2, Integer.MIN_VALUE + 1, Integer.MAX_VALUE);
                if (value > bestValue) {
                    bestValue = value;
                    bestMoves = new ArrayList<>();
                    bestMoves.add(c);
{'fraction_non_alphanumeric': 0.10842496765847348, 'fraction_numerical': 0.01148124191461837, 'mean_word_length': 1.8246174925782142, 'pattern_counts': {'":': 0, '<': 57, '<?xml version=': 0, '>': 49, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4817664', 'n_tokens_mistral': 3698, 'n_tokens_neox': 3467, 'n_words': 789}