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]))
				primary.add(moves.get(i));			

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

			else
				rest.add(moves.get(i));
		}
    	
		//Add the moves in descending order of priority
    	sorted.addAll(primary);
    	sorted.addAll(secondary);
    	sorted.addAll(rest);
    	
    	//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?

Thanks,

C

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.

Ok I think I've got the first 3 so far. I sitll didn't implement history heuristics yet but will do so.