Sign in to follow this  

Improving move ordering

Recommended Posts

cryo75    143

This is my basic move ordering function:


    private List<Move> sortMoves(List<Move> moves, int depth)
    	//Create new sorted list
    	List<Move> sorted = new ArrayList<Move>();
    	//Exit if original list is empty
    	if (moves.size() == 0)
    		return sorted;
    	//Temporary lists to hold killer moves and remaining moves
    	List<Move> primary = new ArrayList<Move>();
    	List<Move> secondary = new ArrayList<Move>();
    	List<Move> rest = new ArrayList<Move>();
		//Loop through the moves and add killer moves first
		for(int i = 0, n = moves.size(); i < n; i++)
			if (killers.primary[depth] != null && moves.get(i).equals(killers.primary[depth]))

			else if (killers.secondary[depth] != null && moves.get(i).equals(killers.secondary[depth]))

		//Add the moves in descending order of priority
    	//Return the sorted moves
    	return sorted;

The moves parameter contains the list of generated moves (which I already sort upon generation by adding a weight to them). The killers include primary and secondary killers for a particular depth.


The code works and I didn't profile it, but I believe it can really be improved upon. Any suggestions?




Share this post

Link to post
Share on other sites
alvaro    21247
If you care about performance, you can take your killer moves and check if they are valid in the current position. The hope is that one of them will produce a beta cut-off and then you don't even need to generate the other moves.

You probably want to put moves that form mills (I think you were writing this for nine men morris) before the other moves.

The order I would try is:
(1) Hash move
(2) Mill-forming moves
(3) Killer moves (non mill forming)
(4) Other non-mill-forming moves, in history-heuristic order

The code can get messy quickly, so it is preferable to make an object that provides a method to obtain the next move, and thus hide the details of sorting moves and perhaps generating them in stages.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this