Re: [computer-go] The dominance of search (Suzie v. GnuGo)
[EMAIL PROTECTED] wrote: I also find this kind of information very interesting and useful. Now I have a better feel for what kind of scaling is realistic to try for and how to measure it. Putting some recent data points together, it look like giving Mogo 2 orders of magnitude more computer power would result in low dan level 19x19 play? Not the sort of thing one can pull out of a back pocket, but tantalizing. I would be very interested to see equivalent scaling numbers from CrazyStone, if Remi would be so kind. - Dave Hillis Hi, Here is some data, each result measured over about 200 games, on a single CPU (AMD Opteron 2.2 GHz): 9x9, 2 minutes per game, GNU Go level 10: 87.0% 13x13, 16 minutes per game, GNU Go level 10: 72.4% 19x19, 32 minutes per game, GNU Go level 0: 53.6% 19x19, 32 minutes per game, GNU Go level 8: 28.1% 19x19, 64 minutes per game, GNU Go level 8: 35.4% (GNU Go version 3.6) Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
-Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Mon, 16 Apr 2007 5:26 AM Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo) [EMAIL PROTECTED] wrote: I also find this kind of information very interesting and useful. Now I have a better feel for what kind of scaling is realistic to try for and how to measure it. Putting some recent data points together, it look like giving Mogo 2 orders of magnitude more computer power would result in low dan level 19x19 play? Not the sort of thing one can pull out of a back pocket, but tantalizing. I would be very interested to see equivalent scaling numbers from CrazyStone, if Remi would be so kind. - Dave Hillis Hi, Here is some data, each result measured over about 200 games, on a single CPU (AMD Opteron 2.2 GHz): 9x9, 2 minutes per game, GNU Go level 10: 87.0% 13x13, 16 minutes per game, GNU Go level 10: 72.4% 19x19, 32 minutes per game, GNU Go level 0: 53.6% 19x19, 32 minutes per game, GNU Go level 8: 28.1% 19x19, 64 minutes per game, GNU Go level 8: 35.4% (GNU Go version 3.6) Rémi Thanks! These are interesting. I assume that the number of playouts per move was variable. If it was a fixed number, or easily characterized, it would be a helpful statistic too. - Dave Hillis Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
[EMAIL PROTECTED] wrote: -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Mon, 16 Apr 2007 5:26 AM Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo) [EMAIL PROTECTED] javascript:parent.ComposeTo(dhillismail%40netscape.net, ); wrote: I also find this kind of information very interesting and useful. Now I have a better feel for what kind of scaling is realistic to try for and how to measure it. Putting some recent data points together, it look like giving Mogo 2 orders of magnitude more computer power would result in low dan level 19x19 play? Not the sort of thing one can pull out of a back pocket, but tantalizing. I would be very interested to see equivalent scaling numbers from CrazyStone, if Remi would be so kind. - Dave Hillis Hi, Here is some data, each result measured over about 200 games, on a single CPU (AMD Opteron 2.2 GHz): 9x9, 2 minutes per game, GNU Go level 10: 87.0% 13x13, 16 minutes per game, GNU Go level 10: 72.4% 19x19, 32 minutes per game, GNU Go level 0: 53.6% 19x19, 32 minutes per game, GNU Go level 8: 28.1% 19x19, 64 minutes per game, GNU Go level 8: 35.4% (GNU Go version 3.6) Rémi Thanks! These are interesting. I assume that the number of playouts per move was variable. If it was a fixed number, or easily characterized, it would be a helpful statistic too. - Dave Hillis Yes, it was variable. On that machine, Crazy Stone does about 15,000 playouts/second on 9x9 with UCT. BTW, CrazyStone-Fast on CGOS is 5k simulations, and CrazyStone-Slower is 20k. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
[EMAIL PROTECTED]: [EMAIL PROTECTED]: Remi, Could you change your time as 10 min. plus 8 min. byo yomi? Otherwise it's too short for human. It's difficult to get a real results. Strogly agree! It's too short for me, 4 kyu, to have a meaningful game with Crazy Stone. I beg you too, Remi. #GNU bots are 10 min + 20 sec x 5. - gg Daniel Liu -Original Message- From: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Wed, 11 Apr 2007 3:33 PM Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo) [EMAIL PROTECTED] wrote: I also find this kind of information very interesting and useful. Now I have a better feel for what kind of scaling is realistic to try for and how to measure it. Putting some recent data points together, it look like giving Mogo 2 orders of magnitude more computer power would result in low dan level 19x19 play? Not the sort of thing one can pull out of a back pocket, but tantalizing. I would be very interested to see equivalent scaling numbers from CrazyStone, if Remi would be so kind. - Dave Hillis I don't have time to do this right now. I have connected Crazy Stone to play 10 minute blitz on KGS, and will leave it all night long. It reached [1d] for a while, and is currently [1k]. There is a big surprise effect when humans play Crazy Stone. The first moves look so stupid. Usually, a human player will lose the first game, then it will win the next ones. Rémi ___ computer-go mailing list [EMAIL PROTECTED] http://www.computer-go.org/mailman/listinfo/computer-go/ AOL now offers free email to everyone. Find out more about what's free from AOL at AOL.com. inline file ___ computer-go mailing list [EMAIL PROTECTED] http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list [EMAIL PROTECTED] http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
2007/4/11, [EMAIL PROTECTED] [EMAIL PROTECTED]: I watched MoGo playing with different rank of players. Usually 5d players has no problem winning. Starting from 4d begin to lose games. However, part of it is due to most players are not familar with 9x9 Go. Taking this into consideration I place MoGo at about amateur 2d. For professional players consider 9x9 is solved. This is all my opinion. Gnu plays at about 5k on 19x19. Let's place MoGo at 4k on 19x19. Besides the 32 times, it also need to make up the difference between 4k and 2d. I just reported precise and objective experiments which may be interesting results for some. I have no opinion watching the program play, and no way to measure it precisely by subjective opinions. However, maybe it lacks some numbers in my report. On KGS, 9x9, MoGo uses about 40s per move, and on 19x19 (when rated 4kyu) used 15s per move. So it almost 3 times less and I reported that it should be 32 times more (so around 21 minutes per move). In the other way, these 15s per move would be 0.5s per move on 9x9. Maybe it does not continue to scale so well with time, I don't know. However with the times I tested, the scale with the board size is what I reported, and at least the number are precise (many dozen thousands of games). Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
On 4/11/07, Sylvain Gelly [EMAIL PROTECTED] wrote: 2007/4/11, [EMAIL PROTECTED] [EMAIL PROTECTED]: I watched MoGo playing with different rank of players. Usually 5d players has no problem winning. Starting from 4d begin to lose games. However, part of it is due to most players are not familar with 9x9 Go. Taking this into consideration I place MoGo at about amateur 2d. For professional players consider 9x9 is solved. This is all my opinion. Gnu plays at about 5k on 19x19. Let's place MoGo at 4k on 19x19. Besides the 32 times, it also need to make up the difference between 4k and 2d. I just reported precise and objective experiments which may be interesting results for some. I have no opinion watching the program play, and no way to measure it precisely by subjective opinions. In case it matters, I think your experiment was interesting, relevant and well designed. Once we get dimwit to a decent level of play I'll probably try to produce similar data. Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
I also find this kind of information very interesting and useful. Now I have a better feel for what kind of scaling is realistic to try for and how to measure it. Putting some recent data points together, it look like giving Mogo 2 orders of magnitude more computer power would result in low dan level 19x19 play? Not the sort of thing one can pull out of a back pocket, but tantalizing. That is quite an large extrapolation. I would rather conclude that we have to find new improvements in the algorithms. But keeping in mind that the scalability with the board size is not impossible. Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Thank you Sylvain for conducting these experiments. We have had some very enlightening results posted here recently in my opinion. I have to admit, I'm surprised at how well the program seems to scale. Fortunately, I didn't make a bet. :) Taking for granted that these results indeed show what they seem to, and combining them with the success of Monte-Carlo methods on 7x7 and 9x9 boards, I'll have to change my opinion about the future of computer go quite radically. It now seems believable to me that computer go will go the way of computer chess, and within the next decade or so as well. Or maybe Chrilly will make a monster go machine even before that. Could somebody comment please on the likely usefulness of massively parallel machines to UCT-like algorithms. Thanks again. Tom. At 21:12 10/04/2007, you wrote: Hello, 2007/4/6, Tom Cooper mailto:[EMAIL PROTECTED][EMAIL PROTECTED]: My guess is that the complexity of achieving a fixed standard of play (eg 1 dan) using a global alpha-beta or MC search is an exponential function of the board size. (...) To some extent, this is testable today by finding how a global search program's strength scales with board size and with thinking time I have experiments of MoGo's playing strength against a fixed player (Gnugo 3.7.10 level 8) on different board sizes and different thinking times. Of course, to meet your statement we have here to assume that the level of gnugo level 8 is a constant with the board size. The results are that in order to keep the same winning rate, you have to increase the number of simulations by something a little larger than linear in the board area. From 9x9 to 13x13, you need something like 3 times more simulations for the same winning rate. Same thing from 13x13 to 19x19. As the time of one simulation is linear in the board area, to keep the same level you have to give a time which increases as power ~2.5 of the board area. So between 9x9 and 19x19, you have to give 32x more time per move for the same play level (always defined as winning rate against gnugo). This is far from being exponential. (maybe if it was exponential, there would be little interest to work on 9x9 go). Sylvain ___ 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] The dominance of search (Suzie v. GnuGo)
As with anything, an efficient serial algorithm (alpha-beta, UCT, etc...) becomes less efficient when made parallel. I think you can see some significant improvement with parallel machines, but it may be that you'll get diminishing returns. I can think of two parallel approaches: 1. Instruct multiple instances to simulate from the same starting point (getting higher confidence estimates more quickly) 2. Instruct different instances to examine different subtrees. Option #1 has the downfall that it may sample a subtree more than necessary before rejecting it. It may also lose some subtree information between processes Option #2 has the downfall that different instances may dwell on a particular subtree for too long before getting instructed to simulate something else. On 4/11/07, Tom Cooper [EMAIL PROTECTED] wrote: Thank you Sylvain for conducting these experiments. We have had some very enlightening results posted here recently in my opinion. I have to admit, I'm surprised at how well the program seems to scale. Fortunately, I didn't make a bet. :) Taking for granted that these results indeed show what they seem to, and combining them with the success of Monte-Carlo methods on 7x7 and 9x9 boards, I'll have to change my opinion about the future of computer go quite radically. It now seems believable to me that computer go will go the way of computer chess, and within the next decade or so as well. Or maybe Chrilly will make a monster go machine even before that. Could somebody comment please on the likely usefulness of massively parallel machines to UCT-like algorithms. Thanks again. Tom. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Thanks Chrilly. For anyone else interested, it is here: http://www.xilinx.com/publications/xcellonline/xcell_53/xc_pdf/xc_hydra53.pdf But, as you say, the the search tree as an adaptable error filteridea is only mentioned in passing. I guess I'll just have to wait for Ulf Lorenz to translate his Dissertation into English :-). Or you learn German. As I side effect you can than also read Goethe and my chess columns. The chess columns are interesting, but then you have to learn also the Austrian version of German). Ulf has used this model for a project to improve the robustness of airplane-schedules. ... Interesting. It is always motivating to hear about game theory getting applied to the real world. (And having been stuck in Amsterdam airport for 5 hours because KLM forgot to schedule a pilot for my flight, I think the airline industry needs all the help it can get!) The problem is, that there is no economic incentive. A robust solution is usually somewhat worse than the non-robust one. I assume that you did not get any compensation for the 5 hours in Schiphol. Such methods will only become important, if KLM has to pay you. 50 Euro/h. The scheduling was done before by humans. These schedules have been robust. Simply for the fact that it is too complicated for a human to make an optimal schedule. But also because humans have some feeling what can go wrong and they anticipate the most likely delays. To a certain degree computer-optimization was introduced to make the schedules less robust. But you have also choosen a very poor airline. KLM was fine a few years agos, but then they started to save money and now its notorious for being late, loosing baggage. But as the other lines have gone the same way, it makes no big difference. There a few good lines left. I my experience the best one is Emirates from Dubai. You should give it a try the next time. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Hello, 2007/4/6, Tom Cooper [EMAIL PROTECTED]: My guess is that the complexity of achieving a fixed standard of play (eg 1 dan) using a global alpha-beta or MC search is an exponential function of the board size. (...) To some extent, this is testable today by finding how a global search program's strength scales with board size and with thinking time I have experiments of MoGo's playing strength against a fixed player (Gnugo 3.7.10 level 8) on different board sizes and different thinking times. Of course, to meet your statement we have here to assume that the level of gnugo level 8 is a constant with the board size. The results are that in order to keep the same winning rate, you have to increase the number of simulations by something a little larger than linear in the board area. From 9x9 to 13x13, you need something like 3 times more simulations for the same winning rate. Same thing from 13x13 to 19x19. As the time of one simulation is linear in the board area, to keep the same level you have to give a time which increases as power ~2.5 of the board area. So between 9x9 and 19x19, you have to give 32x more time per move for the same play level (always defined as winning rate against gnugo). This is far from being exponential. (maybe if it was exponential, there would be little interest to work on 9x9 go). Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
The results are that in order to keep the same winning rate, you have to increase the number of simulations by something a little larger than linear in the board area. From 9x9 to 13x13, you need something like 3 times more simulations for the same winning rate. Same thing from 13x13 to 19x19. As the time of one simulation is linear in the board area, to keep the same level you have to give a time which increases as power ~2.5 of the board area. So between 9x9 and 19x19, you have to give 32x more time per move for the same play level (always defined as winning rate against gnugo). This is far from being exponential. (maybe if it was exponential, there would be little interest to work on 9x9 go). Here's another way to test this sort of thing that is completely intrinsic to the engine (doesn't require gnugo): Start with and empty board and zero komi. Analyze using UCT until the winning percentage at the root reaches X. Note the number of simulations required (or the amount of time). Repeat for a larger board size. One should probably average N trials at each board size for more reliable numbers. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Here's another way to test this sort of thing that is completely intrinsic to the engine (doesn't require gnugo): Start with and empty board and zero komi. Analyze using UCT until the winning percentage at the root reaches X. Note the number of simulations required (or the amount of time). Repeat for a larger board size. One should probably average N trials at each board size for more reliable numbers. Is that a better measure of playing strength? I don't think so. And if the only advantage is that it does not require gnugo, I don't see the point as gnugo is a marvellous tool, why avoid it? Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
I watched MoGo playing with different rank of players. Usually 5d players has no problem winning. Starting from 4d begin to lose games. However, part of it is due to most players are not familar with 9x9 Go. Taking this into consideration I place MoGo at about amateur 2d. For professional players consider 9x9 is solved. This is all my opinion. Gnu plays at about 5k on 19x19. Let's place MoGo at 4k on 19x19. Besides the 32 times, it also need to make up the difference between 4k and 2d. Exponential may not be the case. Just consider this that it could be factorial which is worse than expernential. Daniel Liu -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Tue, 10 Apr 2007 3:12 PM Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo) Hello, 2007/4/6, Tom Cooper [EMAIL PROTECTED]: My guess is that the complexity of achieving a fixed standard of play (eg 1 dan) using a global alpha-beta or MC search is an exponential function of the board size. (...) To some extent, this is testable today by finding how a global search program's strength scales with board size and with thinking time I have experiments of MoGo's playing strength against a fixed player (Gnugo 3.7.10 level 8) on different board sizes and different thinking times. Of course, to meet your statement we have here to assume that the level of gnugo level 8 is a constant with the board size. The results are that in order to keep the same winning rate, you have to increase the number of simulations by something a little larger than linear in the board area. From 9x9 to 13x13, you need something like 3 times more simulations for the same winning rate. Same thing from 13x13 to 19x19. As the time of one simulation is linear in the board area, to keep the same level you have to give a time which increases as power ~2.5 of the board area. So between 9x9 and 19x19, you have to give 32x more time per move for the same play level (always defined as winning rate against gnugo). This is far from being exponential. (maybe if it was exponential, there would be little interest to work on 9x9 go). Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ AOL now offers free email to everyone. Find out more about what's free from AOL at AOL.com. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Don Dailey wrote: (snip) In my opinion, the insight that Chrilly articulated was that all of sudden we are now all using some type of global search - the very idea was considered blasphemy just 2 or 3 years ago. That may be too strong a statement. It may have not been popular but many people consistently believed global search must be a big part of any strong playing program, myself included. Not searching using the same techniques as used for chess, but IMO certainly searching has not ever been altogether dismissed nor considered blasphemy. Look back at posts around 10 years ago (when I first joined the list) and probably since its inception and you'll find this to be true. I personally wrote about it on several occasions suggesting that to counter the evaluation problem the search needed to go very deep and even talked about sampling the tree. Other probability based searches have been studied and written about in academic papers and on this list as well. The crucial combination of techniques didn't bubble up, but not for lack of trying. But I have to admit that personally, I have many more ideas than time with a full time job. Over the last 10 years all I've really done is play around with various algorithms and ideas, study the game of go, collect and read a lot of published papers, and keep up on this list - occasionally posting. My wife still doesn't understand my putting this much time into it! ;-) This is the kind of thing that could consume a person. I don't know if particular ideas would pay off or not because I haven't been able to put in the proper time to focus. In spare time, on and off over the years I've only done a few experiments and algorithms mostly focused on partitioning, goal directed and hierarchical searching methods. This negligible computer-go work, some plans and a few ideas is the extent of my would-be program KatanaGo. Regardless, it has been great fun watching the progress of computer-go over the years and the current flurry of activity with MC/UCT is quite exciting! As I wrote in a post in early Feb of this year (paraphrasing from memory), I think the main reason MC/UCT works is because it goes deep (nearly always to the end) and tends to find paths with more favorable possibilities and more importantly avoid paths littered with problems. Though I'm still pretty amazed by how well it plays, but that's the power of the law of large numbers at work. Correct? As for the point that different paths may converge on similar methods, I agree that could be very plausible scenario, but there is a very long way to go yet... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Don Dailey wrote: I have this idea that perhaps a good evaluation function could replace the play-out portion of the UCT programs. I thought about something similar but only for initializing the counters: introduce 10 fake playouts and estimate the number of wins by a function returning something in [0, 10]. After that, use UCT with real playouts. If your guess was right, that should improve performance, but if it was wrong you are doing nothing irreversible except loosing time. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
I have this idea that perhaps a good evaluation function could replace the play-out portion of the UCT programs. I thought about something similar but only for initializing the counters: introduce 10 fake playouts and estimate the number of wins by a function returning something in [0, 10]. After that, use UCT with real playouts. If your guess was right, that should improve performance, but if it was wrong you are doing nothing irreversible except loosing time. Another option is to replace the playout by a partial playout followed by a static evaluation, which would probably be deterministic (that's acceptable since the partial playout introduced plenty of non-determinism). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
I have this idea that perhaps a good evaluation function could replace the play-out portion of the UCT programs. The evaluation function would return a value between 0 and 1 and would be an estimate of the odds of winning. I have tried this with an older and much weaker version of Suzie. It played positionally better than the Alpha-Beta version, but the rate of very strange moves also increased. UCT greates a more unbalanced tree than Alpha-Beta and the programm has therefore even more chances to cheat. For the same reason extensions do not work so far in Suzie. But I tried not with 0-1 but used the full eval. Maybe I should give it a second try. But as I work now 45 hours/week on Computer-Tomography (which is also quite interesting) and comute each weekend between Germany and Austria its difficult to do. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
To take a normal evaluation function and convert it to a probability of winning function is probably difficult to do well. You might have to map some sort of curve where a few stones ahead represent a near win. A simple approximation: - call the evaluation function - if it is less than zero, consider it one monte carlo run where white wins.If it's greater than zero, consider it a monte carlo run where black wins. It's probably better to use the curve - but my sense of it is that you need to map scores fairly accurately to odds of winning - to truly simulate a monte carlo run. How did you do this before? I think almost any reasonable idea is worth 2 or 3 tries - the devil is in the details. - Don On Sat, 2007-04-07 at 19:52 +0200, Chrilly wrote: I have this idea that perhaps a good evaluation function could replace the play-out portion of the UCT programs. The evaluation function would return a value between 0 and 1 and would be an estimate of the odds of winning. I have tried this with an older and much weaker version of Suzie. It played positionally better than the Alpha-Beta version, but the rate of very strange moves also increased. UCT greates a more unbalanced tree than Alpha-Beta and the programm has therefore even more chances to cheat. For the same reason extensions do not work so far in Suzie. But I tried not with 0-1 but used the full eval. Maybe I should give it a second try. But as I work now 45 hours/week on Computer-Tomography (which is also quite interesting) and comute each weekend between Germany and Austria its difficult to do. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
I don't understand your question. I don't claim non-determinism helps with alpha beta and I'm not recommending a fuzzy evaluation function, I'm just saying it still works. A deeper search will produce better moves in general. One has the randomness anyway. A heuristic evalution can be considered as the sum of a systematic term which is an estimator of the true evaluation and an error term (and a bias). One consequence of this model is, that the shape of the search tree has a significant influence on the evaluation. The programm will favour variations where it has a lot of good moves and the opponent has only a few. Because the more (good) moves the program has, the higher is the expected value of the error terms. The programm has more tickets in the error-term lottery. I have noticed this effect constantly. E.g. if one extends captures, the programm tends to favour lines with captures, if one extends checks stronger, the program likes to check... Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
There is a chapter in Ulf Lorenz Dissertation about this topic. Ulf mentions this aspect also in the Hydra papers. E.g. the one for the XCell Journal. Search on the net for Lorenz, Donninger, Hydra and format pdf. But in this papers the concept is only mentioned without a detailed proof/explanation. This is only done in the Diss. The title of the Diss. is: Ulf Lorenz: Controlled Conspiracy Number Search, Paderborn 2000. But the work is in German. After the match Adams-Hydra Ulf wrote a longer article about his error-filter theory for the ICGA-journal. But the article was rejected. Ulf has used this model for a project to improve the robustness of airplane-schedules. The current algorithms just optimize the scheduling of airplanes (and the crew), but they have usually no notation of robustness. If there is a delay in London, then the flight Frankfurt Paris might be delayed too, because according the schedule the airplane is used after the return from London in Frankfurt for the Paris fligth. And this can in turn delay the flight from Paris to Madrid, because the crew has now - according the law - to take a rest in Paris, but the scheduling programm calculated that its optimal that they are also on board for Paris-Madrid and take the rest in Madrid One can consider the time according schedule as a noisy evaluation function and can try to find more robust solutions which is not much worse than the best solution. Its a conspiracy approach for scheduling problems. Chrilly - Original Message - From: Darren Cook [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Saturday, April 07, 2007 2:18 AM Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo) (R==1). An incorrect pruning decission is not taken forever. The general idea is to use information from the search tree to shape the search tree. Ulf Lorenz from the Univ. Paderborn considers the search tree as an adaptable error filter. ... UCT and Monte Carlo. It's not as much Monte Carlo any longer. Yes, ecaxtly. I also think that the difference is fuzzy. Both methods fit into the adaptable error filter model of Ulf. Hi Chrilly, Do you have a recommendation for a good paper to read on this? Ideally one that doesn't need specialized chess knowledge to appreciate, but I may not have a choice: google is giving me 0 hits on adaptable error filter. Darren -- Darren Cook http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary) http://dcook.org/work/ (About me and my work) http://dcook.org/work/charts/ (My flash charting demos) ___ 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] The dominance of search (Suzie v. GnuGo)
Chrilly wrote: I think on 9x9 the superiority of search based programms is now clearly demonstrated. Its only the question if UCT or Alpha-Beta is superior. Hi Chrilly, Thanks for your report. The question of UCT versus Alpha-Beta is not open any more in my opinion. The current state of the art of Monte Carlo tree search is about 500 Elo points stronger than the version of Crazy Stone you tested against. Do you believe you can easily catch up with those 500 Elo points ? Also, I am convinced that UCT has tremendous potential for further improvement. I have improved Crazy Stone by about 50 Elo points per day in the past 10 days (on 9x9. The improvement on 13x13 and 19x19 is much more). I am very confident that I can easily improve it further very much. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
My guess is that the complexity of achieving a fixed standard of play (eg 1 dan) using a global alpha-beta or MC search is an exponential function of the board size. For this guess, I exclude algorithms that have a tactical or local component. If this guess is correct then, even if Moore's law remains in force, this kind of program should not reach dan level on a 19x19 board within 20 years. To some extent, this is testable today by finding how a global search program's strength scales with board size and with thinking time. For example, results in which Suzie had a week to play a 13x13 game would be interesting. I don't mean to imply by this message that I think I am particularly well qualified to have an opinion on this matter, but when someone writes something that surprises me, I'm inclined to argue :) On 13x13 and especially 19x19 Suzie is still weaker than Gnu-Go. I think the hardware is still too weak to establish the same dominance of search for larger board-sizes. But thats only a matter of time or of a few million $ to build (with Chris Fant) a Go-Chip. Actually about 100.000 Euro for an FPGA based project would be sufficient. Chrilly Donninger ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
I would not be so quick to dismiss what Chrilly is saying. I have noticed that over time, in science, things blend together. For instance mtd(f) is a systematic way to think of aspiration search, (tampering with the alpha/beta window in a search) and helps us to appreciate how they are all pretty much variations of the same basic concepts. I noticed a trend in computer chess towards throwing out more and more moves. Years ago it was only alpha/beta pruning but then later null move pruning, then other kinds of pruning and now the tree is being cut in many places. Chess search trees now look much more like the intial (highly selective) approach that was rejected just a few decades ago. UCT and Monte Carlo. It's not as much Monte Carlo any longer. It's turning more into an evaluation function. When it first started the play-outs were random, now they are semi random - essentially forming a binary evaluation function. In fact they ARE a binary evaluation function - since that exact node will never have this function directly applied to it again (with the standard UCT formulation.) So what we have is a best first search with an evaluation function! (I would still argue that some randomness is important - but I can't explain why in this email but a clue: it has to do with recovering from misconception if you can figure that out!) If you look at what mtd(f) is, it's not alpha/beta, it's more like a hybrid - a best first search that iterates. But it's only a hop, skip, and jump away from standard alpha/beta. It's not hard to imagine that with work, the Chrilly approach will start looking more like the UCT approach. After all, if anything, things have moved more TOWARDS the Chrilly approach and away from the initial things we tried in UCT/monte/carlo. Mabye in a few years we will look back and see that we started from a lot of different places and ended up at the same location.This happens all the time in science. In my opinion, the insight that Chrilly articulated was that all of sudden we are now all using some type of global search - the very idea was considered blasphemy just 2 or 3 years ago. - Don On Fri, 2007-04-06 at 13:54 +0200, Rémi Coulom wrote: Chrilly wrote: I think on 9x9 the superiority of search based programms is now clearly demonstrated. Its only the question if UCT or Alpha-Beta is superior. Hi Chrilly, Thanks for your report. The question of UCT versus Alpha-Beta is not open any more in my opinion. The current state of the art of Monte Carlo tree search is about 500 Elo points stronger than the version of Crazy Stone you tested against. Do you believe you can easily catch up with those 500 Elo points ? Also, I am convinced that UCT has tremendous potential for further improvement. I have improved Crazy Stone by about 50 Elo points per day in the past 10 days (on 9x9. The improvement on 13x13 and 19x19 is much more). I am very confident that I can easily improve it further very much. Rémi ___ 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] The dominance of search (Suzie v. GnuGo)
An imperfect evaluation has errors. Is the exact value of the error known? No. Thus, it's random. :) Daniel Liu -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Fri, 6 Apr 2007 10:57 AM Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo) On 4/6/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: When it comes to a search, one need to ask that is my evaluation function perfect? There are exceptional cases in the late endgame and on tiny boards, but in general this is not an interesting question (because it obviously won't be perfect). In my opinion the question should be: is the evaluation function of a probabilistic nature. Alpha/Beta cutoffs only make sense when calling the evaluation function twice on the exact same position can be guaranteed to provide the exact same value. This is obviously not the case for MC evaluation, hence the success of UCT. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ AOL now offers free email to everyone. Find out more about what's free from AOL at AOL.com. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Thanks for your report. The question of UCT versus Alpha-Beta is not open any more in my opinion. The current state of the art of Monte Carlo tree search is about 500 Elo points stronger than the version of Crazy Stone you tested against. Do you believe you can easily catch up with those 500 Elo points ? Also, I am convinced that UCT has tremendous potential for further improvement. I have improved Crazy Stone by about 50 Elo points per day in the past 10 days (on 9x9. The improvement on 13x13 and 19x19 is much more). I am very confident that I can easily improve it further very much. Rémi The main point of my mail was: Search works (at least in 9x9) well. I think we can agree on this point. For the UCT v. Alpha-Beta question there is a simple proof of the pudding: Sent us the latest/strongest version and we will try to beat it. Suzie is so far a very propretiary system which runs only under GoAheads GUI. And GoAhead does not support GTP. GnuGo is run with a hack. The matches against Crazy-Stone are done by hand. Its Stefan Mertins version of watching TV. I am working currently on a modern C# based GUI which shall support also GTP. But progress is due to my engagement by Siemens rather slow***. Once this GUI exists we will be able to participate on KGS tournaments and other programmers could get Suzie if they like. *** I have also done almost nothing to improve the search, the main progress is due to Peters intensive work on the evaluation. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Chrilly wrote: The main point of my mail was: Search works (at least in 9x9) well. I think we can agree on this point. Yes. For the UCT v. Alpha-Beta question there is a simple proof of the pudding: Sent us the latest/strongest version and we will try to beat it. I do not plan to distribute new versions any more. But I will connect Crazy Stone to the servers, CGOS and KGS. I believe MonteGNU might be available. It is stronger on 9x9 than both GNU Go, and the public versions of Crazy Stone. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
On 4/6/07, Don Dailey [EMAIL PROTECTED] wrote: On Fri, 2007-04-06 at 12:43 -0400, [EMAIL PROTECTED] wrote: Alpha/Beta cutoffs only make sense when calling the evaluation function twice on the exact same position can be guaranteed to provide the exact same value. This is obviously not the case for MC evaluation, hence the success of UCT. I don't know if any of this is true. Noticed the subtle can be in my statement above? I'm quite aware of all the hairy details (e.g., strictly speaking the use of a transposition table already voids the above premise). You can apply alpha beta cutoffs whether the evaluation function is deterministic or not. I know quite well how alpha-beta is used in practice, but that's not the point I tried to get across. The cool thing of alpha-beta cutoffs is that, under certain conditions, it is guaranteed to preserve the minimax result without searching the full tree. However, if the evaluation function is non-deterministic that guarantee simply doesn't make sense any more. I'm not saying that therefore alpha-beta can't be used; in fact I'll be the first to admit that you can apply it to *any* domain with a finite number of known legal actions. Not that that's a good plan, but for sure you will always get something out. In many games it will even play quite well. In practice pathology in search is known to be rare, however, my impression is that in Go it may be more relevant than in other games, such as chess, where, e.g., noise actually helps as a weak mobility component. UCT was specifically designed to deal with uncertainty, so that's why I think it's better suited for highly uncertain evaluations . UCT calls the random play-out only once on any given position and there is no reason in principle that it couldn't be a deterministic evaluation function instead. Sure, and you could even argue that the random play-out *is* deterministic. Fact remains that the uncertainty/variance of one playout is in most cases still huge, and the tree-search has to deal with this (or in Chrilly's words, filter it). Unless the fake mobility is helping significantly, this could be a severe disadvantage for alpha-beta type searchers compared to UCT. To me, a true selective program cuts of a line forever. I would call that a greedy algorithm (because it never reconsiders previous decisions). I have this idea that perhaps a good evaluation function could replace the play-out portion of the UCT programs. Agreed. It only comes down to whether the inherent randomness is critical to the success of UCT or not. If it isn't, then a play-out is nothing more than just an evaluation function. My guess is that the answer which type of search works best for a given evaluation function depends on the amounts of (deterministic) bias and (probabilistic) uncertainty in the evaluations (and so far I see MC mainly as an extremely noisy evaluation with not too much systematic bias). Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
On Fri, 2007-04-06 at 23:41 +0200, Erik van der Werf wrote: My guess is that the answer which type of search works best for a given evaluation function depends on the amounts of (deterministic) bias and (probabilistic) uncertainty in the evaluations (and so far I see MC mainly as an extremely noisy evaluation with not too much systematic bias). It's interesting that Sylvain seems to consider the stronger Mogo versions more brittle in some sense. He claimed (in so many words) that Lazarus gets results more consistent with it's ratings and that the strongest Mogo's do not.I wonder if this is because the play-outs are now more systematically biased? - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
I want to clarify however. If your evaluation function is not deterministic, aspiration search techniques become very dicey.This is a problem anyway with hash table implementations and speculate cutoffs based on the the alpha beta window (and especially the aspiration window) but it's worth mentioning. However, there is nothing wrong with using alpha beta search with an evauation function that is not deterministic. - Don On Fri, 2007-04-06 at 16:24 -0400, Don Dailey wrote: On Fri, 2007-04-06 at 12:43 -0400, [EMAIL PROTECTED] wrote: Alpha/Beta cutoffs only make sense when calling the evaluation function twice on the exact same position can be guaranteed to provide the exact same value. This is obviously not the case for MC evaluation, hence the success of UCT. I don't know if any of this is true. You can apply alpha beta cutoffs whether the evaluation function is deterministic or not. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
On 4/6/07, Don Dailey [EMAIL PROTECTED] wrote: However, there is nothing wrong with using alpha beta search with an evauation function that is not deterministic. I agree that some limited amount of non-determinism isn't necessarily a bad thing, and in some cases it actually helps (e.g., when mobility is important, or to avoid the exploitation of repeatable blunders). However, do you really believe that this still holds if the variance causes a spread over the maximum range of possible values of the underlying ground-truths? Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
(R==1). An incorrect pruning decission is not taken forever. The general idea is to use information from the search tree to shape the search tree. Ulf Lorenz from the Univ. Paderborn considers the search tree as an adaptable error filter. ... UCT and Monte Carlo. It's not as much Monte Carlo any longer. Yes, ecaxtly. I also think that the difference is fuzzy. Both methods fit into the adaptable error filter model of Ulf. Hi Chrilly, Do you have a recommendation for a good paper to read on this? Ideally one that doesn't need specialized chess knowledge to appreciate, but I may not have a choice: google is giving me 0 hits on adaptable error filter. Darren -- Darren Cook http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary) http://dcook.org/work/ (About me and my work) http://dcook.org/work/charts/ (My flash charting demos) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
