Author: Tom Likens
Date: 04:58:58 08/15/03
Go up one level in this thread
On August 14, 2003 at 20:35:02, Omid David Tabibi wrote: >On August 14, 2003 at 20:11:22, Dieter Buerssner wrote: > >>See for example: http://fortuna.iasi.rdsnet.ro/ccc/ccc.php?art_id=232537 >> >>Another interesting question would be: What is a sure maximum of the number of >>possible pseudo legal move. An upper bound for that question can also be found >>rather easily (for legal positions in "normal" chess). You cannot have more than >>9 queens, each queen has at most 27 moves, ... >> > >Those kind of positions with 200+ moves (or pseudo-legal moves) never arise in >actual games, so setting the size of move list to something less than 200 would >practically suffice, wouldn't it? > >Currently I store the generated moves in a stack, so I don't have any problem >with number of moves, but that limits my options in move generation (e.g., I >have to generate all the moves at once). So I'm wondering what value I should >choose for the move list... > >>Dieter Hello Omid, Bruce Moreland came up with a scheme a number of years back (and I believe others used it before him) that essentially makes moot, the question of move list size. I used to have an array (and I suspect many still do) similar to the following in my engine for storing the moves generated during the search... MoveList[MAX_DEPTH][256] On reflection it is easy to see that this is error-prone and wasteful. Moreland's very clever idea, was to make this a linear array of the form: MoveList[MAX_POSSIBLE_MOVES] At depth 0 you start filling this with the moves generated. When you recursively call the search, pass the number of moves you generated so that at the next depth you start filling in moves immediately after the moves stored previously. As Moreland commented, this is essentially a "mark and release" type scheme and it is very effective. It is also easy to code and makes much more efficient use of memory than the original scheme. MAX_POSSIBLE_MOVES only needs to be a few thousand moves and the total size can be made much smaller than the first scheme. I've been using this in my chess engine for a number of years now and it works really well. It also requires only a minimal change to your code, so you will have it up and running in about 10 minutes. If you are parnoid you can bounds check the last element to ensure that you are not stomping on memory. I turn this on in debug mode and have *never* seen a problem with it. regards, --tom
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.