Author: Robert Hyatt
Date: 18:59:18 12/17/97
Go up one level in this thread
On December 17, 1997 at 20:06:35, Don Dailey wrote: >On December 17, 1997 at 18:44:05, Robert Hyatt wrote: > >>On December 17, 1997 at 17:47:16, John Bartkiw wrote: >> >>>> >>>> >>>>I use both, because I can try killers before I generate any moves. If I >>>>get a cutoff, it is really inexpensive. I didn't notice any particular >>>>tree size advantage when I added killers, but I noticed a 10% speed >>>>improvement because of trying them before generating any non-capture >>>>moves. >>>> >>> >>> Just a question. How can you try killers if you don't know if the >>>move is valid? If the last move made the killer not legal. >>> >>>I've just started working on my program and have noticed that a tonne of >>>my cycles are used generating moves. I'm using the bitboard approach >>>along with a make move and unmake move function. >>> >>> To generate my list of moves I make every possible move to see if >>>it's valid (ie. doesn't reveal a check) and then after I've done that I >>>start the whole search. The making and unmaking of the moves twice >>>(once to check if it's valid and then later when actually searching) is >>>really killing my nps. >>> >>> Is there a better approach?? > >Yes there is. First of generate your moves without any testing. >Pretend >they are all legal and do your move ordering etc. In many positions >you will get a beta cutoff and the tests will be greatly wasted on most >of the move list. You should do the same with en-passant captures. another optimization or two here: 1. generate only the captures first, since they get tried first. Then you don't have to take time to shift them to the top of the move list, nor take time to search for them in the move list if you prefer to not shift them up. Of course, this is trivial for bitmap programs, and it pays off since a capture is the most likely refutation of the previous move, and often captures are all that are needed to produce a cutoff. 2. For captures, you probably have to sort the move list based on the expected gain, but for the other moves, don't sort all the moves into their correct positions, do a selection sort where you make a pass thru all the moves and choose the "best" one to search. If you get a cutoff, you save the sorting time. If you do this 3-4 times without a cutoff, after trying the hash move, captures, and history moves, you can safely assume this is an "ALL" node and avoid any further move ordering and just take 'em as they appear in the move list. Again saving a good bit of time. > >Now before you make ANY move you can apply a pre-test to it. It is >possible >in most cases to quickly determine that no check testing is required. >So >do not do check testing in these cases, it will save you a lot of time. >Look at the "from" square of the move you want to make. Is >it on the same diagonal or orthogonal as your king? If not, the move >cannot possibly put you into check (unless it's a king move or >en-passant) >and the test can be a simple table lookup. Of course all of this >assumes >you are not currently in check! But your program should know this too >and you can apply similar very fast tests to this case too. Another one: in normal positions, use "capture the king" at ply N+1 to let you know that the move at ply N was illegal (and hung the king.) But when you are in check at the start of ply=N (which you should know since you want to extend the search when in check) then be more careful and use a special "legal-move generator". This has several benefits: (a) it avoids hanging the king in 99% of the positions, wasting a lot of time; (b) it lets you know how many moves you have to get out of check in case you want to do an extra extension when there is only one (or two). Again bitmaps make legal move generation a lot easier, and *very* fast, although not as fast as psuedo-legal moves...there are many such ideas, most can be found buried in the crafty source code. But they've been around forever of course. > >-- Don
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.