RE: [computer-go] static evaluators for tree search
On Tue, 2009-02-17 at 23:29 -0800, David Fotland wrote: 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. That's what I meant when I said a few ply. Lazarus doesn't get that deep but it also goes several ply. A few years ago I got the impression that many people felt that anything other than local search was completely worthless because you couldn't go the 100+ ply you needed to understand a lot of things.Perhaps I exaggerate, but that was the gist. It's pretty clear of course that you cannot cover these 15 ply (or whatever) with anything resembling a brute force search, where other than alpha/beta pruning you look at every move to some goal depth with perhaps some kind of brief quies search. That's probably what the previous list member meant. 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. This may be the case. I believe that MCTS is just easier to think about and manage and I just have a hunch that a very similar thing could be formulated within the alpha/beta framework. Even if I'm right, there may be no benefit to doing this if they are (as I tentatively believe) more or less equivalent.But alpha/beta has one advantage, that perhaps could be taken advantage of, and that is the hard pruning you talk about. Even though it's hard pruning in some sense, it's fully admissible pruning and there are parts of the tree that MCTS always looks at, but that alpha/beta knows can be correctly rejected. Of course I appreciate the MCTS doesn't waste much time on those, but maybe it wastes enough time to make a difference, I don't know. I think of a proper alpha/beta search as full width too, it is just iterative.There is no move that gets un-admissibly and permanently pruned in alpha/beta even with modern techniques like null move and late move reductions.Those moves are effectively picked up and explored to greater depths on the NEXT iterations.Unless of course they are outside the alpha/beta window in which case it doesn't matter. So modern alpha/beta to me is looking more and more like the TS in MCTS, without the MC with at least one possible advantage. MCTS is really easy to reason about and control however and in comparison alpha/beta is temperamental. If some move in the tree that looks bad is really good, MCTS explores it gradually and in a controlled way and alpha/beta has to wait much longer to modify it's decision. And it's so well integrated with Monte Carlo and it's not clear how to do that so nicely with alpha/beta. So I am only open to the possibility that they are equivalent in some implementable sense, but I may be wrong about this. - Don Davdi ___ 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/
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/
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] 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] 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] 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] 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/