Author: Dave Gomboc
Date: 04:23:57 10/25/02
Go up one level in this thread
On October 25, 2002 at 07:05:02, Uri Blass wrote: >Today I also have phases nit clearly less phases than you. > >1)It should be but and not nit(*ni* are close to *bu* in my keyboard and this is >my excuse for this mistake) > >2)The question that I ask myself is how to do the change to do movei faster. > >The point is that I want to do one change and test and not to divide the move >generator to a lot of functions. > >I do not like the idea of a function that is only for generating next move. > >The problem is that in case that I generate few moves and they do not help then >I may need probably to generate all of them so >I do not save a lot of time by this and I suspect that I use more time in that >case because I need to check that the next move that I generate is not in the >list that I already generated. There's no need to throw away any other moves that you've already generated besides the move you are planning to search. I have to agree with you though: if you were expecting a cut-off, but the first few candidate moves you generated don't cause one, then it may well be best to just assume that none of your other candidate moves will cause a cut-off either, and generate all the rest of them at once and search them in any old order. The better your move ordering is, the more likely that this will be okay. At 'all' nodes, the same idea can apply. Once you've searched your top few candidates, you probably have as good an alpha bound as you're going to get. So you can just generate the rest and search them in any old order. The higher up you are in the tree, the more important it is to have a good move ordering, so extra effort to order them well may be rewarded handsomely. But near the tips, I think it is worth experimenting with just trying a few moves, then searching the rest in any old order. How well or poorly this works will help to indicate the quality of your move ordering. >Generating the last move is espacailly slow and can take o(n^2) >because after doing the steps to generate a move I need to compare it with >average number of about n/2 moves only to find that the move alreasy appeared in >the list. This doesn't sound right. You should be able to generate moves in such a way that you can't possibly generate the same move twice. (Though you do still have to handle any moves from hash, killer, etc. specially.) Slate and Atkin describe such a scheme in Chess Skill in Man and Machine. The gist is that at any point you can generate either all moves from a square, or all moves to a square. This makes it easy to detect when you are generating more moves if you've already generated any particular move -- you just test the from_square and the to_square, and if either are handled, you've already generated that move. I have to caution that this scheme is 20+ years old -- it is likely just too out of date. However, it is not the only possible way to divvy up the move generation work without requiring expensive tests to make sure you haven't already generated moves. Hopefully at least it will give you some ideas about what can be done. Dave
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.