Hi,i'm currently working on a chess game and i'm not very satisfied ,it's not optimized yet but i need a better reprezentation of the board .I used mostly bitboard reprezentation but for only 3 plies i need 2MB of memory and for 4 plies more than 64MB of memory .Since i don't wont to play it on DeepBlue[lol],i want a cheeper way to reprezent it.My every node has an unsigned __int64 data type that keeps the move,the index of the pice. Thanks for your support.

The only thing I can think of is that you are using a breadth-first search algorithm when you should be using a depth-first search algorithm. That's the main problem with breadth-first approaches. As you search deeper the memory requirements grow exponentially. It has nothing to do with your choice to use bitboards.

Transposition tables can eat a lot of mem too.

Quote: Original post by civguy
Transposition tables can eat a lot of mem too.

Yes, but they don't typically grow exponentially as search depth increases.

Yeah. If you are searching 10 moves deep, you should have around 10 sets of Chess Board objects(you get the point) My prgm doesn't use more than and couple hundred kb for board representation.

I use a single copy of the board, on which I make and unmake moves. There is no need to keep the entire tree of positions around.

Quote: Original post by alvaro
I use a single copy of the board, on which I make and unmake moves. There is no need to keep the entire tree of positions around.

Even if you did, you wouldn't need to keep a tree of positions. You only need a stack of positions.

Ok,The problem is that i have a 64 bit bitboard in every node which keeps a possible position of a piece.Every branch of a level has as a first move, the best possible move for an alpha-beta shortcut.Well how could i keep things short if i need all moves to search for ?How can i get rid of the tree if i need it?
I:
-build the tree
-search for the best move
-destroy tree
-rebuild the tree when the turn comes


What do you mean by a stack of moves?


ThankX!

No, that's not right. You expand the tree as you go, and you forget a branch once you have its value. Look at this simplified code:

int alphabeta(Position const &P, int depth, int alpha, int beta, bool wtm){  if(depth<=0)    return static_eval(P, alpha, beta, wtm);    std::vector<Move> moves=generate_moves(P,wtm);  for(size_t i=0;i<moves.size();++i){    Position C=make_move(P,moves);    int v=-alphabeta(P,depth-1,-beta,-alpha,!wtm);    if(v>alpha){      alpha=v;      if(v>=beta)        break;    }  }  return alpha;}

That should be the structure of your search, more or less.

I preallocate enough memory to store 90 * 20 moves.

In english, my program can look 20 plys deep, and it generates all possible moves for each ply, assuming a single ply can only contain 90 different outcomes.

Will