Author: Don Dailey
Date: 16:16:34 05/07/98
Go up one level in this thread
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. 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. 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. 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. 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.