Author: David Blackman
Date: 23:51:58 02/28/01
Go up one level in this thread
On February 28, 2001 at 09:53:54, Travers Waker wrote: For a first cut, it might be best to generate them all, because the code is probably easier that way. After you get it all working and understand it better, you could try smarter stuff. Ignore extra notes below unless brave :-) >Hi. > >I've started work on a chess-playing program, and have reached the point >where I have to write a move generator. After having a look at >alph-beta searching, I'm not sure what approach to take. > >In alph-beta, in any particular position (ie any particualr node in the search >tree) you may not have to generate all the possible moves in that position, >because the current value of beta may cause search of this node in the tree to >stop before it was necessary to try all the moves. From this observation, it >seems to make sense to only generate moves as they are needed, rather than >generating them all at once. > >However, if one only generates moves one at a time, it is very difficult >to implement move ordering more complex than "captures first", becasue >you need a list of all the moves to be able to sort them on some criteria. The usual is to generate moves in several batches. You try to choose the batches so good moves appear in an early batch. And you can sort internally in each batch. A typical approach might be: 0. Take the opponents king, if possible. If you are generating only strictly legal moves, this never happens (but is still a good debugging aid :-), but some programs generate "pseudo-legal" moves instead, where it can happen. 1. The best move according to the hash table. 2. Generate all captures of the opponents piece that just moved. Try the good ones now, save the rest for batch 7. 3. Generate all other captures and promotions, sort according to goodness, try the good ones now, save the rest for batch 7. 4. Killer moves. 5. All legal moves of side-to-move's two most valuable pieces that can be taken. 6. Checks. 7. Generate all remaining legal moves, and append the leftover captures and promotions from batches 2 and 3. Use history heuristic to select the best 4 from this list and try them in order. 8. All the moves left over from batch 7, don't really care about which order. I think everyone has their own version of these rules, and tuning them for best move ordering and speed can be quite a delicate operation. (Above are not what my program uses BTW. It is much more complicated than that, but probably not any better.) >It becomes even >more of a problem when using iterated deepening, if my understanding of >iterated deepening is correct. > >The way I see iterated deepening is that at a particular node in the search >tree, you generate all moves. Then you have to order the moves from best to >worst based on the results of a previous search iteration. Maybe you do this at the root of the tree only. (Although i have heard rumours of better tricks to do there and partly verified them.) In most positions, it is enough to know what the previous iteration thought was the best move. Leave space in your hash table entry for best move in this position. (If failing high, fill in the fail-high move even if you aren't sure it is really the best move.) Also, previous iterations should leave lots of good stuff in the killer table and history table. >Also, getting back to my original point, this seems to make it a good idea to >generate all moves at once, since they are all going to be needed (well, >certainly while you are still at a ply that has been covered by a previous >iteration of iterative deepening). No. With alpha-beta you cutout and return as soon as you see a fail high, even if you haven't searched all the moves. Even with iterative deepening, anything else just takes to long. (Well, there is singular move extension, but you really don't want to know about that until you have your program working, and a good understanding of what is going on.)
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.