Package org.swtpra1.alphabetaplayer.alphabeta

Class AlphaBetaSearchTree

  • Direct Known Subclasses:
    AlphaBetaSearchTreeWithTranspositionTables
    public class AlphaBetaSearchTree
extends java.lang.Object
    Implements the Negamax search algorithm with alpha beta pruning optimization based on a given Evaluation function.

    • Constructor Summary

      Constructors 
      Constructor Description
      AlphaBetaSearchTree​(Evaluator evaluator, int parallelism)
      Creates a search tree instance with a given evaluation function.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.List<Turn> chooseMostPromisingTurns​(Board board, java.util.List<Turn> turns, int player, Evaluator eval, int limit)
      Given a board and a list of candidate turns, we evaluate each one statically, sort them accordingly and take as many of the best turns as possible up to a limit.
      ValuedTurn negamax​(Board board, int player, int depth, boolean presort)
      Wrapper function to start negamax search with alpha-beta pruning optimization.
      protected ValuedTurn negamax​(Board board, int player, int depth, boolean presort, float alpha, float beta)
      Recursive implementation of negamax algorithm with alpha beta pruning optimization.
      protected ValuedTurn negamax​(Board board, int player, int depth, boolean presort, float alpha, float beta, java.util.List<Turn> blacklist)
      Recursive implementation of negamax algorithm with alpha beta pruning optimization.
      ValuedTurn negamax​(Board board, int player, int depth, boolean presort, java.util.List<Turn> blacklist)
      Wrapper function to start negamax search with alpha-beta pruning optimization with a list of undesirable moves.
      protected ValuedTurn parallelNegamax​(Board board, int player, int depth, boolean presort, java.util.List<Turn> blacklist)
      Multithreaded recursive implementation of negamax algorithm with alpha beta pruning optimization.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • evaluator

        protected final Evaluator evaluator

      • executor

        protected final java.util.concurrent.ExecutorService executor

    • Constructor Detail

      • AlphaBetaSearchTree

        public AlphaBetaSearchTree​(Evaluator evaluator,
                           int parallelism)
        Creates a search tree instance with a given evaluation function.
        Parameters:
        evaluator - the evaluator to use to evaluate board positions
        parallelism - see AlphaBetaPlayer.parallelism

    • Method Detail

      • negamax

        public ValuedTurn negamax​(Board board,
                          int player,
                          int depth,
                          boolean presort)
        Wrapper function to start negamax search with alpha-beta pruning optimization.
        Parameters:
        board - the current state of the board
        player - the id (0 or 1) of the player on this layer
        depth - the maximum depth to be considered
        presort - whether to presort the moves and cut off
        Returns:
        the pairing of the best possible move and its evaluation

      • parallelNegamax

        protected ValuedTurn parallelNegamax​(Board board,
                                     int player,
                                     int depth,
                                     boolean presort,
                                     java.util.List<Turn> blacklist)
        Multithreaded recursive implementation of negamax algorithm with alpha beta pruning optimization. Uses the number of threads given.
        Parameters:
        board - the current state of the board
        player - the id (0 or 1) of the player on this layer
        depth - the maximum depth to be considered
        presort - whether to presort the moves and cut off
        blacklist - moves that should never be considered
        Returns:
        the pairing of the best possible move and its evaluation

      • negamax

        public ValuedTurn negamax​(Board board,
                          int player,
                          int depth,
                          boolean presort,
                          java.util.List<Turn> blacklist)
        Wrapper function to start negamax search with alpha-beta pruning optimization with a list of undesirable moves.
        Parameters:
        board - the current state of the board
        player - the id (0 or 1) of the player on this layer
        depth - the maximum depth to be considered
        presort - whether to presort the moves and cut off
        blacklist - moves that should never be considered
        Returns:
        the pairing of the best possible move and its evaluation

      • negamax

        protected ValuedTurn negamax​(Board board,
                             int player,
                             int depth,
                             boolean presort,
                             float alpha,
                             float beta)
        Recursive implementation of negamax algorithm with alpha beta pruning optimization.
        Parameters:
        board - the current board
        player - the id (0 or 1) of the player on this layer
        depth - the maximum depth we search
        presort - whether to presort the turns and cut off
        alpha - to determine whether better moves can be found
        beta - to determine whether better moves can be found
        Returns:
        the pairing of the best possible move and its evaluation

      • negamax

        protected ValuedTurn negamax​(Board board,
                             int player,
                             int depth,
                             boolean presort,
                             float alpha,
                             float beta,
                             java.util.List<Turn> blacklist)
        Recursive implementation of negamax algorithm with alpha beta pruning optimization.
        Parameters:
        board - the current board
        player - the id (0 or 1) of the player on this layer
        depth - the maximum depth we search
        presort - whether to presort the turns and cut off
        alpha - to determine whether better moves can be found
        beta - to determine whether better moves can be found
        blacklist - moves that should never be considered
        Returns:
        the pairing of the best possible move and its evaluation

      • chooseMostPromisingTurns

        public java.util.List<Turn> chooseMostPromisingTurns​(Board board,
                                                     java.util.List<Turn> turns,
                                                     int player,
                                                     Evaluator eval,
                                                     int limit)
        Given a board and a list of candidate turns, we evaluate each one statically, sort them accordingly and take as many of the best turns as possible up to a limit.
        Parameters:
        board - the board we are currently on
        turns - list of candidate turns
        player - the relative player id (0 or 1)
        eval - the function used to evaluate the boards
        limit - how many turns we want at most
        Returns:
        the list of most promising turns