Author: Uri Blass
Date: 05:41:34 08/15/03
Go up one level in this thread
On August 15, 2003 at 07:58:58, Tom Likens wrote: >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) Yes The scheme that you describe is used by tscp of Tom kerrigen and I thought that it was meant by the words "move stack" 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. Yes I increased the original number of tscp to 30,000 after I found no speed panelty from increasing the number. I am sure that I will never have more than dome thousands of moves in the move stack so I could use smaller number but I am not sure if there is a reason to do it. The memory that is needed is extremely small so 30000 or some thousands does not make big difference. Uri
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.