Jump to content
  • Advertisement
Sign in to follow this  
Hermes

Chess engine (need expert oppinion)

This topic is 5459 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!