|
Main
Date: 11 Jan 2007 01:21:25
From: raylopez99
Subject: 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 ked 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)
|
|
|
Date: 11 Feb 2007 00:04:16
From:
Subject: Re: Best way of implementing a multi-node tree in C++? (or C#, a close cousin)
|
Hello, RL! I'm the priy 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" <[email protected] > 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
|
|
Date: 14 Jan 2007 03:50:57
From: raylopez99
Subject: Re: Best way of implementing a multi-node tree in C++? (or C#, a close cousin)
|
Simon Krahnke wrote: > 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. This part I don't understand. I thought min/max and Alpha-Beta took care of this, regarding "useless" searches, unless you define "interrupted" searches as "useless" (that is, an even better move exists but for the interruption) > Why do you dislike recursion? > > A tree is recursive data structure. Traversing it by recursion is just > natural. Recursion is a last resort in my book. I rather get an error in an itteration than a recusion; the latter seems to blow up faster than the former, also recursion seems to use more memory I recall. But once a routine is debugged and stable, then of course all's well.
|
|
Date: 14 Jan 2007 02:44:34
From: raylopez99
Subject: Re: Best way of implementing a multi-node tree in C++? (or C#, a close cousin)
|
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
|
|
Date: 12 Jan 2007 15:01:52
From: raylopez99
Subject: Re: Best way of implementing a multi-node tree in C++? (or C#, a close cousin)
|
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
|
|
Date: 12 Jan 2007 14:40:52
From: raylopez99
Subject: Re: Best way of implementing a multi-node tree in C++? (or C#, a close cousin)
|
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
|
| |
Date: 12 Jan 2007 16:17:49
From: Brian Muth
Subject: Re: Best way of implementing a multi-node tree in C++? (or C#, a close cousin)
|
> 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
|
|
Date: 11 Jan 2007 06:27:19
From: Brian Gideon
Subject: Re: Best way of implementing a multi-node tree in C++? (or C#, a close cousin)
|
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 ked 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
|
|
Date: 11 Jan 2007 05:33:55
From: raylopez99
Subject: Re: Best way of implementing a multi-node tree in C++? (or C#, a close cousin)
|
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 ked 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
|
|
Date: 11 Jan 2007 02:55:48
From: Brian Gideon
Subject: Re: Best way of implementing a multi-node tree in C++? (or C#, a close cousin)
|
Brian Gideon wrote: > Well, since I've actually written a strong playing chess engine I think > I can help. I didn't realize this was cross-posted to rec.games.chess.computer. If I had I wouldn't have bothered answering since there are so many of you in this group that know so much more than I.
|
|
Date: 11 Jan 2007 02:37:51
From: Brian Gideon
Subject: Re: Best way of implementing a multi-node tree in C++? (or C#, a close cousin)
|
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 ked 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)
|
| |
Date: 14 Jan 2007 23:07:42
From: Simon Krahnke
Subject: Re: Best way of implementing a multi-node tree in C++? (or C#, a
|
* raylopez99 <[email protected] > (12:50) schrieb: > Simon Krahnke wrote: > > >> 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. > > This part I don't understand. I thought min/max and Alpha-Beta took > care of this, regarding "useless" searches, unless you define > "interrupted" searches as "useless" (that is, an even better move > exists but for the interruption) Well, the standard search technique is iterative deepening. That is, you start searching with Alpha-Beta with a depth of 1 to 6, depending on how fast your engine is, then you sort your first moves according to the results of that search and then you search again but now one ply deeper, and so on until you decide to stop the search. Pseudo-Code: for(int depth = 3; depth < MAXDEPTH; depth++) for each move do move result[move] = alpha_beta(depth-1) undo move return when time is up[*] sort moves by result[move] return By interrupted search I mean: Inside Alpha-Beta you find out that the time is up and stop the search. You have no result for that interrupted search so the time you spent on it was wasted. By useless search I mean: You complete Alpha-Beta on one move, but don't use the result. That can happen if you just searched your first move again and decide to stop at [*]. You just have one result, that's not enough for sorting. So the complete search was wasted. > Recursion is a last resort in my book. What book? > I rather get an error in an itteration than a recusion; Iteration is just a special kind of recursion. If you want to do the kind of recursion needed in minimax in iteration style you need an explicit stack. Also the maxim recursion depth is about 50 when your engine is really fast. > the latter seems to blow up faster than the > former, also recursion seems to use more memory I recall. Only badly implemented recursion. > But once a routine is debugged and stable, then of course all's well. If it's buggy it's better to "blow up" fast. Crash early. mfg, simon .... l
|
| |
Date: 14 Jan 2007 12:14:18
From: Simon Krahnke
Subject: Re: Best way of implementing a multi-node tree in C++? (or C#, a
|
* raylopez99 <[email protected] > (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#
|
|