Movement storing system - Newbie's question, please help.
Guillem Barnolas
？i! to everyone. I've been in this newsgroup for a long period, but I
have almost never posted anything. It's mainly because I'm not a chess
programmer, though I'd want, and because I don't know how to start.
I've read lots of things about chess programming basics, alpha-beta,
etc, but in those articles they said you have to store the movements
as a tree. Well, I know how to make a binary tree, but not a
multi-leaf tree, and though I've started to understand it, one thing
Bob Hyatt told me once stunned me. He said you only store one ply at a
time, or something like this ( don't flame me if i'm wrong :-) ) but I
don't know how to do it. For example, imagine I decide to make a tree
in which each node is a record with it's value and 60 pointers to the
60 posible moves. Then if I'm looking at ply 3, when I have to come
back to the first movements I've lost them because I only stored one
ply at a time, and if I decide to store everything I can't go beyond
ply 3 because of the dimensions of the tree.
Yes, I know there is a lot of source code in the net, but I know very
little of C and they are all in C. If you could explain it in
Pseudo-Code I would be very pleased.
Robert Hyatt
Guillem Barnolas (guill...@redestb.es) wrote:
:
: ĄHi! to everyone. I've been in this newsgroup for a long period, but I
YOu don't store the complete tree in a depth-first search. For a 3
ply search with no captures, it would go something like this:
generate all moves at the root of the tree...
make one of them.
generate all moves for the opponent (ply=1)
make one of them
generate all moves for you (again, but now at ply=3 after two moves have
been made by the search)
make one of them.
evaluate the position.
unmake that move and make the next.
Evaluate...
continue until there are no more moves at ply=3.
back up to ply=2, unmake that move, make the next,
and come back to ply=3 and repeat the process again.
So all the storage you need is depth*BF, where BF is the
branching factor, or number of moves at each ply...
The storage for a 10 ply search is only (roughly) 40*10 = 400
moves. The tree for a 10 ply search is *huge* of course, but
we don't need to store it...
Dave
>
>I've read lots of things about chess programming basics, alpha-beta,
>etc, but in those articles they said you have to store the movements
>as a tree. Well, I know how to make a binary tree, but not a
>multi-leaf tree, and though I've started to understand it, one thing
>Bob Hyatt told me once stunned me. He said you only store one ply at a
>time, or something like this ( don't flame me if i'm wrong :-) ) but I
>don't know how to do it. For example, imagine I decide to make a tree
>in which each node is a record with it's value and 60 pointers to the
>60 posible moves. Then if I'm looking at ply 3, when I have to come
>back to the first movements I've lost them because I only stored one
>ply at a time, and if I decide to store everything I can't go beyond
>ply 3 because of the dimensions of the tree.
>
> Yes, I know there is a lot of source code in the net, but I know very
>little of C and they are all in C. If you could explain it in
>Pseudo-Code I would be very pleased.
Hello, Guillem
Welcome to the group. No, I wouldn't dream of flaming you if you were
wrong about alpha-beta, etc. I save that for those few who show a
startling lack of common courtesy and manners.
I'm a not too experienced programmer myself, so if Tom, Chris, Bob or
any more experienced programmer corrects anything here, by all means
take their advice. With that caveat, I'll say freely what I think:
** You're just too smart for your own good! ** <g>
In the chess "tree", well, there is *no* tree! That's just how it's
thought of for us conceptually challenged humans. The search never
needs all the other information you were wondering about because it is
a depth-first search. what you describe is needed to keep track of the
data for a breadth-first search. Now you know *why* we don't use
breadth-first search! We're too lazy to do all that coding work!
Depth first search is IMHO used by nearly every program because it
requires far less memory for a deep search, it's easier to debug for
us poor humans, and again, we're just too lazy to do it any other way!
This is a structured description of the AB Minimax procedure: (This is
one approach, not necessarily the fastest, best, etc.)
1. Determine if the level is the top level, or if the limit of search
has been reached, or if the level is a minimizing (mini) or
maximizing (maxi).
level.
1a. If it's the top level, make alpha = - 99999 (any really big
number will do) make beta = + 99999.
1b. If the search limit has been reached, get the static
evaluation of the position for the proper player. Save that
number.
1c. If the level is a mini level
1. Until all children are checked with the search, or alpha
gets bigger than beta.
a. Make beta = the given beta values or the values
reported by working on the children of the position,
whichever is smaller.
b. Use search on the next child of the current position,
passing along the current alpha and beta values.
2. Save beta value
1d. If the level is a maxi level:
1. Until all children are checked with search, or alpha is
bigger than beta:
a. Set alpha to the larger of the given alpha values and
the largest value reported by the search while working
on the children position.
b. Use the search on the next child of the current
position, passing along to it the current alpha and
beta values.
2. Save alpha value.
Since this search was first defined, many enhancements have been found
for it. Sliding "windows" of values for alpha-beta, progressive
deepening (also called iterative deepening), null-move, singular
extensions, etc.
But don't even worry about them for a w-h-i-l-e! That's what versions
2-10 of your software are for!!
I think the *only* way to really understand a-b mini-max search is to
clear off the dining room table, and get a chessboard set up with a
mate in 3 on the board. Have *very* few pieces on the board - just the
barest minimum. So the board is the root position, now have some
papers on hand that have a blank chessboard drawn on them.
Go by hand, slowly, through the moves, marking the child positions
onto a paper chessboard. Lay it out like the "tree" (which remember is
just representational, and doesn't exist, a virtual tree if you will)
now consider each move and the value (use material only and BIG number
for checkmate) for that move. Do the same for your opponents side. Put
your values up where they belong, the principal variation, score, etc.
By working with it by hand, in a very simplistic position, you'll be
able to follow it all the way thru to the end, and soon understand it
well.
I will attach the pseudo-code in "C" for alpha-beta also.
Good luck, and give the above plenty of time.
Regards,
Dave
P.S. Our group is smaller by two gifted chess programmers this week.
Both these men would still be with us if all of us (including them),
used more restraint and courtesy in our posts to this ng.
Sitting at our computers, we have every tool we need to masterfully
insult anyone; prince or pauper. We do *not* have the ability though,
to easily seek out understanding or common ground by talking to the
person face to face. I believe courtesy and restraint in the cyber
world is much more important here than in R/L, just for that reason.
If you have to get programming advice from guys like me, well, you'll
be beating those chess programs for years!<g>
Dave
begin 644 ABSEARCH.TXT
<encoded_portion_removed>
end
Dave
Just wanted to say thanks to all the posters that have made rgcc so
interesting and worthwhile:
KK, Bruce, Bas, Tim, Tom(s), Mike, Ed(s), Chris, Harald, Vincent,
Marcel, Dave C., Bill, Enrique, and of course, Bob H. (and many others
also.)
Whether highly skilled programmer or amateur chess computer fan, or
anything in between, your posts are what makes this ng good to read.
(Usually, anyway.) Whether it's a good cogent question from Bas (some
very good one's) or a well written product report up-date from Mclane
or KK, or technical advice from Bruce, Tom(s), or Bob,
Thanks, guys. Oh! and you too, Elizabeth! (Our bit board speed queen
tester)
Dave
Robert Hyatt
Dave (co...@sprintmail.com) wrote:
: Just wanted to say thanks to all the posters that have made rgcc so
: interesting and worthwhile:
: Dave
Just goes to show that anyone that wants to contribute can contribute. You
don't have to be an active program author with a strong program. All you
need is an idea, or a question, and the desire to follow it through or to
answer it. And thusly a star can/might/will be born... :)
David Eppstein
hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
> You don't store the complete tree in a depth-first search. ... all the
> storage you need is depth*BF, where BF is the branching factor, or
> number of moves at each ply...
My program (for a game other than chess) doesn't actually store the list
of all moves in a position, it just generates them one at a time on the
fly as needed. So the storage needed is really only O(depth).
BUT, in order to output the principal variation from the search (not
just the best move) I store principal variations from all nodes on the
current search path -- this is O(depth^2). Bob, how do you avoid this
quadratic space? Don't tell me you keep it in the hash table, you still
need information on the same number of nodes there, so it's not really
less space, it's just space shared with another part of the program.
Quadratic is still small enough not to worry about, though.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
epps...@ics.uci.edu http://www.ics.uci.edu/~eppstein/
Robert Hyatt
David Eppstein (epps...@euclid.ics.uci.edu) wrote:
: hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
: > You don't store the complete tree in a depth-first search. ... all the
: > storage you need is depth*BF, where BF is the branching factor, or
: > number of moves at each ply...
: My program (for a game other than chess) doesn't actually store the list
: of all moves in a position, it just generates them one at a time on the
: fly as needed. So the storage needed is really only O(depth).
: BUT, in order to output the principal variation from the search (not
: just the best move) I store principal variations from all nodes on the
: current search path -- this is O(depth^2). Bob, how do you avoid this
: quadratic space? Don't tell me you keep it in the hash table, you still
: need information on the same number of nodes there, so it's not really
: less space, it's just space shared with another part of the program.
I do exactly as I suspect you are doing... backing up the path when I
back up a best (not alpha or beta) value. I have an array PV[MAXPLY][MAXPLY]
to do this. It's basically "chickenfeed" as far as memory goes, of course...
I don't generate "on the fly" because I don't know how to do that for
captures, not knowing which will look best according to the "SEE" code.
I do generate captures first, and search the winners and non-losers, then
generate the rest... but not one at a time. To do 'em on the fly, I'd have
to revert back to MVV/LVA, which I didn't like, because it is difficult to
prune moves in the q-search without a trusty SEE score to check...
: Quadratic is still small enough not to worry about, though.
Tom Kerrigan
As far as I know, there is nothing wrong with this post, but I will say
something about actually storing moves in memory, which might help Mr.
Barnolas, too.
What you want to do is have an array of moves, like this:
|-----------------------------------------------------------------|
Cool graphics, eh? So anyway, let's say you're at the root position. You
generate moves to try, and put those moves at the beginning of the array...
|-----|-----------------------------------------------------------|
^
root moves
Now you play a root move and you want to search deeper, so you generate
moves for the position following that root move and save those moves after
the root moves...
|-----|-----|-----------------------------------------------------|
^
ply 2 moves
This way, when you go back to the root, you don't have to generate all
the moves again. For such a data structure, you need something like this:
move generator_data[GEN_STACK];
int ply_begin[MAX_PLY],ply_end[MAX_PLY];
Where ply_begin[2] is the number of the first move of the ply 2 move list
(in generator_data[]).
My simple chess program (~1000 lines long) uses this move saving system,
so you might want to check it out. http://www.frii.com/~kerrigan
Cheers,
Tom
Dave (co...@sprintmail.com) wrote:
: On Fri, 05 Sep 1997 12:15:59 GMT, guill...@redestb.es (Guillem
: Barnolas) wrote:
: Hello, Guillem
: Regards,
: Dave
:
:
Guillem Barnolas
kerr...@deimos.frii.com (Tom Kerrigan) wrote:
>As far as I know, there is nothing wrong with this post, but I will say
>something about actually storing moves in memory, which might help Mr.
>Barnolas.
:-)) It's the first time s'one calls me Mr. Barnolas, but it's
understandable, you don't know my age.
..
>(in generator_data[]).
>My simple chess program (~1000 lines long) uses this move saving system,
>so you might want to check it out. http://www.frii.com/~kerrigan
>Cheers,
>Tom
Lots of thanks, and I'll take a look at that program.