Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Improving move ordering


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 cryo75   Members   -  Reputation: 143

Like
0Likes
Like

Posted 19 March 2013 - 08:54 AM

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

 



Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13684

Like
1Likes
Like

Posted 19 March 2013 - 10:22 AM

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.

#3 cryo75   Members   -  Reputation: 143

Like
0Likes
Like

Posted 19 March 2013 - 10:42 AM

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






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS