473,706 Members | 5,467 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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

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/Standar...ary#Containers

http://en.wikipedia.org/wiki/Set_(computer_science)

Jan 11 '07 #1
9 3508
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/Standar...ary#Containers

http://en.wikipedia.org/wiki/Set_(computer_science)
Jan 11 '07 #2
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

Jan 11 '07 #3
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 SortedDictionar y 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
Jan 11 '07 #4
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
Jan 12 '07 #5
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

Jan 12 '07 #6
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



Jan 13 '07 #7
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
Jan 14 '07 #8
* raylopez99 <ra********@yah oo.com(2007-01-12) schrieb:
I did not realize programming chess playing was so difficult;
Well, if you ask me, it's easy to write a chess engine. To make it
really good is the difficult part.

Here is a simple plan:

1. Do the board and the move representation
2. Do the "do move" and "undo move" operations
3. Test it
4. Write a basic (pseudo legal) move generator
5. Test it
6. Complete the move generator: castling, en passant, promotion
7. Test it
8. If you generate pseudo legal move, write something to filter out
the illegal moves
9. Implement "perft". Use it to stress test the engine
10. Implement UCI and/or XBoard, play with Arena or Winboard
11. Implement a random player, just selects a random move from
the list of legal moves
12. Now you can play games, without any searching stuff, test!
13. Write a simple evaluation function
14. Evaluate each move and use the value add a weight factor to the
random move selector. Have fun.
15. Study MiniMax, NegaMax and Alpha-Beta. Make sure you really
understand how they work!
16. Implement it, write a move selector based on it.
17. Use the protocol to configure the search: infinite, fixed depth,
fixed node count, fixed time.
18. Add the more intelligent mode where you try to efficiently use the
remaining time for the right moves and don't waste time on on
interrupted or useless searches.
19. Complete the protocol.

Then you have a working engine. Might be hard work but it's not that
difficult. And it doesn't play too good. Then you can try to make engine
cleverer (and slower) by a more sophisticated evaluation function, or
faster and deeper searching by adding a transposition table, move
ordering, PVS or mtd(f), null move pruning, extensions, reductions,
razoring or just optimizing the code.
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.
Why do you dislike recursion?

A tree is recursive data structure. Traversing it by recursion is just
natural.

mfg, simon .... f'up2 rgcc, nothing to do with c#
Jan 14 '07 #9
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 " <raylope...@yah oo.comwrote:
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 '07 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
1741
by: nospam | last post by:
Hi all, I'd like to implement a tree of "tags" for a blog I'm writing for fun in PHP. Here's what a single tag looks like: CREATE TABLE tags ( name varchar(30) not null default '', id_self integer(12) not null primary key,
4
2770
by: Sasha | last post by:
Hi everyone, I would like to hear your opinions about a design solution I am contemplating. The problem I am following: Write an editor for a data structure that is recursive in nature. In other words it is a tree, where child nodes can contain links to parent nodes. And there multiple kind of nodes: Here is an example
32
5649
by: David Isaac | last post by:
I have no experience with database applications. This database will likely hold only a few hundred items, including both textfiles and binary files. I would like a pure Python solution to the extent reasonable. Suggestions? Thank you, Alan Isaac
10
5961
by: Will Honea | last post by:
I have a data set which I need to analyze but I am having a problem figuring out a structure for the database - or whether there are better ways of attacking the problem. The base data set is a large number of replies to a survey questionaire. I have adapted a NLP program to produce lexically annotated structural trees which appear to reasonably accurately reduce the text to descending trees. These trees consist of multiple nodes each...
9
7824
by: raylopez99 | last post by:
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...
8
1704
by: Travis | last post by:
I have a tree of pointers and I need the ability to search the tree for a specific node. The problem is I can't provide that pointer for the node I'm looking for as criteria. The only critieria I can provide is a node that is the same and will == true. So naturally this would work if my tree was not of pointers but of objects. Since it's of pointers, it compares my node criteria against every node in the tree and the memory addresses...
4
1574
by: =?Utf-8?B?MjJQb20=?= | last post by:
Hi All, This is all new to me so please be patient with me. What I have is a very large 'Al-In-One' program, not yet complete, that has over 70 Forms/Modules/Classes in it and needs to be broken up into smaller programs/modules that can be called from the main program. I understand that I would need to, via a Click Button to close one part down and open the new section, but how.
0
8693
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
9281
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
9150
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
9044
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
7899
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
5935
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4444
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
2
2497
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
2087
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.