Author: Robert Hyatt
Date: 19:46:32 05/07/98
Go up one level in this thread
On May 07, 1998 at 19:16:34, Don Dailey wrote: >On May 07, 1998 at 15:51:16, Bas Hamstra wrote: > >>Do you think it would be possible to generate moves incrementally? Most >>of the legal moves remain the same after a move is made, it seems. I >>think it might be possible to generate only moves for the pieces that >>are "affected" by the prior move. >> >>If I'm not mistaken KnightCap does this (or was in another program?). It >>has a board representation in which each square is a 32 bit number, each >>bit representing the (uniquely identified) piece by which that square is >>attacked. There can be no more pieces on the board than 32. >> >>Suppose a move a2-a3 is made. Adjust the board (="attackmap") for the >>new squares a3 attacks and delete the a2-attacks. If a2 OR a3 is >>attacked by a piece (of both colors) only the moves for those pieces are >>to be regenerated and the board has to be updated again, for just those >>pieces. >> >>Would that work you think? >> >>Problem: what to do with unmake? Compute it all "back" seems exspensive. >>Or no unmake at all and fetch the previous board? Wouldnt that be >>expensive too on a PC (bandwitdh and all)? >> >>Could someone please react on this thoughts? > >When I hear the term incremental move generation, I'm thinking of >something I've heard called a "next move generator." The idea is >that a program generates only 1 move at a time. This is a supreme >example of what Bob calls procrastination. Why generate 36 moves >when one might do the job? Even what you call incremental move >generation might do a lot more work (at some nodes which I'll talk >about later.) > >I have tried many different forms of move generation in my programs, >including your incremental move idea and "next move" generators. >I have found that "next move" generators are probably the very fastest, >although I don't currently use them today. > a very old idea of course. Chess 4.x used that very approach. But they also used MVV/LVA for capture ordering, which I don't happen to like, based on a bunch of testing done a couple of years ago in r.g.c.c... The problem I have is that it is difficult to generate the moves you want first... IE how would you do history moves? You have to generate a move and then fetch its history count, and then are you sure that is the best move? So for current move ordering strategies, one-at-a-time move generation can produce more speed, but it also produces (generally) bigger trees. >I suspect the real screamers in terms of speed use the 1 move at a >time idea. I'm almost positive Fritz does for instance and I also >believe Wchess does which has a high node count. > I'm not sure about older ones, but I don't think the current one does, based on discussions about selectivity I've had with dave... He seems to generate all, then not search all of them based on some sort of "screening" process that he has refined to a remarkable degree... >But everything has its drawbacks. At nodes where there is no cutoff, >there is likely to be the extra overhead of bookeeping, so "next move" >generators really shine in quies searches and at nodes where cutoffs >come early in the move "list". It could be the real good programs >that use this approach have engineered this problem away for the >most part, I don't really know. that's the other side... every other call generates *all* moves. And one at a time is much slower than generating a batch. So this probably ends up a wash, in general... > >Experimenting with move ordering is not nearly as easy and can >get real hairy. You lose some flexibility. Debugging a next move >generator and optimizing it is much more difficult than simply >generating them all at once and storing the results. A poorly written >next move generator might be slower that a simple intuitive all at once >generator if you don't know what you're doing. > >Cilkchess uses a form of this in its search. I suspect Crafty may >do this too since this seems like a natural thing to do with bitboards. >I haven't looked at Crafty to see though. >What I do is generate moves in stages, not all at once. But this is not >strictly a one at a time generator. In quies search I will generate all >captures of a queen and try them all out before looking at anything >else, then I move on to rooks etc. I'm trying to avoid doing any >unnecesary work. With bitboards I don't think I'm losing much at >all even when I have to generator all the moves. I generate moves in two "chunks"... all captures, then, if necessary, the rest of the moves. But I don't generate anything until I try the hash move to see if it will cutoff, which it does a great deal of the time. And after generating the captures and searching the ones that SEE says win or break even, I try killer moves before generating the non- captures... and when those cause a cutoff, I avoid that second batch of move generations... > >The incremental idea the way you descibed it I implemented in an old >program and it was my slowest program! I don't think it necessarily >had anything to do with the move generator. Programming one of these >was also not nearly as straightforward as "all at once" and debugging >was difficult. Probably the idea is sound if done well. > >- 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.