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: >>>>>[snip] >>>>>>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. >>>> >>>>-Dan. >>> >>>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. >>> >>>Larry. >> >>Hi, >> >>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 :). -Dan. >> >>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... >> >>-Dan. > >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. > >Larry.
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.