Author: Don Dailey
Date: 23:36:55 01/25/98
Go up one level in this thread
P.S.
I don't know how efficient my method is however. It was based on the
idea of putting all the data in the same area of memory. I keep a
search state, move list and basically everything next to each other
in this way.
Tony Scherzer used to do the same thing in effect (back then I don't
think cache was a big issue however.) He had a 512 byte area reserved
for each level of the tree.
With modern cache problems it may very well be best to keep everything
as small as possible and take the advice of putting everything as
close together as possbile (but starting each list where the previous
one ends.)
- Don
On January 26, 1998 at 02:10:38, Don Dailey wrote:
>Here is one possible way thats very clean but wastes a little memory,
>just allocate the memory in your search declaration and pass it as a
>pointer to your move generator.
>
>This is very natural and space is automatically allocated and
>deallocated without you thinking about it at all:
>
>
>int search()
>{
> int move_count;
> MOVE_TYPE move_list[200];
>
>
> move_count = generate( move_list );
>
> for (move_index=0; move_index<move_count; move_index++)
> {
>
> current_move = move_list[ move_index ];
>
> ... stuff
>
> }
>
> ... more stuff
>}
>
>
>
>
>On January 26, 1998 at 00:16:38, Robert Hyatt wrote:
>
>>On January 25, 1998 at 22:49:01, James Long wrote:
>>
>>>On January 25, 1998 at 20:00:34, Bruce Moreland wrote:
>>>
>>>>
>>>>On January 25, 1998 at 17:55:45, James Long wrote:
>>>>
>>>>>A couple months ago I decided to completely rewrite
>>>>>my chess program "Tristram." One of the things I'm
>>>>>doing is moving from C to C++.
>>>>>
>>>>>Now I'm ready to write some move generation routines.
>>>>>In previous versions of Tristram, I declared a
>>>>>global array CHESS_MOVE moves[MAXPLY][MAXPLY].
>>>>>
>>>>>This time I'm thinking about using a doubly linked
>>>>>list, or even an array of singly linked list
>>>>>MoveList moves[MAXPLY].
>>>>
>>>>What is the point of this data structure? I don't know why you'd need a
>>>>memory allocator at all.
>>>
>>>The point? An array of movelist. It contains a list of
>>>moves at each ply. The size of each list varies, which
>>>is why I would need a memory allocator.
>>>
>>
>>
>>simple declare a global array : int movelist[5000]; and another
>>int *last[128];
>>
>>last[ply] points to the last move generated for the current ply+1,
>>which means that at ply+1, you start at last[ply-1] and generate all
>>you want, incrementing last[ply] as you do.
>>
>>no dynamic allocation. No sloppy addressing.
>>
>>
>>
>>>
>>>
>>>>>This means that every time I wanted to add a move to
>>>>>one of the list, I'd have to call the "new" routine
>>>>>to allocate the memory.
>>>>>
>>>>>Before I get into it, has anybody tried this before
>>>>>and found it too expensive?
>>>>
>>>>Assuming you do need one:
>>>>
>>>>The "new" that comes with any compiler has got to be a general-purpose
>>>>routine that can handle elements of any size, allocated in any order,
>>>>and freed in any order.
>>>>
>>>>If you cut corners on this, it makes sense that you can do better. You
>>>>can make a mark and release heap, if you can guarantee that you will
>>>>always free elements in exactly the reverse order than you allocated
>>>>them, for instance.
>>>>
>>>
>>>Another poster replied that it was too slow. I suspected it might,
>>>so I asked before I expended the energy.
>>>
>>>So I guess it's best to allocate more memory than required
>>>from the start, similiar to dimensioning a move array
>>>with 100xMAXPLY elements.
>>
>>not big enough. you can generate more than 200 moves in some
>>positions. So it's easier to use an array of moves and a pointer for
>>each ply point to the end of that ply's list...
>>
>>
>>
>>>
>>>--
>>>James
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.