Re: [computer-go] Congratulations to David Fotland and Many Faces
On Feb 16, 2009, at 5:45 PM, Andy wrote: See attached a copy of the .sgf. It was played private on KGS so you can't get it there directly. One of the admins cloned it and I saved it off locally. I changed the result to be B+4.5 instead of W+2.5. Here is another copy of the game record, with the score corrected, but also containing the original comments, as well as a clarification of the rules used. JKerwin-ManyFaces1.sgf Description: Binary data ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] static evaluators for tree search
At the moment I (and another member of my group) are doing research on applying machine learning to constructing a static evaluator for Go positions (generally by predicting the final ownership of each point on the board and then using this to estimate a probability of winning). We are looking for someone who might be willing to help us build a decent tree search bot that can have its static evaluator easily swapped out so we can create systems that actually play over GTP. As much as we try to find quantitative measures for how well our static evaluators work, the only real test is to build them into a bot. Also, if anyone knows of an open source simple tree search bot (perhaps alpha-beta or something almost chess like) for Go, we might be able to modify it ourselves. The expertise of my colleague and I is in machine learning, not in tree search (although if worst comes to worst I will write my own simple alpha-beta searcher). We would be eager to work together with someone on this list to try and create a competitive bot. We might at some point create a randomized evaluator that returns win or loss nondeterministically for a position instead of a deterministic score, so an ideal collaborator would also have some experience with implementing monte carlo tree search (we could replace playouts with our evaluator to some extent perhaps). But more important is traditional, chess-like searching algorithms. If anyone is interested in working with us on this, please let me know! We have a prototype static evaluator complete that is producing sane board ownership maps, but we will hopefully have many even better ones soon. - George ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] static evaluators for tree search
I'd be more than happy to work with you and the other members of your
group. I'm getting close to wrapping up a restructuring of my bot that
allows easily swapping out evaluation methods and search techniques.
As an example, here's the code that does a few basic MC searches:
11 static if (searchMethod == pureMC || searchMethod == UCB){
12 alias node!(gameSource, binomial).onePly moveData;
13 alias onePlySearcher!(gameSource, moveData) searchBase;
14 }
15 else static if (searchMethod == UCT){
16 alias node!(gameSource, binomial).multiPly moveData;
17 alias multiPlySearcher!(gameSource, moveData) searchBase;
18 }
19 else
20 static assert(0, Don't know what kind of search base to use
for search method ' ~ searchBase ~ ');
...
65 class searcher : searchBase{
66 this(int nThreads){ super(nThreads); }
67 override int pickMoveForPlayout(moveData searchNode, ref Random
gen){
68 static if (searchMethod == pureMC)
69 return
moveSelectionMethods.pickRandomMove(searchNode, gen);
70 else static if (searchMethod == UCB || searchMethod
== UCT)
71 return
moveSelectionMethods.pickHighestConfidenceBound!(sqrt(log(searchNode.simulations+1)))(searchNode,
gen);
72 }
73 override int pickMoveForReal(moveData searchNode, ref Random
gen){
74 static if (searchMethod == pureMC)
75 return
moveSelectionMethods.pickMaxValue(searchNode, gen);
76 else static if (searchMethod == UCB || searchMethod
== UCT)
77 return
moveSelectionMethods.pickMostVisited(searchNode, gen);
78 }
79 }
The prior version of my bot included alpha-beta as an option, and there's no
reason for me to not do that again with this version. I won't make the
alpha-beta multi-thread capable without significant help though (I don't
know of any simple techniques to do so).
On Tue, Feb 17, 2009 at 12:27 PM, George Dahl george.d...@gmail.com wrote:
At the moment I (and another member of my group) are doing research on
applying machine learning to constructing a static evaluator for Go
positions (generally by predicting the final ownership of each point
on the board and then using this to estimate a probability of
winning). We are looking for someone who might be willing to help us
build a decent tree search bot that can have its static evaluator
easily swapped out so we can create systems that actually play over
GTP. As much as we try to find quantitative measures for how well our
static evaluators work, the only real test is to build them into a
bot.
Also, if anyone knows of an open source simple tree search bot
(perhaps alpha-beta or something almost chess like) for Go, we might
be able to modify it ourselves.
The expertise of my colleague and I is in machine learning, not in
tree search (although if worst comes to worst I will write my own
simple alpha-beta searcher). We would be eager to work together with
someone on this list to try and create a competitive bot. We might at
some point create a randomized evaluator that returns win or loss
nondeterministically for a position instead of a deterministic score,
so an ideal collaborator would also have some experience with
implementing monte carlo tree search (we could replace playouts with
our evaluator to some extent perhaps). But more important is
traditional, chess-like searching algorithms.
If anyone is interested in working with us on this, please let me
know! We have a prototype static evaluator complete that is producing
sane board ownership maps, but we will hopefully have many even better
ones soon.
- George
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: static evaluators for tree search
While your goal is laudable, I'm afraid there is no such thing as a simple tree search with a plug-in evaluator for Go. The problem is that the move generator has to be very disciplined, and the evaluator typically requires elaborate and expensive to maintain data structures. It all tends to be very convoluted and full of feedback loops, in addition to the actual alpha-beta which is trivial by comparison. If you look at GnuGo or some other available program, I'm pretty sure you'll find a line of code where the evaluator is called, and you could replace it, but you'll find it's connected to a pile of spaghetti. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: static evaluators for tree search
I am aware such a decoupled program might not exist, but I don't see why one can't be created. When you say the move generator has to be very disciplined what do you mean? Do you mean that the evaluator might be used during move ordering somehow and that generating the nodes to expand is tightly coupled with the static evaluator? - George On Tue, Feb 17, 2009 at 12:55 PM, Dave Dyer dd...@real-me.net wrote: While your goal is laudable, I'm afraid there is no such thing as a simple tree search with a plug-in evaluator for Go. The problem is that the move generator has to be very disciplined, and the evaluator typically requires elaborate and expensive to maintain data structures. It all tends to be very convoluted and full of feedback loops, in addition to the actual alpha-beta which is trivial by comparison. If you look at GnuGo or some other available program, I'm pretty sure you'll find a line of code where the evaluator is called, and you could replace it, but you'll find it's connected to a pile of spaghetti. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: static evaluators for tree search
Do you mean that the evaluator might be used during move ordering somehow and that generating the nodes to expand is tightly coupled with the static evaluator? That's the general idea. No search program can afford to use a fan-out factor of 361. The information about what to cut has to come from somewhere. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: static evaluators for tree search
Do you mean that the evaluator might be used during move ordering somehow and that generating the nodes to expand is tightly coupled with the static evaluator? That's the general idea. No search program can afford to use a fan-out factor of 361. The information about what to cut has to come from somewhere. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] static evaluators for tree search
A simple alfabeta searcher will only get a few plies deep on 19x19, so it won't be very useful (unless your static evaluation function is so good that it doesn't really need an alfabeta searcher) Dave Van: computer-go-boun...@computer-go.org namens George Dahl Verzonden: di 17-2-2009 18:27 Aan: computer-go Onderwerp: [computer-go] static evaluators for tree search At the moment I (and another member of my group) are doing research on applying machine learning to constructing a static evaluator for Go positions (generally by predicting the final ownership of each point on the board and then using this to estimate a probability of winning). We are looking for someone who might be willing to help us build a decent tree search bot that can have its static evaluator easily swapped out so we can create systems that actually play over GTP. As much as we try to find quantitative measures for how well our static evaluators work, the only real test is to build them into a bot. Also, if anyone knows of an open source simple tree search bot (perhaps alpha-beta or something almost chess like) for Go, we might be able to modify it ourselves. The expertise of my colleague and I is in machine learning, not in tree search (although if worst comes to worst I will write my own simple alpha-beta searcher). We would be eager to work together with someone on this list to try and create a competitive bot. We might at some point create a randomized evaluator that returns win or loss nondeterministically for a position instead of a deterministic score, so an ideal collaborator would also have some experience with implementing monte carlo tree search (we could replace playouts with our evaluator to some extent perhaps). But more important is traditional, chess-like searching algorithms. If anyone is interested in working with us on this, please let me know! We have a prototype static evaluator complete that is producing sane board ownership maps, but we will hopefully have many even better ones soon. - George ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] static evaluators for tree search
You're right of course. We have a (relatively fast) move pruning algorithm that can order moves such that about 95% of the time, when looking at pro games, the pro move will be in the first 50 in the ordering. About 70% of the time the expert move will be in the top 10. So a few simple tricks like this shouldn't be too hard to incorporate. However, the main purpose of making a really *simple* alpha-beta searching bot is to compare the performance of static evaluators. It is very hard for me to figure out how good a given evaluator is (if anyone has suggestions for this please let me know) without seeing it incorporated into a bot and looking at the bot's performance. There is a complicated trade off between the accuracy of the evaluator and how fast it is. We plan on looking at how well our evaluators predicts the winner or territory outcome or something for pro games, but in the end, what does that really tell us? There is no way we are going to ever be able to make a fast evaluator using our methods that perfectly predicts these things. So I have two competing motivations here. First, I want to show that the evaluators I make are good somehow. Second, I want to build a strong bot. - George On Tue, Feb 17, 2009 at 2:04 PM, dave.de...@planet.nl wrote: A simple alfabeta searcher will only get a few plies deep on 19x19, so it won't be very useful (unless your static evaluation function is so good that it doesn't really need an alfabeta searcher) Dave Van: computer-go-boun...@computer-go.org namens George Dahl Verzonden: di 17-2-2009 18:27 Aan: computer-go Onderwerp: [computer-go] static evaluators for tree search At the moment I (and another member of my group) are doing research on applying machine learning to constructing a static evaluator for Go positions (generally by predicting the final ownership of each point on the board and then using this to estimate a probability of winning). We are looking for someone who might be willing to help us build a decent tree search bot that can have its static evaluator easily swapped out so we can create systems that actually play over GTP. As much as we try to find quantitative measures for how well our static evaluators work, the only real test is to build them into a bot. Also, if anyone knows of an open source simple tree search bot (perhaps alpha-beta or something almost chess like) for Go, we might be able to modify it ourselves. The expertise of my colleague and I is in machine learning, not in tree search (although if worst comes to worst I will write my own simple alpha-beta searcher). We would be eager to work together with someone on this list to try and create a competitive bot. We might at some point create a randomized evaluator that returns win or loss nondeterministically for a position instead of a deterministic score, so an ideal collaborator would also have some experience with implementing monte carlo tree search (we could replace playouts with our evaluator to some extent perhaps). But more important is traditional, chess-like searching algorithms. If anyone is interested in working with us on this, please let me know! We have a prototype static evaluator complete that is producing sane board ownership maps, but we will hopefully have many even better ones soon. - George ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: static evaluators for tree search
This is old and incomplete, but still is a starting point you might find useful http://www.andromeda.com/people/ddyer/go/global-eval.html General observations (from a weak player's point of view): Go is played on a knife edge between life and death. The only evaluator that matters is is this stone alive, and there are no known proxies that will not fall short a significant amount of the time. If you fall short once or twice in a game against a competent player, you will lose. General strategic considerations will play you false every time. -- Notwithstanding the above, improving general considerations will improve play, but not much. It's all about the minutia of the situation. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] static evaluators for tree search
On Tue, 2009-02-17 at 20:04 +0100, dave.de...@planet.nl wrote: A simple alfabeta searcher will only get a few plies deep on 19x19, so it won't be very useful (unless your static evaluation function is so good that it doesn't really need an alfabeta searcher) I have to say that I believe this is very simplistic, and a lot of people have said things like this so you are certainly not alone. But how deep it goes is not particularly relevant, it's only a very small part of the picture. Before MCTS programs were playing reasonably well with continuous refinements to 1 ply searches. You can probably conceptually separate a tree searching program into 3 parts, and in this sense alpha/beta is no different than MCTS: 1. search 2. selectivity 3. evaluation selectivity is a nebulous term which involves all kinds of decisions about what to do inside the tree. It all boils down to 1 thing however, when to stop and when not to (and possibly what score to assume.) Evaluation has always been the most important part of any tree searching program and alpha/beta just doesn't work without it. Even if you search to the very end of a game, such as tic-tac-toe, you must know whether the game is a win, loss or draw, so you are forced to evaluate in the non-recursive sense.When you cannot go to the end of the game, which is true of any interesting game before it's played out, you really must have a high quality evaluation. The interesting part of MCTS, is not the TS part, it's the MC part. That's the part that does the evaluation. I am convinced that the tree search part could be done in a number of ways which can be seen as more or less equivalent. Even in the papers on MCTS the tree search was shown to be a type of mini-max search. It's possible to structure alpha/beta to have incredibly low branching factors, with modern chess programs for instance it is about 2. That involves a lot of domain specific knowledge and assumptions about the tree. This same thing can be done in GO and would also require a lot of domain specific knowledge. That knowledge could be obtained with the same methods used by MCTS, statistics gathered by playout analysis. The evaluation function could also be merged into the nodes in a similar way to MCTS. I believe what makes go different, is that you can be a lot more selective than you can in chess, it's much easier to evaluate bad moves in GO, but it's much harder to evaluate the quality of positions. You stated that alpha/beta can only go a few ply, but that is also true of MCTS. It only goes a few ply unless you count the Monte Carlo part - in which case you also do that with alpha/beta. So in my opinion the jury is still out. Is the TS in MCTS really so fundamentally different that alpha/beta with selectivity? I'm not so sure and I don't think anyone has really tried very hard probably due to the wonderful success of the original bandit algorithm. There are a bunch of things in computer science that were rejected, and then later found much success due to some simple discovery or even research that showed people were just looking at it wrong, or missed something relatively simple about it, or it simply went out of fashion because something else came along that at the time appeared to better or simpler and became the fad. That could easily happen here I think. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: static evaluators for tree search
I really don't like the idea of ranking moves and scoring based on the distance to the top of a list for a pro move. This is worthless if we ever want to surpass humans (although this isn't a concern now, it is in principle) and we have no reason to believe a move isn't strong just because a pro didn't pick it. Perhaps another pro would pick a different move in the same situation. If we had a pro that ranked all the legal moves, or at least the top 10 or so, this would be one thing, but those data are almost never available. Or if we had two pro's watching a game and giving what they thought was the best move at each point and we scored an evaluator based on how it did only when the pro's agreed (although this would bias scoring towards things like forced moves). Also, there are bad moves and then even worse moves (like filling the eyes of a powerful living group, killing it). If an evaluator makes catastrophic evaluations sometimes and plays a perfect pro move other times, it could still be much worse in balance (if we can't tell when it is blundering versus being brilliant). I think it would be much more informative to compare evaluator A and evaluator B in the following way. Make a bot that searched to a fixed depth d before then calling a static evaluator (maybe this depth is 1 or 2 or something small). Try and determine the strength of a bot using A and a bot using B as accurately as possible against a variety of opponents. The better evaluator is defined to be the one that results in the stronger bot. Obviously this methods introduces a whole host of new problems (even finding the strength of a running bot is non-trivial), but at least it attempts to measure what we would eventually care about --- playing strength. So of course we care about how fast the static evaluators are, because we might be able to search more nodes with a faster evaluator, but for measuring the quality of the evaluations, I can't at the moment think of a better way of doing this. One of the problems with my suggestion is that maybe the evaluators are better at evaluating positions beyond a certain number of moves and that if we could just get to that depth before calling them, they would be much more accurate. Or maybe changes to how searching works can compensate for weaknesses in evaluators or emphasize strengths. Really one would want the strongest possible bot built around a single evaluator versus the strongest possible bot built around another evaluator, but this is clearly impossible to achieve. I guess the another question is, what would you need to see a static evaluator do to be so convinced it was useful that you then built a bot around it? Would it need to win games all by itself with one ply lookahead? - George On Tue, Feb 17, 2009 at 2:41 PM, Dave Dyer dd...@real-me.net wrote: This is old and incomplete, but still is a starting point you might find useful http://www.andromeda.com/people/ddyer/go/global-eval.html General observations (from a weak player's point of view): Go is played on a knife edge between life and death. The only evaluator that matters is is this stone alive, and there are no known proxies that will not fall short a significant amount of the time. If you fall short once or twice in a game against a competent player, you will lose. General strategic considerations will play you false every time. -- Notwithstanding the above, improving general considerations will improve play, but not much. It's all about the minutia of the situation. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: static evaluators for tree search
George Dahl wrote: I guess the another question is, what would you need to see a static evaluator do to be so convinced it was useful that you then built a bot around it? Would it need to win games all by itself with one ply lookahead? Here is one way to look at it: Since a search tends to seek out errors in the evaluation, you must minimize the maximum error that can ever occur. If you do not, then a very fast computer will search many nodes in the tree, find a place that your evaluator makes a big error, and use that error in it's search decisions. So how can one test the error that your evaluator has? As you suggested, you can use the evaluator in a game engine and see how it performs. But that performance is also a function of how big your search is and not only how good your evaluator is. Another option would be to generate positions and test the accuracy of the evaluator. For this, you would two things: 1) An authority on how strong each position is for black 2) A source of applicable positions to test For the authority, I would use MoGo. You can make it almost arbitrarily strong by just waiting longer for it to arrive at an answer (and using more memory, etc). As for the source of applicable positions, that's a bit harder, IMO. My first thought was to use random positions since you don't want any bias, but that will probably result in the evaluation of the position being very near 0.5 much of the time. But I would still try this method since the lack of bias makes it so attractive. Another option is that you could take random positions from actual games and generate a search tree from that position. From that search tree, you could select a few random nodes to use as test positions. But now we are back to being coupled to the search parameters -- the same thing we were trying to avoid by not writing a game engine. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] static evaluators for tree search
On Tue, Feb 17, 2009 at 8:23 PM, George Dahl george.d...@gmail.com wrote: It is very hard for me to figure out how good a given evaluator is (if anyone has suggestions for this please let me know) without seeing it incorporated into a bot and looking at the bot's performance. There is a complicated trade off between the accuracy of the evaluator and how fast it is. We plan on looking at how well our evaluators predicts the winner or territory outcome or something for pro games, but in the end, what does that really tell us? There is no way we are going to ever be able to make a fast evaluator using our methods that perfectly predicts these things. You are optimizing two things; quality and speed. One can be exchanged for the other, so together they span a frontier of solutions. Until you fixate one, e.g., by setting a time constraint, you can look at the entire frontier of (Pareto-optimal) solutions. Any evaluator that falls behind the frontier is bad. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: static evaluators for tree search
Michael Williams wrote: As for the source of applicable positions, that's a bit harder, IMO. My first thought was to use random positions since you don't want any bias, but that will probably result in the evaluation of the position being very near 0.5 much of the time. But I would still try this method since the lack of bias makes it so attractive. Another option is that you could take random positions from actual games and generate a search tree from that position. From that search tree, you could select a few random nodes to use as test positions. But now we are back to being coupled to the search parameters -- the same thing we were trying to avoid by not writing a game engine. Here are some follow-up ideas I had on how to get meaningful test positions... The most important positions to evaluate accurately are those near the root of the search tree (because they will be seen first and may direct further progression of the search. So to generate a tier-N test position, take a position from an actual game and make make N random moves. In tuning your evaluator, tier-N positions are more important to get correct (get correct means minimize the error) than tier-(N+1) positions. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] static evaluators for tree search
I agree with you, but I wouldn't qualify MC evaluation with MCTS as a static evaluation function on top of a pure alfabeta search to a fixed depth (I have the impression that this is what George Dahl is talking about). Dave Van: computer-go-boun...@computer-go.org namens Don Dailey Verzonden: di 17-2-2009 20:57 Aan: computer-go Onderwerp: RE: [computer-go] static evaluators for tree search On Tue, 2009-02-17 at 20:04 +0100, dave.de...@planet.nl wrote: A simple alfabeta searcher will only get a few plies deep on 19x19, so it won't be very useful (unless your static evaluation function is so good that it doesn't really need an alfabeta searcher) I have to say that I believe this is very simplistic, and a lot of people have said things like this so you are certainly not alone. But how deep it goes is not particularly relevant, it's only a very small part of the picture. Before MCTS programs were playing reasonably well with continuous refinements to 1 ply searches. You can probably conceptually separate a tree searching program into 3 parts, and in this sense alpha/beta is no different than MCTS: 1. search 2. selectivity 3. evaluation selectivity is a nebulous term which involves all kinds of decisions about what to do inside the tree. It all boils down to 1 thing however, when to stop and when not to (and possibly what score to assume.) Evaluation has always been the most important part of any tree searching program and alpha/beta just doesn't work without it. Even if you search to the very end of a game, such as tic-tac-toe, you must know whether the game is a win, loss or draw, so you are forced to evaluate in the non-recursive sense.When you cannot go to the end of the game, which is true of any interesting game before it's played out, you really must have a high quality evaluation. The interesting part of MCTS, is not the TS part, it's the MC part. That's the part that does the evaluation. I am convinced that the tree search part could be done in a number of ways which can be seen as more or less equivalent. Even in the papers on MCTS the tree search was shown to be a type of mini-max search. It's possible to structure alpha/beta to have incredibly low branching factors, with modern chess programs for instance it is about 2. That involves a lot of domain specific knowledge and assumptions about the tree. This same thing can be done in GO and would also require a lot of domain specific knowledge. That knowledge could be obtained with the same methods used by MCTS, statistics gathered by playout analysis. The evaluation function could also be merged into the nodes in a similar way to MCTS. I believe what makes go different, is that you can be a lot more selective than you can in chess, it's much easier to evaluate bad moves in GO, but it's much harder to evaluate the quality of positions. You stated that alpha/beta can only go a few ply, but that is also true of MCTS. It only goes a few ply unless you count the Monte Carlo part - in which case you also do that with alpha/beta. So in my opinion the jury is still out. Is the TS in MCTS really so fundamentally different that alpha/beta with selectivity? I'm not so sure and I don't think anyone has really tried very hard probably due to the wonderful success of the original bandit algorithm. There are a bunch of things in computer science that were rejected, and then later found much success due to some simple discovery or even research that showed people were just looking at it wrong, or missed something relatively simple about it, or it simply went out of fashion because something else came along that at the time appeared to better or simpler and became the fad. That could easily happen here I think. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: static evaluators for tree search
Dave Dyer wrote: If you look at GnuGo or some other available program, I'm pretty sure you'll find a line of code where the evaluator is called, and you could replace it, but you'll find it's connected to a pile of spaghetti. That would have to be some other available program. GNU Go doesn't have a static position evaluator and consequently no line of code calling it. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] CGT approximating the sum of subgames
I've been looking into CGT lately and I stumbled on some articles about approximating strategies for determining the sum of subgames (Thermostrat, MixedStrat, HotStrat etc.) It is not clear to me why approximating strategies are needed. What is the problem? Is Ko the problem? Is an exact computation too slow? Can anyone shed some light on this? Dave ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: static evaluators for tree search
On Feb 17, 2009, at 12:55 PM, Dave Dyer dd...@real-me.net wrote: While your goal is laudable, I'm afraid there is no such thing as a simple tree search with a plug-in evaluator for Go. The problem is that the move generator has to be very disciplined, and the evaluator typically requires elaborate and expensive to maintain data structures. It all tends to be very convoluted and full of feedback loops, in addition to the actual alpha-beta which is trivial by comparison. Why would initial research require a full bot molded around the new static evaluator? It's far simpler to leave the necessary machinery in place and add in the new static evaluator. That may mean extra work such as running two evaluation methods and reusing a prior move orderer/generator, but who cares? There's a lot of power in quick and dirty evaluations. If the changes for the new static evaluation reduces bot strength, it's time to go back to the drawing board. It's only once you create a strength improvement that the steps you mention really matter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CGT approximating the sum of subgames
From: Jason House jason.james.ho...@gmail.com On Feb 17, 2009, at 4:39 PM, dave.de...@planet.nl wrote: I've been looking into CGT lately and I stumbled on some articles about approximating strategies for determining the sum of subgames (Thermostrat, MixedStrat, HotStrat etc.) Link? http://www.cs.rice.edu/~cra1/Home/Publications_files/icga_vol29_4.pdf looks promising. ( just something I googled up ) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: static evaluators for tree search
I think it would be much more informative to compare evaluator A and evaluator B in the following way. Make a bot that searched to a fixed depth d before then calling a static evaluator (maybe this depth is 1 or 2 or something small). Try and determine the strength of a bot using A and a bot using B as accurately as possible against a variety of opponents. The better evaluator is defined to be the one that results in the stronger bot. If you do this I'd suggest also including monte-carlo as one of your static evaluators. You want a score, but monte carlo usually returns information like 17 black wins, 3 white wins. However you can instead just sum ownership in the terminal positions, so if A1 is owned by black 15 times, white 5 times, count that as a point for black. If exactly equal ownership count the point for neither side. (Alternatively just sum black and white score of each terminal position.) You could have two or three versions using different number of playouts (with the result trade-off of more playouts means fewer nodes visited in the global search); I suspect 20-50 playouts will be optimum. My hunch is that monte carlo version will always out perform any static evaluation, given the same overall time (*). But it would be interesting to know. Darren *: Or run the experiment giving the static evaluation four times the clock time, on the assumption there is more potential for optimization in complex code. -- Darren Cook, Software Researcher/Developer http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic open source dictionary/semantic network) http://dcook.org/work/ (About me and my work) http://dcook.org/blogs.html (My blogs and articles) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: static evaluators for tree search
Really? You think that doing 20-50 uniform random playouts and estimating the win probability, when used as a leaf node evaluator in tree search, will outperform anything else that uses same amount of time? I must not understand you. What do you mean by static evaluator? When I use the term, I mean something quite general, basically any function of the board state that doesn't do explicit lookahead. I guess 20-50 optimized playouts take so little time they would just be so much faster than the sort of evaluators I might make that could use hundreds of thousands of floating point multiplies. But more towards that costly end of the regime, I think doing thousands of random playouts would be really bad (but then maybe you could just expand more nodes in the tree and do fewer playouts instead). I am looking for higher quality, more costly evaluators than 50 MC playouts. But that is a good point that I should compare to those evaluators since if my evaluator is going to take more time it had better show some other advantage. - George On Tue, Feb 17, 2009 at 6:13 PM, Darren Cook dar...@dcook.org wrote: I think it would be much more informative to compare evaluator A and evaluator B in the following way. Make a bot that searched to a fixed depth d before then calling a static evaluator (maybe this depth is 1 or 2 or something small). Try and determine the strength of a bot using A and a bot using B as accurately as possible against a variety of opponents. The better evaluator is defined to be the one that results in the stronger bot. If you do this I'd suggest also including monte-carlo as one of your static evaluators. You want a score, but monte carlo usually returns information like 17 black wins, 3 white wins. However you can instead just sum ownership in the terminal positions, so if A1 is owned by black 15 times, white 5 times, count that as a point for black. If exactly equal ownership count the point for neither side. (Alternatively just sum black and white score of each terminal position.) You could have two or three versions using different number of playouts (with the result trade-off of more playouts means fewer nodes visited in the global search); I suspect 20-50 playouts will be optimum. My hunch is that monte carlo version will always out perform any static evaluation, given the same overall time (*). But it would be interesting to know. Darren *: Or run the experiment giving the static evaluation four times the clock time, on the assumption there is more potential for optimization in complex code. -- Darren Cook, Software Researcher/Developer http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic open source dictionary/semantic network) http://dcook.org/work/ (About me and my work) http://dcook.org/blogs.html (My blogs and articles) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: static evaluators for tree search
Really? You think that doing 20-50 uniform random playouts and estimating the win probability, when used as a leaf node evaluator in tree search, will outperform anything else that uses same amount of time? Same amount of clock time for the whole game. E.g. if playing 20 random playouts to the end of the game takes N ms, and your static evaluation takes 5*N ms then the playout version can explore 5 times more global nodes. But the main advantage, I feel, is that playouts play out the game. Here is an observation that I think I wrote here many years ago: Many Faces (version 9 or 10) would give a much more accurate analysis of the score of a game by putting it on level 1 and having it play it itself, which took about a second (even with all the overhead of the moves being shown on the board), compared to pressing F9 to get the static evaluation. As already mentioned, life/death analysis is so hard that it just has to be played out. But also, the value of having sente can realistically only be discovered by playing out. This really stumped me when I was trying to statically analyze endgame positions (i.e. trying to extend the Mathematical endgame ideas back a bit further in the game). Darren -- Darren Cook, Software Researcher/Developer http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic open source dictionary/semantic network) http://dcook.org/work/ (About me and my work) http://dcook.org/blogs.html (My blogs and articles) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: static evaluators for tree search
On Tue, Feb 17, 2009 at 8:35 PM, George Dahl george.d...@gmail.com wrote: Really? You think that doing 20-50 uniform random playouts and estimating the win probability, when used as a leaf node evaluator in tree search, will outperform anything else that uses same amount of time? You'll probably find a variety of opinions on that. I think you can make a static evaluator that will give you a better estimate of the win probability estimate than 50 uniform random playouts. But... (there are a few big ones) implementing uniform random playout is a lot less work. On top of that, with some prudent exploration, you rarely spend 50 playouts all in one place. This is definitely something powerful in MCTS programs, that they can reject unpromising lines of play at relatively little cost. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] static evaluators for tree search
From: dhillism...@netscape.net dhillism...@netscape.net Perhaps the biggest problem came from an unexpected quarter. MC playouts are very fast and neural nets are a bit slow. (I am talking about the forward pass, not the off-line training.) In the short time it took to feed a board position to my net and get the results, I could have run enough MC playouts to obtain a better estimate of the ownership map. :/ Would GPUs be better suited to neural nets than to MC playouts? If so, would this tilt the playing field in favor of neural nets on GPUs,. giving them an advantage over MC on relatively fewer general-purpose CPUs? A GPU with hundreds of shaders is relatively cheap compared to even a handful of x86 processors. The same argument may apply to other forms of classification which map well to GPUs. A Good Credit Score is 700 or Above. See yours in just 2 easy steps! ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] static evaluators for tree search
GPUs can speed up many types of neural networks by over a factor of 30. - George On Tue, Feb 17, 2009 at 8:35 PM, terry mcintyre terrymcint...@yahoo.com wrote: From: dhillism...@netscape.net dhillism...@netscape.net Perhaps the biggest problem came from an unexpected quarter. MC playouts are very fast and neural nets are a bit slow. (I am talking about the forward pass, not the off-line training.) In the short time it took to feed a board position to my net and get the results, I could have run enough MC playouts to obtain a better estimate of the ownership map. :/ Would GPUs be better suited to neural nets than to MC playouts? If so, would this tilt the playing field in favor of neural nets on GPUs,. giving them an advantage over MC on relatively fewer general-purpose CPUs? A GPU with hundreds of shaders is relatively cheap compared to even a handful of x86 processors. The same argument may apply to other forms of classification which map well to GPUs. A Good Credit Score is 700 or Above. See yours in just 2 easy steps! ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to David Fotland and Many Faces
On Mon, Feb 16, 2009 at 7:45 PM, Andy andy.olsen...@gmail.com wrote: See attached a copy of the .sgf. It was played private on KGS so you can't get it there directly. One of the admins cloned it and I saved it off locally. I changed the result to be B+4.5 instead of W+2.5. I forgot to make a disclaimer: I am not an organizer of the event or a member of the CrazyStone team. I just happened to see a copy of the game, and I changed the result based on some reports I saw. I've received a few questions about this but you should really direct any questions to an authority. - Andy ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Congratulations to David Fotland and Many Faces
I think you mean Many Faces of Go, not Crazystone. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Andy Sent: Tuesday, February 17, 2009 10:08 PM To: computer-go Subject: Re: [computer-go] Congratulations to David Fotland and Many Faces On Mon, Feb 16, 2009 at 7:45 PM, Andy andy.olsen...@gmail.com wrote: See attached a copy of the .sgf. It was played private on KGS so you can't get it there directly. One of the admins cloned it and I saved it off locally. I changed the result to be B+4.5 instead of W+2.5. I forgot to make a disclaimer: I am not an organizer of the event or a member of the CrazyStone team. I just happened to see a copy of the game, and I changed the result based on some reports I saw. I've received a few questions about this but you should really direct any questions to an authority. - Andy ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Re: static evaluators for tree search
It is very clear that nonuniform random playouts is a far better evaluator than any reasonable static evaluation, given the same amount of time. Many people (including myself) spent decades creating static evaluations, using many techniques, and the best ones ended up with similar strength programs. The strongest MCTS programs are far stronger. I put 25 years effort into a static evaluation, and replaced it with an MCTS system that I worked on for 6 months, and got about 5 stones strength improvement. MCTS playouts are not uniform random, so I can't say how they would perform, but why build a system with uniform random playouts, when it is so easy to do better? David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of George Dahl Sent: Tuesday, February 17, 2009 3:36 PM To: computer-go Subject: Re: [computer-go] Re: static evaluators for tree search Really? You think that doing 20-50 uniform random playouts and estimating the win probability, when used as a leaf node evaluator in tree search, will outperform anything else that uses same amount of time? I must not understand you. What do you mean by static evaluator? When I use the term, I mean something quite general, basically any function of the board state that doesn't do explicit lookahead. I guess 20-50 optimized playouts take so little time they would just be so much faster than the sort of evaluators I might make that could use hundreds of thousands of floating point multiplies. But more towards that costly end of the regime, I think doing thousands of random playouts would be really bad (but then maybe you could just expand more nodes in the tree and do fewer playouts instead). I am looking for higher quality, more costly evaluators than 50 MC playouts. But that is a good point that I should compare to those evaluators since if my evaluator is going to take more time it had better show some other advantage. - George On Tue, Feb 17, 2009 at 6:13 PM, Darren Cook dar...@dcook.org wrote: I think it would be much more informative to compare evaluator A and evaluator B in the following way. Make a bot that searched to a fixed depth d before then calling a static evaluator (maybe this depth is 1 or 2 or something small). Try and determine the strength of a bot using A and a bot using B as accurately as possible against a variety of opponents. The better evaluator is defined to be the one that results in the stronger bot. If you do this I'd suggest also including monte-carlo as one of your static evaluators. You want a score, but monte carlo usually returns information like 17 black wins, 3 white wins. However you can instead just sum ownership in the terminal positions, so if A1 is owned by black 15 times, white 5 times, count that as a point for black. If exactly equal ownership count the point for neither side. (Alternatively just sum black and white score of each terminal position.) You could have two or three versions using different number of playouts (with the result trade-off of more playouts means fewer nodes visited in the global search); I suspect 20-50 playouts will be optimum. My hunch is that monte carlo version will always out perform any static evaluation, given the same overall time (*). But it would be interesting to know. Darren *: Or run the experiment giving the static evaluation four times the clock time, on the assumption there is more potential for optimization in complex code. -- Darren Cook, Software Researcher/Developer http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic open source dictionary/semantic network) http://dcook.org/work/ (About me and my work) http://dcook.org/blogs.html (My blogs and articles) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Re: static evaluators for tree search
Many Faces of Go has a static position evaluator, but it's not spaghetti :) It makes many passes over the board building up higher level features from lower level ones, and it does local lookahead as part of feature evaluation, so it has a lot of code, and is fairly slow. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Gunnar Farnebäck Sent: Tuesday, February 17, 2009 1:30 PM To: computer-go Subject: Re: [computer-go] Re: static evaluators for tree search Dave Dyer wrote: If you look at GnuGo or some other available program, I'm pretty sure you'll find a line of code where the evaluator is called, and you could replace it, but you'll find it's connected to a pile of spaghetti. That would have to be some other available program. GNU Go doesn't have a static position evaluator and consequently no line of code calling it. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] static evaluators for tree search
It's not true that MCTS only goes a few ply. In 19x19 games on 32 CPU cores, searching about 3 million play outs per move, Many Faces of Go typically goes over 15 ply in the PV in the UCT tree. I agree that it is much easier to reliably prune bad moves in go than it is in chess. Many Faces (pre MCTS) was a selective alpha-beta searcher. Switching to MCTS made it much stronger, so I think MCTS is better than alpha-beta for go. The reason is that to get any depth out of alpha-beta I had to hard-prune most moves, and misses too many good moves. MCTS is full width, so misses nothing, and still searches twice as deep as the pruned alpha-beta. Perhaps a dumber but faster evaluation function could do better than I did though. Davdi -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Don Dailey Sent: Tuesday, February 17, 2009 11:58 AM To: computer-go Subject: RE: [computer-go] static evaluators for tree search On Tue, 2009-02-17 at 20:04 +0100, dave.de...@planet.nl wrote: A simple alfabeta searcher will only get a few plies deep on 19x19, so it won't be very useful (unless your static evaluation function is so good that it doesn't really need an alfabeta searcher) I have to say that I believe this is very simplistic, and a lot of people have said things like this so you are certainly not alone. But how deep it goes is not particularly relevant, it's only a very small part of the picture. Before MCTS programs were playing reasonably well with continuous refinements to 1 ply searches. You can probably conceptually separate a tree searching program into 3 parts, and in this sense alpha/beta is no different than MCTS: 1. search 2. selectivity 3. evaluation selectivity is a nebulous term which involves all kinds of decisions about what to do inside the tree. It all boils down to 1 thing however, when to stop and when not to (and possibly what score to assume.) Evaluation has always been the most important part of any tree searching program and alpha/beta just doesn't work without it. Even if you search to the very end of a game, such as tic-tac-toe, you must know whether the game is a win, loss or draw, so you are forced to evaluate in the non-recursive sense.When you cannot go to the end of the game, which is true of any interesting game before it's played out, you really must have a high quality evaluation. The interesting part of MCTS, is not the TS part, it's the MC part. That's the part that does the evaluation. I am convinced that the tree search part could be done in a number of ways which can be seen as more or less equivalent. Even in the papers on MCTS the tree search was shown to be a type of mini-max search. It's possible to structure alpha/beta to have incredibly low branching factors, with modern chess programs for instance it is about 2. That involves a lot of domain specific knowledge and assumptions about the tree. This same thing can be done in GO and would also require a lot of domain specific knowledge. That knowledge could be obtained with the same methods used by MCTS, statistics gathered by playout analysis. The evaluation function could also be merged into the nodes in a similar way to MCTS. I believe what makes go different, is that you can be a lot more selective than you can in chess, it's much easier to evaluate bad moves in GO, but it's much harder to evaluate the quality of positions. You stated that alpha/beta can only go a few ply, but that is also true of MCTS. It only goes a few ply unless you count the Monte Carlo part - in which case you also do that with alpha/beta. So in my opinion the jury is still out. Is the TS in MCTS really so fundamentally different that alpha/beta with selectivity? I'm not so sure and I don't think anyone has really tried very hard probably due to the wonderful success of the original bandit algorithm. There are a bunch of things in computer science that were rejected, and then later found much success due to some simple discovery or even research that showed people were just looking at it wrong, or missed something relatively simple about it, or it simply went out of fashion because something else came along that at the time appeared to better or simpler and became the fad. That could easily happen here I think. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] static evaluators for tree search
One way to figure out how good your static evaluator is, is to have it do a one ply search, evaluate, and display the top 20 or so evaluations on a go board. Ask a strong player to go through a pro game, showing your evaluations at each move. He can tell you pretty quickly how bad your evaluator is. If you evaluator produces an estimate of the score (like Many Faces of Go), you can compare it to Many Faces. The Game Score Graph function just shows the static evaluation with no search at each position in a game. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of George Dahl Sent: Tuesday, February 17, 2009 11:23 AM To: computer-go Subject: Re: [computer-go] static evaluators for tree search You're right of course. We have a (relatively fast) move pruning algorithm that can order moves such that about 95% of the time, when looking at pro games, the pro move will be in the first 50 in the ordering. About 70% of the time the expert move will be in the top 10. So a few simple tricks like this shouldn't be too hard to incorporate. However, the main purpose of making a really *simple* alpha-beta searching bot is to compare the performance of static evaluators. It is very hard for me to figure out how good a given evaluator is (if anyone has suggestions for this please let me know) without seeing it incorporated into a bot and looking at the bot's performance. There is a complicated trade off between the accuracy of the evaluator and how fast it is. We plan on looking at how well our evaluators predicts the winner or territory outcome or something for pro games, but in the end, what does that really tell us? There is no way we are going to ever be able to make a fast evaluator using our methods that perfectly predicts these things. So I have two competing motivations here. First, I want to show that the evaluators I make are good somehow. Second, I want to build a strong bot. - George On Tue, Feb 17, 2009 at 2:04 PM, dave.de...@planet.nl wrote: A simple alfabeta searcher will only get a few plies deep on 19x19, so it won't be very useful (unless your static evaluation function is so good that it doesn't really need an alfabeta searcher) Dave Van: computer-go-boun...@computer-go.org namens George Dahl Verzonden: di 17-2-2009 18:27 Aan: computer-go Onderwerp: [computer-go] static evaluators for tree search At the moment I (and another member of my group) are doing research on applying machine learning to constructing a static evaluator for Go positions (generally by predicting the final ownership of each point on the board and then using this to estimate a probability of winning). We are looking for someone who might be willing to help us build a decent tree search bot that can have its static evaluator easily swapped out so we can create systems that actually play over GTP. As much as we try to find quantitative measures for how well our static evaluators work, the only real test is to build them into a bot. Also, if anyone knows of an open source simple tree search bot (perhaps alpha-beta or something almost chess like) for Go, we might be able to modify it ourselves. The expertise of my colleague and I is in machine learning, not in tree search (although if worst comes to worst I will write my own simple alpha-beta searcher). We would be eager to work together with someone on this list to try and create a competitive bot. We might at some point create a randomized evaluator that returns win or loss nondeterministically for a position instead of a deterministic score, so an ideal collaborator would also have some experience with implementing monte carlo tree search (we could replace playouts with our evaluator to some extent perhaps). But more important is traditional, chess-like searching algorithms. If anyone is interested in working with us on this, please let me know! We have a prototype static evaluator complete that is producing sane board ownership maps, but we will hopefully have many even better ones soon. - George ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Re: static evaluators for tree search
Many Faces uses information from the static evaluator to order and prune moves during move generation. For example if the evaluation finds a big unsettled group, the move generator will favor eye making or escaping moves for the big group. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of George Dahl Sent: Tuesday, February 17, 2009 10:14 AM To: computer-go Subject: Re: [computer-go] Re: static evaluators for tree search I am aware such a decoupled program might not exist, but I don't see why one can't be created. When you say the move generator has to be very disciplined what do you mean? Do you mean that the evaluator might be used during move ordering somehow and that generating the nodes to expand is tightly coupled with the static evaluator? - George On Tue, Feb 17, 2009 at 12:55 PM, Dave Dyer dd...@real-me.net wrote: While your goal is laudable, I'm afraid there is no such thing as a simple tree search with a plug-in evaluator for Go. The problem is that the move generator has to be very disciplined, and the evaluator typically requires elaborate and expensive to maintain data structures. It all tends to be very convoluted and full of feedback loops, in addition to the actual alpha-beta which is trivial by comparison. If you look at GnuGo or some other available program, I'm pretty sure you'll find a line of code where the evaluator is called, and you could replace it, but you'll find it's connected to a pile of spaghetti. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
