Best way of implementing a multi-node tree in C++? (or C#, a close cousin)

Discussion in 'C++' started by raylopez99, Jan 11, 2007.

  1. raylopez99

    raylopez99 Guest

    What's the best way of implementing a multi-node tree in C++? What I'm
    trying to do is traverse a tree of possible chess moves given an intial
    position (at the root of the tree). Since every chess position has
    around 30 moves, it would mean every node of the tree would have 30
    branches (on average), which in turn themselves would average about 30
    branches each.

    I can think of a variety of ways of implementing this, including a
    series of linked lists all pointing to the same header node at the
    root, but I would like to know if there's a practical 'best' way, since
    the tree will be traversed often, and it must be traversed quickly.
    There will be no additions to the tree besides making it grow bigger
    (longer, as move moves are added in a sequence). Certain branches will
    be pruned, but the tree does not have to be rebalanced after pruning
    (meaning the pruned branches will be simply marked as pruned but can
    stay where they are).

    Ideally I would like something already found in the .NET Standard
    Collection Classes or Generic Collection classes, which include:
    SortedList (key/value collection) and KeyedCollection, which are kinds
    of Sets/Maps it appears.

    BTW, nearly every reference I look shows as the sole example of tree a
    red-black binary tree, which is not that helpful to me, though I
    realize probably as a mathematical matter you can parse any multnode
    tree into a red-black binary tree.

    Thanks,

    RL

    Refs:

    http://en.wikipedia.org/wiki/Standard_Template_Library#Containers

    http://en.wikipedia.org/wiki/Set_(computer_science)
     
    raylopez99, Jan 11, 2007
    #1
    1. Advertising

  2. How close cousins C++? and C#, can be debated, but I'll leave that for
    some other time. Since you posted this in comp.lang.c++ you'll get a
    C++ answer from me, how to convert this to C# is up to you.

    On Jan 11, 10:21 am, "raylopez99" <> wrote:
    > What's the best way of implementing a multi-node tree in C++? What I'm
    > trying to do is traverse a tree of possible chess moves given an intial
    > position (at the root of the tree). Since every chess position has
    > around 30 moves, it would mean every node of the tree would have 30
    > branches (on average), which in turn themselves would average about 30
    > branches each.


    So, you want different kinds of moves and from each move you want a
    list of all possible moves that can be performed after, and this will
    of course give you a tree-structure.

    > I can think of a variety of ways of implementing this, including a
    > series of linked lists all pointing to the same header node at the
    > root, but I would like to know if there's a practical 'best' way, since
    > the tree will be traversed often, and it must be traversed quickly.
    > There will be no additions to the tree besides making it grow bigger
    > (longer, as move moves are added in a sequence). Certain branches will
    > be pruned, but the tree does not have to be rebalanced after pruning
    > (meaning the pruned branches will be simply marked as pruned but can
    > stay where they are).


    How you store the list of possible moves depend on a number of things,
    like the variance of the number of moves, if 30 is max but average is 5
    then perhaps you don't want to allocate memory for 30 in each node. If
    you plan to have really many moves in the tree you might want to
    actually remove pruned moves to make room for adding more, this and the
    above would indicate a dynamic structure so a list is not a bad idea.

    > Ideally I would like something already found in the .NET Standard
    > Collection Classes or Generic Collection classes, which include:
    > SortedList (key/value collection) and KeyedCollection, which are kinds
    > of Sets/Maps it appears.


    As I said you'll get C++ from me, and I'll go for a std::list, which is
    a normal double-linked list. You should be able to find one in any
    decent collections library.

    > BTW, nearly every reference I look shows as the sole example of tree a
    > red-black binary tree, which is not that helpful to me, though I
    > realize probably as a mathematical matter you can parse any multnode
    > tree into a red-black binary tree.


    Red-black, balanced and whatnot trees are all good if you store values
    with a key and want to be able to retrieve the value quickly given a
    specific key. Your problem is not one of those.

    Now for my solution:

    First declare a class representing a move

    class Move {
    protected:
    std::list<Move> moves; // list of possible moves after this
    public:
    void addMove(Move& m); // Adds a move
    const std::list<Move> getMoves() const;
    }

    Now, you might want to create subclasses of this move representing each
    of the possible moves (or subsections of possible moves), or you might
    want to add the details describing a move straight in the Move-class,
    either way should be fine as long as you follow Liskov's Substitution
    Principle*.

    So when you want to traverse the tree of moves you can define a
    recursive function like so:

    void traversMoves(Move& m) {
    std::list<Move>::iterator iter, end;
    end = m.getList().end();
    iter = m.getList().begin();
    for (; iter != end; ++iter) {
    foo(*iter);
    traverseMoves(*iter);
    }
    }

    This will traverse the move-tree and call the function foo() with each
    Move as a parameter, to make it more general you might want to create
    functor-objects which you pass as an argument to the
    traverseMoves()-function instead of hard-coding the foo()-function.

    Hope that this will give you some idea on how to proceed.

    * http://www.objectmentor.com/resources/articles/lsp.pdf

    --
    Erik Wikström
     
    =?iso-8859-1?q?Erik_Wikstr=F6m?=, Jan 11, 2007
    #2
    1. Advertising

  3. raylopez99

    Brian Gideon Guest

    Well, since I've actually written a strong playing chess engine I think
    I can help. My first question is...are you actually wanting to write
    an intelligent engine or just scan all of the possible moves?

    raylopez99 wrote:
    > What's the best way of implementing a multi-node tree in C++? What I'm
    > trying to do is traverse a tree of possible chess moves given an intial
    > position (at the root of the tree). Since every chess position has
    > around 30 moves, it would mean every node of the tree would have 30
    > branches (on average), which in turn themselves would average about 30
    > branches each.
    >


    The best way is to not store the moves at all. The branching factor,
    which I think is a little higher than 30, will cause the tree to grow
    so quickly that you'll run out of memory. The complexity of the tree
    is O(b^n) where b is the average branching factor and n is the number
    plies. Do the numbers. It's not pretty.

    > I can think of a variety of ways of implementing this, including a
    > series of linked lists all pointing to the same header node at the
    > root, but I would like to know if there's a practical 'best' way, since
    > the tree will be traversed often, and it must be traversed quickly.
    > There will be no additions to the tree besides making it grow bigger
    > (longer, as move moves are added in a sequence). Certain branches will
    > be pruned, but the tree does not have to be rebalanced after pruning
    > (meaning the pruned branches will be simply marked as pruned but can
    > stay where they are).
    >


    It really depends on what the intent of the application is. Are you
    asking because you want to create an intelligent player or just scan
    the possible moves?

    > Ideally I would like something already found in the .NET Standard
    > Collection Classes or Generic Collection classes, which include:
    > SortedList (key/value collection) and KeyedCollection, which are kinds
    > of Sets/Maps it appears.


    None of those will work.

    >
    > BTW, nearly every reference I look shows as the sole example of tree a
    > red-black binary tree, which is not that helpful to me, though I
    > realize probably as a mathematical matter you can parse any multnode
    > tree into a red-black binary tree.


    A red-black has a specific purpose. It happens to be the one of the
    most common implementation for sorted dictionaries. A sorted
    dictionary has absolutely nothing to do with decision trees. No, you
    can't transform a decision tree into a red-black tree.

    >
    > Thanks,
    >
    > RL
    >
    > Refs:
    >
    > http://en.wikipedia.org/wiki/Standard_Template_Library#Containers
    >
    > http://en.wikipedia.org/wiki/Set_(computer_science)
     
    Brian Gideon, Jan 11, 2007
    #3
  4. raylopez99

    raylopez99 Guest

    Thanks Brian Gideon for replying! My comments below.

    Brian Gideon wrote:
    > Well, since I've actually written a strong playing chess engine I think
    > I can help. My first question is...are you actually wanting to write
    > an intelligent engine or just scan all of the possible moves?


    I just program for fun, as a hobby. Since I also play chess, I figured
    I would write a two-ply alpha-beta algorithm for generating the best
    moves from any given position (within this event horizon). I have a
    number of books on this subject (some with pseudo-code), so I'm
    generally familiar with the subject (as a amateur). If you have open
    source code (dumbed down or otherwise, since from what I can tell the
    "move ordering" algorithm is the proprietary part of any chess engine,
    since, like you say, after around ply 4 you cannot exhaustively search
    the entire chess tree), please feel free to send it my way or otherwise
    post it in some FTP public directory)

    >
    > raylopez99 wrote:
    > > What's the best way of implementing a multi-node tree in C++? What I'm
    > > trying to do is traverse a tree of possible chess moves given an intial
    > > position (at the root of the tree). Since every chess position has
    > > around 30 moves, it would mean every node of the tree would have 30
    > > branches (on average), which in turn themselves would average about 30
    > > branches each.
    > >

    >
    > The best way is to not store the moves at all. The branching factor,
    > which I think is a little higher than 30, will cause the tree to grow
    > so quickly that you'll run out of memory. The complexity of the tree
    > is O(b^n) where b is the average branching factor and n is the number
    > plies. Do the numbers. It's not pretty.


    Very interesting! So you would have a predefined way of traversing the
    tree and perform "alpha-beta" (from memory, sorry if my lingo is off)
    "on the fly", with a suitable cutoff, pruning the tree as you go from
    right to left or whatever order you traverse. Never even thought of
    this. Then you can store the best moves in a stack and pop/push the
    winner candidate moves to the top of the stack. Very clever, as this
    saves memory (if this is what was in mind). BTW it amazes me that
    ChessBase commercial computer programs can find the best move X% of the
    time (with X around 90% it seems) with just five seconds of time
    elapsed. The way I code, I can't get anything to work that fast (and
    it seems C++.NET is very resource hog intensive--getting a console
    "Hello World" appl to run seems to take a few seconds on a modern
    Pentium 4 system, LOL.

    >
    > > I can think of a variety of ways of implementing this, including a
    > > series of linked lists all pointing to the same header node at the
    > > root, but I would like to know if there's a practical 'best' way, since
    > > the tree will be traversed often, and it must be traversed quickly.
    > > There will be no additions to the tree besides making it grow bigger
    > > (longer, as move moves are added in a sequence). Certain branches will
    > > be pruned, but the tree does not have to be rebalanced after pruning
    > > (meaning the pruned branches will be simply marked as pruned but can
    > > stay where they are).
    > >

    >
    > It really depends on what the intent of the application is. Are you
    > asking because you want to create an intelligent player or just scan
    > the possible moves?


    Actually both. Though I would like to scan all the moves for 2 ply (I
    don't think it will cost too much memory)

    >
    > > Ideally I would like something already found in the .NET Standard
    > > Collection Classes or Generic Collection classes, which include:
    > > SortedList (key/value collection) and KeyedCollection, which are kinds
    > > of Sets/Maps it appears.

    >
    > None of those will work.
    >


    Far from me to argue with you, but I do recall a binary tree can be
    made from a Map/Set (this was my motivation for writing the above).


    > >
    > > BTW, nearly every reference I look shows as the sole example of tree a
    > > red-black binary tree, which is not that helpful to me, though I
    > > realize probably as a mathematical matter you can parse any multnode
    > > tree into a red-black binary tree.

    >
    > A red-black has a specific purpose. It happens to be the one of the
    > most common implementation for sorted dictionaries. A sorted
    > dictionary has absolutely nothing to do with decision trees. No, you
    > can't transform a decision tree into a red-black tree.
    >


    OK. Probably true, and if you say so. Though if I were betting money
    some clever Russian probably could do some transformation.

    Thanks for replying. Just collecting information for now. I do have
    Professor Hyatt's open source code ("Crafty") but it's kind of hard for
    me to follow.

    RL
     
    raylopez99, Jan 11, 2007
    #4
  5. raylopez99

    Brian Gideon Guest

    First, let me say this. Writing a chess engine is *incredibly*
    difficult. But, don't get discouraged. Take it one step at a time.

    raylopez99 wrote:
    > I just program for fun, as a hobby. Since I also play chess, I figured
    > I would write a two-ply alpha-beta algorithm for generating the best
    > moves from any given position (within this event horizon). I have a
    > number of books on this subject (some with pseudo-code), so I'm
    > generally familiar with the subject (as a amateur).


    Start by getting the minimax algorithm to work then move to alpha-beta
    pruning.

    > If you have open
    > source code (dumbed down or otherwise, since from what I can tell the
    > "move ordering" algorithm is the proprietary part of any chess engine,
    > since, like you say, after around ply 4 you cannot exhaustively search
    > the entire chess tree), please feel free to send it my way or otherwise
    > post it in some FTP public directory)
    >


    There are plenty of resources available on the net. You just have to
    know what to google for. Don't worry about move ordering right now.
    Take small steps. Get the minimax algorithm working, then add
    alpha-beta pruning, and then worry about move ordering. Here's a
    resource I've used in the past. Hopefully that will get you started.

    http://www.seanet.com/~brucemo/topics/topics.htm

    > > The best way is to not store the moves at all. The branching factor,
    > > which I think is a little higher than 30, will cause the tree to grow
    > > so quickly that you'll run out of memory. The complexity of the tree
    > > is O(b^n) where b is the average branching factor and n is the number
    > > plies. Do the numbers. It's not pretty.

    >
    > Very interesting! So you would have a predefined way of traversing the
    > tree and perform "alpha-beta" (from memory, sorry if my lingo is off)
    > "on the fly", with a suitable cutoff, pruning the tree as you go from
    > right to left or whatever order you traverse. Never even thought of
    > this.


    Yes, I suppose that's one way of looking at it. The important thing is
    that you prune so that you don't have to even examine parts of the
    tree. Let me back track a little bit though. It is good to store
    small parts of the tree. It's usually done in what's called a
    transposition table which has a fixed and limited size. It's purpose
    is to recognize positions that have already been examined. Chess is a
    game where different paths can lead to the same position.

    > Then you can store the best moves in a stack and pop/push the
    > winner candidate moves to the top of the stack. Very clever, as this
    > saves memory (if this is what was in mind).


    Yep, all of these algorithms visit one node at a time and use the
    function call stack to do so. An actual tree is never really built in
    memory.

    > BTW it amazes me that
    > ChessBase commercial computer programs can find the best move X% of the
    > time (with X around 90% it seems) with just five seconds of time
    > elapsed. The way I code, I can't get anything to work that fast (and
    > it seems C++.NET is very resource hog intensive--getting a console
    > "Hello World" appl to run seems to take a few seconds on a modern
    > Pentium 4 system, LOL.
    >


    Those programs are *incredibly* sophisticated. Their speed comes from
    a combination of the algorithms that are used and how a position is
    represented. For example, the algorithms don't stop at alpha-beta.
    There's the principal variation search (PVS) and MTD(f) algorithms that
    are generally better. I believe most (?) engines use a form of the PVS
    algorithm. The way a position is represented is also important. Most
    use a bitboard strategy where the position is completely defined in
    small number 64-bit fields. That way moves are generated by doing low
    level bit masks and shifts.

    > >
    > > > I can think of a variety of ways of implementing this, including a
    > > > series of linked lists all pointing to the same header node at the
    > > > root, but I would like to know if there's a practical 'best' way, since
    > > > the tree will be traversed often, and it must be traversed quickly.
    > > > There will be no additions to the tree besides making it grow bigger
    > > > (longer, as move moves are added in a sequence). Certain branches will
    > > > be pruned, but the tree does not have to be rebalanced after pruning
    > > > (meaning the pruned branches will be simply marked as pruned but can
    > > > stay where they are).
    > > >

    > >
    > > It really depends on what the intent of the application is. Are you
    > > asking because you want to create an intelligent player or just scan
    > > the possible moves?

    >
    > Actually both. Though I would like to scan all the moves for 2 ply (I
    > don't think it will cost too much memory)
    >
    > >
    > > > Ideally I would like something already found in the .NET Standard
    > > > Collection Classes or Generic Collection classes, which include:
    > > > SortedList (key/value collection) and KeyedCollection, which are kinds
    > > > of Sets/Maps it appears.

    > >
    > > None of those will work.
    > >

    >
    > Far from me to argue with you, but I do recall a binary tree can be
    > made from a Map/Set (this was my motivation for writing the above).


    A chess game tree isn't binary though. SortedList uses an array
    implementation. You may be thinking of the SortedDictionary which uses
    a red-black tree implementation. However, neither are really suitable
    for storing a chess position.

    > > > BTW, nearly every reference I look shows as the sole example of tree a
    > > > red-black binary tree, which is not that helpful to me, though I
    > > > realize probably as a mathematical matter you can parse any multnode
    > > > tree into a red-black binary tree.

    > >
    > > A red-black has a specific purpose. It happens to be the one of the
    > > most common implementation for sorted dictionaries. A sorted
    > > dictionary has absolutely nothing to do with decision trees. No, you
    > > can't transform a decision tree into a red-black tree.
    > >

    >
    > OK. Probably true, and if you say so. Though if I were betting money
    > some clever Russian probably could do some transformation.
    >


    I doubt it. First, a red-black tree is used to store key-value pairs
    in a sorted order. What would it mean to store chess positions in a
    sorted order anyway? Also, a red-black tree is binary so unless you
    only plan on storing 2 moves per position then there's an even more
    fundamental conflict.


    > Thanks for replying. Just collecting information for now. I do have
    > Professor Hyatt's open source code ("Crafty") but it's kind of hard for
    > me to follow.


    It's hard for me to follow as well. Crafty is an excellent program.
    Mine couldn't even come close to beating it :(. I had mine good enough
    to beat GNU Chess half the time though :)

    >
    > RL
     
    Brian Gideon, Jan 11, 2007
    #5
  6. raylopez99

    raylopez99 Guest

    Thanks again Brian Gideon for the reply.

    I did not realize programming chess playing was so difficult; after all
    the "eight queens" problem is a standard CSci exercise to illustrate
    recursion; also moving chess pieces is a standard exercise in a C# book
    I have by Deitel.

    Some of the stuff about move generation with bitmaps and quiescent
    search makes sense. The website link I had from a previous search;
    thanks.

    As a programming exercise I might just build a 2 ply chess playing
    engine with min-max and no alpha-beta, in view of the work involved. I
    have a book by Brian Flaming with source code on a N-th branching tree,
    in view of the fact that none of the .NET or generic collection
    containers seem to work for chess.

    If you care to answer: which is used more often in chess--recursion or
    iteration? I generally don't like recursion but for traversing a tree
    perhaps it's necessary.

    BTW, I recall a 'neural' learning chess program was offered in beta
    form--it looked like some students resume building exercise or senior
    project--if chess programming according to the alpha-beta/ min-max is
    difficult, imagine a non-traditional algortihm like a neural or genetic
    algorithm! http://en.wikipedia.org/wiki/Genetic_algorithm

    BTW, once quantum computers are perfected, the chess tree can be solved
    'instantaeously'--so in theory you can beat even the best chess
    program, since the entire tree will be searched at once (sci-fi for now
    though).

    RL

    Brian Gideon wrote:
    > First, let me say this. Writing a chess engine is *incredibly*
    > difficult. But, don't get discouraged. Take it one step at a time.
    >
    > r
     
    raylopez99, Jan 12, 2007
    #6
  7. raylopez99

    raylopez99 Guest

    Just to complete this thread, another open source code project for a
    chess playing engine used for pedagogical purposes is: "grey matter" /
    Gray Matter : found here:
    http://gray-matter.googlecode.com/svn/trunk/src/

    Trouble is, they try and do "too much" (they should have a dumbed down
    version just for teaching purposes; one that doesn't even check for 50
    move draw rule, en passant, etc), and it's hard to follow this code,
    though you can tell roughly what they are doing.

    RL
     
    raylopez99, Jan 12, 2007
    #7
  8. raylopez99

    Brian Muth Guest

    Brian Muth, Jan 13, 2007
    #8
  9. raylopez99

    raylopez99 Guest

    Of course I have. But it's one thing to beat Kasparov, another to
    write a tiny chess playing program. I heard somebody even programmed
    an Excel spreadsheet to play chess.

    RL

    Brian Muth wrote:
    > > I did not realize programming chess playing was so difficult...

    >
    > Some of the best minds have worked on this problem over the decades. Have
    > you not heard of the Deep Blue project?
    >
    > http://en.wikipedia.org/wiki/Deep_Blue
    > http://www.research.ibm.com/deepblue/home/html/b.html
    >
    > Brian
     
    raylopez99, Jan 14, 2007
    #9
  10. raylopez99

    Guest

    Hello, RL!

    I'm the primary author of Gray Matter. It's largely a 1-man project
    (with just some feedback from my friends). I was searching for my own
    project when I came across your message, and I'm very interested.

    I like your idea of a "dumbed down" version. I may fork the code and
    simplify it as far as possible. Also, how is it hard to follow? I'd
    like to make it more clear! I'd appreciate your feedback, and I'd
    also be glad to grant you commit privileges.

    Thanks,
    Raj

    On Jan 12, 5:01 pm, "raylopez99" <> wrote:
    > Just to complete this thread, another open source code project for a
    > chess playing engine used for pedagogical purposes is: "grey matter" /
    > Gray Matter : found here:http://gray-matter.googlecode.com/svn/trunk/src/
    >
    > Trouble is, they try and do "too much" (they should have a dumbed down
    > version just for teaching purposes; one that doesn't even check for 50
    > move draw rule, en passant, etc), and it's hard to follow this code,
    > though you can tell roughly what they are doing.
    >
    > RL
     
    , Feb 11, 2007
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    1,495
  2. Tjerk Wolterink
    Replies:
    2
    Views:
    1,443
    Dimitre Novatchev
    Aug 24, 2006
  3. Peter Mueller
    Replies:
    6
    Views:
    4,586
    Stefan Ram
    Jan 13, 2008
  4. John Bankhead

    Null parent node on custom tree node after populate on demand

    John Bankhead, Dec 4, 2006, in forum: ASP .Net Web Controls
    Replies:
    0
    Views:
    286
    John Bankhead
    Dec 4, 2006
  5. Replies:
    35
    Views:
    305
    Robert Klemme
    Nov 17, 2007
Loading...

Share This Page