Author: Russell Reagan
Date: 18:49:40 03/07/04
Go up one level in this thread
On March 07, 2004 at 19:43:17, Joshua Shriver wrote:
>What is the best way to store the data for a move generator?
I'm not 100% sure what you're asking.
Are you trying to store the entire game tree to be searched in memory? If so, I
don't think anyone does that (at least not anyone with a strong program, since
that requires an exponentially increasing amount of memory).
>Using all 18 pieces, since you can assume it should work with all 18 pieces
>taken into consideration.
Where are you getting the number 18 from? I count 32 total pieces, or 16 total
pieces per color, or 12 piece types, or 6 piece types per color. Maybe I'm
misunderstanding.
>Is this the best way to go about it? Or is there a more efficient way of holding
>the data for a move generator if not a tree.
It depends how you use the tree. If you are storing the entire tree to be
searched, then that is very inefficient. You'll run out of memory very fast. If
you are doing a depth first search with your structure, that is still somewhat
inefficient (and probably messy source code), because you don't need all of
those pointers. However, I am not entirely sure what you are doing with those 18
pointers, because I don't know why you are using 18 of them :-) So maybe I am
misunderstanding.
Typically, most chess programs don't ever store a tree like we think of a binary
tree and other kinds of trees in computer science. We just store the current
position, and the information needed to move from position to position. Each
position is a node in the tree, and a chess move is the information we need to
move from node to node. We just visit the nodes without really building or
storing a tree by making moves and undoing moves on a chess board. We save the
moves we have previously made so that we can undo them later, but that's it
(well, you need to backup castling rights, en passant square, and stuff like
that too).
Let's take a small tree for an example.
R
/ \
A D
/ \ / \
B C E F
R is the root node, and the rest of the capital letters are just nodes.
Lowercase letters are moves (see expanded tree below containing moves). So to
get from position 'R' to position 'A', we make move 'a'.
R
/ \
a d
/ \
A D
/ \ / \
b c e f
/ \ / \
B C E F
We have this small game tree which is not stored in memory (just what we would
store if we did store it). Let's assume we have a function to generate legal
moves for the current position, and a function to make a move, and one to undo a
move. We can get from position R to position B by the following:
make_move(a); // now we are at node A
move_move(b); // now we are at node B
To get back to the root node:
undo_move(b); // now we are at node A
undo_move(a); // now we are at node R
If we wanted to get from R to E, we would do:
make_move(d); // now we are at D
make_move(e); // now we are at E
So we can move from node to node that way, and all we ever have to store is the
list of moves we made to get where we are in the tree. So if we moved from R to
E, we only have to store moves d and e. That's a lot better than the entire
tree, or all of those pointers, IHMO :-)
There are plenty of simple open source chess programs you can take a look at to
see how it works in practice. TSCP is a popular one to learn from.
http://home.comcast.net/~tckerrigan/
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.