Code: Select all
22ms 8.10% 8.10% 22.20ms 8.17% bitbucket.org/zurichess/zurichess/engine.(*stack).sort
1) Use stdlib provided sort function This is too slow because Golang doesn't support generics and has to do lots of calls to compare/swap.
2) Don't sort, but pop the best move. Can be O(n^2) in the worst case, but works with very good move scoring.
3) What I use now: sort using shell sort. Fast O(n log(n)) sorting; high cost upfront, constant time finding the best move repeatedly.
I believe stockfish uses 2), but that was slower for my engine. I also use far fewer phases (4 in zurichess vs 12? in stockfish).
I tried caching moves (and avoid generating/sorting moves for repeated positions), but that only worked in 13-17% of the cases and was a slow down overall.
Any other ideas?