kylchiu/sporkfish

Chess engine in Python

sporkfish's Issues

[Design] Searcher switching

• Design a switching interface that allows switching between different searchers, e.g. searcher could be single process or use a different algorithm completely - could be inheritance or factory pattern
• Refactor the single and multi-process negamax searchers as different classes, putting these under the (newly created) Searcher folder

[Feature] Aspiration Windows

See:

• https://mediocrechess.blogspot.com/2007/01/guide-aspiration-windows-killer-moves.html
• https://www.chessprogramming.org/Aspiration_Windows

[Feature] Separate PR (DEV) and master (PROD) CI github actions

Separate the DEV and PROD actions so that we only get a red badge if prod CI is broken.

[Feature] mypy static type checking

Add mypy to workflow.

[Feature] Zobrist Hash should only be initialized when using transposition tables

[Feature] Add propriety board via bitboards

• #51
• #52

[Design] Lichess Bot

• #35
• #36
• #37
• #38
• #39
• #131

Consider:

• Async Lichess bot
• Simultaneous games (multiple correspondence, one rated)

[Feature] Endgame Syzygy tablebases

Requirements:

• Add SyzygyTablebase class (https://en.wikipedia.org/wiki/Endgame_tablebase), which essentially are databases solving all positions given there are only a certain number of pieces left. Please wrap the python-chess API here: https://python-chess.readthedocs.io/en/latest/syzygy.html. The structure should be fairly similar the OpeningBook class, see opening_book.py.
• Integrate it into engine.py, similar to what is done with OpeningBook.
• Please add tests.

You can download databases for testing on: https://syzygy-tables.info/?fen=4k3/8/8/8/8/8/8/4K3_w_-_-_0_1

[Investigate] Improve Zobrist hashing speed

Zobrist hashing and cache caused 10x slowdown. Check why.

[Investigate] How to validate piece values / piece square tables

          Guess that's the whole point of having MG and EG? they evaluate to give different scores?

How do I validate the piece values are correct/meaningful? Seems a bit like a random blackbox to me still.

Originally posted by @ccjeremylo in #15 (comment)

[Feature] Killer Heuristic

This involves storing moves that cause beta cutoffs and trying them first if they are legal next time you are at the same depth. https://rustic-chess.org/search/ordering/killers.html

[Investigation] Improve time management

Investigate and consider other time management strategies.

[Design] Decouple engine and board

Engine currently makes the move for the board, but this isn't ideal as engine does not own the board. Making a move should be moved to the UCIClient level instead.

[Feature] pypy in docker file

          I'd like to install pypy as well. Adding this as a new feature later..

Originally posted by @KYLChiu in #22 (comment)

[Investigate] Board switching -slow

ncalls tottime percall cumtime percall filename:lineno(function)
254103 8.220 0.000 22.513 0.000 evaluator.py:873(evaluate)
17411446 5.067 0.000 9.103 0.000 init.py:725(piece_at)
17411318 4.558 0.000 14.572 0.000 board_py_chess.py:109(piece_at)
18221628 3.290 0.000 3.290 0.000 init.py:735(piece_type_at)
270052 1.188 0.000 2.835 0.000 init.py:2200(push)
1576589 1.115 0.000 2.544 0.000 init.py:1706(generate_pseudo_legal_moves)
6840750 0.911 0.000 0.911 0.000 piece.py:14(init)
12264738 0.864 0.000 0.864 0.000 evaluator.py:897()
3063713 0.691 0.000 0.806 0.000 init.py:314(scan_reversed)
1510784 0.689 0.000 4.759 0.000 init.py:3582(generate_legal_moves)

Notice that piece wrapping id 4.5 seconds itself. The code is just

       def piece_at(self, square: Square) -> Optional[Piece]:
      """
      Get the piece at the specified square.

      :param square: The target square.
      :type square: int
      :return: The piece at the specified square, or None if the square is empty.
      :rtype: Optional[Piece]
      """

      return (
          Piece(piece.piece_type, piece.color)
          if (piece := self.board.piece_at(square))
          else None
      )

but due to sheer amount of calls, this becomes a problem.

[Docs] Generate sphinx docs from docstrings

[Bug] Searcher returns None for certain FEN

Investigate why this returns None

FEN: r1r3k1/1ppp1ppp/p7/8/1P1nPPn1/3B1RP1/P1PP3q/R1BQ2K1 w - - 2 18

[Feature] Basic time management integrated with Lichess Bot

• Implement a simple time management strategy.
• Get times from Lichess and pass to client, executing time management strategy.

[Tests] Test multiprocessing on different OSes work within dockerfile

Re-enable lazy smp and test it works. Most urgent to check Windows.

[Feature] Add black and isort into CI

[Feature] Add Numba decorators and test performance

• #47
• #48
• #61

See https://numba.pydata.org/

[Feature] Add numba decorator for Zobrist hashing and test

[Tests] Add tests for workflow

Add tests for workflow, including

• Searcher
• Evaluator
• UCI

[Feature] History Heuristic

https://www.chessprogramming.org/History_Heuristic

[Feature] NNUE

This is a long-term feature to implement NNUE (efficiently updated neural network) to replace
See:

• https://www.chessprogramming.org/Stockfish_NNUE

Requirements:

• Implement NNUE.
• Train it on data - where to get it?
• Implement switching interface with evaluation function.

[Feature] Principal variation search / Negascout

Requirements:

1. Create a new class called PrincipalVariationSearch inheriting from NegamaxSP. Implement the pseudocode here, https://en.wikipedia.org/wiki/Principal_variation_search
2. Any attempts to avoid duplication with NegamaxSP will be much appreciated.
3. It should be completely identical to NegamaxSP in move ordering, pruning, quiescent, ID, aspiration window and transposition functionality, only the search algorithm should be different.
4. Add relevant tests

Comments:

• As usual, this turns out to be a more tedious task than I originally envisioned. For 1. I think (?) we cannot inherit from NegamaxSP and just use _negamax in PrincipalVariationSearcher.start_search_from_root, because then you only get null window searches at the root.
• Let's add a comment that there is an issue but leave handling it to a later PR: https://www.chessprogramming.org/PVS_and_Aspiration

[Feature] Lichess bot pass down time and increment

[Feature] Null move pruning - depth reduction factor configuration

Make depth reduction factor configurable.

[Feature] Config classes should not provide a default value

Given we pass them in the config file, no need to pass default values in config classes.

Change tests to be more explicit in argument passing.

[Feature] Zobrist hash: internal hashes (en_passant, castling) should be seeded

[Feature] Lichess bot exception / termination handling improvements

[Design] Configuration refactoring

Currently engine creation is hardcoded in UCIClient. Engine creation should be far more flexible, i.e. we should be able to pass in config from the main function. Easiest way to do this is serialised config via yml file, or if you think of a better option please suggest. This should include:

• Config for the engine, e.g. depth for searcher, opening book etc.
• Config for the UCI parts, i.e. time management.
• [Consider] Additional config - e.g. for logging

[Feature] Send challenge to AI and add to CI as a test

[Feature] Add board interface and switching

[Feature] Monte Carlo Tree Search

Long term research task to implement MCTS.

[Investigation] Investigate null move pruning behaviour

E.g. test behaviour when depth_reduction_factor = 0

[Feature] Dockerfile for easier code sharing

@claudiayip could you upload the docker file we made if you still have it - when you get a chance pls?

[Bug] (board_setup["black"]["two_kings"], 3) TT gives inconsistent results with base case

[Feature] Implement bitboard boards

[Feature] Add numba decorator for board and test

[Feature] Get and print Principal Variation

https://www.chessprogramming.org/Principal_Variation - this should be printed in the searcher (currently just prints the best move). This is useful for:

• Debugging
• PV move ordering for AB-negamax
• Implementing PVS in future.

[Bug] Fix multiple slow tests where old board is used

Incorrect merge case

[Feature] Lichess bot to accept challenges from other players

Requirements:

• Accept challenges from other players.

Tips:

• Check state logging to know what to extract. You can also check the lichess REST API for the returned json format, e.g. https://lichess.org/api#tag/Account/operation/accountMe
• Check berserk API for accepting challenge. https://berserk.readthedocs.io/en/master/
• Check using multi-threading and (potentially) multi-processing. Just an FYI that synchronisation will be difficult as we need to force a single request at a time.

[Feature] Numbafy evaluator

ncalls tottime percall cumtime percall filename:lineno(function)
254103 7.704 0.000 17.060 0.000 evaluator.py:877(evaluate)

For a depth 6 call, we have 7 seconds spent in evaluate alone (excluding outgoing function calls). This could potentially be sped up by using numba.

[Feature] Null move pruning - Zugzwang check

[Feature] Incremental Zobrist hash

https://en.wikipedia.org/wiki/Zobrist_hashing

[Feature] Iterative Deepening

Add iterative deepening: https://www.chessprogramming.org/Iterative_Deepening. The benefits are:

• If we reach a depth but run out of time, the best move at the previous depth can be returned instead.
• Transposition tables (cache) can be populated at higher depths and re-used, allowing for more aggressive pruning of the search tree.

To do it:

• See the search function at: https://github.com/KYLChiu/sporkfish/blob/master/sporkfish/searcher.py. It needs to run search through depths from 1 to max_depth instead of running it only at max_depth.
• Additionally you need to pass in the time string from the UCI "go" command down to the searcher class. In the search function, compare against it, breaking early and returning the previous best move if it exceeds the time limit.
• Please play around with the multi-processing implemented in _negamax_mp, i.e. you may send some processes to depth + k for k={1,2,3...} to populate transpositions table in parallel and see what works best.

[Feature] Null-move Pruning

Null-move pruning is a method to reduce the alpha-beta negamax search tree. It refers passing to your turn (i.e. making a "null" move) and dynamically evaluating the position. If the evaluated score after the null move is "too good" (above beta). The assumption is that the opponent wouldn't allow such a favourable position, so the search can be pruned (beta-cutoff).

Requirements:

• Implement this in searcher.py, in a separate function. Call it in _negamax.

See:

• https://en.wikipedia.org/wiki/Null-move_heuristic
• https://github.com/yigitkucuk/Theodora/blob/main/main.py

[Tests] Add evaluator tests to make sure static evaluation scores relative to sidetomove

NB: static evaluation function must return a score relative to the side to being evaluated, e.g. the simplest score evaluation could be:
score = materialWeight * (numWhitePieces - numBlackPieces) * who2move

• positive if winning and if on side to move,
• negative if winning and not on side to move

[Feature] Create Lichess bot