Author: Travers Waker
Date: 06:53:54 02/28/01
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. 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. Since moves don't have an evaluation, only positions do, one actaully has to make each of these moves in order to be able to look up the evaluation of the position each move leads to in the hash table (you can only look up positions in the hash table, not moves, right?). Only then, once all the possible moves have been made and unmade, is it possible to order the moves based on the evalutions of the postions they lead to. OK, so now you know which move is best according to previous itertions, so you make it and you get to another node. Now the whole process reapeats itself for this node. Is my understanding of iterated deepening on the right track? I still have to do some thinking about the benefits of it, so if anyone wants to point out to me why this is such a wonderful thing, I would appreciate your comments. 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). So then what's the point of generating captures first? This is such a simple form of ordering that it's certain to work better to order on the results of previous iterations of iterative deepening. I guess making "capture" moves first still makes sense for the first iteration of iterative deepening (when there may not be entries in the hash table to rely on) and when searching at plys deeper than the previous iteration. OK, I'm sure I've exposed numerous misconceptions of mine, so I'm going to stop right there. I'd really appreciate if those of you in the know can comment on and correct what I have written. Thanks for any help. Travers
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.