Computer Chess Club Archives




Subject: Re: C or C++ for Chess Programming?

Author: Dan Newman

Date: 02:50:34 08/23/00

Go up one level in this thread

On August 21, 2000 at 20:22:08, Larry Griffiths wrote:

>On August 20, 2000 at 06:54:22, Dan Newman wrote:
>>On August 19, 2000 at 09:39:02, Larry Griffiths wrote:
>>>On August 19, 2000 at 05:17:56, Dan Newman wrote:
>>>>On August 18, 2000 at 20:13:23, Dann Corbit wrote:
>>>>>On August 18, 2000 at 05:07:09, Dan Newman wrote:
>>>>>>OTOH, I have occasionally considered attempting a full blown OPP chess
>>>>>>program complete with pools of chess pieces with overloaded new so that
>>>>>>(for instance) on pawn promotion I could delete the pawn and new a queen...
>>>>>Dumb as a box o' rocks observation:
>>>>>Since the absolute "max" of posible chessmen is known, why hot just preallocate
>>>>>a "box" of chess pieces with enough spares for either side.  Captured
>>>>>pieces/pawns go into the box and promoted pieces are pulled from it.
>>>>>At the start of a game, it contains:
>>>>>White rooks: 8
>>>>>White knights: 8
>>>>>White bishops: 8
>>>>>White queens: 8
>>>>>White pawns: 0
>>>>>No White king slot
>>>>>Black rooks: 8
>>>>>Black knights: 8
>>>>>Black bishops: 8
>>>>>Black queens: 8
>>>>>Black pawns: 0
>>>>>No Black king slot
>>>>>If you wanted to carry the metaphor further, you could have all the starting
>>>>>chess men in the box to start with and construct the board by pulling pieces and
>>>>>pawns out of the box.
>>>>>Each piece could have a bit that means in use/in box to use for error checking.
>>>>>Sounds like bizarre overkill, perhaps.  But if your evaluation removes hundreds
>>>>>of pieces or promotes hundreds of pieces during a search, it might be useful to
>>>>>do it that way.
>>>>This is more or less what I had in mind with the pool idea.  When, frex,
>>>>"new WhiteQueen" gets executed, the overloaded new would find an unused
>>>>white queen and return a pointer to it.  This would be a lot faster than
>>>>going through the memory allocator...
>>>>A neat thing about this scheme (of making a class for each piece type) is
>>>>that you can put the move generator code into those classes and then simply
>>>>iterate through the piece lists calling the virtual move generator functions
>>>>to generate the moves.  OTOH, this is also going to add a lot of function
>>>>call overhead to the program.
>>>>If you are doing bitboards though, this isn't really an option.  Instead of
>>>>pieces being relatively heavyweight objects, they are grouped together in
>>>>bitboards by type...
>>>>I think it may be a mistake (when deciding what classes are needed to do a
>>>>chess progam in C++) to identify the physical objects involved in the game
>>>>and make classes for them.  (That's the first thing I thought of when first
>>>>attempting this a few years back.  The first two sorts of object I though of
>>>>were the pieces and the board.  Beyond that what else is there?
>>>>I quickly decided *that* was a mistake when I didn't see an easy way to turn
>>>>pawns into queens.)  Instead (I think) you really need to look at what
>>>>"things" are needed to play the game (like search, eval, moves, state info,
>>>>etc.) and encapsulate those things instead--when it makes sense to do so.
>>>>In my current chess program I've only haphazardly OOP'ed stuff in a few
>>>>places where it helped.  For instance, my move is a class, and I get at its
>>>>from and to-square coords via member functions so that I can experiment
>>>>with move representation without having to do massive changes to the code.
>>>>But for the most part I just use C++ as a "better" C.
>>>Hi Dan,
>>>My programs has a base class Piece and all my pieces are derived from it.  The
>>>move genereate, makemove, and unmake move are also in the piece class along with
>>>updating my bitboards.  I have a piece pool manager to get pieces and assigning
>>>them to the board.  Pawn promotion flags the pawn in the piece list as inactive
>>>and gets a queen from the piece pool when it gets promoted.
>>>My program is just as fast as it always was when I did not do it this way.
>>That's interesting.  It sounds like you have a sort of hybrid program, if
>>you have bitboards *and* separate pieces in piece lists.  Actually, I guess
>>I have pieces too (in a way) since I have a "board" array with byte sized
>>entries which store the piece type and color--much as Crafty has.  But I
>>don't have piece lists now that I use bitboards...  In fact that's the main
>>reason I like bitboards; I always found piece lists problematical :).
>I keep a list of black pieces and a list of white pieces.  When a ply has to
>generate moves for the pieces, it loops thru the piece list.  I guess this was
>the quickest way to generate moves without scanning thru the entire boards
>squares looking for black pieces.

Yes, you really don't want to be scanning the board to find your pieces.  I
tried it once, and it did give a fairly large hit on movegen performance, but
I don't remember exactly how much.  Maybe 30% in the middlegame.  OTOH, if move
generation takes only 10 or 20% of the cpu cycles, then the hit on the whole
program is maybe only 3 to 6%.  Well, I'd do a lot for 6% :).  And piece lists
turn out to be useful in other places too, like the SEE...

>for(int i=0;i<blackpiecelist->Count;i++)
>   {
>   if(!blackpiecelist[i]->State&psCAPTURED)
>      {  // The piece is not captured (or promoted)
>      blackpiecelist[i]->GenerateCaptures;
>      }
>   }
>When a piece is captured or a pawn is promoted, then its state is set to
>CAPTURED.  (probably should have used MIA or something instead of CAPTURED :)

I marked my pieces captured like this in my next to last program (an 0x88).
I decided next time I did a piece list program that I'd contract the list
on the fly (expensive), and perhaps have separate (short) piece lists for each
piece type.

In my first program I swapped in the tail-end piece to replace a captured
piece, and when I restored the captured piece I just put it at the end.  It
was cheap, but I didn't like the scrambled piece lists that resulted.

In yet another program I tried doubly linked lists for piece lists and when
a piece was captured I unlinked it and saved it in a stack for later
restoration.  This works fairly well, but make() and unmake() are a bit more
expensive since a lot of pointers have to be set and reset.

ISTR writing one that had a fixed length array of 16 pointers-to-piece for a
piece list, and I just set a captured piece's slot to NULL.  The board was
also an array of pointers-to-piece, empty squares set to NULL.

I've tried about everything with piece lists that I could think of but was
never really satisfied.  Bitboards are a great relief :).


>>I've always wondered where make()/unmake() ought to go in an object oriented
>>program.  I think I'd have a move class and that's where they'd go, but then
>>how do you give the move's member functions access to all the state data
>>that they need: 1) pass the board and so forth into make(), 2) have the
>>board (and other state) be static members of the move class, or 3) make the
>>board, etc., global?  Each choice seems to have its drawbacks.  1) makes
>>the code cost more cycles that it needs to, 2) begs the question as to how
>>other parts of the code are to get to the board, 3) seems to be contrary
>>to the OOP paradigm...  I think 1) is probably the best choice.  Just
>>pass a pointer to the state data into make().  I guess you end up having
>>to do something like this anyway if you want to have a parallel search...
>Very good questions Dan :)   My pieces have an OwnerBoard field in case it needs
>to access something in the board class.  My Make/UnMake call is in my SearchTree
>method which is part of my Board class. It calls the Make/UnMake in my Piece
>class.  I am still moving the methods and objects around to see where they fit
>best.  I also have a lot of globals (bitboards, squares etc.) that need to go
>somewhere.  I really need to get rid of all my globals so that I could do some
>parallel tasking with my SMP pc.
>I do agree that there is some loss of performance when I have to start pointer
>chains like Board->Piecelist->State etc.  I currently have inline assembler with
>MMX and the pointer chains make the assembler sections harder to code.
>I am try to keep the data closest to the objects that use them the most so that
>I do not have long chains of pointers.
>I still have a long way to go, but it has made the code so much simpler compared
>to my previous chess program.

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.