Author: Bruce Moreland
Date: 16:26:11 03/01/00
Go up one level in this thread
On March 01, 2000 at 13:56:49, John Coffey wrote: >The transposition table will tell us if a move is more desired than the other >moves. So will iterative deepening and iterative iterative deepending. In both >cases it seems necessary to sort the moves from most prefered to least prefered. > What is the method for doing this? Is it just a standard sort routine? > >When doing move generation on a position that we haven't seen before, could >we do things like sort captures to the top of the list, especially when a more >valuable piece is being captured. Move ordering is important because you get the theoretical best case with good move ordering, and the theoretical worst case with bad move ordering, and the best is fairly zippy and the worst can be described as glacial. Winning captures are apt to be good moves. So are moves that have tended to be good elsewhere in the search. Losing captures tend to be bad. You can spend a few months testing this and trying to figure out new ways of ordering, if you wish. It'd probably be time well spent. If you have your list generated, and you want to order it, there are a couple of possibilities: 1) Sort the list up-front. 2) Iterate through the list, select the best one, and try it. Repeat the process for the next move. This is actually why I started writing a chess program. I had the source to GnuChess, and saw that it used method #2, and couldn't believe that this was right. I figured I could write a a great sort routine, and sort the moves up front. And since I'd gone to the trouble of writing a sort routine, I may as well write the rest of the program. What I didn't account for is that many times you will fail high and exit on the first move or two that you check. By "many times" I mean a huge percentage of the time, like half the time. So in these cases, the time spent sorting the whole list is simply wasted, and the second method, which makes one very simple pass through the list, is much more efficient. Another point is that after trying the first few moves, you can simply give up trying to order the rest. If you don't fail high on the first few moves that you try, the odds are that you aren't going to fail high, and you'll have to check all of the moves anyway. And if you *are* going to fail high, your move ordering system is obviously not doing a great job of helping you find the move that's going to do it, so might as well just bag it. bruce
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.