[Investigation] Investigate null move pruning behaviour

ccjeremylo commented 9 months ago

E.g. test behaviour when depth_reduction_factor = 0

ccjeremylo commented 9 months ago

Base

tests/test_searcher.py::TestPerformance::test_perf_base[r1r3k1/1ppp1ppp/p7/8/1P1nPPn1/3B1RP1/P1PP3q/R1BQ2K1 w - - 2 18-6]
105218986 function calls (104948916 primitive calls) in 29.705 seconds

Ordered by: internal time List reduced from 174 to 10 due to restriction <10>

ncalls tottime percall cumtime percall filename:lineno(function) 254103 6.846 0.000 19.747 0.000 evaluator.py:878(evaluate) 17411446 4.746 0.000 8.283 0.000 init.py:725(piece_at) 17411318 4.300 0.000 13.202 0.000 board_py_chess.py:109(piece_at) 18221628 3.089 0.000 3.089 0.000 init.py:735(piece_type_at) 1576589 0.968 0.000 2.048 0.000 init.py:1706(generate_pseudo_legal_moves) 270052 0.834 0.000 2.132 0.000 init.py:2200(push) 12264738 0.721 0.000 0.721 0.000 evaluator.py:902() 6840750 0.619 0.000 0.619 0.000 piece.py:14(init) 6840828 0.615 0.000 0.615 0.000 :2(init) 3063713 0.542 0.000 0.626 0.000 init.py:314(scan_reversed)

NMP: `null_move_depth = 0`

FAILURES self = <test_searcher.TestPerformance object at 0x1209e9e90>, fen_string = 'r1r3k1/1ppp1ppp/p7/8/1P1nPPn1/3B1RP1/P1PP3q/R1BQ2K1 w - - 2 18' max_depth = 6

    @pytest.mark.slow
    def test_perf_null_move_pruning(self, fen_string: str, max_depth: int) -> None:
        """Performance test with null move pruning"""
>       self._run_perf_analytics(
            fen=fen_string,
            max_depth=max_depth,
            enable_null_move_pruning=True,
        )

tests/test_searcher.py:102:

tests/test_searcher.py:74: in _run_perf_analytics
    _searcher_with_fen(
tests/test_searcher.py:28: in _searcher_with_fen
    score, move = s.search(board)
sporkfish/searcher.py:423: in search
    new_score, new_move, elapsed, error_code = do_search_with_info(
/opt/homebrew/lib/python3.11/site-packages/stopit/utils.py:148: in wrapper
    return func(*args, **kwargs)
sporkfish/searcher.py:377: in do_search_with_info
    score, move = self._negamax_sp(
sporkfish/searcher.py:298: in _negamax_sp
    child_value = -self._negamax(board, depth - 1, -beta, -alpha)
sporkfish/searcher.py:234: in _negamax
    value = -self._negamax(board, null_move_depth, -beta, -alpha)
sporkfish/searcher.py:234: in _negamax
    value = -self._negamax(board, null_move_depth, -beta, -alpha)
E   RecursionError: maximum recursion depth exceeded while calling a Python object
!!! Recursion detected (same locals & position)

NMP: `null_move_depth = 1`

tests/test_searcher.py::TestPerformance::test_perf_null_move_pruning[r1r3k1/1ppp1ppp/p7/8/1P1nPPn1/3B1RP1/P1PP3q/R1BQ2K1 w - - 2 18-6]
195598993 function calls (195107169 primitive calls) in 55.805 seconds

Ordered by: internal time List reduced from 154 to 10 due to restriction <10>

ncalls tottime percall cumtime percall filename:lineno(function) 469626 12.818 0.000 36.842 0.000 evaluator.py:878(evaluate) 31499432 8.571 0.000 14.884 0.000 init.py:725(piece_at) 31499304 7.916 0.000 23.958 0.000 board_py_chess.py:109(piece_at) 32913334 5.471 0.000 5.471 0.000 init.py:735(piece_type_at) 3174708 1.960 0.000 4.124 0.000 init.py:1706(generate_pseudo_legal_moves) 491806 1.534 0.000 3.852 0.000 init.py:2200(push) 22933916 1.394 0.000 1.394 0.000 evaluator.py:902() 2693526 1.216 0.000 2.705 0.000 board_py_chess.py:121(is_capture) 12460484 1.158 0.000 1.158 0.000 piece.py:14(init) 12460562 1.135 0.000 1.135 0.000 :2(init)

NMP: `null_move_depth = 2`

tests/test_searcher.py::TestPerformance::test_perf_null_move_pruning[r1r3k1/1ppp1ppp/p7/8/1P1nPPn1/3B1RP1/P1PP3q/R1BQ2K1 w - - 2 18-6]
61209305 function calls (61064950 primitive calls) in 17.602 seconds

Ordered by: internal time List reduced from 156 to 10 due to restriction <10>

ncalls tottime percall cumtime percall filename:lineno(function) 134301 3.629 0.000 10.408 0.000 evaluator.py:878(evaluate) 9219648 2.506 0.000 4.342 0.000 init.py:725(piece_at) 9219520 2.316 0.000 6.994 0.000 board_py_chess.py:109(piece_at) 9641399 1.594 0.000 1.594 0.000 init.py:735(piece_type_at) 1299511 0.812 0.000 1.705 0.000 init.py:1706(generate_pseudo_legal_moves) 1089980 0.492 0.000 1.095 0.000 board_py_chess.py:121(is_capture) 144337 0.465 0.000 1.172 0.000 init.py:2200(push) 2541474 0.447 0.000 0.518 0.000 init.py:314(scan_reversed) 1236697 0.436 0.000 3.244 0.000 init.py:3582(generate_legal_moves) 1279668 0.425 0.000 0.921 0.000 init.py:3544(_is_safe)

NMP: `null_move_depth = 3`

tests/test_searcher.py::TestPerformance::test_perf_null_move_pruning[r1r3k1/1ppp1ppp/p7/8/1P1nPPn1/3B1RP1/P1PP3q/R1BQ2K1 w - - 2 18-6]
20257420 function calls (20206723 primitive calls) in 5.718 seconds

Ordered by: internal time List reduced from 156 to 10 due to restriction <10>

ncalls tottime percall cumtime percall filename:lineno(function) 47132 1.257 0.000 3.621 0.000 evaluator.py:878(evaluate) 3263902 0.871 0.000 1.520 0.000 init.py:725(piece_at) 3263774 0.821 0.000 2.456 0.000 board_py_chess.py:109(piece_at) 3415644 0.566 0.000 0.566 0.000 init.py:735(piece_type_at) 347925 0.215 0.000 0.452 0.000 init.py:1706(generate_pseudo_legal_moves) 50679 0.160 0.000 0.402 0.000 init.py:2200(push) 2233258 0.132 0.000 0.132 0.000 evaluator.py:902() 673527 0.118 0.000 0.137 0.000 init.py:314(scan_reversed) 1269925 0.116 0.000 0.116 0.000 piece.py:14(init) 1270003 0.114 0.000 0.114 0.000 :2(init)

KYLChiu commented 7 months ago

Thorough analysis! Much appreciated.

KYLChiu / sporkfish