search

KYLChiu / sporkfish

Chess engine in Python
MIT License
5 stars 0 forks source link

Principal Variation Search #141

Closed michelle-lai-swl closed 3 months ago

michelle-lai-swl commented 5 months ago

Implemented pseudo-code described here: https://en.wikipedia.org/wiki/Principal_variation_search

Performs similar to negamax in most cases, but shows significant improvements in some cases. Performance change: (used test_performance.py)

FEN: r1b2rk1/ppqn1pbp/6p1/3pp3/7B/2PB1N2/PP3PPP/R2QR1K1 w - - 0 16 PVS: 27345484 function calls (27283687 primitive calls) in 15.451 seconds Negamax: 49480947 function calls (49373488 primitive calls) in 27.578 seconds

FEN: 8/8/8/8/5R2/2pk4/5K2/8 b - - 0 1 PVS: 19218758 function calls (19146750 primitive calls) in 9.663 seconds Negamax: 20640107 function calls (20567047 primitive calls) in 10.045 seconds

FEN: r1b2rk1/ppq2ppp/3bpn2/3pP3/8/2PB2B1/PP1N1PPP/R2QK2R b KQ - 0 11 PVS: 84376165 function calls (84159373 primitive calls) in 47.843 seconds Negamax: 79506308 function calls (79300989 primitive calls) in 43.080 seconds

Creds: Created with the wonders of Github Copilot with Kelvin's help

ccjeremylo commented 5 months ago

Implemented pseudo-code described here: en.wikipedia.org/wiki/Principal_variation_search

Performs similar to negamax in most cases, but shows significant improvements in some cases. Performance change: (used test_performance.py)

FEN: r1b2rk1/ppqn1pbp/6p1/3pp3/7B/2PB1N2/PP3PPP/R2QR1K1 w - - 0 16 PVS: 27345484 function calls (27283687 primitive calls) in 15.451 seconds Negamax: 49480947 function calls (49373488 primitive calls) in 27.578 seconds

FEN: 8/8/8/8/5R2/2pk4/5K2/8 b - - 0 1 PVS: 19218758 function calls (19146750 primitive calls) in 9.663 seconds Negamax: 20640107 function calls (20567047 primitive calls) in 10.045 seconds

FEN: r1b2rk1/ppq2ppp/3bpn2/3pP3/8/2PB2B1/PP1N1PPP/R2QK2R b KQ - 0 11 PVS: 84376165 function calls (84159373 primitive calls) in 47.843 seconds Negamax: 79506308 function calls (79300989 primitive calls) in 43.080 seconds

Creds: Created with the wonders of Github Copilot with Kelvin's help

Wow this is impressive

Not quite clear to me the (subtle?) differences between PVS and NegaScout yet (or if they are actually the same thing?) - is NegaScout still in our "book of work"?

Looking at the issues, seems like they (PVS and NegaScout) are being lumped in together, i.e. #71

PS: did a quick visualisation of the fen strings, can't say I managed to reach any conclusion why sometimes PVS is so much faster, sometimes we get similar perf...

KYLChiu commented 5 months ago

One overarching issue with this design (my fault) is that any underlying changes e.g. TT move ordering now needs to be implemented twice.

I have an idea on how to refactor it to save us form DRY (don't repeat yourself) - @michelle-lai-swl for next PR pls.