Sorting moves by sub tree size speeds up alphabeta search considerably
Posted: Sat May 02, 2020 3:36 pm
I made a surprising discovery. Sorting moves by sub tree size speeds up alphabeta search.
The nice thing about alphabeta, is that it always finds the best move ( in the sense that it will find the same best move, as minimax/negamax would have found, so it won't miss any good continuation or mate due to pruning some move, that it should not have pruned ). Once you have this certainty, you have the freedom to sort the moves any way you want, because the worst thing can happen, is that search won't speed up, or will be slower, but the end result remains the same. So by sorting you cannot miss any good move.
My idea was, that moves that have a small tree size, are ones that have many beta cuts in their sub trees, so why not start with these moves. Surprisingly enough, this slows down search compared to no sorting. However if you search moves first that had large sub tree sizes, this speeds up search considerably. I tried with opening positions and known mate puzzles as well. Speed up is considerable in both cases.
Tested on this engine : https://github.com/easychessanimations/gobbit.
The nice thing about alphabeta, is that it always finds the best move ( in the sense that it will find the same best move, as minimax/negamax would have found, so it won't miss any good continuation or mate due to pruning some move, that it should not have pruned ). Once you have this certainty, you have the freedom to sort the moves any way you want, because the worst thing can happen, is that search won't speed up, or will be slower, but the end result remains the same. So by sorting you cannot miss any good move.
My idea was, that moves that have a small tree size, are ones that have many beta cuts in their sub trees, so why not start with these moves. Surprisingly enough, this slows down search compared to no sorting. However if you search moves first that had large sub tree sizes, this speeds up search considerably. I tried with opening positions and known mate puzzles as well. Speed up is considerable in both cases.
Code: Select all
nodesStart := pos.Nodes
score = -pos.AlphaBetaRec(AlphaBetaInfo{
Alpha: -abi.Beta,
Beta: -abi.Alpha,
CurrentDepth: abi.CurrentDepth + 1,
MaxDepth: maxDepth,
NullMoveMade: nullMoveMade,
NullMoveDepth: nullMoveDepth,
})
pos.Pop()
subTree := pos.Nodes - nodesStart
PosMoveTable[PosMove{st.Zobrist, move}] = subTree