Sorting moves by sub tree size speeds up alphabeta search considerably

[easychessanimations]

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.

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

Tested on this engine : https://github.com/easychessanimations/gobbit.

[User923005]

How does this method compare with the usual alternatives:
1) sorting by estimated best move first (almost everyone does it this way)
2) sorting my longest time last iteration first (seems closely related to your idea)

[BrianR]

An interesting idea.
The only way to really know is to play some matches.
This is particularly the case for search-related changes, where speed and depth differences do not always result in better play.
For evaluation changes, generally faster is typically better.

[H.G.Muller]

Crafty has been doing that or ages, right? In the root.

[BrianR]

Yes.
But every engine is different.
I tried Crafty's approach in Tinker and it did not seem to help.
So, again, try it and see.