Hi I've read a lot of articles on the net on representing data on a chess game. I read about representing the game board, representing the game board piece states. I was wondering how do I represent a cheass game tree with a minimal overhead. I want a very small game tree and I want to see if a average chess game can be made with a small game tree. Plz advice

Have a look on the web for tutorials on alpha-beta pruning (and minimax), since that's the algorithm used for chess.

I've read both the techniques. What I wanted was , what level of game tree would be required to create an average chess game ? Do I have to store all possibilities of the chess game moves ? Should I remove the symmetric data ?

Well, I'm not really an expert; I've only implemented basic alpha-beta for simpler games like nine man's morris and checkers (and I never really got the checkers one working properly), and that was a couple of years ago. However, for me the depth of the game tree that I searched through was dependent on the difficult setting; how many moves ahead you want the A.I. to search through.

There's an approach that I think is called 'iterative deepening' that can help, especially if you have a time limit for your moves. With this approach the A.I. first calculates the game tree to only 1 move ahead, then 2, then 3, then so on until it runs out of time. It then makes the best move that it came up with in the time limit. Hopefully that is of some help.

And I'm not sure that you need to worry about symmetric data unless you are designing an endgame database (and that is beyond what I've done, so I'll be no help there). Your chess program is extremely unlikely to get far enough down the tree that rotations and reflections of the chess board position will crop up regularly. You might get the same position in different parts of the tree, which I can't remember gives you much benefit if you treat differently.

Hopefully a more hardcore chess engine programmer will give you some more advice. That's about the limit of what I know off the top of my head.

thnks for the advice trapper zoid. i've started to think if i can represent a chess game tree in a minimal data storage way. I was going through other games, their game tree's are way too small in comparison to a chess game tree. But my objective was to create a small game tree so that i can create an average game within my memory limits. I'm also considering whether i can represent all the game moves during the gameplay itself. For every move that i make , i can create a small buffer game tree which i can then search using the available algorithms. just a suggession! i'm still considering various options.

Have you checked the Chess AI articles here...
http://www.gamedev.net/reference/list.asp?categoryid=18
?

I've checked it. I've also read the chess.verhelst.org articles. I've read a lot of articles past these couple of days. All of them seem to be of the point of view of huge game trees and using the fasted seach algorithm to reach the goal. But as a discussion i wanted to know what i've to do in order to create a game tree of a chess game, and whether i've to create it on my own by playing chess. I've almost finalised on the board and piece representation part of the game. All i want is now figure out how to create the game tree. I've also read that there are a lot of chess programs which have huge databases. Can someone direct these databases to me. I'm continuing to seach the net for a low - end game tree for chess as i cannot represent a huge game tree as part of my program. i've limited storage and processing power to create my chess game.

You don't need a lot of memory to explore a huge tree in a game like chess. One common way of doing this is having a single global board, on which you make moves and then undo them. The tree isn't stored anywhere. You just generate moves as you need them and at any given time you only need to have in memory the moves that are legal from positions in the branch that leads to the current position you are evaluating.

Some partial C++:

class Board {  ...};Board global_board;class Move {  ...};...int alpha_beta(int alpha, int beta, int depth, bool wtm /*White To Move*/){  if(depth<=0)    return static_eval(alpha,beta,wtm);  // You should probably call quiescence_search() here, instead of static_eval()  // I'm just trying to keep things simple    Move child[MAX_LEGAL_MOVES];  int num_children = generate_children(child); // fills up the array of moves    for(int i=0;i<num_children;++i){    UndoInfo ui = make_move(child);    int v = -alpha_beta(-beta,-alpha,depth-1,!wtm);    undo_move(child,ui);    if(alpha<ui){      alpha=ui;      if(beta<ui)        break; // beta cut    }  }  return alpha;}

As you see, I haven't stored the tree anywhere. Make sure that you understand how this works. Note that you need to keep some information to be able to undo a move. For instance, you need to know what castlings were allowed before the move, the number of moves towards the 50-move rule and the en-passant information. You may store here what type of piece has been captured, although I usually put that in the move for easy sorting.

You could keep `wtm' (whether it's white's turn or not) as part of the board description, but that complicates implementing the null-move pruning.

Instead of having a local array of moves at each level, it is a little bit better to have one big array of moves and have each call to alpha_beta point to a different segment in the big array.

Instead of generating all the moves, a lazy approach is probably faster. You can use a function next_move() when you need the next move and generate them as you need them (I think Crafty does this, but I have never found the time to do it on my own chess program).

That is exactly the way I was going to approach my problem. I did continue to read on a lot of techniques to approach my problem and came to the conclusion exactly mentioned by alvaro.

Hey,

I've done some pretty extensive experiments with my chess engine Fimbulwinter, which I let play humans on various chess servers.

Keeping in mind that "average" play strength is 1600 ELO, and that I am using a pretty rudimentry evaluator:

Max Tree Depth      ELO Strength3                   13504                   15005                   18006                   2000+

Also keep in mind this was mainly for Blitz play (between 3 and 15 minutes).

So to answer your question, you need to search to 4 ply to play an average game of chess. Most people can't play an average game of chess, and will probably lose to a 3 ply searcher.